MySQL Bugs: #28404: Optimizer does not consider index that can be used for ORDER BY

Bug #28404	Optimizer does not consider index that can be used for ORDER BY
Submitted:	13 May 2007 18:33	Modified:	11 Nov 2018 14:44
Reporter:	Valeriy Kravchuk	Email Updates:
Status:	Verified	Impact on me:	None
Category:	MySQL Server: Optimizer	Severity:	S2 (Serious)
Version:	4.0.31, 4.1.25, 4.1.26, 5.0.42-BK, 5.0.46, 5.1.33	OS:	Linux
Assigned to:		CPU Architecture:	Any
Tags:	bfsm_2007_05_31, bfsm_2007_06_21, bfsm_2007_06_28

Description:
When there are many indexes in table, optimizer wrongly does not even consider the one on column used in ORDER BY, when LIMIT N clause is also present. When N is much smaller than number of rows selected using any other index, access to table using that index may give faster execution time (than any other index + filesort).

How to repeat:
create table tindexes(id int auto_increment primary key, c2 int, c3 int,
c4 int, c5 int, key k2(c2), key k3(c3), key k4(c4), key k5(c5)) engine=MyISAM;

insert into tindexes (c2, c3, c4, c5) values (1,2,3,4);
insert into tindexes (c2, c3, c4, c5) values (5,6,7,8);
insert into tindexes (c2, c3, c4, c5) values (4,3,2,1);

insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
...

repeat the above many times to get:

mysql> select count(*) from tindexes;
+----------+
| count(*) |
+----------+
|    98304 |
+----------+
1 row in set (0.00 sec)

Now:

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

mysql> explain select id, c5 from tindexes where c2=1 and c3=2 and c4 > 2 order
 by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: ref
possible_keys: k2,k3,k4
          key: k2
      key_len: 5
          ref: const
         rows: 39569
        Extra: Using where; Using filesort
1 row in set (0.01 sec)

mysql> explain select id, c5 from tindexes force index(k5) where c2=1 and c3=2
and c4 > 2 order by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: NULL
          key: k5
      key_len: 5
          ref: NULL
         rows: 98304
        Extra: Using where
1 row in set (0.01 sec)

But compare execution time:

mysql> select id, c5 from tindexes force index(k5) where c2=1 and c3=2 and c4 >
 2 order by c5 limit 100;
+-----+------+
| id  | c5   |
+-----+------+
|   1 |    4 |
|   4 |    4 |
|   7 |    4 |
...
| 298 |    4 |
+-----+------+
100 rows in set (0.18 sec)

mysql> select id, c5 from tindexes where c2=1 and c3=2 and c4 > 2 order by c5 l
imit 100;
+-----+------+
| id  | c5   |
+-----+------+
|   1 |    4 |
|   4 |    4 |
|   7 |    4 |
...
| 298 |    4 |
+-----+------+
100 rows in set (0.28 sec)

Suggested fix:
Consider SELECT ... ORDER BY ... LIMIT N differtently. This query will return AT MOST N rows, not more. Cosider index on column in ORDER BY clause as one of possible ways to acces the table.

I think this test also applies to the bug title given, but the events are very different.  I do think, however, that if I created another bug, it would be marked a duplicate of this one.

Description:
When a LIMIT clause (in conjunction with an ORDER BY) is being used to display the last X records of a table, no index is used for the order by.

How to repeat:
drop table if exists tindexes;
create table tindexes(id int auto_increment primary key, c2 int, c3 int, c4 int, c5 int, key k2(c2), key k3(c3), key k4(c4), key k5(c5)) engine=MyISAM;
insert into tindexes values (NULL,1,2,3,4),(NULL,5,6,7,8),(NULL,4,3,2,1),(NULL,8,7,6,5);
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
analyze table tindexes;
select count(*) from tindexes;

+----------+
| count(*) |
+----------+
|     2048 |
+----------+

# The last 10 rows minus 1
explain select id, c5 from tindexes order by c5 limit 2038,9\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: NULL
          key: k5
      key_len: 5
          ref: NULL
         rows: 2048
        Extra: 

# The last 10 rows
explain select id, c5 from tindexes order by c5 limit 2038,10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2048
        Extra: Using filesort

# The last 10 rows overshooting the row count just to be thorough.
explain select id, c5 from tindexes order by c5 limit 2038,100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 2048
        Extra: Using filesort

Suggested fix:
The results of this bug on a paginated web application using a data source with 1.4 millions records is devastating.  I will be forced to use "force index" syntax in my application which will force me to abandon the built-ins of the django framework that my application is running on.

The optimizer should behave the same whether the last row is within the LIMIT clause or not.

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/31792

ChangeSet@1.2565, 2007-07-29 23:00:56-07:00, igor@olga.mysql.com +12 -0
  Preliminary patch for bug #28404.

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/31882

ChangeSet@1.2565, 2007-07-31 03:22:06-07:00, igor@olga.mysql.com +14 -0
  Fixed bug#28404.
  This patch adds cost estimation for the queries with ORDER BY / GROUP BY
  and LIMIT. 
  If there was a ref/range access to the table whose rows were required
  to be ordered in the result set the optimizer always employed this access
  though a scan by a different index that was compatible with the required 
  order could be cheaper to produce the first L rows of the result set.
  Now for such queries the optimizer makes a choice between the cheapest
  ref/range accesses not compatible with the given order and index scans
  compatible with it.

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/31968

ChangeSet@1.2565, 2007-08-01 11:53:22-07:00, igor@olga.mysql.com +14 -0
  Fixed bug#28404.
  This patch adds cost estimation for the queries with ORDER BY / GROUP BY
  and LIMIT. 
  If there was a ref/range access to the table whose rows were required
  to be ordered in the result set the optimizer always employed this access
  though a scan by a different index that was compatible with the required 
  order could be cheaper to produce the first L rows of the result set.
  Now for such queries the optimizer makes a choice between the cheapest
  ref/range accesses not compatible with the given order and index scans
  compatible with it.

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/32029

ChangeSet@1.2565, 2007-08-02 12:45:56-07:00, igor@olga.mysql.com +14 -0
  Fixed bug#28404.
  This patch adds cost estimation for the queries with ORDER BY / GROUP BY
  and LIMIT. 
  If there was a ref/range access to the table whose rows were required
  to be ordered in the result set the optimizer always employed this access
  though a scan by a different index that was compatible with the required 
  order could be cheaper to produce the first L rows of the result set.
  Now for such queries the optimizer makes a choice between the cheapest
  ref/range accesses not compatible with the given order and index scans
  compatible with it.

Igor, I don't mean to be rude or impatient.  I am a MySQL Enterprise Gold customer and I really have no idea how to patch the enterprise product.  (I also haven't applied a patch to MySQL since ver. 3.x)  I'd prefer not to have to patch the server.  (I honestly don't know if I could get approval to use it in production either.)  Can you give me any estimate as to when patches like this get implemented in the enterprise product after they are deemed effective?  Will the 5.0.x product ever reflect this patch, or will it only appear in 5.1.x, or worse even 5.2.x?

Pushed into 5.1.22-beta

Noted in 5.1.22 changelog.

If a LIMIT clause was present, the server could fail to consider
indexes that could be used for ORDER BY or GROUP BY.

This was pushed to 5.1.23, not 5.1.22.

Will this be fixed in 5.0.x?

Valeriy, we cannot make changes in GA versions that change the query plans, so the answer is No.

Igor,

Can you please explain why the patch to this bug
<http://mysql.bkbits.net:8080/mysql-5.1/?PAGE=cset&REV=46b23474o9Ke9qmPMq6tNUhGFV1IoQ>

includes fix-ups like this:

==== mysql-test/r/endspace.result ====
2007-08-02 12:45:48-07:00, igor@olga.mysql.com +1 -1
  Adjusted results for test cases affected fy the fix for bug #28404.

--- 1.12/mysql-test/r/endspace.result	2007-03-09 06:55:55 -08:00
+++ 1.13/mysql-test/r/endspace.result	2007-08-02 12:45:48 -07:00
@@ -154,7 +154,7 @@ teststring	
 teststring
 explain select * from t1 order by text1;
 id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
-1	SIMPLE	t1	index	NULL	key1	34	NULL	3	
+1	SIMPLE	t1	ALL	NULL	NULL	NULL	NULL	3	Using filesort
 alter table t1 modify text1 char(32) binary not null;
 select * from t1 order by text1;
 text1

The query does not include a LIMIT statement, and it seems to be using a table scan after the patch. This change in behaviour caught my attention when some test cases for my private branch (with smart ALTER TABLE in InnoDB, based on MySQL 5.1) started failing.

Is there some way to avoid the table scan and filesort in ORDER BY? I tried making my tables in the test case much bigger, but it didn't help. In my tests, I would like to be sure that MySQL is making use of the newly created indexes.

Marko,

Now we can use an index for ORDER BY only if 
1. the index it's covering
or  
2. ORDER BY is used with LIMIT N  and the cost
of N random accesses is less than the cost of filesort.
The latter is always true for small N and big tables.

By some reasons the handler interface does not return the HA_KEYREAD_ONLY flag for the declared index. That's why the index is not considered as covering. And the table in the test is not big enough for make the optimizer choose the index for ORDER BY with LIMIT.

Sorry, but I am forced to re-open this bug report. While the bug is fixed for the original test case now (in 5.1.33 from bzr):

...
mysql> select count(*) from tindexes;
+----------+
| count(*) |
+----------+
|    98304 | 
+----------+
1 row in set (0.00 sec)

mysql> explain select id, c5 from tindexes where c2=1 and c3=2 and c4 > 2 order
    ->  by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: k2,k3,k4
          key: k5
      key_len: 5
          ref: NULL
         rows: 248
        Extra: Using where
1 row in set (0.00 sec)

mysql> explain select id, c5, c2 from tindexes where c2=1 and c3=2 and c4 > 2 order  by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: k2,k3,k4
          key: k5
      key_len: 5
          ref: NULL
         rows: 248
        Extra: Using where
1 row in set (0.00 sec)

in a but more complicated test case, involving join to relatively small table created like this:

mysql> create table tjoin(id int auto_increment primary key, c6 int);
Query OK, 0 rows affected (0.40 sec)

mysql> insert into tjoin(c6) values(10);
Query OK, 1 row affected (0.00 sec)

mysql> insert into tjoin(c6) select 20 from tjoin;
Query OK, 1 row affected (0.00 sec)
Records: 1  Duplicates: 0  Warnings: 0

...

mysql> insert into tjoin(c6) select 20 from tjoin;
Query OK, 512 rows affected (0.01 sec)
Records: 512  Duplicates: 0  Warnings: 0

we still have the same problem:

mysql> explain select tindexes.id, c6, c5 from tindexes join tjoin on tjoin.id = tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c5 limit 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
         type: ALL
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1024
        Extra: Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: eq_ref
possible_keys: PRIMARY,k2,k3,k4
          key: PRIMARY
      key_len: 4
          ref: test.tjoin.id
         rows: 1
        Extra: Using where
2 rows in set (0.00 sec)

That is, server prefers to sort 1024 rows to select 10 instead of just selecting 10:

mysql> explain select tindexes.id, c6, c5 from tindexes force index(k5) join tjoin on tjoin.id = tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c5 limit 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: NULL
          key: k5
      key_len: 5
          ref: NULL
         rows: 10
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.tindexes.id
         rows: 1
        Extra: 
2 rows in set (0.00 sec)

Note that because of the join order selected index on k5 was not even considered. Moreover, with ORDER BY c4 instead of c5:

mysql> explain select tindexes.id, c6, c5 from tindexes join tjoin on tjoin.id = tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c4 limit 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
         type: ALL
possible_keys: PRIMARY
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1024
        Extra: Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: eq_ref
possible_keys: PRIMARY,k2,k3,k4
          key: PRIMARY
      key_len: 4
          ref: test.tjoin.id
         rows: 1
        Extra: Using where
2 rows in set (0.00 sec)

index is used also in WHERE, but still is NOT considered. Now:

mysql> explain select c5 from tindexes join tjoin on tjoin.id = tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c5 limit 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 1024
        Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: eq_ref
possible_keys: PRIMARY,k2,k3,k4
          key: PRIMARY
      key_len: 4
          ref: test.tjoin.id
         rows: 1
        Extra: Using where
2 rows in set (0.00 sec)

looks like even if we have covering index on column used in ORDER BY and all other columns in SELECT list and LIMIT N where N is relatively small number, we may still have cases when optimizer do not use the index.

Note that both original and recent test case with JOIN shows that we had the same bug in 4.1.x:

valeriy-kravchuks-macbook-pro:mysql-pro-gpl-4.1.25-apple-darwin8.11.1-i386 openxs$ bin/mysql -uroot test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1 to server version: 4.1.25-pro-gpl

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

mysql> create table tindexes(id int auto_increment primary key, c2 int, c3 int, c4 int, c5 int,
    -> key k2(c2), key k3(c3), key k4(c4), key k5(c5)) engine=MyISAM;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into tindexes values (NULL,1,2,3,4),(NULL,5,6,7,8),(NULL,4,3,2,1),(NULL,8,7,6,5);
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

mysql> insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
Query OK, 4 rows affected (0.00 sec)
Records: 4  Duplicates: 0  Warnings: 0

...

mysql> insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
Query OK, 32768 rows affected (2.10 sec)
Records: 32768  Duplicates: 0  Warnings: 0

mysql>  explain select id, c5 from tindexes where c2=1 and c3=2 and c4 > 2 order    -> by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: ref
possible_keys: k2,k3,k4
          key: k2
      key_len: 5
          ref: const
         rows: 18567
        Extra: Using where; Using filesort
1 row in set (0.00 sec)

mysql> explain select id, c5 from tindexes force index(k5) where c2=1 and c3=2 and c4 > 2 order by c5 limit 100\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: index
possible_keys: NULL
          key: k5
      key_len: 5
          ref: NULL
         rows: 65536
        Extra: Using where
1 row in set (0.00 sec)

mysql>  create table tjoin(id int auto_increment primary key, c6 int);
Query OK, 0 rows affected (0.01 sec)

mysql>  insert into tjoin(c6) values(10);
Query OK, 1 row affected (0.00 sec)

mysql> insert into tjoin(c6) select 20 from tjoin;
Query OK, 1 row affected (0.01 sec)
Records: 1  Duplicates: 0  Warnings: 0

...

mysql> insert into tjoin(c6) select 20 from tjoin;
Query OK, 512 rows affected (0.00 sec)
Records: 512  Duplicates: 0  Warnings: 0

mysql> explain select tindexes.id, c5 from tindexes join tjoin on tjoin.id =    
-> tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c5 limit 10\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
         type: index
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: NULL
         rows: 1024
        Extra: Using index; Using temporary; Using filesort
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
         type: eq_ref
possible_keys: PRIMARY,k2,k3,k4
          key: PRIMARY
      key_len: 4
          ref: test.tjoin.id
         rows: 1
        Extra: Using where
2 rows in set (0.00 sec)

So, based on query plans above, I'd say 4.1.x had the same problem as 5.0.x, and this bug is not a regression in 5.0 comparing to 4.1.

See bug #36259 : it's a regression from this one

A fix that subjects a clustered index to the costing instead of using it unconditionally seems likely to be a suitable and fast enough to be practical for customers solution.

The fix in bug #36259 might usefully support optimizer-switch, since it can have undesired side effects sometimes. http://dev.mysql.com/doc/refman/5.1/en/server-system-variables.html#sysvar_optimizer_switc...

Copying some status and comments from bug #36259:

[28 May 13:52] Georgi Kodinov 
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). .. more

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.

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)

For docs, please use the performance tag for the changelog entry for this one.

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)

Pushed into 5.1.47 (revid:joro@sun.com-20100505145753-ivlt4hclbrjy8eye) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

Pushed into mysql-next-mr (revid:alik@sun.com-20100524190136-egaq7e8zgkwb9aqi) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (pib:16)

Pushed into 6.0.14-alpha (revid:alik@sun.com-20100524190941-nuudpx60if25wsvx) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

Pushed into 5.5.5-m3 (revid:alik@sun.com-20100524185725-c8k5q7v60i5nix3t) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

Pushed into 5.1.47-ndb-7.0.16 (revid:martin.skold@mysql.com-20100617114014-bva0dy24yyd67697) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

Pushed into 5.1.47-ndb-6.2.19 (revid:martin.skold@mysql.com-20100617115448-idrbic6gbki37h1c) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

Pushed into 5.1.47-ndb-6.3.35 (revid:martin.skold@mysql.com-20100617114611-61aqbb52j752y116) (version source revid:vasil.dimov@oracle.com-20100331130613-8ja7n0vh36a80457) (merge vers: 5.1.46) (pib:16)

MySQL 4.0 was also affected, as we can see from original test case:

openxs@suse:~/dbs/4.0> bin/mysql -uroot test
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 1 to server version: 4.0.31-debug

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

mysql> create table tindexes(id int auto_increment primary key, c2 int, c3 int,
    -> c4 int, c5 int, key k2(c2), key k3(c3), key k4(c4), key k5(c5)) engine=MyISAM;
Query OK, 0 rows affected (0.00 sec)

mysql> insert into tindexes (c2, c3, c4, c5) values (1,2,3,4);
Query OK, 1 row affected (0.00 sec)

mysql> insert into tindexes (c2, c3, c4, c5) values (5,6,7,8);
Query OK, 1 row affected (0.00 sec)

mysql> insert into tindexes (c2, c3, c4, c5) values (4,3,2,1);
Query OK, 1 row affected (0.00 sec)

mysql> insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
Query OK, 3 rows affected (0.00 sec)
Records: 3  Duplicates: 0  Warnings: 0

...

mysql> insert into tindexes (c2, c3, c4, c5) select c2, c3, c4, c5 from tindexes;
Query OK, 49152 rows affected (6.60 sec)
Records: 49152  Duplicates: 0  Warnings: 0

mysql> select count(*) from tindexes;
+----------+
| count(*) |
+----------+
|    98304 |
+----------+
1 row in set (0.00 sec)

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

mysql> explain select id, c5 from tindexes where c2=1 and c3=2 and c4 > 2 order
    ->  by c5 limit 100\G
*************************** 1. row ***************************
        table: tindexes
         type: ref
possible_keys: k2,k3,k4
          key: k3
      key_len: 5
          ref: const
         rows: 39198
        Extra: Using where; Using filesort
1 row in set (0.00 sec)

mysql> explain select id, c5 from tindexes force index(k5) where c2=1 and c3=2
    -> and c4 > 2 order by c5 limit 100\G
*************************** 1. row ***************************
        table: tindexes
         type: index
possible_keys: NULL
          key: k5
      key_len: 5
          ref: NULL
         rows: 98304
        Extra: Using where
1 row in set (0.00 sec)

Index k5 was not considered while it can be used and leads to faster execution.

So, setting "regression" tag was a mistake (attempts to fix this bug led to regressions, but that's a different story). This is a kind of optimization that probably was never done properly in MySQL.

I have reasons to think that my second test case, with JOIN, also works as expected, at least in Oracle 8.0.13. Depending on number of rows in tjoin table we may get different plans for query without FORCE INDEX:

mysql> explain select tindexes.id, c6, c5 from tindexes join tjoin on tjoin.id = tindexes.id where c2=1 and c3=2 and c4 > 2 order  by c5 limit 10\G             *************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: tindexes
   partitions: NULL
         type: index
possible_keys: PRIMARY,k2,k3,k4
          key: k5
      key_len: 5
          ref: NULL
         rows: 20
     filtered: 12.50
        Extra: Using where
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: tjoin
   partitions: NULL
         type: eq_ref
possible_keys: PRIMARY
          key: PRIMARY
      key_len: 4
          ref: test.tindexes.id
         rows: 1
     filtered: 100.00
        Extra: NULL
2 rows in set, 1 warning (0,00 sec)

and it seems the plan optimizer chooses really leads to faster execution and less operations performed, in both cases when index is NOT used and smaller table is read entirely and when order of joining changes and index is used on tindexes.

I think this bug should be re-verified carefully and probably closed.