Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question
2  
It's better because the depot condition is an equality check while the other 2 conditions (on range_from and range_to) are range conditions, so they are better to be (in the index) after the equality checks. –  ypercube Nov 21 '13 at 13:08
add comment

3 Answers

It all depends on which of your two conditions is able to narrow down the data faster. In your data, looking for a depot first makes for a smaller intermediate result set.

share|improve this answer
add comment

The between condition is short form for:

 ... range_from <= $value 
 and $value <= 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.

share|improve this answer
add comment

The explain statement explains more, it's within the key_len column and this answer is basically the thoery/explainment behind ypercube's comment at the top

It's better because the depot condition is an equality check while the other 2 conditions (on range_from and range_to) are range conditions, so they are better to be (in the index) after the equality checks.

unique index (range_from, range_to, custno, depot)

    +----+-------------+-----------+-------+---------------+------------+---------+------+---------+--------------------------+
| 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 |
+----+-------------+-----------+-------+---------------+------------+---------+------+---------+--------------------------+

key_len tells me that only

range_from part of the compound index unique index (range_from, range_to, custno, depot) is being used to filter out non matching records, because bigint not null = 8 bytes. The rest off your compound key is still being used to satisfy the select columns "Using index" within Extra column tells you that

unique index (depot, range_from, range_to, custno)

+----+-------------+----------+-------+---------------+-------+---------+------+--------+--------------------------+
| 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 |
+----+-------------+----------+-------+---------------+-------+---------+------+--------+--------------------------+

key_len tells me that

depot and range_from part of the compound index unique index (depot, range_from, range_to, custno) is being used to filter out non matching records, because smallint not null is 2 bytes + bigint not null is 8 bytes = 10 bytes. The rest off your compound key is still being used to satisfy the select columns "Using index" within Extra column tells you that.

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

What makes the second compound index more useable (selective) for the query above because more non-matching records can be filterd out what will improve performance

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.