Hash Join

With --join hash, join on equality by reading the right input once into a hash table keyed by the join columns and the left input once to probe it, with duplicate keys all matching, colliding keys told apart, NULL keys never matching, and LEFT JOIN padding.

Not run yet · 10 tests

Why this stage exists

The index nested loop is fast when there is an index and few outer rows. Take both away, with two big tables, no index and a report joining everything, and the nested loop is back to reading the inner table once per outer row: quadratic.

A hash join reads each table once. It is how analytical databases join, and with no index it is usually the fastest equality join there is.

Build, then probe

--join hash: users u join orders o on u.id = o.user_id

HashJoin (on: u.id = o.user_id)

↑ probe: 100 rows

ran

SeqScan (table=users, alias=u)

↑ build: 200 rows, first

ran

SeqScan (table=orders, alias=o)

rows_examined=300 hash_build_rows=200 hash_probe_rows=100. A nested loop would examine 20100.

Build. Read the right input to the end, putting each row in a hash table under the value of its join column: every order goes into the bucket of its user_id.
Probe. Read the left input. For each user, hash its id, look in that bucket, and pair the user with each order found there.

Only equality works: a hash says nothing about which keys are smaller, so on u.id < o.user_id cannot be hashed and stays a nested loop.

The right side always builds, and the left side always probes. That keeps LEFT JOIN simple: the left rows are the ones that stream past, so a left row that found nothing is padded on the spot. Choosing which table to put on the right, ideally the smaller one, is a question for the join-order stage.

Duplicates are not collisions

Two different things can share a bucket, and a correct hash join gets both right:

Duplicate keys. Three rows of a and two rows of b with k = 7 must give all six pairs. The bucket holds a list of rows, not one.
Collisions. Two different keys can hash to the same bucket. A table of 1024 buckets indexed by key mod 1024 puts 1024, 2048 and 3072 together. Those rows are in the bucket but are not partners. Always compare the key values, never just the hash.

NULL is the third trap. NULL = NULL is unknown, so a build row with a NULL key is never inserted, and a probe row with a NULL key finds nothing.

Order and counters

Rows come out in probe order, and for each probe row its matches in the order the build side read them. The [EXEC] line gains two fields, how many rows each side handed up:

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

The algorithm in words

Hash keys

Which conjuncts the table is keyed by.

1.Every conjunct of the condition that is l = r or r = l, l a column on the left and r a column on the right, is a hash key, in the order written.
2.The other conjuncts are the residual. With no hash key, the join is a nested loop.

Running a HashJoin

Build, then probe.

1.Build: read the right child to the end. Insert each row whose keys are all non-NULL into the table, under its key values, keeping the order rows arrived in.
2.Probe: read the left child row by row. A row with a NULL key pairs with nothing.
3.Otherwise hash its keys, and in that bucket take only the rows whose key values are equal to its own. Test the residual on each, and hand up the pairs for which it is true, in build order.
4.Under a LEFT JOIN, a left row that paired with nothing is handed up padded.

Output contract for this stage

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

Input	Output
`--join hash`, users join orders (100 and 200 rows)	`[EXEC] rows_examined=300 hash_build_rows=200 hash_probe_rows=100`
`explain` of it	`HashJoin (on: u.id = o.user_id)` over the users scan, then the orders scan
a LEFT JOIN	`HashJoin (left, on: u.id = o.user_id)`
`on u.id < o.user_id` with `--join hash`	`NestedLoopJoin (on: u.id < o.user_id)`

What you should see when done

shell

$droid --db hash.db --join hash
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, 7);
Insert statement executed successfully (1 rows)
>insert into a (id, k) values (2, NULL);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (1, 7);
Insert statement executed successfully (1 rows)
>insert into b (id, k) values (2, 7);
Insert statement executed successfully (1 rows)
>select a.id, b.id from a join b on a.k = b.k;
id | id
1 | 1
1 | 2
(2 rows)
[EXEC] rows_examined=4 hash_build_rows=2 hash_probe_rows=2
>.exit
exiting.. good bye!

Common bugs in this stage

Keeping one row per key. Duplicate keys must all match.
Matching on the hash alone. Colliding keys are not equal.
Inserting NULL keys, or matching a NULL probe key against them.
Building on the left. The right child builds; the left one probes and is padded under LEFT JOIN.
Losing build order inside a bucket. Matches come out in the order the build side read them.

Language notes

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

C: an array of buckets, each the head of a linked list of rows appended at the tail, is enough; FNV-1a over the key's bytes is an easy hash.
C++: std::unordered_multimap keeps duplicates, but not their order across rehashes; a map from key to std::vector<Row> does.
Rust: HashMap<Vec<Value>, Vec<Row>> with Value deriving Hash and Eq gives duplicates in order and compares keys for you.
Zig: std.HashMap with a context that hashes and compares your key values, mapping to an ArrayList of rows.

Loading starter code…

No run yet

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