Sort-merge join

Deep dive

How it works

In: two inputs R and S and a join condition (equality, range, band or as-of) · Out: matching pairs, in key order · State: the two sorted inputs and two cursors (plus a mark on the inner cursor for duplicates) · Cost: O(n log n + m log m) to sort, O(n + m + output) to merge; merge only if already sorted.

Sort R and S by key (in memory with radix sort or pdqsort; spill with external merge sort).
Cursors i, j at 0. While both are valid:
- R[i].k < S[j].k: advance i (galloping when the gap is large).
- R[i].k > S[j].k: advance j.
- equal: find the run ends i₂ and j₂ where the key changes, emit R[i..i₂] × S[j..j₂], then set i = i₂ and j = j₂.
Outer joins emit unmatched rows padded with NULLs as the cursor passes them.
Iterator-based engines without random access keep a mark on the inner cursor and restore to it for each duplicate of the outer key. PostgreSQL's Merge Join requires mark/restore from its inner input.

R: 1 3 3 5 8          S: 3 3 4 8 8 9
     └─┘ ×  └─┘  → 4 pairs for key 3          8 × (8,8) → 2 pairs

Code

/// Inner equi-join of two inputs sorted by key. Emits (left_row, right_row).
pub fn merge_join(l: &[(u64, u32)], r: &[(u64, u32)], out: &mut Vec<(u32, u32)>) {
    let (mut i, mut j) = (0, 0);
    while i < l.len() && j < r.len() {
        let (a, b) = (l[i].0, r[j].0);
        if a < b {
            i = gallop(l, i, b);
        } else if a > b {
            j = gallop(r, j, a);
        } else {
            let i2 = i + l[i..].partition_point(|x| x.0 == a); // end of the equal-key runs
            let j2 = j + r[j..].partition_point(|x| x.0 == a);
            for x in &l[i..i2] {
                for y in &r[j..j2] { out.push((x.1, y.1)); }
            }
            i = i2;
            j = j2;
        }
    }
}

/// First index > `from` whose key >= target; requires v[from].0 < target.
/// Exponential then binary search: O(log distance), so skipping a long stretch is cheap.
fn gallop(v: &[(u64, u32)], from: usize, target: u64) -> usize {
    let (mut lo, mut step) = (from, 1);
    while lo + step < v.len() && v[lo + step].0 < target {
        lo += step;
        step *= 2;
    }
    let hi = (lo + step + 1).min(v.len());
    lo + v[lo..hi].partition_point(|x| x.0 < target)
}

/// As-of join: for each left row (e.g. a trade), the last right row (e.g. a quote) with key <= its key.
pub fn asof_join(l: &[(u64, u32)], r: &[(u64, u32)], out: &mut Vec<(u32, Option<u32>)>) {
    let mut j = 0;
    for &(k, row) in l {
        while j < r.len() && r[j].0 <= k { j += 1; } // monotone: total work O(n + m)
        out.push((row, if j == 0 { None } else { Some(r[j - 1].1) }));
    }
}

Prepare inputs with v.sort_unstable_by_key(|x| x.0). For 64-bit integer keys, an LSD radix sort is usually 2-4× faster than a comparison sort.

Complexity and constants

Sort: comparison sorting is order of tens of ns per element for 10⁶-10⁸ 16-byte records. Radix sort reaches several hundred million keys/s per core. The sort dominates the merge by about 10×.
Merge: sequential reads at memory bandwidth. Order of 1 ns per input row plus output cost.
Galloping makes matching a short list against a long one cost O(m log(n/m)) instead of O(n + m).
External: run generation with replacement selection makes runs of about 2M on random input. One merge pass with fanout M/B handles TB-scale data in 2 passes.

Efficiency

Cost: the sort dominates the merge by about 10× (order of); comparison sorts cost tens of ns per element for 10⁶-10⁸ 16-byte records, radix sort several hundred million keys/s per core. The merge is sequential, order of 1 ns per input row plus output. External: replacement selection makes runs of about 2M; one merge pass handles TB-scale data in 2 passes. Bound: the sort (compute and memory bandwidth, or I/O when external).
Levers:
- skip the sort — index scans, clustered tables and upstream merges are already ordered; interesting orders also save GROUP BY/ORDER BY sorts — planner-tracked order
- sort (key, row id) pairs, radix sort for fixed-width keys, gather payloads after matching — less data moved — wide rows
- range-partition both inputs with the same sampled splitters — independent parallel merges — multi-core
- gallop — O(m log(n/m)) instead of O(n + m) — one side much smaller
- hash join instead — Balkesen et al. found tuned hash join still faster on unsorted input — equi-join with no ordering need
Naive → standard → state of the art:
- nested loop · O(n·m)
- sort both, merge · O(n log n + m log m), 2-pass external
- presorted inputs, radix sort, range-partitioned parallel merge · merge-only cost

Implementation notes

Normalized keys: encode multi-column or string keys into a binary-comparable prefix (big-endian, sign-flipped, collation-transformed), so the sort and the merge compare with memcmp or a few u64 comparisons.
Sort only (key, row id) pairs, not full rows. Gather the payload after matching (late materialization).
Parallel: range-partition both inputs with the same splitters (choose them from a sample), then merge-join each range independently. MPSM sorts locally and merges across partitions to avoid a global sort.
Interesting orders: a planner that tracks sort order can chain merge joins and a streaming GROUP BY without re-sorting.
Band joins (|a.t − b.t| ≤ δ): keep a sliding window of the inner side and drop rows that fall below outer − δ.

Pitfalls

Many-to-many joins on a common key produce n × m rows. In iterator engines with mark/restore, the inner run is re-read for every outer duplicate.
Sorting a huge side to join it with a tiny one: hash join wins by orders of magnitude.
Collation mismatch: both sides must sort with the same comparison and NULL ordering as the merge uses, or rows silently go unmatched.
Range-partitioning skew in parallel joins: one hot key lands in one partition. Split hot keys explicitly.
Galloping on near-equal streams adds overhead. Use linear steps first and gallop only after several misses in a row, as TimSort does.

Variants and alternatives

Hash jointhe default for unsorted equi-joins.

IEJoininequality joins with two predicates (a.x < b.x AND a.y > b.y), using sorted arrays and bit arrays.

Zig-zag joinintersect several sorted index scans by leapfrogging (CockroachDB, Datastore).

LSM compaction and k-way merges use the same merge loop over sorted runs.

In production

Databases: PostgreSQL Merge Join, SQL Server Merge Join, Oracle, DuckDB (piecewise merge join, IEJoin for inequalities, ASOF JOIN).
Data processing: Spark SortMergeJoin (the default for large equi-joins).
Time-series and dataframes: kdb+ aj, pandas merge_asof (as-of joins).

Implementations

name	lang	repo	install	verdict	licence	health	as_of	notes
DataFusion	Rust	apache/datafusion	`cargo add datafusion`	—	—	—	—	`SortMergeJoinExec` physical operator
itertools	Rust	rust-itertools/itertools	`cargo add itertools`	—	—	—	—	`merge_join_by` over two sorted iterators; a building block, not an engine
DuckDB	C++	duckdb/duckdb	`brew install duckdb`	—	—	—	—	piecewise merge join, IEJoin and ASOF joins for inequality predicates
Apache Spark	Scala	apache/spark	`pip install pyspark`	—	—	—	—	sort-merge join for large equi-joins (`spark.sql.join.preferSortMergeJoin`)

Sources

M. Blasgen, K. Eswaran, Storage and Access in Relational Data Bases, IBM Systems Journal, 1977. paper
G. Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys, 1993. paper
M.-C. Albutiu, A. Kemper, T. Neumann, Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems, VLDB, 2012. paper
C. Balkesen, G. Alonso, J. Teubner, M. T. Özsu, Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited, VLDB, 2013. paper
Z. Khayyat et al., Lightning Fast and Space Efficient Inequality Joins, VLDB, 2015. paper

Use when

Avoid when