Parameters (MySQL 8.4 / MariaDB 11.4 filesort)
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 MySQL filesorts. The in‑memory algorithm depends on context: radix sort for short fixed keys, introsort for the general case, or a bounded priority queue when LIMIT is small. If the data exceeds sort_buffer_size, sorted runs spill to tmpdir and are k‑way merged.
What you'll see in the animation
- Rows flow into the sort_buffer (purple/blue zone).
- MySQL picks one of three in-memory algorithms based on the key and query:
- • Radix sort (blue) — fixed-length key ≤ 16 B (INT, BIGINT, DATE). Distributes rows into digit buckets with zero comparisons. O(n·k).
- • Introsort (purple) — general case (VARCHAR keys, composites > 16 B). Quicksort with heapsort fallback after O(log n) depth. Guaranteed O(n log n).
- • Priority queue (blue) — ORDER BY … LIMIT k with small k. Maintains a bounded max-heap of k rows; each incoming row is pushed/popped. O(n·log k).
- If all rows fit in sort_buffer_size, the result streams from memory — zero disk I/O.
- If rows overflow, each sorted chunk is flushed as a run to tmpdir (yellow). Final phase: k-way merge across runs (green).
Cost readout (filesort)
Sort algorithm ?MySQL picks: radix sort (key ≤ 16 B), introsort (general case), or priority queue (small LIMIT). See sql/filesort.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 a sorted chunk written to tmpdir. The inner table is merged across all runs in the merge phase.
—
Merge passes ?How many times the merge must re-read all rows. MySQL merges up to ~15 runs per pass. 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):
1. Radix sort — Used when the sort key is fixed-length
and ≤ 16 bytes on 64-bit systems (e.g. INT, BIGINT,
DATE, DATETIME). It distributes rows into
digit-buckets with zero comparisons. O(n·k) where k is the key
width in bytes. Cache-friendly because it processes all rows in sequential
passes.
2. Introsort (std::sort) — The general-case
algorithm for variable-length keys (VARCHAR) or composite keys
exceeding 16 bytes. Introsort starts as quicksort (cache-friendly, in-place,
small constant factor) but switches to heapsort if recursion depth exceeds
O(log n), guaranteeing O(n log n) worst case. This is what MySQL actually
uses — not plain quicksort.
3. Priority queue (bounded heap) — Used when the query
has ORDER BY … LIMIT k and k×row_size fits in the sort buffer.
MySQL maintains a max-heap of k elements. Each incoming row is compared to
the heap's maximum; if smaller, it replaces it. After scanning all n rows,
the heap holds the k smallest. O(n·log k) — much faster than fully sorting
when k ≪ n. No disk spill possible because only k rows are ever in
memory.
Single-pass vs two-pass filesort:
Single-pass (original algorithm): The sort buffer holds the entire row alongside the sort key. After sorting, rows are already complete — no second read. This is faster but uses more buffer space per row.
Two-pass (rowid sort): The sort buffer holds only the sort key + row pointer. After sorting, MySQL must re-read each row from the table by rowid. Uses less memory per entry but requires a second random-I/O pass.
MySQL chooses between them based on max_length_for_sort_data
(default 4096 in MySQL 8.4). If the total row length exceeds this
threshold, the two-pass algorithm is used.
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 in the MySQL source tree.