MySQL Bugs: #4484: Optimizer chooses wrong Index with ORDER BY

Bug #4484	Optimizer chooses wrong Index with ORDER BY
Submitted:	9 Jul 2004 14:00	Modified:	12 Aug 2004 0:32
Reporter:	Christian Schrader	Email Updates:
Status:	Won't fix	Impact on me:	None
Category:	MySQL Server	Severity:	S3 (Non-critical)
Version:	4.0.20	OS:	Linux (Linux)
Assigned to:		CPU Architecture:	Any

Description:
When optimizing an ORDER BY Clause, the wrong index is choosen.
Example:
index1 = column1, column2   (rows 3)
index2 = column1, column3   (rows 3)
SELECT *  FROM example WHERE column1=constant ORDER BY column2 LIMIT 1;
This query uses index1, as expected.
SELECT *  FROM example WHERE column1=constant ORDER BY column3 LIMIT 1;
This query also uses index1, although index2 should be the obvious choice?

This is something that has its impact only with larger tables, where the second key_part is also of considerable size.

How to repeat:
CREATE TABLE test (
  productID mediumint(6) NOT NULL default '0',
  categoryID mediumint(6) NOT NULL default '0',
  productName varchar(100) NOT NULL default '',
  clicks mediumint(6) NOT NULL default '0',
  KEY productName_idx (categoryID,productName),
  KEY clicks_idx (categoryID,clicks)
) TYPE=MyISAM;

--
-- Dumping data for table `test`
--

INSERT INTO test VALUES (1,1,'a',1);
INSERT INTO test VALUES (2,1,'b',2);
INSERT INTO test VALUES (3,1,'c',3);
INSERT INTO test VALUES (4,1,'d',4);

desc SELECT *  FROM test WHERE categoryID=1 ORDER BY productName DESC LIMIT 1;

desc SELECT *  FROM test WHERE categoryID=1 ORDER BY clicks DESC LIMIT 1;

Suggested fix:
When choosing the index the ORDER BY clause should be more carefully considered.
The same problem seems to arise, when multiple tables are joined and two or more indexes could be used. It seems that then always the smallest index is chosen, even if a larger one would be more efficient due to an ORDER BY clause that could be resolved with the index.

Hi, I was unable to repeat this using 4.1.3 or 4.0.20-max.
Am I missing anything?

root@localhost:bug4484~> select version();
+------------+
| version()  |
+------------+
| 4.0.20-max |
+------------+
1 row in set (0.00 sec)

root@localhost:bug4484~>  desc SELECT *  FROM test WHERE categoryID=1 ORDER BY clicks 
DESC LIMIT 1;
+-------+------+----------------------------+------------+---------+-------+------+-------------+
| table | type | possible_keys              | key        | key_len | ref   | rows | Extra       |
+-------+------+----------------------------+------------+---------+-------+------+-------------+
| test  | ref  | productName_idx,clicks_idx | clicks_idx |       3 | const |    3 | Using where |
+-------+------+----------------------------+------------+---------+-------+------+-------------+
1 row in set (0.00 sec)

Best Regards

Verified with 4.0.20, 4.1.3 and 5.0-bk work as expected though ....

Hi!
We will be releasing 4.1 soon as production/GA and it will resolve this issue.