Bound a hash join's memory with --join-memory: when the build side has more rows than the limit, split both inputs into ceil(b / limit) partitions by a hash of their keys in the temporary file, join partition by partition, and report partitions=P.
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.
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.
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.
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
Partition, then join each partition in memory.
These are the exact lines the tests check. The full definition is on the output contract page, section 71.
| Input | Output |
|---|---|
--join hash --join-memory 10, users join orders | [EXEC] rows_examined=300 hash_build_rows=200 hash_probe_rows=100 partitions=20 |
the same with --join-memory 200 | ... partitions=1 |
--join-memory 0, --join-memory abc or --join-memory 1000001 | [ERROR:00109] ..., exit status 1 |
--join-memory with nothing after it | [ERROR:00102] ..., exit status 1 |
$droid --db spill.db --join hash --join-memory 1Welcome 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 | id1 | 11 | 3(2 rows)[EXEC] rows_examined=4 hash_build_rows=3 hash_probe_rows=1 partitions=3 sort_runs=1>.exitexiting.. good bye!
partitions=0 for a join that fits: it is one partition.The page above is the same for every language. These are the only language-specific hints.
Vec of partition writers indexed by hash % P; BufWriter per partition is fine for P in the hundreds.