Why architecture matters here
The architecture matters because the join algorithm is the single biggest lever on query performance, and the three main choices have wildly different cost profiles. A nested-loop join is O(N×M) and only competitive when one side is tiny or there is an index on the inner side to avoid the full scan. A merge join is O(N log N + M log M) because it must sort both inputs, but it is cheap if the inputs arrive already sorted on the join key. A hash join is O(N+M) with no sort required — but it needs memory and only works for equality predicates. Choosing wrong by one algorithm can turn a sub-second query into one that never finishes.
Hash join is the workhorse for the analytical shape of query — large fact tables joined to each other and to dimensions on equality keys, with no helpful indexes. In a data warehouse, joining a billion-row sales table to a hundred-million-row customer table on customer_id is exactly the case hash join was built for: no index scan is affordable, the predicate is equality, and streaming both sides once is the only tractable plan. The nested loop is hopeless here and the merge join pays a heavy sort tax, so the hash join wins by construction.
The build-side choice is the first decision that separates a good plan from a bad one, and it depends entirely on statistics. The optimizer wants to build on the smaller input because the hash table's size — and thus whether it fits in memory — is set by the build side, not the probe side. If the planner's row-count estimates are wrong, it may build on the larger relation, blow through the memory budget, and spill unnecessarily, or even pick a nested loop believing a side is tiny when it is huge. This is why stale or missing statistics degrade hash joins so sharply: the algorithm is only as good as the size estimate that chose its build side.
Finally, the memory budget makes the hash join a resource-management problem, not just an algorithm. Each query gets a bounded working memory (work_mem in PostgreSQL, and analogous budgets elsewhere); if the hash table fits, the join runs entirely in memory at full speed, and if it does not, the join spills partitions to disk and pays extra I/O. Set the budget too low and joins that could have been in-memory thrash on disk; set it too high and many concurrent joins collectively exhaust RAM and the system pages or OOMs. The hash join therefore sits at the intersection of the optimizer's cost model, the statistics that feed it, and the memory manager that bounds it — understanding all three is what lets you reason about why a given join is fast, slow, or spilling, rather than treating the plan as an inscrutable black box.
The architecture: every piece explained
The build phase consumes one input in full and constructs an in-memory hash table keyed on the join column. Each build row is hashed and inserted into a bucket; when multiple rows share a key (or collide), they chain within the bucket. This phase is blocking — the join cannot emit any output until the entire build side has been read and hashed — which is why the build side is chosen to be the smaller one: less memory, and less time spent before probing can start streaming.
The probe phase streams the other input past the completed hash table. For each probe row, the engine hashes its join key, finds the corresponding bucket, and compares against the build rows there; every match emits a joined output row. The probe side is never materialized — it flows through in a single pass — so the probe can be arbitrarily large as long as the build side's hash table fits. This asymmetry is the whole reason the smaller relation goes on the build side.
The hash function and partitioning are what let the join exceed memory. When the build side is too large to hash into memory at once, the engine first partitions both inputs by a hash of the join key into K buckets, writing each bucket to a spill file on disk. Because the same key always hashes to the same partition on both sides, a build row and a matching probe row always land in the same partition number — so the join can be completed one partition pair at a time, loading each build partition into memory and probing it with the matching probe partition.
The memory budget (work_mem and friends) decides which regime the join runs in. If the build side's estimated size fits the budget, the join stays fully in memory — the fast path. If not, it uses the grace hash join (partition everything to disk, then join partition-by-partition) or the hybrid hash join (keep the first partition in memory and process it while spilling the rest, saving one round-trip). Spill batches are the per-partition disk files, and if a single partition is still too big for memory — usually because of skew, where one key value dominates — the engine recurses, re-partitioning that batch with a different hash seed until each piece fits. Together these pieces — build, probe, hash-partitioning, the memory budget, spill batches, and recursive re-partitioning — are the complete hash-join machine, and each exists to preserve the linear cost as inputs grow past the memory they are given.
End-to-end flow
Trace an in-memory hash join first. The optimizer, using table statistics, estimates that the customer dimension (two million rows) is smaller than the orders fact table (five hundred million) and that the customer hash table will fit in work_mem. It chooses customer as the build side. Execution begins: the engine scans all two million customer rows, hashes each on customer_id, and inserts them into the in-memory hash table. The build phase completes; nothing has been emitted yet.
Now the probe phase streams the orders table. For each order row, the engine hashes its customer_id, locates the bucket, and finds the matching customer row (or rows). On each match it emits a joined row carrying columns from both sides. Orders flows through in a single pass, five hundred million rows touched once each, never materialized. The whole join costs one scan of each input plus the hashing — linear in the sum of the sizes — and returns as fast as the slower input can be read.
Now the spilling case. Suppose the build side is not the tidy two-million-row dimension but a one-hundred-million-row intermediate result that does not fit in work_mem. The engine switches to grace/hybrid mode. In the partition pass it reads the build side and hashes each row into, say, 64 partitions, writing each partition to its own spill file; it does the same to the probe side using the identical hash, so partition i of the build and partition i of the probe contain all the rows whose keys hash to i. Now each partition is roughly one sixty-fourth the size and fits in memory.
The join phase then processes partitions one at a time: load build partition 0 into an in-memory hash table, stream probe partition 0 past it emitting matches, discard it, and move to partition 1. Because matching keys always share a partition number, no cross-partition comparison is ever needed — the global join has been decomposed into 64 independent in-memory joins. If partition 7 turns out to still be too big — because one customer_id accounts for a fifth of all orders, a classic skew — the engine recurses on that partition alone, re-hashing it with a new seed into sub-partitions until each fits. The output is identical to the in-memory join; only the path differs, and the extra cost is the I/O of writing and re-reading the spilled partitions. That graceful degradation — from pure in-memory, to partitioned-on-disk, to recursively-partitioned under skew — is what lets one algorithm span join sizes from megabytes to terabytes without ever falling back to a quadratic scan.