Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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?

share|improve this question
1  
What is the EXPLAIN if you do SELECT object_setting_id ... (the rest as it is)? –  ypercube Jun 24 '13 at 13:17
    
And what if you keep the SELECT * but remove the ORDER BY clause? –  ypercube Jun 24 '13 at 13:22
    
Selection only the object_setting_id yields an additional "Using Index" (as expected), filesort stays :( No Order By clause has then only "Using Index" (also as expected). However, NOT using a Where immediately picks PRIMARY as the key and thus does not yield a filesort. Why is that so? The documentation leads me to believe something different 8) –  clops Jun 24 '13 at 14:39
1  
I can't reproduce the EXPLAIN output with InnoDB tables. Are you sure that the table is not a MyISAM table (or some other engine)? See the SQL-Fiddle (removed my previous, wrong comments.) –  ypercube Jun 27 '13 at 16:18
2  
@Darhazer The ASC and DESC descriptors are allowed in index definitions but ignored in MySQL. –  ypercube Jun 28 '13 at 10:11
show 2 more comments

3 Answers

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.

share|improve this answer
    
So what you are basically saying is, that secondary indexes contain the columns of the PK, which are used to retrieve the rows out of the clustered index, but the columns are not integrated (or appended) into the index structure, which draws them useless for sorting? Since the rows inside the clustered index need not to be sorted by PK as well, it uses filesort? But what happens, if one adds the PK columns to a composite index manually? This way the B-tree should include the PK columns as well and should be able to avoid a filesort like in a myisam composite index? –  GhostGambler Feb 28 at 9:59
add comment

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.

share|improve this answer
1  
According to this presentation the PK is added to every secondary index as last part. One would therefore have a combined index (object_id, object_setting_id) in the upper example. This would fulfill the case SELECT * FROM t1 WHERE key_part1 = constant ORDER BY key_part2; from the url you posted and thus should use the index without need of filesort? Can you provide your example statement with the create table statements? –  GhostGambler Feb 27 at 16:58
1  
What is there to provide? I used your example from above. The results were the same. The MySQL documentation is clear as to WHY the filesort was used. Your EXPLAIN exhibits the MySQL documentation statement: object_id index was used to fetch the rows but ORDER BY was by object_setting_id. Ergo, The key used to fetch the rows is not the same as the one used in the ORDER BY. –  Van Feb 27 at 17:50
1  
Yes, but the unclear aspect is that innodb merges secondary indexes with the clustering index somehow and why in this case order by cannot be fulfilled directly by this combined index although it seems applicable. @RolandoMySQLDBA (maybe) made a good point why this does not work as one might expect, which I am working through right now. (The request for the DDL statements had nothing to do with your answer. I just wanted to try myself and it is easy to click on 'export', while it is tedious to create the table from the output of the original question... sorry if this confused you.) –  GhostGambler Feb 27 at 17:57
    
@Van is key1 the primary key in your testing? –  ypercube Feb 27 at 19:00
    
I used the original posters schema to test. If you are using the MySQL example then yes, key1 is the primary key. –  Van Mar 1 at 10:13
add comment

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

share|improve this answer
    
I am testing in 5.5 :( –  clops Jun 28 '13 at 8:48
    
Whcih minor version of 5.5 are you using, @clops? –  ypercube Jun 28 '13 at 10:11
    
Actually this was fixed in 5.0 as the bug tracker says, so this should not be a problem? –  GhostGambler Feb 25 at 8:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.