MySQL not using indexes ("Using filesort") when using ORDER BY

Question

I'm hitting some quite major performances issues due to the use of "ORDER BY"-statements in my SQL-code.

Everything is fine as long as I'm not using ORDER BY-statements in the SQL. However, once I introduce ORDER BY:s in the SQL code everything slows down dramatically due to the lack of correct indexing. One would assume that fixing this would be trivial, but judging from forum discussions, etc this seems to be a rather common issue that I've yet to see a definitive and concise answer to this question.

Question: Given the following table ...

CREATE TABLE values_table (
  id int(11) NOT NULL auto_increment,
  ...
  value1 int(10) unsigned NOT NULL default '0',
  value2 int(11) NOT NULL default '0',
  PRIMARY KEY  (id),
  KEY value1 (value1),
  KEY value2 (value2),
) ENGINE=MyISAM AUTO_INCREMENT=2364641 DEFAULT CHARSET=utf8;

... how do I create indexes that will be used when querying the table for a value1-range while sorting on the value of value2?

Currently, the fetching is OK when NOT using the ORDER BY clause.

See the following EXPLAIN QUERY output:

OK, when NOT using ORDER BY:

EXPLAIN select ... from values_table this_ where this_.value1 between 12345678 and 12349999 limit 10;

+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+
| id | select_type | table | type  | possible_keys | key      | key_len | ref  | rows | Extra       |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+
|  1 | SIMPLE      | this_ | range | value1        | value1   | 4       | NULL | 3303 | Using where |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-------------+

However, when using ORDER BY I get "Using filesort":

EXPLAIN select ... from values_table this_ where this_.value1 between 12345678 and 12349999 order by this_.value2 asc limit 10;

+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+
| id | select_type | table | type  | possible_keys | key      | key_len | ref  | rows | Extra                       |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | this_ | range | value1        | value1   | 4       | NULL | 3303 | Using where; Using filesort |
+----+-------------+-------+-------+---------------+----------+---------+------+------+-----------------------------+

Some additional information about the table content:

SELECT MIN(value1), MAX(value1) FROM values_table;
+---------------+---------------+
| MIN(value1)   | MAX(value2)   |
+---------------+---------------+
|             0 |    4294967295 |
+---------------+---------------+

...

SELECT MIN(value2), MAX(value2) FROM values_table;
+---------------+---------------+
| MIN(value2)   | MAX(value2)   |
+---------------+---------------+
|             1 |        953359 |
+---------------+---------------+

Please let me know if any further information is needed to answer the question.

Thanks a lot in advance!

Update #1: Adding a new composite index (ALTER TABLE values_table ADD INDEX (value1, value2);) does not solve the problem. You'll still get "Using filesort" after adding such an index.

Update #2: A constraint that I did not mention in my question is that I'd rather change the structure of the table (say adding indexes, etc.) than changing the SQL queries used. The SQL queries are auto-generated using Hibernate, so consider those more or less fixed.

Answer 1

You cannot use an index in this case, as you use a RANGE filtering condition.

If you'd use something like:

SELECT  *
FROM    values_table this_
WHERE   this_.value1 = @value
ORDER BY
        value2
LIMIT 10

, then creating a composite index on (VALUE1, VALUE2) would be used both for filtering and for ordering.

But you use a ranged condition, that's why you'll need to perform ordering anyway.

Your composite index will look like this:

value1 value2
-----  ------
1      10
1      20
1      30
1      40
1      50
1      60
2      10
2      20
2      30
3      10
3      20
3      30
3      40

, and if you select 1 and 2 in value1, you still don't get a whole sorted set of value2.

If your index on value2 is not very selective (i. e. there are not many DISTINCT value2 in the table), you could try:

CREATE INDEX ix_table_value2_value1 ON mytable (value2, value1)

/* Note the order, it's important */    

SELECT  *
FROM    (
        SELECT  DISTINCT value2
        FROM    mytable
        ORDER BY
                value2
        ) q,
        mytable m
WHERE   m.value2 >= q.value2
        AND m.value2 <= q.value2
        AND m.value1 BETWEEN 13123123 AND 123123123

This is called a SKIP SCAN access method. MySQL does not support it directly, but it can be emulated like this.

The RANGE access will be used in this case, but probably you won't get any performance benefit unless DISTINCT value2 comprise less than about 1% of rows.

Note usage of:

m.value2 >= q.value2
AND m.value2 <= q.value2

instead of

m.value2 = q.value2

This makes MySQL perform RANGE checking on each loop.