The idea: sort in passes, one page at a time
A database often has to sort a table that is much bigger than memory. The table lives on disk as N pages, and the sort may use only B buffer pages (frames) of memory. Disk is slow, so the cost that matters is the number of page I/Os: one read or one write of one page. External merge sort works in passes. Pass 0 cuts the file into sorted pieces called runs. Every later pass merges several runs into one longer run. When one run is left, the file is sorted.
On the canvas a page holds 2 keys. Colours show runs, and a grey page on the disk has already been read in this pass. Each step moves real keys between the disk and the frames, so you can count the I/Os yourself.
Pass 0: sorted runs
Read B pages into the B frames, so memory is full. Sort their keys in memory with any sort (this costs no I/O). Write the B pages back to disk as one sorted run. Repeat for the next B pages. You get ⌈N/B⌉ runs, each B pages long, except perhaps the last one (Demo: pass 0 only: 12 pages with B = 4 give 3 runs of 4 pages, 24 I/Os).
Merge passes: B − 1 inputs, 1 output
A merge pass needs one frame per run it reads, plus one frame for output. So with B frames it merges B − 1 runs at a time:
- Each input buffer holds the current page of one run. The first key left in it is that run's head.
- The smallest head is the next key of the output. It moves to the output buffer.
- When the output buffer is full, it is written to disk as the next page of the new run.
- When an input buffer is empty, the next page of its run is read into it.
If there are more than B − 1 runs, the pass works through them in groups of B − 1, and each group becomes one run. A group of just one run is still read and written, page by page (Demo: a short last run is copied). Picking the smallest of the heads is the in-memory k-way merge; a real sort keeps the heads in a heap or a tournament tree.
Counting the I/Os
Every pass reads each page once and writes each page once, so every pass costs 2N page I/Os, whatever B is. Only the number of passes changes. Pass 0 leaves ⌈N/B⌉ runs, and each merge pass divides the number of runs by B − 1:
The counter panel prints the formula next to the live counts, so you can check one against the other.
| Demo | Runs after each pass (pages) | Passes | Page I/Os |
|---|---|---|---|
| N = 8, B = 3 | 3+3+2, then 6+2, then 8 | 3 | 48 |
| N = 8, B = 4 | 4+4, then 8 | 2 | 32 |
| N = 8, B = 8 | 8 (fits in memory) | 1 | 16 |
| N = 12, B = 4 | 4+4+4, then 12 | 2 | 48 |
| N = 7, B = 3 | 3+3+1, then 6+1, then 7 | 3 | 42 |
| N = 16, B = 3 | 3+3+3+3+3+1, then 6+6+4, then 12+4, then 16 | 4 | 128 |
More buffers, fewer passes
More buffers help twice: pass 0 makes fewer, longer runs, and each merge pass merges more of them at once. For the 16-page file, B = 3 needs 4 passes (128 I/Os) but B = 5 needs only 2 (64 I/Os). The last line of the counter panel shows this for every B in the menu. If the whole file fits (N ≤ B), pass 0 is the whole sort (Demo: the file fits in memory).
Because the number of passes grows like a logarithm, real sorts rarely need more than two. With 8 KB pages and B = 1,000 frames (8 MB), pass 0 makes runs of 1,000 pages, and one 999-way merge pass handles up to 999,000 pages (about 8 GB). So a file of a few gigabytes is sorted in 2 passes, reading and writing it twice.
In a database: MariaDB filesort
When MariaDB cannot read rows in ORDER BY order from an index, EXPLAIN shows
Using filesort. The sort uses a buffer of sort_buffer_size bytes. If all rows fit, it
sorts in memory and stops, like the one-pass demo. If not, it sorts one buffer full at a time and writes each as
a sorted chunk to a temporary file (pass 0), then merges the chunks. Its merge step joins 7 chunks at a time
(MERGEBUFF in the source) until fewer than 15 are left, and then does one final merge. The status
variable Sort_merge_passes counts the merge passes. If it keeps growing, a bigger
sort_buffer_size for that session gives fewer and longer chunks, exactly as a bigger
B does here.
SET SESSION sort_buffer_size = 4 * 1024 * 1024; SELECT * FROM orders ORDER BY customer_id; SHOW SESSION STATUS LIKE 'Sort_merge_passes';
With ORDER BY … LIMIT MariaDB can skip all this and keep only the top rows in a priority
queue (see MariaDB EXPLAIN and Top-k LIMIT). For how filesort fits into a
whole query plan, see How MySQL Executes JOIN, GROUP BY and ORDER BY.
See also the in-memory merge sort on Bottom-up Merge Sort, the heap that picks the smallest head on K-way Merge, the pages a database keeps in memory on the InnoDB buffer pool, and sorted runs merged again and again on LSM Tree vs B-Tree.
See also File Organizations, which compares heap, sorted and hashed files by the block accesses each operation costs.
What the page leaves out
Real pages hold hundreds of rows, not 2 keys. Real sorts read and write several pages at a time (blocked I/O) and use double buffering so the CPU sorts while the disk works; both trade a little merge width for faster disk access. Replacement selection, which makes pass-0 runs about twice as long as memory, is a textbook technique that MariaDB's filesort does not use. The page also skips how filesort packs sort keys and row data into the buffer, its row-id mode, and the cost of comparisons, which is small next to the disk I/O.