MySQL Bugs: #2276: select from range not optimazed

Bug #2276	select from range not optimazed
Submitted:	4 Jan 2004 16:36	Modified:	7 Jan 2004 8:50
Reporter:	bill zheng	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server: MyISAM storage engine	Severity:	S3 (Non-critical)
Version:	4.0.14-nt	OS:	Windows (Windows 2000 Server)
Assigned to:		CPU Architecture:	Any

Description:
when selecting from a range on an indexed column, sorting the result by the same column in descending order, and then "LIMITing" the result, mysql first gets all records in the range and sorts the result without using the index.

How to repeat:
CREATE TABLE tbl_test (
  id_ int(11) NOT NULL auto_increment,
  data_ int(11) NULL,
  PRIMARY KEY  (id_)
)

populate the table with 10,000,000 records.
now do the following tests:
1.
select id_ from tbl_test where id_<5000000 and data_ is not null order by id_ ASC limit 10
2.
select id_ from tbl_test where id_<5000000 and data_ is not null order by id_ DESC limit 10

if the primary key is used properly, both query would cost mysql about the same time. but in reality, query 1 runs much faster than query 2.

related tests:
1.select min(id_) from tbl_test where id_>100 and id_<5000000
2.select max(id_) from tbl_test where id_>100 and id_<5000000

in both tests, mysql does not return instantly, it seems to retrieve all records within the range first, then min/max on the result.

Suggested fix:
when running queries like the followings:
SELECT X FROM TABLE WHERE .... ORDER BY X DESC/ASC LIMIT n
SELECT MIN(X)/MAX(X) FROM TABLE WHERE .....
and there is an index IDX_X on column X, and IDX_X is the only index used in the query plan, mysql should use IDX_X to sort first, select next.

We need your table in order to reproduce a problem.

You can ZIP it and upload it in this database.

We seem to have enough information for now to test without a dump of your table.

A preliminary test result, though: the first two queries are both extremely fast using a current release of MySQL, so you may consider upgrading and seeing if you still have the performance difference.

The MIN/MAX queries are slow, however.  We are testing those.

The MIN/MAX queries should be fast:

explain select min(id_) from tbl_test where id_>100 and id_<5000000:

tbl_test | range | PRIMARY       | PRIMARY |       4 | NULL | 5220629 | Using where; Using index |

| Handler_read_key               | 1       |
| Handler_read_next              | 4999899 |
| Key_blocks_used                | 31172   |
| Key_read_requests              | 238755  |
| Key_reads                      | 40003   |

The query is slow with BETWEEN also.

i must have had an index on the data_ column when running "select id_ from tbl_test where id_<5000000 and data_ is not null order by id_ DESC limit 10". it now runs as fast as it should. sorry for the mistake.
however, min/max is slow.

Thank you for taking the time to write to us, but this is not
a bug. Please double-check the documentation available at
http://www.mysql.com/documentation/ and the instructions on
how to report a bug at http://bugs.mysql.com/how-to-report.php

Additional info:

It's not a bug - but a missing feature.
This optimization was added in MySQL 4.1