MySQL Bugs: #36259: Optimizing with ORDER BY

Bug #36259	Optimizing with ORDER BY
Submitted:	22 Apr 2008 17:11	Modified:	9 Jun 2009 10:35
Reporter:	aligi piccin	Email Updates:
Status:	Duplicate	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S5 (Performance)
Version:	5.0.54, 5.1.23, 5.1.24, 5.1.25	OS:	Windows
Assigned to:	Georgi Kodinov	CPU Architecture:	Any
Tags:	INDEX, innodb, Optimizer, order by, regression

Description:
An INNODB table: col1 integer,col2 integer,col3 integer, col1 is primary key, secondary index on (col2,col3)
Up to release 5.1.22 the query 
"SELECT * FROM tbl WHERE col2=x AND col3=y ORDER BY col1" 
worked fine, output from explain said the secondary index was properly used, with an extra filesort to sort the extracted rows.
Starting with rel 5.1.23 (but 5.1.24 too) the same query becomes many times slower, output from explain says the secondary index is not used!! 
The optimizer choose to use the primary index to perform a table scan and so finding the requested rows without the need of an extra filesort.
But this is an extremely slower way of doing the job.
I had to downgrade back to 5.1.22

How to repeat:
CREATE TABLE  `newtable` (
  `col1` int(10) NOT NULL,
  `col2` int(10) ,
  `col3` int(10) ,
  PRIMARY KEY (`col1`),
  KEY `i2` (`col2`,`col3`)
) ENGINE=InnoDB 

Use explain to verify optimizer bahaviour on this query: 
"SELECT * FROM newtable WHERE col2=x AND col3=y ORDER BY col1"

Thank you for a problem report. Please, send a complete test case, with all the data, to repeat the behaviour described. I am not able to repeat it on random data:

C:\Program Files\MySQL\MySQL Server 5.1\bin>mysql -uroot test -P3310
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 8
Server version: 5.1.24-rc-community MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> create table nt (c1 int auto_increment primary key, c2 int, c3 int,
    -> key i2(c2,c3)) engine=InnoDB;
Query OK, 0 rows affected (0.16 sec)

mysql> insert into nt(c2, c3) values (1,1);
Query OK, 1 row affected (0.03 sec)

mysql> insert into nt(c2, c3) values (2,2);
Query OK, 1 row affected (0.02 sec)

mysql> insert into nt(c2, c3) select rand()*100000, rand()*100000 from nt;
Query OK, 2 rows affected (0.16 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into nt(c2, c3) select rand()*100000, rand()*100000 from nt;
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into nt(c2, c3) select rand()*100000, rand()*100000 from nt;
Query OK, 8 rows affected (0.05 sec)
Records: 8  Duplicates: 0  Warnings: 0

mysql> insert into nt(c2, c3) select rand()*100000, rand()*100000 from nt;
Query OK, 16 rows affected (0.09 sec)
Records: 16  Duplicates: 0  Warnings: 0

...

mysql> insert into nt(c2, c3) select rand()*100000, rand()*100000 from nt;
Query OK, 131072 rows affected (5.50 sec)
Records: 131072  Duplicates: 0  Warnings: 0

mysql> select count(*) from nt where c2=1 and c3=1;
+----------+
| count(*) |
+----------+
|        1 |
+----------+
1 row in set (0.03 sec)

mysql> analyze table nt;
+---------+---------+----------+----------+
| Table   | Op      | Msg_type | Msg_text |
+---------+---------+----------+----------+
| test.nt | analyze | status   | OK       |
+---------+---------+----------+----------+
1 row in set (0.05 sec)

mysql> explain select * from nt where c2=1 and c3=1 order by c1;
+----+-------------+-------+------+---------------+------+---------+------------
-+------+--------------------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref
 | rows | Extra                    |
+----+-------------+-------+------+---------------+------+---------+------------
-+------+--------------------------+
|  1 | SIMPLE      | nt    | ref  | i2            | i2   | 10      | const,const
 |    1 | Using where; Using index |
+----+-------------+-------+------+---------------+------+---------+------------
-+------+--------------------------+
1 row in set (0.36 sec)

Sorry, i apologize for i submitted a too much simplified table structure (my REAL table structure is much more complicated) but this way the problem was lost.
Here is a simplified structure where i can find the problem too:
CREATE TABLE  `testable` (
  `col1` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `col2` int(10) unsigned NOT NULL DEFAULT '0',
  `col3` int(10) unsigned NOT NULL DEFAULT '0',
  `col4` varchar(5) NOT NULL,
  PRIMARY KEY (`col1`),
  KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=21 
It seems that the presence of the varchar column in the secondary indeex is in some way cause of the problem.
I use query browser and get the wrong access plan even on an empty table
"EXPLAIN EXTENDED SELECT * FROM `testable` where col2=1 and col3=1 order by col1"

Verified just as described:

mysql> select version();
+---------------------+
| version()           |
+---------------------+
| 5.1.24-rc-community |
+---------------------+
1 row in set (0.02 sec)

mysql> CREATE TABLE  `testable` (
    ->   `col1` int(10) unsigned NOT NULL AUTO_INCREMENT,
    ->   `col2` int(10) unsigned NOT NULL DEFAULT '0',
    ->   `col3` int(10) unsigned NOT NULL DEFAULT '0',
    ->   `col4` varchar(5) NOT NULL,
    ->   PRIMARY KEY (`col1`),
    ->   KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
    -> ) ENGINE=InnoDB AUTO_INCREMENT=21 ;
Query OK, 0 rows affected (0.09 sec)

mysql> EXPLAIN EXTENDED SELECT * FROM `testable` where col2=1 and col3=1 order b
y col1;
+----+-------------+----------+-------+---------------+---------+---------+-----
-+------+----------+--------------------------+
| id | select_type | table    | type  | possible_keys | key     | key_len | ref
 | rows | filtered | Extra                    |
+----+-------------+----------+-------+---------------+---------+---------+-----
-+------+----------+--------------------------+
|  1 | SIMPLE      | testable | index | I2            | PRIMARY | 4       | NULL
 |    1 |   100.00 | Using where; Using index |
+----+-------------+----------+-------+---------------+---------+---------+-----
-+------+----------+--------------------------+
1 row in set, 1 warning (0.05 sec)

mysql> insert into testable(col2, col3, col4) values (1,1, 'a'), (2,2, 'b');
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 2 rows affected (0.11 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 4 rows affected (0.05 sec)
Records: 4  Duplicates: 0  Warnings: 0

...

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 262144 rows affected (11.98 sec)
Records: 262144  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM `testable` FORCE INDEX (I2) where col2=1 and col3=1 order b
y col1;
+------+------+------+------+
| col1 | col2 | col3 | col4 |
+------+------+------+------+
|   21 |    1 |    1 | a    |
+------+------+------+------+
1 row in set (0.00 sec)

mysql> SELECT * FROM `testable` where col2=1 and col3=1 order by col1;
+------+------+------+------+
| col1 | col2 | col3 | col4 |
+------+------+------+------+
|   21 |    1 |    1 | a    |
+------+------+------+------+
1 row in set (1.11 sec)

Test case:

select version();
CREATE TABLE  `testable` (
`col1` int(10) unsigned NOT NULL AUTO_INCREMENT,
`col2` int(10) unsigned NOT NULL DEFAULT '0',
`col3` int(10) unsigned NOT NULL DEFAULT '0',
`col4` varchar(5) NOT NULL,
PRIMARY KEY (`col1`),
KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
) ENGINE=InnoDB AUTO_INCREMENT=21 ;

insert into testable(col2, col3, col4) values (1,1, 'a'), (2,2, 'b');
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;
insert into testable(col2, col3, col4) select rand()*10000, rand()*100000, 'b' from testable;

ANALYZE TABLE testable;

EXPLAIN SELECT * FROM `testable` where col2=1 and col3=1 order by col1;

SELECT * FROM `testable` FORCE INDEX (I2) where col2=1 and col3=1 order by col1;
SELECT * FROM `testable` where col2=1 and col3=1 order by col1;

See also BUG#35850.

Dear bug verifiers:

Could you try repeating on MySQL 5.1.25? There are chances that this is fixed by fix for BUG#35850.

Bug #37680 was marked as a duplicate of this one.

And yes, looks like it is fixed in 5.1.25-rc:

C:\Program Files\MySQL\MySQL Server 5.1\bin>mysql -uroot -proot -P3310 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 14
Server version: 5.1.25-rc-community MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> CREATE TABLE  `testable` (
    -> `col1` int(10) unsigned NOT NULL AUTO_INCREMENT,
    -> `col2` int(10) unsigned NOT NULL DEFAULT '0',
    -> `col3` int(10) unsigned NOT NULL DEFAULT '0',
    -> `col4` varchar(5) NOT NULL,
    -> PRIMARY KEY (`col1`),
    -> KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
    -> ) ENGINE=InnoDB AUTO_INCREMENT=21 ;
Query OK, 0 rows affected (0.27 sec)

mysql> insert into testable(col2, col3, col4) values (1,1, 'a'), (2,2, 'b');
Query OK, 2 rows affected (0.13 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 2 rows affected (0.13 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

...

mysql> insert into testable(col2, col3, col4) select rand()*10000, rand()*100000
, 'b' from testable;
Query OK, 262144 rows affected (12.77 sec)
Records: 262144  Duplicates: 0  Warnings: 0

mysql> EXPLAIN EXTENDED SELECT * FROM `testable` where col2=1 and col3=1 order b
y col1;
+----+-------------+----------+------+---------------+------+---------+---------
----+------+----------+------------------------------------------+
| id | select_type | table    | type | possible_keys | key  | key_len | ref
    | rows | filtered | Extra                                    |
+----+-------------+----------+------+---------------+------+---------+---------
----+------+----------+------------------------------------------+
|  1 | SIMPLE      | testable | ref  | I2            | I2   | 8       | const,co
nst |    1 |   100.00 | Using where; Using index; Using filesort |
+----+-------------+----------+------+---------------+------+---------+---------
----+------+----------+------------------------------------------+
1 row in set, 1 warning (0.11 sec)

mysql> SELECT * FROM `testable` where col2=1 and col3=1 order by col1;
+------+------+------+------+
| col1 | col2 | col3 | col4 |
+------+------+------+------+
|   21 |    1 |    1 | a    |
+------+------+------+------+
1 row in set (0.06 sec)

It seems ok but it is not, try with this modified table:
CREATE TABLE  testable2 (
  `col1` int(10) unsigned NOT NULL DEFAULT '0',
  `col2` int(10) unsigned NOT NULL DEFAULT '0',
  `col3` int(10) unsigned NOT NULL DEFAULT '0',
  `col4` varchar(5) DEFAULT NULL,
  `col5` int(10) unsigned NOT NULL,
  PRIMARY KEY (`col1`) USING BTREE,
  KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
Just adding col5 to table structure wakeup the bug again.
It seems, but i am not sure, that neither the datatype neither other attributes of col5 have any influence on the bug: the only presence of col5 is sufficient to wakeup the bug
The query:
EXPLAIN EXTENDED SELECT * FROM testable2 where col2=1 and col3=1 order by col1

How many rows do you have in that new table? I can repeat your EXPLAIN result on empty table, but this is NOT a bug by itself.

Indeed, bug is NOT fixed in a bit more complex cases:

C:\Program Files\MySQL\MySQL Server 5.0\bin>mysql -uroot -proot -P3310 test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 17
Server version: 5.1.25-rc-community MySQL Community Server (GPL)

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> show create table testable2\G
*************************** 1. row ***************************
       Table: testable2
Create Table: CREATE TABLE `testable2` (
  `col1` int(10) NOT NULL AUTO_INCREMENT,
  `col2` int(10) unsigned NOT NULL DEFAULT '0',
  `col3` int(10) unsigned NOT NULL DEFAULT '0',
  `col4` varchar(5) DEFAULT NULL,
  `col5` int(10) unsigned NOT NULL,
  PRIMARY KEY (`col1`) USING BTREE,
  KEY `I2` (`col2`,`col3`,`col4`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=latin1
1 row in set (0.42 sec)

mysql> select * from testable2;
Empty set (0.02 sec)

mysql> insert into testable2 (col2, col3, col4, col5) values (1,1,'a', 1), (2,2,
 'b', 2);
Query OK, 2 rows affected (0.03 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable2 (col2, col3, col4, col5) select rand()*10000, rand(
)*10000, col4, col5 from testable2;
Query OK, 2 rows affected (0.39 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> insert into testable2 (col2, col3, col4, col5) select rand()*10000, rand(
)*10000, col4, col5 from testable2;
Query OK, 4 rows affected (0.03 sec)
Records: 4  Duplicates: 0  Warnings: 0

...

mysql> EXPLAIN EXTENDED SELECT * FROM testable2 where col2=1 and col3=1 order
    -> by col1;
+----+-------------+-----------+-------+---------------+---------+---------+----
--+--------+----------+-------------+
| id | select_type | table     | type  | possible_keys | key     | key_len | ref
  | rows   | filtered | Extra       |
+----+-------------+-----------+-------+---------------+---------+---------+----
--+--------+----------+-------------+
|  1 | SIMPLE      | testable2 | index | I2            | PRIMARY | 4       | NUL
L | 524679 |     0.00 | Using where |
+----+-------------+-----------+-------+---------------+---------+---------+----
--+--------+----------+-------------+
1 row in set, 1 warning (0.03 sec)

mysql> SELECT * FROM testable2 force index(i2) where col2=1 and col3=1 order by
col1;
+------+------+------+------+------+
| col1 | col2 | col3 | col4 | col5 |
+------+------+------+------+------+
|    1 |    1 |    1 | a    |    1 |
+------+------+------+------+------+
1 row in set (0.05 sec)

mysql> SELECT * FROM testable2 where col2=1 and col3=1 order by col1;
+------+------+------+------+------+
| col1 | col2 | col3 | col4 | col5 |
+------+------+------+------+------+
|    1 |    1 |    1 | a    |    1 |
+------+------+------+------+------+
1 row in set (1.02 sec)

ANALYZE/OPTIMIZE/CHECK TABLE does NOT help. 

On the flip side, bug is NOT repeatable with MyISAM table:

mysql> alter table testable2 engine=MyISAM;
Query OK, 524288 rows affected (5.89 sec)
Records: 524288  Duplicates: 0  Warnings: 0

mysql> SELECT * FROM testable2 force index(i2) where col2=1 and col3=1 order by
col1;
+------+------+------+------+------+
| col1 | col2 | col3 | col4 | col5 |
+------+------+------+------+------+
|    1 |    1 |    1 | a    |    1 |
+------+------+------+------+------+
1 row in set (0.02 sec)

mysql> SELECT * FROM testable2 where col2=1 and col3=1 order by col1;
+------+------+------+------+------+
| col1 | col2 | col3 | col4 | col5 |
+------+------+------+------+------+
|    1 |    1 |    1 | a    |    1 |
+------+------+------+------+------+
1 row in set (0.00 sec)

mysql> explain SELECT * FROM testable2 where col2=1 and col3=1 order by col1;
+----+-------------+-----------+------+---------------+------+---------+--------
-----+------+-----------------------------+
| id | select_type | table     | type | possible_keys | key  | key_len | ref
     | rows | Extra                       |
+----+-------------+-----------+------+---------------+------+---------+--------
-----+------+-----------------------------+
|  1 | SIMPLE      | testable2 | ref  | I2            | I2   | 8       | const,c
onst |    1 | Using where; Using filesort |
+----+-------------+-----------+------+---------------+------+---------+--------
-----+------+-----------------------------+
1 row in set (0.00 sec)

Bug #37759 was marked as a duplicate of this one.

Bug #37786 is a duplicate of this one.

Bug #35136 was marked as a duplicate of this one.

Bug #42457 was marked as a duplicate of this one.

It seems we have similar problem with the latest mysql 5.1.34 under Linux

mysql> select version();
+----------------------+
| version()            |
+----------------------+
| 5.1.34-community-log | 
+----------------------+
1 row in set (0.00 sec)

mysql>  CREATE TABLE testTable ( id int(11) NOT NULL auto_increment, TransactionId int(11) NOT NULL default '0', Parent int(11) NOT NULL default '0' ,ContentTypy varchar(80),PRIMARY KEY  (id), KEY Attachments1 (Parent), KEY Attachments2(TransactionId), KEY Attachments3 (Parent,TransactionId))  ENGINE=InnoDB DEFAULT CHARSET=utf8;
Query OK, 0 rows affected (0.73 sec)

mysql> insert into testTable (Parent,TransactionId) values(10,10);
Query OK, 1 row affected (0.00 sec)

mysql> insert into testTable (Parent,TransactionId) values(10,20);
Query OK, 1 row affected (0.00 sec)

mysql> insert into testTable (Parent,TransactionId) values(10,30);
Query OK, 1 row affected (0.03 sec)

mysql> insert into testTable (Parent,TransactionId) select rand()*10000, rand()*100000 from testTable;   
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql> insert into testTable (Parent,TransactionId) select rand()*10000, rand()*100000 from testTable;
Query OK, 6 rows affected (0.00 sec)
Records: 6  Duplicates: 0  Warnings: 0

...

mysql> insert into testTable (Parent,TransactionId) select rand()*10000, rand()*100000 from testTable;
Query OK, 12288 rows affected (1.31 sec)
Records: 12288  Duplicates: 0  Warnings: 0

mysql> explain select * from testTable where Parent=10 order by id;
+----+-------------+-----------+-------+---------------------------+---------+---------+------+-------+-------------+
| id | select_type | table     | type  | possible_keys             | key     | key_len | ref  | rows  | Extra       |
+----+-------------+-----------+-------+---------------------------+---------+---------+------+-------+-------------+
|  1 | SIMPLE      | testTable | index | Attachments1,Attachments3 | PRIMARY | 4       | NULL | 25291 | Using where | 
+----+-------------+-----------+-------+---------------------------+---------+---------+------+-------+-------------+
1 row in set (0.00 sec)

mysql> explain select * from testTable where Parent=10 ;
+----+-------------+-----------+------+---------------------------+--------------+---------+-------+------+-------+
| id | select_type | table     | type | possible_keys             | key          | key_len | ref   | rows | Extra |
+----+-------------+-----------+------+---------------------------+--------------+---------+-------+------+-------+
|  1 | SIMPLE      | testTable | ref  | Attachments1,Attachments3 | Attachments3 | 4       | const |    7 |       | 
+----+-------------+-----------+------+---------------------------+--------------+---------+-------+------+-------+
1 row in set (0.00 sec)

I am having this problem, I believe it's similar to http://bugs.mysql.com/bug.php?id=39258.  I have also seen this behavior in the Attachments table of RT, after an OPTIMIZE TABLE was done (the upgrade from 5.0 didn't show any problems, but weeks later after defragmenting, the problem occurred within hours) -- So I believe this is another instance of http://bugs.mysql.com/bug.php?id=37680, which is what led me here.

This is extremely important, as not everyone can downgrade (to a *beta* version!!!), and we can't simply unoptimize the table.  I have seen this happen in two very different environments in the past few months, and it seems like anyone can fall victim to this, merely by defragmenting their tables.

This regression imho is caused by the fix for bug #28404.

The problem is that the Innodb table's primary keys (which are clustered) are always considered covering keys.

The change introduced by #28404 results in covering keys that can be used to resolve ORDER BY to be used unconditionally (without cost comparison).
This happens as follows : 

1.the primary keys are considered covering for Innodb : 
13127           bool is_covering= table->covering_keys.is_set(nr) ||
13128                             nr == table->s->primary_key &&
13129                             table->file->primary_key_is_clustered();

3. covering indexes are *always* considered better than the existing alternative (note how it skips checking the read time) :

13206           if (is_covering || 
13207               ref_key < 0 && (group || table->force_index) ||
13208               index_scan_time < read_time)
13209           {

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/75135

2905 Georgi Kodinov	2009-05-28
      Bug #36259 : proof-of-concept fix (not final!).
      
      Don't accept unconditionally (without comparing the cost) 
      clustered ordering indexes.

Closing as a duplicate of bug #28404 (since it's now opened).

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/77871

2990 Georgi Kodinov	2009-07-03
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering indexes to be preferred 
      over non-covering in the following two cases : 
       - when comparing the ordering indexes among themselves
       - when comparing the ref key to ordering indexes.
      
      Fixed by not considering the ordering indexes supperior to the 
      ref key. They're only supperior to non-covering ordering indexes. 
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.

Fixed by the fix for bug #45828

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/78030

2990 Georgi Kodinov	2009-07-06
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/78124

2990 Georgi Kodinov	2009-07-07
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.

A patch for this bug has been committed. After review, it may
be pushed to the relevant source trees for release in the next
version. You can access the patch from:

  http://lists.mysql.com/commits/78293

3017 Georgi Kodinov	2009-07-07
      Bug #36259 (Optimizing with ORDER BY) and bug#45828 (Optimizer won't 
      use partial primary key if another index can prevent filesort
      
      The fix for bug #28404 causes the covering ordering indexes to be 
      preferred unconditionally over non-covering and ref indexes.
      
      Fixed by comparing the cost of using a covering index to the cost of
      using a ref index even for covering ordering indexes.
      Added an assertion to clarify the condition the local variables should
      be in.
     @ mysql-test/include/mix1.inc
        Bug #36259: fixed a non-stable test case
     @ mysql-test/r/innodb_mysql.result
        Bug #36259 and #45828 : test case
     @ mysql-test/t/innodb_mysql.test
        Bug #36259 and #45828 : test case
     @ sql/sql_select.cc
        Bug #36259 and #45828 : don't consider covering indexes supperior to
        ref keys.

Pushed into 5.4.4-alpha (revid:anozdrin@bk-internal.mysql.com-20090710111017-bnh2cau84ug1hvei) (version source revid:joro@sun.com-20090709161101-iov57k1sd3q7kve3) (merge vers: 5.4.4-alpha) (pib:11)

Pushed into 5.1.37 (revid:joro@sun.com-20090713174543-cd2x7q1gi1hzoand) (version source revid:staale.smedseng@sun.com-20090710151930-6e6kq5tp7ux1rtbh) (merge vers: 5.1.37) (pib:11)

Bug #46508 was marked as a duplicate of this one.

Was this actually pushed to 5.1.37?  http://dev.mysql.com/doc/refman/5.1/en/news-5-1-37.html doesn't show Bug 36259 in the list of bugs fixed....

Pushed into 5.1.37-ndb-7.0.8 (revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)

Pushed into 5.1.37-ndb-6.3.27 (revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (version source revid:jonas@mysql.com-20090826105955-bkj027t47gfbamnc) (merge vers: 5.1.37-ndb-6.3.27) (pib:11)

Pushed into 5.1.37-ndb-6.2.19 (revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (version source revid:jonas@mysql.com-20090825194404-37rtosk049t9koc4) (merge vers: 5.1.37-ndb-6.2.19) (pib:11)

Pushed into 5.1.35-ndb-7.1.0 (revid:magnus.blaudd@sun.com-20090827163030-6o3kk6r2oua159hr) (version source revid:jonas@mysql.com-20090826132541-yablppc59e3yb54l) (merge vers: 5.1.37-ndb-7.0.8) (pib:11)

Sheeri, this is a duplicate of bug #45828 that is included in 5.1.37, 5.4.2 .