Fun MySQL fact of the day: priority order

Yesterday and Friday, we took a quick peek into the sequence of events MySQL uses to LIMIT and OFFSET result sets. For the most part, it was relatively straight forward: MySQL either sends a row to the client or doesn't and it stops as soon as it sends n rows. Conceptually speaking, it's hard to make it any more efficient than it is. But what about when you mix in a filesort?

Back on April 17, we briefly discussed the two sorting algorithms of filesort: the quicksort+mergesort algorithm we've mostly focused on and the priority queue algorithm we haven't considered yet. Today we will, but before we do, let's first consider a table, (id,a,b,c) with no secondary indices and a query such as SELECT * FROM my_table WHERE c = 1 ORDER BY b LIMIT 10.

When we run this query, we can reason about a few things we know:

  1. it will perform an index scan to evaluate WHERE c = 1 on each row in the index
  2. it will be filesorted in order b
  3. the result set will be limited to 10

Now, based on what we know, if MySQL chooses the mergesort algorithm, MySQL will be required to store each row WHERE c = 1 in temporary files, merge sort the files, and then return the ordered results. In a table where there are thousands or millions of records where c = 1, the temporary files will be rather substantial and the sorting can get pretty expensive, especially if we only care about the first 10 rows. This is where the priority queue sorting algorithm comes into play: for queries with a LIMIT where the entire result set (of size (row_size + key_size) * (LIMIT + 1)) fits in the sort buffer as a priority queue (MySQL may also use <sort_key, rowid> with priority queue sort), priority queue sorting might be chosen.

In this implementation, for each row WHERE c = 1, MySQL will push the row into the priority queue. When the priority queue is full, the "lowest priority" row is dropped and the new one is inserted in the appropriate position. After all rows WHERE c = 1 are evaluated, the sort buffer is quick sorted as usual and then returned to the client as usual, all without any temporary files. So, while this sounds pretty great, you there are tradeoffs: while we reduce in storage requirements (and disk speed), we increase in processing complexity.