# 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:

- it will perform an index scan to evaluate
`WHERE c = 1`

on each row in the index - it will be
`filesort`

ed in order`b`

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