Bug #11409 ORDER BY uses filesort where index should be used
Submitted: 17 Jun 2005 10:01 Modified: 23 Jun 2005 20:18
Reporter: Holger S. Email Updates:
Status: Not a Bug Impact on me:
None 
Category:MySQL Server Severity:S3 (Non-critical)
Version:MySQL 5.0.7-beta-standard-log OS:Linux (Debian Linux Sarge)
Assigned to: CPU Architecture:Any

[17 Jun 2005 10:01] Holger S.
Description:
Hello,

concerning to EXPLAIN output, MySQL uses Filesort even when it is advised to ORDER BY a primary key and without  any WHERE restrictions on even very  simple tables.

Your dokumentation says, that the Index should be used in this case: http://dev.mysql.com/doc/mysql/en/order-by-optimization.html

How to repeat:
-- phpMyAdmin SQL Dump
-- version 2.6.2-pl1
-- http://www.phpmyadmin.net
-- 
-- Host: localhost
-- Generation Time: Jun 17, 2005 at 11:47 AM
-- Server version: 5.0.7
-- PHP Version: 4.3.10-13
-- 
-- Database: `test`
-- 

-- --------------------------------------------------------

-- 
-- Table structure for table `user`
-- 

CREATE TABLE `user` (
  u_id mediumint(8) unsigned NOT NULL auto_increment,
  u_name varchar(32) NOT NULL,
  PRIMARY KEY  (u_id),
  UNIQUE KEY u_name (u_name)
) ENGINE=MyISAM DEFAULT CHARSET=latin1 AUTO_INCREMENT=323585 ;

-- 
-- Dumping data for table `user`
-- 

INSERT INTO user VALUES (1, '#InFernalz|Degoe');
INSERT INTO user VALUES (2, '21.PzD-Friedrich');
INSERT INTO user VALUES (3, 'Alfonso');
INSERT INTO user VALUES (4, 'Azarrua.SuperSoca-D');
INSERT INTO user VALUES (5, 'Body_Counter');
INSERT INTO user VALUES (6, 'EX_GUILI****[FRA]');
INSERT INTO user VALUES (7, 'FF77');
INSERT INTO user VALUES (8, 'Fokss');
INSERT INTO user VALUES (9, 'Fokss_0');
INSERT INTO user VALUES (10, 'guilherme');
INSERT INTO user VALUES (11, 'J@ni.fin');
INSERT INTO user VALUES (12, 'Jaakko');
INSERT INTO user VALUES (13, 'Jarkko');
INSERT INTO user VALUES (14, 'Joueur');
INSERT INTO user VALUES (15, 'kai hardies');
INSERT INTO user VALUES (16, 'lajos a bátor');
INSERT INTO user VALUES (17, 'Luke_Skywalker');
INSERT INTO user VALUES (18, 'Majors Zakis (Lat)');
INSERT INTO user VALUES (19, 'PEACE');
INSERT INTO user VALUES (20, 'PJ');
INSERT INTO user VALUES (21, 'portu');
INSERT INTO user VALUES (22, 'Red Shadow');
INSERT INTO user VALUES (23, 'Rema-zuikeli');
INSERT INTO user VALUES (24, 'riffraff');
INSERT INTO user VALUES (25, 'shifty [ P.I.A.F ]');
INSERT INTO user VALUES (26, 'Sparky');
INSERT INTO user VALUES (27, 'Specialist');
INSERT INTO user VALUES (28, 'superchu');
INSERT INTO user VALUES (29, '[ P.I.A.F ] shifty');
INSERT INTO user VALUES (30, '[=GFT=]Tango1602');

mysql> explain select * from user ORDER BY u_id DESC;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | user  | ALL  | NULL          | NULL | NULL    | NULL |   30 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

mysql> explain select * from user ORDER BY u_name DESC;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | user  | ALL  | NULL          | NULL | NULL    | NULL |   30 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

mysql> explain select u_id from user ORDER BY u_name DESC;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | user  | ALL  | NULL          | NULL | NULL    | NULL |   30 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

mysql> explain select u_name from user ORDER BY u_name DESC;
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key    | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------------+
|  1 | SIMPLE      | user  | index | NULL          | u_name | 34      | NULL |   30 | Using index |
+----+-------------+-------+-------+---------------+--------+---------+------+------+-------------+
1 row in set (0.01 sec)

mysql> explain select u_id from user ORDER BY u_id DESC;
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | user  | index | NULL          | PRIMARY | 3       | NULL |   30 | Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+-------------+
1 row in set (0.00 sec)

Only the last two sortings are done using the index and without filesort, but only due to the fact that all data are retrieved directly from the index.
[23 Jun 2005 10:55] Alexander Keremidarski
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:

"filesort" refers to the algortthm used to sort the result set. It has nothing to do with index usage.

MySQL uses Index to determine *which* rows it needs to extract, not te *order* in which they have to be read from disk.

In all queries included MySQL needs to retrieve values from *all* rows which makes renders index scan useless except for the case when type=index where index cache can speed up.
[23 Jun 2005 20:18] Sergei Golubchik
Actually, documentation only says that

... MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting. ...

it does not say the index *should* be used. In this case it's not used because it's usually faster to read the table data file sequentially, sort, write to temp file (if the table is big enough), and read again almost sequentially, then read the table once in the index order, using random I/O both for the index file and data file.