Fun MySQL fact of the day: filesort

So far this week, we've been looking at ORDER BY clauses that are index-optimized away, and fun quirks aside, things have been pretty great. But what about when we can't optimize away the ORDER BY?

If we consider our existing secondary index, (a,b,c) but change our query to SELECT a, b, c FROM my_table ORDER BY a, c, MySQL is no longer able to read all of the rows in order, a,c, from (a,b,c). If you managed to survive the last couple weeks of Fun MySQL Facts Of The Day, you'll probably remember why: in a b+tree index, records are ordered "left-to-right". This means that c is ordered by b, which means that c is out-of-order to a. So what? So, we need to do some actual sorting before returning the results set.

MySQL handles this using a method called filesort, and you can see filesort happening by looking in the Extra column of your EXPLAIN, which will show Using filesort. But, of course, it's more complex than that: the filesort algorithm varies, depending on circumstance, heuristics, data, and the query itself. But, ultimately, filesort will sort using either a priority queue or a merge sort, and while you have no direct control over which sort algorithm it uses, you can see which one will be used by enabling optimiser traces (MySQL 5.6+). In such a trace, you'll see something like filesort_priority_queue_optimization.usable: false, indicating that merge sorts will be used.

Over the next few days, we're going to look at some of the fun ways filesort behaves, but in the meantime, go SET optimizer_trace="enabled=on" and SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE\G.

Updated (2019-04-21) - I previously stated that filesort doesn't use files. I was comically wrong: it does.