MySQL: Avoid filesort when using IN and ORDER BY

Pablo Borowicz picture Pablo Borowicz · Sep 17, 2009 · Viewed 7.4k times · Source

Let's suppose I have the following table (let's call it my_table):

CREATE TABLE `my_table` (
  `table_id` int(10) unsigned NOT NULL auto_increment,
  `my_field` int(10) unsigned NOT NULL default '0'
   PRIMARY KEY  (`table_id`),
   KEY `my_field` (`my_field`,`table_id`)
 ) ENGINE=MyISAM

The primary key for my_table is table_id (auto_increment) and I also have a key with my_field and table_id.

If I test this query...

EXPLAIN SELECT * FROM my_table
WHERE my_field = 28
ORDER BY table_id DESC;

... I get:

id  select_type  table     type  possible_keys  key       key_len  ref    rows  Extra
--- -----------  --------  ----  -------------  --------  -------  -----  ----  -----
1   SIMPLE       my_table  ref   my_field       my_field  8        const  36

You can see that it's using the correct key (my_field).

But if I try this...

EXPLAIN SELECT * FROM my_table
WHERE my_field IN (1, 28, 20)
ORDER BY table_id DESC;

... I get:

id  select_type  table     type  possible_keys  key     key_len  ref     rows  Extra
--- -----------  --------  ----  -------------  ------  -------  ------  ----  ---------------------------
1   SIMPLE       my_table  ALL   my_field       (NULL)  (NULL)   (NULL)  406   Using where; Using filesort

You can see that it's not using any key at all, and worse, using filesort.

Even if I do "FORCE INDEX (my_field)", It still does the filesort.

Is there any way to avoid the filesort?

Answer

Josh Davis picture Josh Davis · Sep 17, 2009

It is my understanding that MySQL cannot use the index to sort this query.

MySQL can only use the index if it just happens to be sorted the same way as your query. Let's say that your records for (table_id,my_field) are

(1,1), (2,28), (3,14), (4,20)

An index on (my_field,table_id) would be stored like this

(1,1), (14,3), (20,4), (28,2)

When executing the query from your IN example (for simplicity's sake, we'll say that your ORDER BY is ASCending), MySQL would find

(1,1), (20,4), (28,2)

...in this order. No matter what, it will have to sort those into (1,1),(28,2),(20,4). That's the filesort. That's why MySQL could only use that index if the query was ORDER BY my_field or ORDER BY my_field, table_id because the index is already in this order. That's also why it cannot [currently, some future version may allow you to sort composite indexes in mixed order] use the index if you mix ASC and DESC. The index is sorted in ASC,ASC and no matter which way you read it, it won't be in the right order.

Note that there's nothing wrong with "filesort", it's part of the normal execution of a query. It doesn't actually use files either and should be very fast.

If you have to sort thousands of rows, you may get better results by using a small derived table, especially if each row is really big (lots of fields, BLOBs, etc...)

  SELECT t.*
    FROM (
          SELECT table_id FROM my_table WHERE my_field IN (1, 28, 20)
         ) tmp
    JOIN my_table t USING (table_id)
ORDER BY t.table_id DESC

You will trade the filesort for a derived table. In some cases, it can be much more performant and in others, slightly less. YMMV