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".