Build your own mini columnar query engine · Stage 5 of 8

Hash join and broadcast join

Join two tables. Implement a hash join (build a hash table on one side, probe with the other) and a broadcast join (same result; the small build side is "broadcast"). In this single-process engine both produce identical output — only the intended data distribution differs, which is the whole point of the lesson.

Task

HashJoin(left, right, left_keys, right_keys, how="inner")
BroadcastJoin(left, right, left_keys, right_keys, how="inner")   # same result

Support how="inner" and how="left". Output columns = all left columns + all right columns except the (duplicate) right key columns.

Semantics you must get right

Duplicate build keys fan out. If the build side has two rows with key 3, every probe row with key 3 matches both → store a list per key, not a single row. (A join that dedups the build side is a classic bug.)
NULL keys never match (SQL). Drop rows whose key is NULL from both the build map and the probe — including a build-side NULL that must not match a probe-side NULL.
Left outer emits each unmatched left row once, with NULLs for right columns.

Checks

Inner & left joins vs DuckDB (G6), including duplicate keys and NULL keys.
HashJoin and BroadcastJoin give the same result.
A Hypothesis property joins random tables (with NULLs and duplicate keys) and compares against DuckDB.

Hints

Hint 1

Build a hash multimap from the smaller (build) side: key tuple -> list of rows. Keep it a LIST, not a single row, so duplicate build keys fan out correctly. Then probe with every row of the other side.

Hint 2

SQL join semantics: a NULL key never matches anything. Drop rows whose key tuple contains None from both the build map and the probe lookups.

Hint 3

BroadcastJoin has the SAME result as HashJoin (only the data distribution differs), so route both through one join routine. For how='left', emit unmatched left rows once with NULLs for the right columns.

Run it locally

uv run de start SPK-BYO/05-join
uv run de test