Sorting More Than Fits in Memory

Why this stage exists

The Sort operator of the previous stage collects every row it is given and sorts them in memory. That works until the table is larger than memory, and then it does not work at all. Databases sort tables far larger than their RAM every day, for ORDER BY, for building indexes and for joins, with an idea older than most of computing: external merge sort.

The idea has two halves. First, read as many rows as fit, sort them, and write them out as a sorted run; repeat until the input is used up. Second, merge the runs: every run is sorted, so the smallest row overall is the smallest of the runs' first rows. Take it, advance that run, repeat. The merge needs only one row from each run in memory at a time.

This engine counts its memory in rows, set with --sort-memory. The default is 10000 rows, so every table in the earlier stages sorted in memory and will keep doing so.

Runs, and how many

With 100 rows and a limit of 10, the Sort writes ten runs of ten rows. With a limit of 7 it writes fifteen, the last one with two rows. The number of runs is ceil(rows / limit), and the [EXEC] line now reports it for every plan that has a Sort:

$droid --db big.db --sort-memory 10
>select id, v from s order by v;
...
(100 rows)
[EXEC] rows_examined=100 sort_runs=10

Rows that fit make one run, sorted in memory and never written. A Sort that no row reaches makes none: sort_runs=0. A plan without a Sort, such as a query with no ORDER BY or one ordered by the key, prints rows_examined alone, as it always did.

Merging without losing stability

The previous stage promised that rows with equal keys come out in the order they arrived, which is key order. Spilling must keep that promise. Inside a run it is kept by the stable sort. Across runs it is kept by the merge's tie rule: when two runs offer equal rows, take the one from the earlier run. Every row of an earlier run arrived before every row of a later one, so the earlier run's row is the one that came first.

That is the whole reason the output does not depend on the limit. The tests sort the same 100 rows with limits of 1, 7, 10 and 1000 and compare every line: same rows, same order, ties included.

A file that is not the database

Runs go to a temporary file beside the database, named by adding .tmp to its path. It is scratch space for one statement, and it lives outside everything the earlier parts built to protect the database:

• it is not logged, and no transaction owns it: a ROLLBACK has nothing in it to undo, and a sort inside a transaction still sees that transaction's rows, because it sorts what the scan hands up;
• the pager's statistics do not count it;
• a SELECT that spills leaves the database file and the log exactly as they were.

Because nothing in it can ever be needed again, cleaning up is simple: delete it when the statement ends, whether the statement succeeded or failed, and delete any leftover at open, which is what a crash in the middle of a sort leaves. The sort_spill fail-point stops the program right after the first run is written, so the tests can see the file exist and then see the next open remove it.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 45.

The temporary file is <db path>.tmp. It exists only while a statement that spills is running, and the next open deletes one that a crash left. explain does not change: the plan cannot know how many rows will reach the Sort.

What you should see when done

$droid --db big.db --sort-memory 3
Welcome to droid!
>create table s (id int, v int);
Create table statement executed successfully
>insert into s (id, v) values (1, 2);
Insert statement executed successfully (1 rows)
>insert into s (id, v) values (2, 1);
Insert statement executed successfully (1 rows)
>insert into s (id, v) values (3, 2);
Insert statement executed successfully (1 rows)
>insert into s (id, v) values (4, 1);
Insert statement executed successfully (1 rows)
>insert into s (id, v) values (5, 2);
Insert statement executed successfully (1 rows)
>select id, v from s order by v;
id | v
2 | 1
4 | 1
1 | 2
3 | 2
5 | 2
(5 rows)
[EXEC] rows_examined=5 sort_runs=2
>select id from s;
id
1
2
3
4
5
(5 rows)
[EXEC] rows_examined=5
>.exit
exiting.. good bye!

The first run held ids 1, 2 and 3, the second ids 4 and 5. The ties on v = 1 (ids 2 and 4) and on v = 2 (1, 3 and 5) span both runs and still come out in key order. And there is no big.db.tmp left in the directory.

Common bugs in this stage

• The merge breaks ties by whichever run it looks at first, or last. Ties come out in the wrong order only when they span runs. On a tie, the lower run number wins.
• The last run is forgotten. The buffer that is still in memory when the input ends must be written too, or merged with the others. One row in five goes missing.
• Writing a run when the rows fit. Correct output, but sort_runs and the fail-point say a spill happened that should not have.
• Keys not stored with the rows. Recomputing keys from the row during the merge works only if the row still holds every column the keys need. Write the computed keys into the run.
• The temporary file left behind after an error. A key that divides by zero on row 95 must still delete the runs already written.
• Runs through the buffer pool as database pages. They get logged, counted, or written into the database file. The temporary file is separate.
• Opening one reader per run with all its pages in memory. That is the in-memory sort again. Read each run one page at a time.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C and C++: tmpfile() would be simpler, but the contract names the file, so fopen the path, write runs with fwrite, and remove it at the end. A small binary heap of run numbers makes the merge's smallest-row choice fast; compare by keys, then by run number.
• Rust: std::fs::File with BufWriter and BufReader; std::collections::BinaryHeap is a max-heap, so wrap entries in std::cmp::Reverse and put the run number in the ordering for ties.
• Zig: std.fs.cwd().createFile and deleteFile; std.PriorityQueue with a compare function that breaks ties by run number.