Low Cardinality of Index performing better than High Cardinality? For testing purposes I have 2 Tables TableA and TableB in an mysql-InnoDB, both with the same columns

id bigint not null auto_increment,
depot smallint not null,
custno bigint not null,
range_from bigint not null,
range_to bigint not null,
depot2 smallint not null,
primary key (id)


and the same data (~5M rows). Now TableA has the index

unique index (range_from, range_to, custno, depot)


and TableB has the index 

unique index (depot, range_from, range_to, custno)


The cardinality of "depot" is very low (~100 different values), the cardinality of "custno" is medium, and the cardinality of range_from and range_to is very high.

The Select

select sql_no_cache custno,depot,range_from,range_to 
from TableB 
where $value between range_from 
                 and range_to 
  and depot=$other;


takes about .8 seconds.
Explain says:

+----+-------------+-----------+-------+---------------+------------+---------+------+---------+--------------------------+
| id | select_type | table     | type  | possible_keys | key        | key_len | ref  | rows    | Extra                    |
+----+-------------+-----------+-------+---------------+------------+---------+------+---------+--------------------------+
|  1 | SIMPLE      | TableB    | range | range_from    | range_from | 8       | NULL | 1992762 | Using where; Using index |
+----+-------------+-----------+-------+---------------+------------+---------+------+---------+--------------------------+


Now the same select on TableA takes .03 sec and here is what explain says:

+----+-------------+----------+-------+---------------+-------+---------+------+--------+--------------------------+
| id | select_type | table    | type  | possible_keys | key   | key_len | ref  | rows   | Extra                    |
+----+-------------+----------+-------+---------------+-------+---------+------+--------+--------------------------+
|  1 | SIMPLE      | TableA   | range | depot         | depot | 10      | NULL | 107736 | Using where; Using index |
+----+-------------+----------+-------+---------------+-------+---------+------+--------+--------------------------+


Even though the Index starts with a low cardinality column the select outperforms the other index by a factor of at least 20.
Can someone please explain this to me like i am 4 years old? Every article I read so far advocated for using the high cardinality values first in indices.

Mysql version is 5.5.32 btw.
The between condition is short form for:

 ... range_from &lt;= $value 
 and $value &lt;= range_to


In this context range_from and range_to have an effective cardinality of 2, in range or out of range. 

Given your indexes the range_from needs to be searched for all values up to and including $value.  If value is close to the end the possible values, the number of records that need to be checked is quite high.  If you are looking for recent records, this is will be close to all the records.  

Using the index with the depot column first, far fewer records match the range_from value.  If you have 100 depots, you have 1% of the records to check compared to not using it.  Depots with few records will be faster than those with more records.  Your results on table A will vary depending on the value of $other.

In either case, the query could be completed within the index.  Without depot in the index, the query optimizer might decide to scan the table rather than the index.  Some SQL dialects allow a hint to the optimizer indicating the number of rows the query will match.  This can influence the resulting query plan. 

While you consider the cardinality low, from an optimization standpoint, it is quite high it reduces the number of index rows to be scanned by a factor of 100.

While the cardinality of the from_range may be high from a values standpoint. When running a range search it is of little value in searching for records.  For high values (which may be the most common case), it will match close to 100% of the records.  Its high cardinality, is of more use when running a range check of the form:

where from_range between $low and $high


The index may be more useful if the range columns are ordered range_to, range_from.