When a hash table does not fit
An in-memory hash join first builds a table of the left records and then probes it with the right records. That is attractive when the table fits, but a large file may not. Partitioning makes a smaller problem out of each key group: send records from both files to the same numbered partition whenever their keys are equal. A second pass joins corresponding partitions. This is often called a Grace hash join. Its benefit depends on the partitions actually fitting; hashing is not a guarantee against a popular key or an unlucky distribution.
We study a finite inner equijoin under bag semantics, with keys that are non-null and compared exactly.
Definition 20.3.1
(Bag equijoin and partition function)
Each position in an input file is a distinct occurrence, even when two records are identical. The bag inner equijoin of and contains one ordered pair for every left occurrence and right occurrence with equal keys, and no other pair; it need not be sorted. A partition function is a map from keys to , with , that is deterministic during the run; equal keys therefore have the same hash value, while unequal keys may collide.
Concept lensAlgebraic
The join size as an inner product
Write and for the numbers of occurrences of key in and . The bag equijoin is the disjoint union, over keys , of the pairs with key , so is the inner product of the two multiplicity vectors. A partition function splits the key set into the classes , and the sum splits into one term per partition; this is why corresponding partitions can be joined independently. In the first worked example below, .
Two passes and their memory contract
Let the files occupy blocks. A block transfer reads or writes one block. During partitioning use one input buffer and output buffers; direct each occurrence to its partition and flush every nonempty final partial buffer. The partition files preserve occurrences, are individually packed, and are written to fresh storage. Let be their actual block counts, and put , . Because partial blocks are flushed independently, can exceed , and can exceed . Empty partitions occupy no blocks.
For the second pass, read each into an in-memory hash table, including all its occurrences, then read once. On each probe compare the actual key against every candidate in the corresponding table bucket and emit one pair for every equal-key occurrence. A second hash function may organize this table; it must also map equal keys to the same bucket, and its collisions require equality checks. Reuse one output buffer across all partitions and flush it only when full or at the end. The table, including its indexing overhead, must fit in memory blocks for every . Reserve one further block for reading and one for output. The memory budget in blocks must therefore be at least ; small control descriptors are excluded. There is no cached-partition shortcut, compression, index access, or reuse of input buffers across passes in this accounting.
Theorem 20.3.2
(Correctness under bag semantics)
Under this contract, with the same partition function applied to both files, the algorithm emits exactly the bag equijoin: every equal-key pair of occurrences once, and no other pair.
Proof
(Each equal-key pair meets exactly once)
An input occurrence is sent to exactly one partition and is retained there. For any equal-key pair , determinism and equal-key consistency give . The build reads once into table , and the probe reads once and visits all candidates in its table bucket. The actual comparison accepts , so this pair is emitted once. Each occurrence has only one partition and each probe is processed once, so it cannot be emitted elsewhere. Conversely, emission requires an actual equality comparison, so a hash collision between unequal keys creates no spurious pair. The reasoning counts occurrences, not distinct values.
Two different mechanisms appear in this proof, and each covers a failure the other cannot.
Proof X-ray
Two independent checks
The partition function decides which records can meet; the actual equality comparison decides which of those meetings produces a pair. Completeness uses only the first: because the same deterministic is applied to both files, two equal keys always land in the same partition, so no matching pair is separated. Soundness uses only the second: since hashes can collide, sharing a partition or a bucket is merely candidacy, and the key comparison removes the cross-key pairs. Exactly-once emission rests on a third, quieter fact, that every occurrence is routed to one partition and each probe occurrence is read once; this is why the argument counts occurrences rather than distinct keys, and why duplicates multiply rather than merge.
Proposition 20.3.3
(Block-transfer count)
If every build table fits, is the number of output pairs and each output block holds pairs, the algorithm performs exactly
block transfers, taking the final term to be zero when . This counts materialized output writes and the specified partition files, not computation, seeks, failures, or storage deletion.
Proof
(Add the disjoint transfer phases)
The original input scans cost reads. Writing the partition files costs writes, and loading and probing them costs another reads, including all nonempty partitions. Finally the packed output uses writes. Adding these disjoint transfers proves the count. The table-fit condition is essential: if a partition does not fit, the stated second pass is not an executable implementation and this formula is not its cost.
Worked example 20.3.4
(Duplicates, collisions and partial blocks)
Let all input and partition blocks hold two records, and let . Take
Partition by parity, using odd and even files. The left files contain and , requiring and blocks. The right files contain and , requiring and blocks. Thus , , . Assuming both left hash tables fit, key 1 produces two pairs, key 2 produces two, and key 4 produces one; key 3 has no match. The even partition also puts unequal keys 2 and 4 together, but equality checks reject cross-key pairs. Hence and the transfer count is . The two occurrences of 2 in are not collapsed.
Common mistake
(Treating a shared partition as a match)
In the even partition of the example, keys and share a partition, and they could share a table bucket too. Emitting every candidate in the bucket would add the cross-key pairs and , giving spurious pairs ( has one and one ; has two s and one ). Partition and bucket collisions only produce candidates; the final key-equality test is what makes the output correct.
Common mistake
(Collapsing duplicate occurrences)
Under bag semantics the two s in are distinct occurrences. Deduplicating before the join, or keeping one table entry per distinct key on the build side, gives in the example instead of . If set semantics is wanted, that is a different output contract and must be stated.
The count formula also applies when nothing matches; the edge case shows which terms survive.
Worked example 20.3.5
(An empty join with an empty partition)
Use the same block size and parity partitioning with and , so . The left odd file holds in one block and the left even file is empty; the right odd file is empty and the right even file holds in one block. Hence . The odd partition builds a table and probes nothing; the even partition builds an empty table and still reads its one block, finding no match. Thus , no output block is written, and the count is .
Memory must be budgeted for both passes, and the larger requirement decides.
Worked example 20.3.6
(Checking the memory budget)
Take partition buffers, and suppose the largest build table needs blocks. The partition pass needs blocks and the probe pass needs , so the budget must be at least blocks. With only blocks the partition pass still runs, but the largest partition cannot be joined by the stated second pass; it must be repartitioned or processed by another method before the count above applies. The figure also says nothing about a different input, whose largest table must be checked separately.
Counterexample mode
A small average partition does not imply a fit
Claim: if the average partition fits in memory, every partition does. Suppose has 100 occurrences of one key and the table can hold only 20. With ten partitions the average is ten occurrences, but all 100 must go to the same partition because equal keys hash together. Changing the key hash cannot split this group while preserving the simple algorithm. Likewise, a uniform-looking aggregate block count says nothing by itself about table overhead or the largest partition. The repaired hypothesis is the one in the contract: the largest build table fits.
What to do when assumptions fail
If a partition is too large, an implementation may repartition it using another function, provided it applies the same function to both sides. This can help when the excess consists of many different keys; it cannot split a single repeated key under key-only partitioning. Alternatively, process a partition with a block nested-loop method, or explicitly split a heavy key and replicate or rescan its partners. Those are different algorithms with extra transfers and memory contracts. Detect overflow before claiming the two-pass count, and include any failed attempt and subsequent work in measured costs.
Large output is a separate problem. If one key occurs times on the left and times on the right, it contributes pairs. No partition function can remove the need to produce those pairs when the requested result is materialized. Partitioning also makes no promise about ordering; a consumer requiring sorted output needs additional work. Input records, temporary partitions and output pairs may have different sizes, so count actual block totals rather than silently equating with .
Practice with solutions
Quick check
(Three left and four right occurrences share key . How many pairs does the join emit for ?)
Count ordered pairs of occurrences.
Solution · Answer
Each left occurrence pairs with every right occurrence, giving . Identical-looking records remain distinct occurrences.
Quick check
(Let , , , , and . All left partitions fit. Count transfers under the specified procedure.)
Add the input scans, the partition writes and reads, and the packed output.
Solution · Answer
The original reads cost , partition writes and reads cost , and packed output costs . The total is transfers.
Quick check
(With and , suppose is partitioned by for odd and for even , but by the reversed rule. What does the second pass output, and which hypothesis failed?)
Find the partition of each occurrence of .
Solution · Answer
The left goes to partition and the right to partition , so they are never in corresponding partitions and the output is empty, although the correct join has one pair. The correctness theorem requires the same partition function on both files; each function is deterministic, but equal keys across the two files no longer meet.