MySQL Bugs: #10512: Optimizer selecting wrong index with composite indexes

Bug #10512	Optimizer selecting wrong index with composite indexes
Submitted:	10 May 2005 14:21	Modified:	17 May 2005 12:27
Reporter:	Dean Ellis	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	4.0.25 forward	OS:
Assigned to:	Igor Babaev	CPU Architecture:	Any

Description:
Optimizer appears to be selecting the wrong index in cases with composite indexes, resulting in a seemingly unnecessary filesort.

How to repeat:
DROP TABLE IF EXISTS t1;
CREATE TABLE t1 ( a INT, b INT, c INT, INDEX i1 (a,b,c), INDEX i2 (a,c) );
INSERT INTO t1 VALUES (0,0,0),(1,1,1),(2,2,2),(3,3,3),(0,1,2);
EXPLAIN SELECT * FROM t1 WHERE a = 0 ORDER BY c;

Suggested fix:
n/a

This is not a bug as i1 is a covering index for the query
SELECT * FROM t1 WHERE a = 0 ORDER BY c;
while i2 is not.

The situation changes for the query
SELECT a,c FROM t1 WHERE a = 0 ORDER BY c;

mysql> EXPLAIN SELECT a,c FROM t1 WHERE a = 0 ORDER BY c;
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | t1    | ref  | i1,i2         | i2   |       5 | const |    2 | Using where; Using index |
+----+-------------+-------+------+---------------+------+---------+-------+------+--------------------------+

Unfortunately the cost of filesort currently is not taken into account. 
So far when comparing plans with and without filesort the optimizer does not follow strictly the cost-based pradigm.   
This will be tentatively fixed in 5.1.

Altering the test case to avoid the covering index:

DROP TABLE IF EXISTS t1;
CREATE TABLE t1 ( a INT, b INT, c INT, d INT, INDEX i1 (a,b,c), INDEX i2 (a,d,c), INDEX i3 (a,c) );
INSERT INTO t1 VALUES (0,0,0,0),(1,1,1,1),(2,2,2,2),(3,3,3,3),(0,1,2,3);
EXPLAIN SELECT * FROM t1 WHERE a = 0 ORDER BY c;

What is the reason i1 is selected in this case?

dean, the reason is the order of the indexes... rearrange them to this and it'll be better.

CREATE TABLE t1 ( a INT, b INT, c INT, d INT, 
INDEX i3 (a,c),INDEX i1 (a,b,c),INDEX i2 (a,d,c))

I think this was reported elsewhere recently, cant remember.