When the Build Side Does Not Fit

Why this stage exists

A hash join holds its whole build side in memory. Ten thousand orders fit; a billion do not. The external-sort stage solved the same problem for ORDER BY by writing sorted runs to disk. This stage solves it for hash joins, with the same temporary file and the same kind of limit: --join-memory <rows>, 10000 by default.

Partitions

The idea that makes it work: rows with equal keys hash to the same value. So if both inputs are split by the same hash into the same number of partitions, every pair that can join lies inside one partition. Each partition can be joined on its own, and a partition is small enough to fit.

The number of partitions is fixed by the build side's size: P = ceil(b / limit). With 200 build rows and --join-memory 10, that is 20. A build side of exactly limit rows fits, and is one partition.

So the join reads the build side, writing it to the temporary file once it no longer fits; splits it into P partitions; reads the probe side into the same P partitions; then builds and probes one partition at a time. Each input is read once and written once more.

Skew

One key with more rows than the limit cannot be split by any hash: all its rows go to one partition. Real engines split again with a second hash, which does not help either, and then fall back to something slower. Here the rule is simple: the limit decides how many partitions there are, and an oversized partition is joined in memory all the same. The join never fails because of the limit.

What spilling changes

The same rows come out, but not in probe order: partition by partition. A spilled join promises no order, so a query that needs one must say ORDER BY. The database file and the log are not touched, and the temporary file is gone when the statement ends.

partitions=<P> follows hash_probe_rows on the [EXEC] line, 1 when nothing spilled:

[EXEC] rows_examined=300 hash_build_rows=200 hash_probe_rows=100 partitions=20

Output contract for this stage

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

What you should see when done

$droid --db spill.db --join hash --join-memory 1
Welcome to droid!
>create table a (id int primary key, k int);
Create table statement executed successfully
>create table b (id int primary key, k int);
Create table statement executed successfully
>insert into a (id, k) values (1, 1);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (1, 1);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (2, 2);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (3, 1);
Insert statement executed successfully (1 rows)
>select a.id, b.id from a join b on a.k = b.k order by b.id;
id | id
1 | 1
1 | 3
(2 rows)
[EXEC] rows_examined=4 hash_build_rows=3 hash_probe_rows=1 partitions=3 sort_runs=1
>.exit
exiting.. good bye!

Common bugs in this stage

• Different hashes or partition counts on the two sides. A pair split across partitions is lost.
• Promising probe order. Rows come partition by partition.
• Refusing a partition over the limit. Skewed keys must still join.
• Leaving the temporary file behind, or writing it into the database file.
• Counting partitions=0 for a join that fits: it is one partition.

Language notes

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

• C: reuse the run writer of the external sort; a partition is a run that is not sorted.
• C++: one output buffer per partition, flushed to its own page chain in the temporary file.
• Rust: a Vec of partition writers indexed by hash % P; BufWriter per partition is fine for P in the hundreds.
• Zig: an array of P small buffers, each with the page number of its chain's tail.