Join Algorithms: Hash Join

A hash join computes the result of an equi-join `R ⋈_{R.a = S.b} S` by exploiting a hash function `h` applied to the join attribute. The core observation is that if `r.a = s.b`, then `h(r.a) = h(s.b)` for any deterministic hash function `h`. This means all tuples that could match are guaranteed to land in the same hash bucket, while tuples in different buckets are guaranteed not to match. Comparison is therefore only ever needed within a bucket, not across the whole cross product. The simplest version, classic (in-memory) hash join, designates the smaller relation as the build input and the larger as the probe input. It scans the build relation once, inserting every tuple into an in-memory hash table keyed by the join attribute (the build phase). It then scans the probe relation once, hashing each tuple's join key and looking it up in the table, emitting a joined output tuple for every match found (the probe phase). If the build relation's hash table fits in memory, this costs one sequential scan of each relation — no repeated re-scanning as in nested-loop join. When the build relation is too large to fit in memory, the algorithm generalizes to Grace hash join (partitioning-based hash join, named after the GRACE database machine project). Both relations are first partitioned on disk using a hash function `h1` on the join attribute into `k` partitions each. Because `h1` is applied identically to both relations, tuples from `R` and `S` that could ever match are guaranteed to fall into partitions with the same index `i`: `R_i` can only join with `S_i`, never with `S_j` for `j ≠ i`. This is the partitioning invariant, and it is what makes the divide-and-conquer strategy correct: after partitioning, the original join reduces to `k` independent, smaller joins, each solvable by the in-memory algorithm — and if any partition pair is still too large, the process recurses with a fresh hash function `h2`, `h3`, and so on. This recursive step is called recursive partitioning.

The algorithm has two structurally distinct regimes, but both reduce to the same fundamental build/probe primitive once partitions are small enough.

Regime 1 — In-memory hash join (used directly, or on each partition pair after partitioning): 1. Choose the smaller relation as build input `B`, the other as probe input `P`. 2. Scan `B`; for each tuple, compute `h(key)` and insert into an in-memory hash table. 3. Scan `P`; for each tuple, compute `h(key)`, look up the bucket, and for every build tuple in that bucket with an equal key, output the joined pair.

Regime 2 — Grace (partitioning) hash join (used when `B` does not fit in memory): 1. Partition phase. Using hash function `h1` with `k` buckets, scan `R` and write each tuple to partition file `R_1, …, R_k`. Do the same for `S`, using the same `h1`, producing `S_1, …, S_k`. 2. Recursive check. For each `i`, if `R_i` (the smaller of the pair) fits in available memory, proceed to build/probe on `(R_i, S_i)` directly. Otherwise, recursively partition `R_i` and `S_i` using a new hash function `h2`, producing sub-partitions, and repeat. 3. Build/probe phase. For each final partition pair `(R_i, S_i)` that fits in memory, run the in-memory hash join: build a hash table on the smaller side, probe with the other, emit matches. The number of partitions `k` is chosen so that each resulting partition of the build relation is expected to fit in `M` memory pages — roughly `k ≈ ⌈B / M⌉` where `B` is the build relation's size in pages, though real systems add a fudge factor for hash-table overhead and uneven bucket sizes. ``` function HASH_JOIN(R, S, M): // M = number of memory buffer pages available if size(R) > size(S): swap(R, S) // R becomes the (smaller) build side if fits_in_memory(R, M): return BUILD_PROBE(R, S) else: return GRACE_HASH_JOIN(R, S, M) function GRACE_HASH_JOIN(R, S, M): k = choose_partition_count(size(R), M) // e.g. k = ceil(size(R) / M) h1 = new_hash_function() // --- Partition phase --- R_parts = PARTITION(R, h1, k) // R_parts[i] is a file on disk S_parts = PARTITION(S, h1, k) result = [] for i in 1..k: Ri, Si = R_parts[i], S_parts[i] if fits_in_memory(min(Ri, Si), M): result += BUILD_PROBE(Ri, Si) else: // recursive partitioning: partition sizes still exceed memory result += GRACE_HASH_JOIN(Ri, Si, M) // uses a fresh hash function internally return result function PARTITION(T, h, k): parts = [empty file for i in 1..k] for tuple t in T: i = h(t.joinKey) mod k append t to parts[i] return parts function BUILD_PROBE(B, P): // B = build (smaller), P = probe (larger), both in memory table = empty hash table for tuple b in B: table.insert(h2(b.joinKey), b) // in-memory hash function, distinct from partition hash output = [] for tuple p in P: bucket = table.lookup(h2(p.joinKey)) for b in bucket: if b.joinKey == p.joinKey: output.append(combine(b, p)) return output ``` A crucial implementation detail: the hash function used for partitioning (`h1`, `h2`, …) must be different from the hash function used for the in-memory hash table in `BUILD_PROBE`. If they were the same, every tuple within a partition would collide into the same bucket (since they all already share the same value under `h1`), destroying the point of hashing inside `BUILD_PROBE`. Real systems draw these from independent hash function families or use different seeds.

Correctness argument. The key invariant is the partitioning invariant: for any hash function `h` and any two tuples `r ∈ R`, `s ∈ S` with `r.a = s.b`, it must be that `h(r.a) = h(s.b)`, since `h` is a deterministic function applied to equal inputs. Consequently, if `r` is written to partition `R_i` and `s` is written to partition `S_j` using the same `h1`, then `r` and `s` can only match if `i = j`. This means no true join result is ever lost by partitioning (no false negatives): every genuinely matching pair ends up co-located in some `(R_i, S_i)`. Conversely, the algorithm never fabricates a match across different partition indices, because `BUILD_PROBE` only compares tuples that were routed to the same file and additionally re-checks key equality explicitly (guarding against hash collisions within a bucket, which would otherwise cause false positives). The explicit equality check inside `BUILD_PROBE`'s inner loop is what makes hashing collision-safe: a shared bucket is only a candidate match, verified by direct comparison. Recursion terminates because each level of partitioning splits data into `k` roughly equal-sized pieces (assuming a well-distributed hash function and no extreme skew), so partition sizes shrink geometrically; after `⌈log_k(B/M)⌉` levels, every partition fits in memory `M`. In the worst case of severe key skew, one partition could contain nearly the entire relation and re-partitioning would not reduce its size — a real limitation discussed below.

Time complexity. Let `M` and `N` denote the sizes (in disk pages) of the build and probe relations, with `M ≤ N`, and let `B` be the number of memory buffer pages available.

• In-memory hash join (no partitioning needed, `M ≤ B`): each relation is read exactly once from disk, giving I/O cost `O(M + N)`. CPU cost is `O(M + N)` expected, since hash-table insert and lookup are `O(1)` expected per tuple.
• One-pass Grace partitioning: partitioning requires reading and rewriting both relations once — cost `O(M + N)` reads plus `O(M + N)` writes — after which each partition pair is joined in memory at cost proportional to its size, summing to `O(M + N)` again. Total: `O(M + N)` I/O for one partitioning pass, a constant factor (roughly 3×: one read+write per relation for partitioning, one more read for build/probe) worse than the in-memory case but still linear.
• Recursive partitioning at depth d: each level re-reads and re-writes the data, so total I/O is `O(d · (M + N))` where `d = ⌈log_{k}(M / B)⌉` — logarithmic in the ratio of data size to memory size, not in `N` itself. In practice `d` is 0, 1, or rarely 2 for realistic memory sizes, since `k` (the fan-out) is typically in the hundreds.

This is the central efficiency claim: hash join is O(M + N) expected time (ignoring the small logarithmic partitioning-depth factor), dramatically better than nested-loop join's O(M · N) (block nested loop reduces this by a constant factor but remains quadratic in the number of blocks). The saving comes precisely from avoiding pairwise comparison — a `O(1)`-expected hash lookup replaces an `O(N)` inner scan.

Space complexity. The in-memory build phase requires `O(M)` memory for the hash table (where `M` here means the size of the smaller relation's partition, not the whole relation, once partitioned). Partitioning itself requires `O(k)` output buffers, one page each, so total buffer requirement is `B ≥ k + 2` (one input buffer, one output buffer per partition, plus a small constant); this constrains how large `k` can be chosen and is exactly why recursive partitioning is sometimes unavoidable — you cannot always jump straight to arbitrarily many partitions in one pass.

Honest tradeoffs. Hash join sacrifices output ordering entirely — unlike a merge join, its output is in whatever order probe-side matches happen to be found, so a query needing sorted output pays an extra sort afterward. It is also vulnerable to skew: if many tuples share the same join-key value (a "hash join hotspot"), they all land in one partition regardless of `k`, and that partition may never shrink under further hashing, forcing a fallback to nested-loop join or a specialized skew-handling strategy for that value. Finally, hash join's expected-time guarantee depends on good hash function quality and accurate estimates of relation size; if the optimizer misestimates and the chosen build side turns out too large for memory, performance degrades to disk-thrashing rather than smooth degradation.

Suppose we join `Employees(emp_id, dept_id, name)` with `Departments(dept_id, dept_name)` on `dept_id`. Say `Employees` has 9 tuples and `Departments` has 4, and available memory buffer holds only 2 tuples worth of hash table at a time (artificially small, to force partitioning and make the trace instructive). We pick `Departments` as the build side (smaller), and use `k = 2` partitions with `h1(x) = x mod 2`.

Departments (dept_id, dept_name): (1,Sales), (2,Eng), (3,HR), (4,Ops)

Employees (emp_id, dept_id): (101,1), (102,2), (103,1), (104,3), (105,2), (106,4), (107,3), (108,1), (109,4) Partition phase using `h1(dept_id) = dept_id mod 2`:

Each partition's build side (2 Departments tuples) now fits in the 2-tuple memory budget, so no further recursion is needed. Run `BUILD_PROBE` on each partition pair:

Partition 0 build/probe. Build hash table on `{(2,Eng), (4,Ops)}`. Probe with each Employees tuple:

Partition 1 build/probe. Build hash table on `{(1,Sales), (3,HR)}`. Probe with each Employees tuple:

The final result is the union of both partitions' outputs — all 9 Employees tuples matched, exactly as a full join would require, and no employee from partition 0 was ever compared against a department in partition 1: the partitioning invariant made those comparisons provably unnecessary rather than merely skipped by luck. Total work: 4 Departments tuples and 9 Employees tuples were each read once during partitioning, then once again during build/probe within their partition — versus a naive nested-loop join which would perform 4 × 9 = 36 comparisons. Here only 4 comparisons total occurred inside `BUILD_PROBE` (2 hash lookups per partition, each an `O(1)`-expected operation), illustrating concretely how hashing collapses the comparison count.

Hash join's partitioning strategy traces its lineage to the GRACE database machine project in Japan, which pioneered hardware-assisted relational hash-partitioning in the early 1980s, and to parallel database research at the University of Wisconsin that formalized and popularized the "hybrid hash join" used in commercial engines.

Every major relational database — PostgreSQL, MySQL, Oracle, SQL Server, and cloud analytic engines like Snowflake, BigQuery, and Spark SQL — implements hash join as a core physical operator, typically chosen by The Query Optimizer whenever an equi-join over large, unindexed relations is detected. Distributed query engines extend the idea to shuffle hash join, partitioning data across machines by hash of the join key so that matching rows land on the same node, mirroring the single-machine partitioning phase at cluster scale. In-memory analytic systems use radix hash join, a variant that partitions using bits of the hash value directly for cache efficiency, since modern CPU cache hierarchies make random-access hash-table probing expensive without careful data locality. Understanding hash join is also foundational for reasoning about join-order and algorithm-selection decisions made by the optimizer, since the choice between hash join, sort-merge join, and Join Algorithms: Nested-Loop fundamentally shapes query execution plans and, ultimately, Query Execution Plan cost estimates.

Ask the tutor: How does the query optimizer decide, at plan time, whether to use hash join, sort-merge join, or nested-loop join for a given equi-join?