Fun MySQL fact of the day: filesort uses files

Last Thursday, I provided incorrect information. As it usually happens, I was misled by the Internet, and in turn, I contributed to further misleading the Internet. I only realized it after couple hours with a debug build of MySQL and some breakpoints in some non-obvious places. Thankfully, the incorrect information was fairly innocent, albeit slightly comical if not outrageously so given the context. But don't worry, I'll clarify everything the best I can today.

On Friday, we looked at the <sort_key, rowid> mode of filesort, but there's one more mode we need to look at before moving on: <sort_key, additional_fields>. Unlike <sort_key, rowid>, when MySQL uses the <sort_key, additional_fields> mode of filesort, MySQL will not be required to make 2 trips into the storage engine. Instead, MySQL will buffer the sort_key and the SELECTed columns in memory, sorting each tuple by sort_key and returning the queried columns from the same buffer. This is, of course, less "efficient" in terms of memory usage than <sort_key, rowid>, but <sort_key, additional_fields> saves the extra step of random IO. And this brings us to where I got things terribly wrong: filesort might involve files. So it is aptly named. Even if the Internet says otherwise.

/me shakes fist at Internet!

Let's dig into this: like last week, if we consider selecting and ordering 10,000 rows of (BIGINT, VARCHAR(100)) with a 4-byte character set, we're looking at 816bytes/row (with extra overhead, too), requiring nearly 8MB of memory. That's a fair bit of memory, and before we move on, we should discuss sort_buffer_size, which is the buffer size MySQL uses to sort rows. By default, MySQL sets sort_buffer_size to 262144 (bytes), allowing for 256KB worth of rows to be sorted in memory, or sort_buffer_size / size_of_row_being_sorted rows at a time to be precise. In our case, that's roughly 321 rows. So what about the other 9,679 rows in our result set of 10,000? Well, after the buffer gets sorted in-place using a quick sort, the rows are written into a temporary file. Once all of the data is fetched from the storage engine, MySQL will then read and merge-sort (via buffers) the temporary file prior to returning the results.

So, bottom line: filesort will use a temporary file iff sort_buffer_size is less than the the size of the data being sorted. But, the advice from last week still doesn't change: keep your sort keys and number of rows sorted as small as possible.