Using filesort in simple query

Question

I have very simple table:

CREATE TABLE `navigation` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `parent_id` int(11) unsigned DEFAULT NULL,
  `title` varchar(255) NOT NULL COMMENT 'Название ссылки',
  `priority` tinyint(3) NOT NULL COMMENT 'Параметр сортировки'
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

with only 41 rows. Also I have very simple query:

mysql> EXPLAIN SELECT t.id, t.parent_id, t.title, t.priority FROM navigation t ORDER BY t.priority ASC;
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
| id | select_type | table | type | possible_keys | key  | key_len | ref  | rows | Extra          |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
|  1 | SIMPLE      | t     | ALL  | NULL          | NULL | NULL    | NULL |   41 | Using filesort |
+----+-------------+-------+------+---------------+------+---------+------+------+----------------+
1 row in set (0.00 sec)

How can I to avoid using filesort? Or is it impossible? I have read a lot of topics on SO, but couldn't understand right answer. Thank you.

Answer 1

How can I to avoid using filesort? Or is it impossible? I have read a lot of topics on SO, but couldn't understand right answer.

You would need an index over the priority column:

ALTER TABLE navigation ADD INDEX (priority);

However, the chances are that MySQL will calculate that using such an index to sort the results will ultimately be more expensive than a filesort (since the former will involve sequentially reading the index file in order to perform random I/O into the table, whereas the latter will involve sequentially reading the table and performing an in memory sort on the results). You can override this assessment with an index hint:

SELECT   t.id, t.parent_id, t.title, t.priority
FROM     navigation t FORCE INDEX FOR ORDER BY (priority)
ORDER BY t.priority ASC;

A covering index would altogether avoid the need to read into the table and thus could immediately return results merely from walking sequentially through the index file; it would therefore likely be selected by the query optimiser without further hinting:

ALTER TABLE navigation ADD INDEX(priority, id, parent_id, title);

Which approach is right for you will depend on your application's requirements, but remember Knuth's maxim: "premature optimisation is the root of all evil".

Answer 2

To avoid a filesort, most of the times you should be adding an index. In your case that would mean an index on the priority column. You can do this as follows:

ALTER TABLE `navigation` ADD INDEX (`priority`);

Note that even with this index it is still possible that a filesort is used as that might actually be faster than using the index. With 41 rows this could be the case, even with an index defined.

Answer 3

According to this blog post filesort occurs everytime you sort on an unindexed column. It has nothing to do with actual sorting taking place in the file system. With the description in Erik's answer you should get rid of it.