MySQL InnoDB Sorting Issue

Question

I was surprised to see MySQL's InnoDB showing an interesting behavior, which I cannot fully explain. According to the official MySQL InnoDB Documentation:

"All indexes other than the clustered index are known as secondary indexes. In InnoDB, each record in a secondary index contains the primary key columns for the row, as well as the columns specified for the secondary index. InnoDB uses this primary key value to search for the row in the clustered index"

So to my understanding, any single-column index is actually a compound index over the selected column and the primary key (please correct me if this is not the case). Thus if I select from a table filtering by an indexed column and sorting by the primary key it should be an effective operation not requiring a filesort.

In practice, however, this is not the case as I illustrate below:

mysql> describe object_settings;
+-------------------+--------------+------+-----+---------+----------------+
| Field             | Type         | Null | Key | Default | Extra          |
+-------------------+--------------+------+-----+---------+----------------+
| object_setting_id | int(11)      | NO   | PRI | NULL    | auto_increment |
| object_id         | int(11)      | NO   | MUL | NULL    |                |
| name              | varchar(50)  | YES  | MUL | NULL    |                |
| value             | varchar(255) | YES  |     | NULL    |                |
+-------------------+--------------+------+-----+---------+----------------+
4 rows in set (0.00 sec)

mysql> select * from object_settings;
+-------------------+-----------+------+-------+
| object_setting_id | object_id | name | value |
+-------------------+-----------+------+-------+
|                 1 |        10 | foo  | bar   |
|                 2 |        10 | bar  | foo   |
|                 3 |        11 | bar  | foo   |
|                 4 |        12 | bar  | foo   |
|                 5 |        13 | bar  | foo   |
+-------------------+-----------+------+-------+
5 rows in set (0.00 sec)

mysql> explain select * from object_settings where object_id = 10 order by object_setting_id DESC;
+----+-------------+-----------------+------+---------------+-----------+---------+-------+------+-----------------------------+
| id | select_type | table           | type | possible_keys | key       | key_len | ref   | rows | Extra                       |
+----+-------------+-----------------+------+---------------+-----------+---------+-------+------+-----------------------------+
|  1 | SIMPLE      | object_settings | ref  | object_id     | object_id | 4       | const |    2 | Using where; Using filesort |
+----+-------------+-----------------+------+---------------+-----------+---------+-------+------+-----------------------------+
1 row in set (0.00 sec)

Why is there a filesort operation present all of a sudden? Or does the MySQL Documentation mean something completely different to my understanding?

Answer 1

I have some rather distressing news: ORDER BY can still wreak some havoc with filesorts.

With all the hype about this being addressed and fixed, there is simply no way to get InnoDB to effectively use the index on an ORDER BY.

Start with the Ground Zero of InnoDB row data, the Clustered Index.

Rows are tagged with

• a 6-byte transaction ID field
• a 7-byte roll pointer field

Rows tend to be ordered by the whatever order the data was entered. The columns of a PRIMARY KEY are included in secondary indexes and are used to search for rows in the Clustered Index, Unfortunately, the two ID fields are not really used in dictating any ordering of rows within the Clustered Index. (For more info, please see MySQL Documentation on InnoDB Physical Row Structure)

Here is something even more disturbing: Did you know you could order rows in a table by the columns of the PRIMARY KEY or any arbitrary ordering you choose?

Here is the syntax:

ALTER TABLE tblname ORDER BY col_name [, col_name] ...

This could speed up some queries that a PRIMARY KEY ordered, but what's disturbing is that it only applies to MyISAM tables. Why not InnoDB ?

According to the MySQL Documentation on ALTER TABLE ... ORDER BY:

ORDER BY enables you to create the new table with the rows in a specific order. Note that the table does not remain in this order after inserts and deletes. This option is useful primarily when you know that you are mostly to query the rows in a certain order most of the time. By using this option after major changes to the table, you might be able to get higher performance. In some cases, it might make sorting easier for MySQL if the table is in order by the column that you want to order it by later.

ORDER BY syntax permits one or more column names to be specified for sorting, each of which optionally can be followed by ASC or DESC to indicate ascending or descending sort order, respectively. The default is ascending order. Only column names are permitted as sort criteria; arbitrary expressions are not permitted. This clause should be given last after any other clauses.

ORDER BY does not make sense for InnoDB tables because InnoDB always orders table rows according to the clustered index.

This comes as no surprise to me since I mentioned this in one of my earlier posts : (Aug 29, 2011 : Preordering the table by a specified column)

Therefore, doing an ORDER BY on an InnoDB table never guarantees proper index selection due to its internal index organization. Thus, one should not be surprised by a filesort on an InnoDB table no matter what secondary indexes the table has.

Answer 2

I tested this on 5.6.14 (Ubuntu) and the results are the same. The ORDER BY is causing the file sort. Why is this happening?
Reference: http://dev.mysql.com/doc/refman/5.6/en/order-by-optimization.html

In some cases, MySQL cannot use indexes to resolve the ORDER BY, although it still uses indexes to find the rows that match the WHERE clause. These cases include the following:
.....
The key used to fetch the rows is not the same as the one used in the ORDER BY:

 SELECT * FROM t1 WHERE key2=constant ORDER BY key1;

So the answer is, The key used to fetch the rows is not the same as the one used in the ORDER BY, thus:

.... where object_id = 10 order by object_setting_id DESC;

satisfies the case.

Answer 3

It is a known issue that MySQL does not take advantage of this when performing omrder by. If I remember correctly, it was fixed in MySQL 5.5, e.g. in 5.5 it won't use the filesort

bug report