Match rows by hashing, not by scanning every pair. Build a hash table on the smaller relation keyed by the join attribute; probe it with each row of the larger relation; emit all matches. The witness proves the result is the exact same multiset a nested-loop join would produce — in O(n+m) comparisons instead of O(n·m). Rendered, not quoted.
source Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, VLDB 1984, pp. 323–333 — vldb.org/conf/1984/P323.PDF
Two relations join on a shared attribute k. Naively you compare every build row against every probe row — n·m comparisons.
Hashing replaces the scan: partition the build side into buckets by h(k)=k mod 4, then each probe row visits only its own bucket. Equal keys always land in the same bucket, so no match can be missed; unequal keys sharing a bucket (a collision) are rejected by an explicit key test.
| side | rows |
|---|---|
| BUILD R (small) | 5 |
| PROBE S (large) | 6 |
Joining by hashing — the build-and-probe algorithm is the-hash-table lifted into relational algebra. The same bucket-and-key-test that powers a dictionary now powers the equi-join.
It is the workhorse of query execution and the-query-optimization's favourite operator: whenever the optimizer can afford to build a table in memory, hash join beats sort-merge and nested-loop on unindexed equi-joins.
Live re-check: recompute the hash join under the current flag and compare its output multiset to the nested-loop ground truth.
BUILD side R = (k, r):
PROBE side S = (k, s):
Build — hash R into buckets by k mod 4:
Probe — each S row visits one bucket, key-tests every entry:
Joined rows (k : r › s):
Skew. If one key owns most rows, its bucket degrades to a linear scan and O(n+m) collapses toward O(n·m). Bratbergsengen's cost model assumes near-uniform hashing.
Memory. The build side must fit in RAM. If it doesn't, you spill — the Grace / hybrid partitioning the paper analyses — or the in-memory table thrashes.
Collisions are not matches. Two keys in one bucket must still be compared. Drop the key test and you emit garbage; skip duplicate entries and you under-join (window 6).
"Same bucket means the rows join."
→ No. k=5 and k=1 collide in bucket 1 (both ≡1 mod 4); the explicit key test keeps them apart. z›Z matches only c, never a or b.
"One match per probe row is enough."
→ Duplicate keys demand the full cross-product. k=1 has 2 build rows × 2 probe rows = 4 output rows, not 1.
"Hash join and nested-loop can differ."
→ For an equi-join they are provably the same bag. Any difference is a bug — exactly what the witness catches.
Planted void (disclosed): make probe stop at the first matching build row in each bucket — ignore duplicate keys. Probe rows with several matches get under-joined; the output no longer equals the nested-loop join.
The witness in window 7 flips red the instant this fires.