MySQL Bugs: #3446: MyISAM Optimizer not using indices as documented for ORDER BY

Bug #3446	MyISAM Optimizer not using indices as documented for ORDER BY
Submitted:	12 Apr 2004 9:42	Modified:	14 Apr 2004 18:18
Reporter:	Matt Johnson	Email Updates:
Status:	Not a Bug	Impact on me:	None
Category:	MySQL Server	Severity:	S2 (Serious)
Version:	4.0.18	OS:	Linux (Linux)
Assigned to:	Sergei Golubchik	CPU Architecture:	Any

Description:
Hi,

Either there is a serious deficiency in my logic, or the MyISAM query optimizer is having serious trouble in 4.0.18.

Manual 7.2.9 (How MySQL Optimizes ORDER BY) suggests that if a key exists k1 (f1), that said key will be used for the query:

SELECT * FROM t1 ORDER BY f1;

However, in 4.0.18, it isn't! EXPLAIN indicates that filesort is being used, regardless of any valid index present.

How to repeat:
create table bar (data varchar(50), ordinal int unsigned primary key);
insert into bar values ('one', 1), ('two', 2), ('three', 3), ('four', 4);
explain select * from bar order by ordinal;

===

EXPLAIN says:

mysql> explain select * from bar order by ordinal;
+-------+------+---------------+------+---------+------+------+----------------+
| table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+-------+------+---------------+------+---------+------+------+----------------+
| bar   | ALL  | NULL          | NULL |    NULL | NULL |    4 | Using filesort |
+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

...which seems fundamentally wrong.

Promoted to 'Server' since it may not be just MyISAM.

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:

For small amount of rows MySQL always prefer table scan against index scan.

There is no reason to use index for just 4 rows.

Okay -- 4 rows I can understand, but I have an identical issue with a table with around 200 rows whereby MySQL resolutely uses filesort instead of indexing despite valid indices being present.

If this still counts as a "small number of rows" fair enough, but MySQL's preference to table scan in a quantifiably small table should be documented.

--M

The logic is as follows:

for SELECT * FROM table ORDER BY index
MySQL usually does not use an index, because using filesort and then retrieving rows with a record cache (sequentially from disk, that is) is usually faster then reading rows from the disk in a random - index - order.

MySQL would use an index if you use a LIMIT - to retrieve only few rows it is faster to read only these rows in the index order than to read the whole table to perform a filesort.

MySQL will use an index if it covers all the columns necessary for the query - in SELECT * - all columns in the table.