Parameters (MySQL 8.4 / MariaDB 11.4 filesort)
About this exampleAbout this example
Example query this animation executes
-- No index on order_date → filesort SELECT customer, order_date, total FROM orders ORDER BY order_date;
No index covers the ORDER BY, so the server filesorts. A small LIMIT uses a bounded priority queue; otherwise rows go into the sort buffer and are sorted there (a comparison sort on MySQL; on MariaDB a radix sort, since order_date is a 3-byte key). If the rows exceed sort_buffer_size, sorted runs are written to tmpdir and merged.
What you'll see in the animation
- Each pill is an orders row such as "Alice Jan 15", sorted by its order_date. Rows are copied into the sort buffer (purple zone).
- Comparison sort (MySQL, the default drawing): pivot, compare and swap until every row is in date order. MySQL uses std::sort or std::stable_sort; MariaDB its own quicksort when radix sort does not apply.
- MariaDB radix sort (sort key of 20 B or less, 1,000 to 99,999 rows in the buffer, keys not packed): rows drop into buckets by one key byte at a time, with zero comparisons. order_date is a 3-byte key, so MariaDB radix sorts any buffer of 1,000 to 99,999 rows here, whatever the row size; choose MariaDB under Server to see it. MySQL has no radix sort.
- Priority queue (LIMIT set): k seats hold the earliest dates seen so far; a later row is turned away, an earlier one evicts the latest seated date.
- If the rows overflow sort_buffer_size, each sorted buffer is written to tmpdir as a run (yellow), and a merge takes the earliest head across runs (green).
- Next step runs one step at a time; the simplified code beside the drawing highlights the lines each step runs.
Cost readout (filesort)
Sort algorithm ?Priority queue for a small LIMIT; otherwise a comparison sort of the buffer (MySQL std::sort or std::stable_sort, MariaDB quicksort), or on MariaDB a radix sort when the sort key is 20 B or less and the buffer holds 1,000 to 99,999 rows. See sql/filesort.cc and sql/filesort_utils.cc.
—
Rows per run ?How many rows fit in sort_buffer_size. More rows per run = fewer total runs = less disk I/O.
—
Sorted runs ?Each run is one sorted buffer of rows written to tmpdir. The merge reads all runs back in order.
—
Merge passes ?How many times the merge re-reads all rows. Both engines merge 7 runs at a time while more than 15 remain (MERGEBUFF and MERGEBUFF2), then do a final merge. More runs = more passes.
—
Disk spill? ?If all rows fit in sort_buffer_size, no disk I/O needed. Otherwise, sorted runs are spilled to tmpdir.
—
Total I/O rows ?Total rows read + written across all merge passes. Each pass reads and writes all rows once.
—
Total I/O rows vs row count (log–log, row size + sort_buffer_size fixed)
Learn more — the three sort algorithms + single-pass vs two-pass
Algorithm selection (in sql/filesort.cc and
sql/filesort_utils.cc):
1. Comparison sort: MySQL 8.4 and 9.x sort the
buffer with std::sort (an introsort: quicksort with a
heapsort fallback) when it holds 100 rows or fewer or the keys have
variable length, and with std::stable_sort (a merge sort)
otherwise. MariaDB uses its own quicksort, my_qsort2. All are
O(n log n) comparisons; the drawing shows quicksort.
2. Radix sort (MariaDB only): MariaDB radix sorts the
buffer when the sort key is at most 20 bytes, the buffer holds 1,000 to
99,999 rows and the keys are not packed (radixsort_is_applicable
in mysys/mf_radix.c). It makes one counting pass per key byte,
least significant byte first, with zero comparisons. MySQL 8.4
and 9.x have no radix sort in filesort and always use a comparison sort.
The length that counts is the sort key's, not the
row's: ORDER BY order_date sorts on a 3-byte DATE key (one
byte more if the column allows NULL; when MariaDB sorts row IDs instead
of rows it appends the primary key, 7 bytes in all with an INT id). A
fixed-size key such as a DATE is never packed. So whatever the row size,
MariaDB radix sorts each buffer that holds 1,000 to 99,999 rows: with
its default sort_buffer_size of 2 MiB the lesson's 10,000
rows of 200 bytes fit in one buffer and are radix sorted, and a sort that
spills radix sorts each full run.
3. Priority queue (bounded heap): used by both
engines when the query has ORDER BY … LIMIT k, k rows fit in
the sort buffer and it is expected to beat a full sort (MySQL
check_if_pq_applicable; MariaDB compares the sort costs in
filesort()). The server keeps a heap of the k
best rows. Each incoming row is compared to the worst of them; if it is
better, it replaces it. After all n rows, the heap holds the k earliest.
O(n·log k), much faster than fully sorting when k ≪ n, and nothing is
written to tmpdir.
Single-pass vs two-pass filesort:
Single-pass (sort the rows): The sort buffer holds the columns the query needs alongside the sort key. After sorting, rows are already complete, with no second read. This is faster but uses more buffer space per row.
Two-pass (sort row IDs): The sort buffer holds only the sort key and a row pointer. After sorting, the server re-reads each row from the table by its row ID. Less memory per entry, but a second random-I/O pass.
How they choose: MySQL 8.4 and 9.x sort full rows
whenever they can (Sort_param::decide_addon_fields) and fall
back to row IDs mainly when the query reads a MEDIUMBLOB, LONGBLOB,
MEDIUMTEXT or LONGTEXT column, or uses full-text search; max_length_for_sort_data is deprecated
there and has no effect. MariaDB still uses
max_length_for_sort_data (default 1024 bytes): longer rows
are sorted by row ID.
The animation above shows the general sort buffer → sorted runs → merge pattern, which is common to both strategies. The difference is what lives inside each sort-buffer entry.
Sources: MySQL 8.4 reference manual §10.2.1.16 "ORDER BY Optimization";
sql/filesort.cc and sql/filesort_utils.cc in the
MySQL and MariaDB source trees; mysys/mf_radix.c and
mysys/mf_qsort.c in MariaDB.