MySQL 5.1 Database Reference Guide :: 7.2.12 ORDER BY Optimization

Previous / Next / Up / Table of Contents

7.2.12. `ORDER BY` Optimization

$8.99

In some cases, MySQL can use an index to satisfy an ORDER BY clause without doing any extra sorting.

The index can also be used even if the ORDER BY does not match the index exactly, as long as all of the unused portions of the index and all the extra ORDER BY columns are constants in the WHERE clause. The following queries use the index to resolve the ORDER BY part:

SELECT * FROM t1 
  ORDER BY key_part1,key_part2,... ;
    
SELECT * FROM t1 
  WHERE key_part1=constant 
  ORDER BY key_part2;
    
SELECT * FROM t1 
  ORDER BY key_part1 DESC, key_part2 DESC;
    
SELECT * FROM t1
  WHERE key_part1=1 
  ORDER BY key_part1 DESC, key_part2 DESC;

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:

You use ORDER BY on different keys:
```
SELECT * FROM t1 ORDER BY key1, key2;
```

You use ORDER BY on non-consecutive parts of a key:

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

You mix ASC and DESC:

SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;

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;
```
You are joining many tables, and the columns in the ORDER BY are not all from the first non-constant table that is used to retrieve rows. (This is the first table in the EXPLAIN output that does not have a const join type.)
You have different ORDER BY and GROUP BY expressions.
The type of table index used does not store rows in order. For example, this is true for a HASH index in a MEMORY table.

With EXPLAIN SELECT ... ORDER BY, you can check whether MySQL can use indexes to resolve the query. It cannot if you see Using filesort in the Extra column. See Section 7.2.1, “Optimizing Queries with EXPLAIN”.

A filesort optimization is used that records not only the sort key value and row position, but the columns required for the query as well. This avoids reading the rows twice. The filesort algorithm works like this:

Read the rows that match the WHERE clause.
For each row, record a tuple of values consisting of the sort key value and row position, and also the columns required for the query.
Sort the tuples by sort key value
Retrieve the rows in sorted order, but read the required columns directly from the sorted tuples rather than by accessing the table a second time.

This algorithm represents a significant improvement over that used in some older versions of MySQL.

To avoid a slowdown, this optimization is used only if the total size of the extra columns in the sort tuple does not exceed the value of the max_length_for_sort_data system variable. (A symptom of setting the value of this variable too high is that you should see high disk activity and low CPU activity.)

If you want to increase ORDER BY speed, check whether you can get MySQL to use indexes rather than an extra sorting phase. If this is not possible, you can try the following strategies:

Increase the size of the sort_buffer_size variable.
Increase the size of the read_rnd_buffer_size variable.
Change tmpdir to point to a dedicated filesystem with large amounts of empty space. This option accepts several paths that are used in round-robin fashion. Paths should be separated by colon characters (‘:’) on Unix and semicolon characters (‘;’) on Windows, NetWare, and OS/2. You can use this feature to spread the load across several directories. Note: The paths should be for directories in filesystems that are located on different physical disks, not different partitions on the same disk.

By default, MySQL sorts all GROUP BY col1, col2, ... queries as if you specified ORDER BY col1, col2, ... in the query as well. If you include an ORDER BY clause explicitly that contains the same column list, MySQL optimizes it away without any speed penalty, although the sorting still occurs. If a query includes GROUP BY but you want to avoid the overhead of sorting the result, you can suppress sorting by specifying ORDER BY NULL. For example:

INSERT INTO foo
SELECT a, COUNT(*) FROM bar GROUP BY a ORDER BY NULL;

Previous / Next / Up / Table of Contents

7.2.12. ORDER BY Optimization

7.2.12. `ORDER BY` Optimization