Tuesday, April 12, 2011

Optimizing MySQL filesort with small limit.

"filesort" is the MySQL catchall algorithm for producing ordered results. (For an explanation on how it works, see Sergey Petrunias blog http://s.petrunia.net/blog/?p=24).

For small data sets, "filesort" simply uses a quicksort in memory. However, for large data sets we create temporary (sorted) files, which are later merged.

In the recent MySQL release candidate http://dev.mysql.com/tech-resources/articles/whats-new-in-mysql-5.6.html this has been optimized for the following kinds of queries (and subqueries)

SELECT ... FROM single_table ... ORDER BY non_index_column [DESC] LIMIT N [OFFSET M];

If we have space in memory for (N + M) rows, we create a (bounded) Priority Queue to hold the data. This means we can produce the ordered result using a single table scan, thus saving the writing/reading of temporary files, and saving the merge step.

How can you see it in action? Sorry, there's no explain for it (yet). What you can do currently is to inspect the status counters which are associated with filesort, and verify they are all zero.

FLUSH STATUS;
SHOW SESSION STATUS LIKE 'Sort%';
<run your select ... limit query>
SHOW SESSION STATUS LIKE 'Sort%';

What kind of speedup can you expect? This depends on your data set, and your sort_buffer_size of course. With this table, and about 20 million rows, and default sort buffer, execution time drops from about 40 seconds to 10 seconds on my desktop machine:

CREATE TABLE t1(
  f0 int auto_increment PRIMARY KEY,
  f1 int,
  f2 varchar(200)
);

SELECT * FROM t1 ORDER BY f2 LIMIT 100;

4 comments:

  1. Oh, I forgot about SQL_CALC_FOUND_ROWS. This query:

    SELECT SQL_CALC_FOUND_ROWS * FROM t1 ORDER BY f2 LIMIT 100;

    still takes about 10 seconds with MySQL 5.6. Older versions will do the full sort/merge. Executing this with MySQL 5.5 takes about half an hour on my desktop. See bug: http://bugs.mysql.com/bug.php?id=18454

    ReplyDelete
  2. Didrik, what about queries that don't need a table scan for example suppose you add an index on the f1 column to the t1 table in your example, and then execute the query:

    SELECT * from t1 WHERE f1 between x AND y ORDER BY f2 LIMIT 100;

    ReplyDelete
  3. Wouldn't EXPLAIN actually show this? If there's an extra pass-through for sorting, Extra: Using filesort would show up. So wouldn't a lack of that be an indication that this is happening? For example, comparing EXPLAIN on MySQL 5.5 and 5.6, 5.5 would have Extra: Using filesort and 5.6 wouldn't?

    Or am I understanding the "filesort" thing wrong?

    ReplyDelete
  4. If there is no 'using filesort' in the explain, then we're reading
    the table in sorted order anyways, and will stop sending more results
    when we have reached the limit.

    By the way, there's no 'using priority queue' in the explain, but the
    optimizer trace will show it, see here http://jorgenloland.blogspot.co.uk/2011/10/optimizer-tracing-query-execution-plan.html

    ReplyDelete