Why a matching key is not the end of the work
Two sorted files can be scanned together: if the current keys differ, the smaller one cannot match any later occurrence in the other file. When the keys agree, however, advancing both cursors once is unsafe. A key appearing three times on one side and twice on the other contributes six occurrence pairs. A group can be larger than memory, so even a correct in-memory cross product is not a complete external algorithm.
We develop one explicit, deliberately simple algorithm. Its output is fixed by the following definition.
Definition 20.2.1
(Bag equijoin of sorted files)
Let and be finite files whose records carry keys from a totally ordered set, with the order consistent with equality, and let both files be sorted in ascending key order. A record at a given position of a file is an occurrence; distinct positions are distinct occurrences even if their records look identical. Null keys are excluded and comparison is exact. The bag equijoin of and is the collection of all ordered pairs of an occurrence of and an occurrence of whose keys are equal, each such pair counted once, and no other pairs. Output order is unspecified.
If a key occurs times in and times in , it therefore contributes exactly pairs, and a key present in only one file contributes none.
The storage model and algorithm
Let and occupy and input blocks. Each block holds records and each block holds records; the final input block may be partially filled. A sequential input scan reads each occupied block exactly once. A read or write of one block is one transfer. A temporary group block holds records; a temporary group block holds records. A pair-output block holds pairs. Temporary groups and the final output are packed, and a nonempty partial last block is written once. Empty files require no block transfer. Readers use valid-record counts for partial input and temporary blocks.
Reserve enough memory simultaneously for the current block of each input, two temporary-group write buffers, temporary group blocks, one temporary group input block, and one output buffer. Buffer sizes may differ; small descriptors and comparisons are outside the accounting. Input blocks, including the first lookahead record of a later key, remain resident while a matched group is processed. The output buffer remains resident across groups. Temporary files are fresh and have no cached blocks on reread; deleting them is free in this model. No seek, comparison, allocation, failure, or latency cost is counted.
At all times the two cursors point to the next unconsumed records. Run the following procedure:
- If either input ends, drain the other input without emitting pairs and then go to step 4. Otherwise compare the current keys. If one is smaller, consume its entire equal-key group and compare again.
- If both keys equal , copy the complete group from each input, preserving occurrences, to separate packed temporary files and . Keep each first subsequent record as lookahead. Flush each nonempty group's final partial temporary block.
- Read the temporary file in consecutive chunks of at most blocks. For every chunk, scan all temporary blocks once and emit the pair of every resident occurrence and every occurrence. Flush full pair-output blocks, but retain a partial block for the next group. Delete the two temporary files after processing the group, then resume step 1.
- After both inputs have been drained, flush the pair-output buffer if nonempty.
The draining rule makes the cost below exact even if one file reaches its end early. An implementation may stop instead, but then its actual base-scan cost depends on how far the other cursor has traveled.
Theorem 20.2.2
(Correctness and exact transfers)
For every common key , let be its occurrence counts, and . Put . The algorithm emits precisely the bag equijoin and performs exactly
transfers. The sum is zero if no key is common; the output term is zero if .
Proof
(Partition by key, then by chunk, and count each transfer once)
If the current key is smaller than the current key, every remaining key is at least the latter; therefore the smaller group has no match in the remaining file. It also cannot match an already consumed group: any such match would have been handled when that key was current, since neither cursor skips a possible matching group. The same argument applies with the files exchanged. Thus skipping a smaller group loses no pair. When the keys agree, sortedness makes each complete group contiguous, and copying retains every occurrence exactly once. Every occurrence lies in exactly one temporary chunk; the full scan for that chunk visits every occurrence once. Consequently each pair for is emitted exactly once. No pair for unequal keys is emitted. The argument applies to each common key, including duplicate records.
The two complete input scans cost . For key , packing the temporary groups writes blocks. Reading all left chunks costs ; the chunks each cause reads of the right group. Across groups the output buffer is never prematurely flushed, so pairs require exactly writes. These disjoint reads and writes give the expression. It is the cost of this specified implementation, not a lower bound or a claim that every merge join must materialize both groups.
Proof X-ray
Two partitions and three accounting conventions
The correctness half rests on two partitions. Sortedness partitions all matching pairs by their common key, and it is used at exactly one point: when the current keys differ, every later key of the other file is at least as large, so the smaller group can be discarded. Without sortedness that discard is unjustified and pairs are lost. For a fixed key, the chunks partition the left occurrences, and each chunk meets one complete scan of the right group; hence a pair is produced for exactly one chunk and exactly one right block. The cost half is an exact count only because of three conventions in the model. The draining rule makes the base scan exactly , whatever file ends first. The resident lookahead record means that no input block is read twice when a group boundary falls inside a block. Retaining the partial output block across groups replaces a sum of per-group ceilings by the single ceiling . Removing any one of these conventions leaves correctness intact but turns the formula into an inequality.
The first example checks every term of the formula on a small file in which one group needs two chunks.
Worked example 20.2.3
(One group exceeds the chunk budget)
Let , , and input blocks be
Thus , . Key 1 has and ; key 2 has and . Key 4 has no partner. The pair count is . For key 1, temporary writes cost and rereads cost . For key 2 those costs are and . Four output blocks contain seven pairs. Including five input reads, the total is transfers. Although key 1 spans input and temporary block boundaries, all six of its occurrence pairs are present.
Concept lensGeometric
Each matched group as a grid of block pairs
For a matched key , picture the grid whose cell holds the pairs between temporary block of and block of ; every pair for lies in exactly one cell. Step 3 covers the grid by horizontal strips of at most rows. Each strip is read once, reads in all, and each of the strips sweeps all columns. Within a group the procedure is thus a block nested-loop join, and is the cost of this tiling. Above, key 1 gives a grid cut into two strips.
Worked example 20.2.4
(Edge case: no common key)
Let and let the input blocks be
so and . The cursors compare (consume the group of ), (consume ), (consume ), (consume ) and (consume ). Now has ended, so step 1 drains the rest of , namely the records , which completes the reading of without emitting a pair. No key is common, so the sum over matched groups is empty and ; step 4 finds the output buffer empty and writes nothing. The formula gives , which is exactly the five block reads of the two sequential scans. Without the draining rule an implementation could stop after reading two blocks of , so its count would depend on the data rather than on .
Worked example 20.2.5
(Many small groups: the price of spooling)
Let , , and
Then , and each of the keys has , hence and . Each key costs temporary writes and temporary reads, so the three groups cost transfers. The output has pairs, which fit in a single output block. The total is . An implementation that joins such one-record groups in memory would use only the input reads and output write. Spooling is what makes the procedure correct for groups of any size, but on many tiny groups it multiplies the cost several times over.
The counterexample below shows why the second step copies complete groups instead of advancing the cursors pair by pair.
Counterexample mode
Advancing both cursors loses pairs
For and , advancing both cursors after every match can output only and . The bag join instead has six pairs, including and . Treating repeated values as one key also loses multiplicity.
Interpreting and comparing the cost
The formula starts with already sorted, materialized files. If sorting is needed, add the actual transfers of the specified external sorts, including their final writes; do not count the same read twice. If a sorter pipelines its final merge directly into this join, the model and count must be changed. Similarly, a consumer that streams output instead of writing it removes the stated output-write term only if its own costs are accounted for separately.
Spooling every matching group makes the method straightforward, but can be wasteful for small groups. A different implementation could keep a group in memory, reverse which group is chunked, or exploit a rewindable sorted input. Such choices change memory assumptions and transfer counts. In particular, sorting does not guarantee a linear join cost when a duplicate group requires repeated scans, and the materialized output itself can be quadratic in the frequencies. No elapsed-time or universal optimality conclusion follows from a block count.
Common mistakes
Common mistake
(Summing a ceiling per group for the output)
Writing the output cost as assumes that the output buffer is flushed after every group. In the algorithm above the partial output block is kept for the next group, so the cost is the single term . With two common keys that each give one pair and , the per-group sum is , while the algorithm writes one block.
Common mistake
(Counting the input blocks a group spans instead of its packed size)
The terms and count blocks of the packed temporary files, not the input blocks that the group happens to touch. In with , the two occurrences of key straddle two input blocks, but they fill only temporary block. Using the span would overstate both the temporary writes and every reread of the group.
Practice with solutions
Exercise 20.2.6
(With , , , and , suppose the only common key has and . Find the exact number of transfers.)
Core
Solution(3)
- 1
Compute the packed group sizes and the number of chunks
, , , and there are left chunks.
- 2
Count the temporary transfers
Temporary writes cost ; rereads cost .
- 3
Add the base scans and the output
The output costs and the input scans , so the total is transfers.
Quick check
(Two common keys each produce one pair and . Why must the output buffer be retained across groups for the theorem to be exact?)
Compare the number of output blocks written with and without a flush after each group.
Solution · Answer
The two pairs share one output block, which the theorem counts as write. Flushing after each group would write two partially filled blocks, so the one-write output count would no longer be exact.
Quick check
(The sorted inputs have key counts and . Find and identify the skipped groups.)
Only keys present in both files contribute.
Solution · Answer
The common keys are and , so . Key is skipped from and key from ; neither has a partner. Equal values at different positions still contribute separate pairs.
Quick check
(For one matched group with , and , how many temporary reads does the stated orientation use? What if the files exchange roles and the same two-block chunk capacity is available for the new outer group?)
Apply with the roles of and exchanged.
Solution · Answer
The stated orientation reads blocks. Reversing roles reads . Temporary writes and output writes are unchanged. This comparison requires a memory budget that supports either orientation; it does not prove the reverse orientation is always better.