MySQL Bugs: #2243: bad key selection implies filesort

Bug #2243	bad key selection implies filesort
Submitted:	31 Dec 2003 5:46	Modified:	2 Feb 2004 4:42
Reporter:	[ name withheld ]	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server	Severity:	S3 (Non-critical)
Version:	3.23.58/4.0.16	OS:	Linux (linux)
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
I make the following query:

explain select * from table where key_part1=1 order by key_part2, key_part3 limit 90, 10;

on a table with key1 on (key_part1, key_part2, key_part3) and key2 on (key_part1, other_field, key_part2, key_part3).

and I get
-> possible_keys: key1, key2.
-> key: key2
-> extra: Using where; Using filesort

field definitions: key_part1 tinyint unsigned, key_part2 tinyint unsigned, key_part3 int

It should use the shorter key and not filesort.

How to repeat:
create table table1 (key_part1 int, key_part2 int, key_part3 int, other_field int, key key1(key_part1,key_part2,key_part3), key key2(key_part1,other_field, key_part2, key_part3));
insert into table1 values (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0);
update table1 set key_part1=round(rand()), key_part2=round(rand()), key_part3=rand()*10000, other_field=rand()*10000;

mysql> explain select * from table1 where key_part1=0 order by key_part2, key_part3;
+--------+------+---------------+------+---------+-------+------+------------+
| table  | type | possible_keys | key  | key_len | ref   | rows | Extra      |
+--------+------+---------------+------+---------+-------+------+------------+
| table1 | ref  | key1,key2     | key1 |       5 | const |   30 | where used |
+--------+------+---------------+------+---------+-------+------+------------+
1 row in set (0.00 sec)

mysql> explain select * from table1 where key_part1=1 order by key_part2, key_part3;
+--------+------+---------------+------+---------+-------+------+-----------------------------------------+
| table  | type | possible_keys | key  | key_len | ref   | rows | Extra                                   |
+--------+------+---------------+------+---------+-------+------+-----------------------------------------+
| table1 | ref  | key1,key2     | key2 |       5 | const |   27 | where used; Using index; Using filesort |
+--------+------+---------------+------+---------+-------+------+-----------------------------------------+
1 row in set (0.01 sec)

mysql> alter table table1 drop index key2;
Query OK, 60 rows affected (0.01 sec)
Records: 60  Duplicates: 0  Warnings: 0

mysql> explain select * from table1 where key_part1=1 order by key_part2, key_part3;
+--------+------+---------------+------+---------+-------+------+------------+
| table  | type | possible_keys | key  | key_len | ref   | rows | Extra      |
+--------+------+---------------+------+---------+-------+------+------------+
| table1 | ref  | key1          | key1 |       5 | const |   42 | where used |
+--------+------+---------------+------+---------+-------+------+------------+
1 row in set (0.00 sec)

mysql> explain select * from table1 where key_part1=0 order by key_part2, key_part3;
+--------+------+---------------+------+---------+-------+------+------------+
| table  | type | possible_keys | key  | key_len | ref   | rows | Extra      |
+--------+------+---------------+------+---------+-------+------+------------+
| table1 | ref  | key1          | key1 |       5 | const |   15 | where used |
+--------+------+---------------+------+---------+-------+------+------------+
1 row in set (0.00 sec)

Verified with 4.0.18; even after ANALYZE it is choosing the second index.

Just a note, when MySQL happens to choose indexes which appear to be suboptimal, you can provide hints with USE INDEX and FORCE INDEX.

This is partially fixed in 4.0 where both queries use filesort.

However, this is still a bug in the optimiser as this hint makes it work correctly: 

drop table if exists table1;
create table table1 (key_part1 int, key_part2 int, key_part3 int, other_field int, key key1(key_part1,key_part2,key_part3), key key2(key_part1,other_field, key_part2, key_part3));
insert into table1 values (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0), (0,0,0,0),(0,0,0,0),(0,0,0,0),(0,0,0,0);
update table1 set key_part1=round(rand()), key_part2=round(rand()), key_part3=rand()*10000, other_field=rand()*10000;
analyze table table1;
explain select * from table1 use index (key1) where key_part1=0 order by key_part2, key_part3;
explain select * from table1 use index (key1)  where key_part1=1 order by key_part2, key_part3;
drop table if exists table1;

The reason the optimizer chooses key2 and not key1 is that key2 covers all columns of table1.
With that access plan the optimizer will be able to get all requested data through index and not access table data at all.

Let me explain by example:
mysql> explain select key_part1, key_part2,  key_part3 from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key1
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where; Using index
1 row in set (0.00 sec)

mysql> explain select key_part1, key_part2,  key_part3, other_field from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key2
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where; Using index; Using filesort
1 row in set (0.00 sec)

mysql> explain select * from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key2
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where; Using index; Using filesort
1 row in set (0.00 sec)
mysql> alter table table1 add column name varchar(25) not null;
Query OK, 60 rows affected (0.04 sec)
Records: 60  Duplicates: 0  Warnings: 0

mysql> explain select * from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key1
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain select key_part1, key_part2, key_part3, other_field from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key2
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where; Using index; Using filesort
1 row in set (0.00 sec)
mysql> explain select key_part1, key_part2, key_part3 from table1  where key_part1=0 order by key_part2, key_part3\G
*************************** 1. row ***************************
        table: table1
         type: ref
possible_keys: key1,key2
          key: key1
      key_len: 5
          ref: const
         rows: 33
        Extra: Using where; Using index
1 row in set (0.00 sec)

I'm closing the bug as 'not a bug'.
Feel free to reopen it if you have any new comments/thoughs.