Join Algorithms: Sort-Merge

A sort-merge join (also called merge join) evaluates an equi-join $r \bowtie_{r.A = s.B} s$ by first sorting both $r$ and $s$ on their join attributes $A$ and $B$, and then scanning both sorted relations exactly once in a coordinated fashion, emitting output tuples wherever the join attributes agree. The technique depends on a simple ordering fact: if $r$ and $s$ are both sorted on the join attribute, all tuples of $r$ and $s$ with a given join value $v$ occupy contiguous blocks of sorted position, so a two-pointer merge (as in classic merge sort) can locate every matching group without random access or repeated re-scanning of one whole relation per row of the other. When a relation does not already fit in main memory, "sorting it" is not a single in-memory operation — it requires external sorting, specifically the external merge sort algorithm. External sort has two phases: a run-generation phase, which reads the relation in memory-sized chunks, sorts each chunk internally, and writes it back as a sorted run; and a merge phase, which repeatedly merges groups of runs into longer sorted runs until one fully sorted run remains. The number of runs mergeable at once is bounded by the number of available memory buffer pages, which is why the merge phase may require several passes for very large relations. The join proper — the merge step — walks pointers over the two now-sorted relations. At each point it compares the current join-key values; if they differ, the pointer on the smaller side advances; if they are equal, the algorithm must handle the possibility of duplicate keys: a whole group of tuples on each side sharing that key value must be cross-matched, which requires temporarily "pinning" and possibly rewinding one side. This duplicate-handling detail is the single subtlety that separates a correct sort-merge join from a naive two-pointer scan that silently drops matches.

Phase 1 — External sort of both relations. Each relation is sorted on its join attribute using external merge sort, described below as two sub-stages. Run generation. With $M$ buffer pages available in memory, read $M$ pages of the relation at a time, sort them internally (e.g., quicksort or heapsort, $O(M \log M)$ per chunk), and write the sorted chunk to disk as one run. A relation of $b$ blocks yields $\lceil b/M \rceil$ initial sorted runs, each of length $\le M$ blocks. Merge passes. Runs are merged in groups. With $M$ buffer pages, $M-1$ can serve as input buffers (one page per input run being merged) and 1 page serves as the output buffer, so up to $M-1$ runs are merged at a time into one longer run. This halves — more precisely, divides by $M-1$ — the number of runs each pass. Passes repeat until a single run remains.

Phase 2 — Merge join. Once $r$ and $s$ are each a single sorted stream (on disk or effectively so), scan both with a coordinated merge, matching equal join-key groups and emitting the Cartesian product of each matching group. ``` // PART A: External Merge Sort (produces relation R sorted on attribute A) function EXTERNAL-SORT(relation R, join-attribute A, memory-pages M): runs := [] // --- Run generation --- for each chunk C of up to M pages read from R: load C into memory sort C in-memory by A // O(M log M) comparisons write sorted C to disk as a new run runs.append(run) // --- Merge passes --- while length(runs) > 1: new_runs := [] for each group G of up to (M - 1) runs from runs: new_run := MERGE-RUNS(G, A) // (M-1)-way merge, 1 output buffer new_runs.append(new_run) runs := new_runs return runs[0] // the single, fully sorted run

function MERGE-RUNS(runs G, attribute A): open one input buffer per run in G, load first page of each output_run := empty while any run in G has unread tuples: t := tuple with smallest A-value among current buffer heads append t to output_run (flush output buffer to disk when full) advance the pointer of the run t came from if that run's current buffer page is exhausted: load its next page (if any remain) return output_run

// PART B: Merge Join (R and S each sorted on join attribute) function MERGE-JOIN(R_sorted, S_sorted, attribute A, attribute B): result := empty r := first tuple of R_sorted s := first tuple of S_sorted while r != end-of-R and s != end-of-S: if r.A < s.B: r := next tuple of R_sorted else if r.A > s.B: s := next tuple of S_sorted else: // r.A == s.B : matching group begins. // Mark the start of S's matching group so it can be rewound // for every tuple in R's matching group with the same key. s_group_start := s while r != end-of-R and r.A == s.B: s := s_group_start while s != end-of-S and r.A == s.B: result.append(r joined with s) s := next tuple of S_sorted r := next tuple of R_sorted // s now points just past S's matching group; loop continues normally return result ``` The nested rewind (`s := s_group_start`) is the crux of correct duplicate handling: it is exactly analogous to the two-pointer technique used for computing intersections of sorted lists, but generalized to groups rather than single elements, so no matching pair is missed when either side repeats the join key.

External sort cost. Let $b$ be the number of blocks in a relation and $M$ the number of memory buffer pages available.

• Run generation reads and writes every block once: $2b$ block transfers, producing $\lceil b/M \rceil$ initial runs.
• Each merge pass also reads and writes every block once: $2b$ transfers per pass. A pass merges groups of up to $M - 1$ runs at a time, so the number of runs shrinks by a factor of $M-1$ each pass. Starting from $\lceil b/M \rceil$ runs, the number of passes needed to reach $1$ run is

• Total transfers for sorting one relation:

Merge-join cost. Once both relations are sorted, the merge phase reads each relation's sorted representation exactly once more (one additional pass each, since the final merge pass of the sort can be pipelined directly into the join without writing the fully sorted result back to disk — an important practical optimization). In the worst case (no pipelining), this adds $b_r + b_s$ transfers. Total:

This is near-linear in the relation sizes, in sharp contrast to block nested-loop join's $O(b_r \cdot b_s / M)$ when no index or sorted order is available. For very large $b_r, b_s$ relative to $M$, sort-merge is asymptotically far superior; the crossover point in practice depends on $M$, since $\log_M b$ shrinks quickly as $M$ grows (larger memory buffers mean fewer, wider merge passes).

Special case — one merge pass suffices. If $b/M \le M - 1$ (equivalently $b \le M(M-1) \approx M^2$), the entire relation can be sorted with a single run-generation pass followed by a single merge pass: two passes total, cost $4b$. This is the common case for moderately sized relations and a large buffer pool, and it is why sort-merge is often described loosely as "$O(b)$" in practical settings even though the general bound is $O(b\log_M b)$.

Correctness of run generation. Each chunk of $\le M$ blocks fits entirely in memory, so an in-memory comparison sort correctly totally-orders it; concatenating disjoint sorted chunks as separate runs preserves sortedness within each run (not across runs), which is exactly the precondition the merge phase requires.

Correctness of the $(M-1)$-way merge. By induction on the number of tuples emitted: at each step the algorithm outputs the globally smallest not-yet-output tuple among all input runs, because each run is internally sorted, so the smallest remaining tuple overall must be at the current head of some run. Maintaining one buffer pointer per run and always emitting the minimum head is therefore a correct merge, and repeating this until all runs are exhausted produces one sorted run containing all input tuples exactly once.

Correctness of the merge-join with duplicates. The invariant maintained by `MERGE-JOIN` is: at the top of the outer loop, every tuple pair $(r', s')$ with $r'.A = s'.B$ and $(r', s')$ preceding the current position in sort order has already been emitted, and none has been emitted twice. The group-rewind step is what preserves this invariant when the join key repeats: without rewinding $s$ back to `s_group_start` for each new $r$ in the matching group, only the first $r$-tuple in the group would be matched against all $s$-tuples in the group, silently losing $(|R\text{-group}| - 1) \times |S\text{-group}|$ result rows. The nested loop guarantees every pair within the matching groups is visited exactly once, giving the full cross product of the two groups, which is precisely the correct join semantics for that key value.

Space. External sort needs $O(M)$ memory (a constant number of buffer pages), independent of $b$ — the entire point of an external algorithm. The merge-join phase needs only a few buffer pages beyond the sorted inputs, plus enough space to buffer one matching group of the inner relation for the rewind, which costs $O(g)$ extra buffer pages where $g$ is the number of blocks spanned by the largest duplicate group (usually small, but adversarial data with a hugely repeated key can force this buffer to spill to disk too).

Tradeoffs. Sort-merge pays sorting cost up front regardless of how selective the join actually is; a highly selective join might be faster with an index nested-loop join that avoids touching most of the outer relation. Sort-merge shines precisely when no useful index exists, both relations are large, and the join is not highly selective — or when the relations are already sorted (e.g., a clustering index on the join column), in which case sort-merge degenerates to a nearly free linear merge.

Join `R(A)` with `S(B)` where `R` has 8 blocks and `S` has 5 blocks, and the buffer pool has $M = 3$ pages.

Sorting R (8 blocks, M = 3):

Total for sorting R: $16 + 16 + 16 = 48$ block transfers, matching $2b(1 + \lceil \log_2(8/3)\rceil) = 2(8)(1+2)=48$.

Sorting S (5 blocks, M = 3):

Total for sorting S: $20$ transfers.

Merge-join phase: one additional linear pass over each sorted relation (assuming the sorted runs are materialized on disk rather than pipelined): $8 + 5 = 13$ transfers.

Grand total: $48 + 20 + 13 = 81$ block transfers. Compare to block nested-loop join with the same $M=3$ (2 buffer pages for the outer relation's blocks per pass, 1 reserved for the inner scan — using the smaller relation S as outer): roughly

At this tiny scale, nested-loop actually wins because $M$ is too small for sort-merge's per-relation-size logarithm to pay off — a reminder that asymptotic superiority ($O(b\log_M b)$ vs. $O(b_r b_s/M)$) only dominates once relations are large relative to $M$. Re-running the comparison at $b_r = 8000$, $b_s=5000$, $M=100$ makes sort-merge's advantage overwhelming, since nested-loop's cost grows with the product of relation sizes while sort-merge's grows with their sum times a small logarithm.

Tracing the merge step itself on small sorted data, $R.A = [10, 20, 20, 30, 45]$, $S.B = [15, 20, 20, 20, 50]$:

Result: $2 \times 3 = 6$ joined tuples on key 20, correctly capturing the full cross product of R's two 20's and S's three 20's — exactly the count a naive single-pointer merge (without rewinding) would have missed, producing only 3 instead of 6.

External sorting and merge-based algorithms predate relational databases entirely — they originate in the era of magnetic tape processing, when "memory" meant a handful of kilobytes and data lived on sequential tape reels that made random access essentially impossible. The technique of producing sorted runs and merging them in passes was the standard way to sort files far larger than any machine's core memory, and it was formalized and popularized in the classic literature on sorting and searching.

The join algorithm itself emerged as relational database systems matured in the 1970s and needed efficient equi-join evaluation without assuming indexes existed on every join column. Sort-merge join was one of the earliest join strategies implemented in production relational engines, alongside nested-loop join, and its cost model became a foundational component of early cost-based query optimizers.

Sort-merge join is a workhorse operator in essentially every mature relational database engine — PostgreSQL, Oracle, DB2, SQL Server — selected by the optimizer whenever both join inputs are large, no efficient index supports an index nested-loop join, and at least one input is already sorted or cheaply sortable (for instance, following an `ORDER BY`, a merge-friendly index scan, or a prior sort-based operator in the same plan). It is also the natural join strategy after a `GROUP BY`-then-sort or a range partition, since the sort has effectively already been paid for. In distributed and big-data engines — Apache Spark SQL, Hive, Presto/Trino — sort-merge join is the default strategy for large "shuffle joins": both tables are hash-partitioned by join key across worker machines, each partition is sorted locally, and a merge join runs within each partition, avoiding the memory blow-up that a distributed hash join would otherwise risk on skewed or oversized partitions. The same external-sort machinery underlies `ORDER BY` execution, `GROUP BY` aggregation via sorting, duplicate elimination in `DISTINCT`, and bulk index construction, making external merge sort one of the most reused primitives in the entire query execution engine. Understanding sort-merge join's cost model is also a direct prerequisite for reasoning about The Query Optimizer's decisions, since the optimizer must estimate and compare exactly the $O(b\log_M b)$ costs derived here against the alternative costs of Join Algorithms: Nested-Loop and hash-based joins before committing to a physical execution plan.

Ask the tutor: How does a query optimizer decide between sort-merge join, hash join, and nested-loop join for a specific query plan?