In a sort-merge join, what has to happen when the join key has duplicate values on both sides, and why does that force the algorithm to re-read part of one input?

## Why duplicates break the simple sweep The textbook merge is: compare current keys, advance the smaller, emit on equal. That is correct only if equal keys never repeat on both sides at once. Relational joins operate on multisets: if key 7 appears three times on the left and four times on the right, the join must produce all twelve pairs. A cursor that advanced both sides on a match would produce three or four pairs, not twelve. ## Mark and restore The standard fix is a mark/restore protocol on the inner input. On reaching a matching key, the operator marks the position of the first inner row of that key group. It pairs the current outer row with every inner row of the group. When the group ends it takes the next outer row; if that row has the same key, it restores the inner cursor to the mark and replays the group. Only when the outer key changes does it release the mark and let the inner cursor move past the group. ## Cost implications For a key with L left rows and R right rows, the operator produces L times R output rows and reads the inner group L times. Summed over keys, the work is proportional to the output size, which is the honest framing: a many-to-many join is expensive because the answer is large, not because the algorithm is bad. What is genuinely lost is the clean one-pass property — the inner side must be re-readable. ## Re-readability and buffering Not every input can be rewound cheaply. An index scan can be repositioned; the output of an arbitrary pipeline generally cannot. Engines handle this by materialising or buffering the inner group, or inserting a spool operator between the child and the merge join. If a single key group is huge, that buffer can exceed memory and spill, so a skewed join key hurts merge join here just as it hurts hash join in the build phase. ## Skew is the practical failure mode One popular value — a default tenant, an unknown-customer sentinel row — with tens of thousands of rows on both sides produces hundreds of millions of pairs from a single key. Plans look fine on average statistics and then one value dominates runtime. The signal is a plan whose estimated rows are modest but whose actual output count is orders of magnitude higher, concentrated in one key. ## When rewinds disappear If the inner side is unique on the join key — joining to a dimension by primary key, or any foreign-key join into the parent — each group has exactly one inner row, so a match consumes it and the sweep stays one pass. Optimizers learn the uniqueness from constraints and index metadata and cost the join accordingly, which is one reason declaring uniqueness improves plan quality rather than being mere documentation. ## Related subtlety: NULLs Under standard equality semantics NULL keys match nothing, so rows with NULL join keys sort together at one end and are skipped by the merge without producing pairs. They still cost the sort, which is a reason to filter them earlier when they are numerous.