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.

N = 8 pages and B = 3 buffers. Pass 0 turns the unsorted file into 3 sorted runs of 3, 3 and 2 pages. Pass 1 merges runs 1 and 2 into a run of 6 pages and copies run 3. Pass 2 merges the runs of 6 and 2 pages into one sorted run of 8 pages. Each pass reads 8 pages and writes 8 pages, 16 I/Os, 48 in all
Each pass reads and writes the whole file once; the passes only differ in how many runs are left.

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.
B = 3 frames during a merge. Frame 1 holds page 20 24 of run 1, so its head is 20; frame 2 holds page 18 19 of run 2, head 18; frame 3 is the output buffer. 18 is the smallest head and moves to the output buffer. A full output buffer is written to disk; an empty input buffer reads its run's next page
Only one page of each run is in memory at a time, so B frames can merge B − 1 runs of any length.

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:

passes=1+⌈logB−1⌈N/B⌉⌉,I/O=2N×passes

The counter panel prints the formula next to the live counts, so you can check one against the other.

DemoRuns after each pass (pages)PassesPage I/Os
N = 8, B = 33+3+2, then 6+2, then 8348
N = 8, B = 44+4, then 8232
N = 8, B = 88 (fits in memory)116
N = 12, B = 44+4+4, then 12248
N = 7, B = 33+3+1, then 6+1, then 7342
N = 16, B = 33+3+3+3+3+1, then 6+6+4, then 12+4, then 164128

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.

On the mind map

Open the Databases & Storage mind mapDatabases& StorageSchema and storage: how rows land on diskSchema and storageIndexes: find rows without a full scanIndexesRunning a query: parse, plan, executeRunning a queryCost-based optimizer: estimate rows, pick cheapest planCost-based optimizerQuery rewrites: same answer, simpler queryQuery rewritesTransactions: ACID: isolation and recoveryTransactionsApps and connections: the client side of the databaseApps and connectionsMongoDB: documents, replica sets, shardsMongoDBHow MySQL runs a queryHow MySQL runs a querybuffer pool, undo, redo, binlogHow PostgreSQL runs a queryHow PostgreSQL runs a querynew tuple per update, VACUUM, WALSELECT clause orderSELECT clause orderFROM, WHERE, GROUP BY, HAVING, SELECTJoin algorithmsJoin algorithmsnested loop, hash, merge: pick by sizeExternal merge sort2N I/Os per pass, merge B−1 runs at onceFile organizationsFile organizationsHeap inserts, sorted ranges, hash findsMySQL JOIN, GROUP, ORDERMySQL JOIN, GROUP, ORDERtemporary table and filesortPostgres JOIN, GROUP, ORDERPostgres JOIN, GROUP, ORDERHashAggregate or Sort, by work_memRelational algebraRelational algebraselect, project, join: tables in, table outSQL joins on rowsSQL joins on rowsOuter joins pad unmatched rows with NULLSQL subqueriesSQL subqueriesOne NULL makes NOT IN return no rowsTriggers and proceduresTriggers and proceduresPer row; a CALL is not one statementWindow functionsWindow functionsaggregate per row without collapsingOpen the Databases & Storage mind mapDatabases & Storageparse, plan, executeRunning a queryHow MySQL runs a queryHow MySQL runs a querybuffer pool, undo, redo, binlogHow PostgreSQL runs a queryHow PostgreSQL runs a querynew tuple per update, VACUUM, WALSELECT clause orderSELECT clause orderFROM, WHERE, GROUP BY, HAVING, SELECTJoin algorithmsJoin algorithmsnested loop, hash, merge: pick by sizeExternal merge sort2N I/Os per pass, merge B−1 runs at onceFile organizationsFile organizationsHeap inserts, sorted ranges, hash findsMySQL JOIN, GROUP, ORDERMySQL JOIN, GROUP, ORDERtemporary table and filesortPostgres JOIN, GROUP, ORDERPostgres JOIN, GROUP, ORDERHashAggregate or Sort, by work_memRelational algebraRelational algebraselect, project, join: tables in, table outSQL joins on rowsSQL joins on rowsOuter joins pad unmatched rows with NULLSQL subqueriesSQL subqueriesOne NULL makes NOT IN return no rowsTriggers and proceduresTriggers and proceduresPer row; a CALL is not one statementWindow functionsWindow functionsaggregate per row without collapsing
This page on the Databases & Storage mind map · 55 pages in 8 branches · open it to see the whole map and test yourself in recall mode.