droidPart 5 · Querying

Querying · Stage 6

Sorting More Than Fits in Memory

Give the Sort operator a memory limit, spill sorted runs to a temporary file when its input passes the limit, merge the runs stably into one order, count the runs, and leave no file behind, even after a crash.

Not run yet · 9 tests

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:

shell

$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.

Input, in arrival order

id 1

id 2

id 3

id 4

id 5

id 6

id 7

↓ cut into runs of at most 3 rows, each sorted and written

Run 1

id 2

id 3

id 1

Run 2

id 4

id 6

id 5

Run 3

id 7

↓ merge: take the smallest front row; on a tie, the lower run

Merged

id 2

id 4

id 7

id 3

id 6

id 1

id 5

order by v with --sort-memory 3: seven rows make three runs (sort_runs=3). The three a's come out as ids 2, 4, 7, the order they arrived in, because each tie goes to the earlier run.

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.

The algorithm in words

Make the runs

The Sort operator of the previous stage held every row. Now it holds at most the limit, and writes out what it cannot hold.

1.Ask the child for rows, computing each row's keys, into a buffer that holds at most the limit.
2.When the buffer is full and another row arrives, sort the buffer stably and write it, keys and rows, to the temporary file as one run. Remember where the run starts and how many rows it has. Empty the buffer and go on.
3.When the child has no more rows: if nothing was written, sort the buffer and hand rows up from memory, exactly as before. That is one run.
4.Otherwise write the last buffer as the final run. The number of runs is ceil(rows / limit).
5.Invariant: runs are numbered in the order they were written, and every row of run i arrived before every row of run i + 1.

Merge the runs

Each run is sorted; the output is the merge of all of them. Only the first unread row of each run has to be in memory.

1.Open a reader on each run, positioned at its first row.
2.To hand up the next row, look at the current row of every run that has one left and take the smallest by the keys of section 44.
3.On a tie, take the row from the run with the lower number. That is what keeps the merge stable: an earlier run holds rows that arrived earlier.
4.Advance the reader you took from. A run with no rows left drops out.
5.When every run is empty, the Sort has no more rows; delete the temporary file.
6.One merge over every run is enough for this stage, even with a hundred runs. A real engine with many runs merges a few at a time in passes, writing longer runs; that is an optimisation no test asks for.

Clean up

The temporary file belongs to one statement, and must not outlive it.

1.Create the file with the first run, beside the database, as the database path plus .tmp.
2.Delete it when the statement ends: after its last row, and also when it fails, for example with 01501 while computing a key.
3.At open, before recovery, delete a .tmp file a crash left behind: nothing in it is ever needed again.
4.Do not log it, and do not count it in the pager statistics: it is not part of the database.

Output contract for this stage

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

Input	Output
`--sort-memory 10`, then a SELECT whose Sort gets 100 rows	`[EXEC] rows_examined=100 sort_runs=10`
the same with `--sort-memory 1000`, or no option	`[EXEC] rows_examined=100 sort_runs=1`
a Sort that no row reaches	`sort_runs=0`
a SELECT whose plan has no Sort	`[EXEC] rows_examined=<n>`, with no `sort_runs`
`--sort-memory <rows>`, before or after `--db` and `-c`, as `--cache-pages` goes	accepted for 1 to 1000000
`--sort-memory 0`, `1000001` or `abc`	`[ERROR:00107] <message>`, exit status 1
`--sort-memory` with nothing after it	`[ERROR:00102] <message>`, exit status 1
`DROID_FAILPOINT=sort_spill` and a Sort over its limit	the program stops after the first run, exit status 3
the temporary file cannot be created, written or read	`[ERROR:01504] <message>`; the statement fails and its file is deleted (no test sets this up)

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

shell

$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.

Loading starter code…

No run yet

9 tests wait for your first run

Run tests builds your code, drives the binary through every case for this stage, and shows expected and received output side by side here. Failing cases come first.