Hash Join

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

1. 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.
2. 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

Output contract for this stage

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

What you should see when done

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