Additional languages
« 7.2.8 LEFT JOIN and RIGHT JOIN Optimization
7.2.10 GROUP BY Optimization »
Section Navigation      [Toggle]

7.2.9. ORDER BY Optimization

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”.

MySQL has two filesort algorithms for sorting and retrieving results. The original method uses only the ORDER BY columns. The modified method uses not just the ORDER BY columns, but all the columns used in the query.

The optimizer selects which filesort algorithm to use. Prior to MySQL 4.1, it uses the original algorithm. As of MySQL 4.1, it normally uses the modified algorithm except when BLOB or TEXT columns are involved, in which case it uses the original algorithm.

The original filesort algorithm works as follows:

  1. Read all rows according to key or by table scanning. Rows that do not match the WHERE clause are skipped.

  2. For each row, store a pair of values in a buffer (the sort key and the row pointer). The size of the buffer is the value of the sort_buffer_size system variable.

  3. When the buffer gets full, run a qsort (quicksort) on it and store the result in a temporary file. Save a pointer to the sorted block. (If all pairs fit into the sort buffer, no temporary file is created.)

  4. Repeat the preceding steps until all rows have been read.

  5. Do a multi-merge of up to MERGEBUFF (7) regions to one block in another temporary file. Repeat until all blocks from the first file are in the second file.

  6. Repeat the following until there are fewer than MERGEBUFF2 (15) blocks left.

  7. On the last multi-merge, only the pointer to the row (the last part of the sort key) is written to a result file.

  8. Read the rows in sorted order by using the row pointers in the result file. To optimize this, we read in a big block of row pointers, sort them, and use them to read the rows in sorted order into a row buffer. The size of the buffer is the value of the read_rnd_buffer_size system variable. The code for this step is in the sql/records.cc source file.

One problem with this approach is that it reads rows twice: One time when evaluating the WHERE clause, and again after sorting the pair values. And even if the rows were accessed successively the first time (for example, if a table scan is done), the second time they are accessed randomly. (The sort keys are ordered, but the row positions are not.)

The modified filesort algorithm incorporates an optimization such that it records not only the sort key value and row position, but also the columns required for the query. This avoids reading the rows twice. The modified filesort algorithm works like this:

  1. Read the rows that match the WHERE clause.

  2. 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.

  3. Sort the tuples by sort key value

  4. 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.

Using the modified filesort algorithm, the tuples are longer than the pairs used in the original method, and fewer of them fit in the sort buffer (the size of which is given by sort_buffer_size). As a result, it is possible for the extra I/O to make the modified approach slower, not faster. To avoid a slowdown, the 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. If you use MySQL 4.1 or later, 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;

User Comments

Posted by Homme Bitter on February 13 2006 2:47pm[Delete] [Edit]

Make sure you have the sequence of your index fields correct and you do not have any other indexes that might also be used, but are not fully optimized.
SELECT * FROM t1 ORDER BY key_part2,key_part1,... ;
Will not be optimized if you have another index just describing key_part1 as a whole key.

Posted by Henrik Grubbström on March 24 2006 7:28pm[Delete] [Edit]

To be certain that this optimization is done you often need to force the correct index to be used with FORCE INDEX.

Another problem is that the optimization is lost when you have an OR on a prefix of the index:

SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=1 OR key1=2 ORDER BY key2,key3 LIMIT 5, 5;

This can be worked around by using UNION:

(SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=1 ORDER BY key2,key3 LIMIT 10)
UNION
(SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=2 ORDER BY key2,key3 LIMIT 10)
ORDER BY key2,key3 LIMIT 5, 5

This rewrite can make the query go ~20000 times faster on a table with ~2M rows.

Posted by Ravenous Bugblatter Beast on August 15 2006 11:22pm[Delete] [Edit]

If you are selecting a wide result set and using ORDER BY RAND() with a LIMIT, you can often speed things up by changing a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE conditions ORDER BY RAND() LIMIT m

To a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE id IN (SELECT id FROM tab WHERE conditions ORDER BY RAND() LIMIT m)

Although the second query has to perform an additional select, it only has to sort a result set containing the single id column, rather than the full result set you are returning from the query.

Posted by ML on August 29 2006 8:58am[Delete] [Edit]

===========================================================
Posted by Ravenous Bugblatter Beast on August 15 2006

If you are selecting a wide result set and using ORDER BY RAND() with a LIMIT, you can often speed things up by changing a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE conditions ORDER BY RAND() LIMIT m

To a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE id IN (SELECT id FROM tab WHERE conditions ORDER BY RAND() LIMIT m)

Although the second query has to perform an additional select, it only has to sort a result set containing the single id column, rather than the full result set you are returning from the query.
===========================================================

it's true, but if we have a big database with 1000ths of table rows and we must to join them ...... so oooops ;)
Lately I saw the following link http://jan.kneschke.de/projects/mysql/order-by-rand/ .....you can read here how to get more speed from your executing query in some cases. First read the explanation and see bottom of the page:

============================================================
Performance

Now let's see what happends to our performance. We have 3 different queries for solving our problems.

* Q1. ORDER BY RAND()
* Q2. RAND() * MAX(ID)
* Q3. RAND() * MAX(ID) + ORDER BY ID

Q1 is expected to cost N * log2(N), Q2 and Q3 are nearly constant.

The get real values we filled the table with N rows ( one thousand to one million) and executed each query 1000 times.
----------------------------------------------------------
Rows ||100 ||1.000 ||10.000 ||100.000 ||1.000.000
----------------------------------------------------------
Q1||0:00.718s||0:02.092s||0:18.684s||2:59.081s||58:20.000s
Q2||0:00.519s||0:00.607s||0:00.614s||0:00.628s||0:00.637s
Q3||0:00.570s||0:00.607s||0:00.614s|0:00.628s ||0:00.637s
----------------------------------------------------------

As you can see the plain ORDER BY RAND() is already behind the optimized query at only 100 rows in the table.
============================================================

Posted by Hugo Azevedo on November 12 2006 3:50am[Delete] [Edit]

All this is much faster than an ORDER BY RAND(), the problem is, it does not do the same.

Imagine you have a table with two columns (id, name) of thousands of names of people.

If you want to produce a result of only one record, then this is by far the fastest way to do it. You select a random ID from the table, and query it directly.

The problem is, if you want to retrieve two random records from the table.

ORDER BY RAND() will give you, for example, ID 390 and ID 4957 in a result, but the sugested way, will calculate a random index (ex. 390) and return two records based on that index, ID 390 and ID 391...
This means, that the order of the result is not random, only the first "fetched" ID. If you query for more than two records, it will give you ID 390, 391, 392, 393...

In other words, this does not produce an actual random selected result on more than one record.

Posted by [name withheld] on February 21 2007 11:20pm[Delete] [Edit]

When performing an ORDER BY col1 ASC - where col1 is an ENUM data type - the ORDER BY clause will not order by the natural language order, but the order of the values in the definition of the ENUM field.

To order by an ENUM field make sure the ENUM values are in alphabetical order or reverse-alphabetical order and then perform the ORDER BY clause.

Add your own comment.