skip to content

How does a sort-merge join algorithm produce its result, and what must be true of its two inputs before the merge step can begin?

level: middleimportance: must knowfreq 62%

answer

  1. two cursors, advance the smaller key
  2. merge phase of merge sort
  3. sort cost dominates, merge is linear
  4. output arrives sorted — reusable order
  5. same collation and leading key order

basics

~20 s

Both inputs must arrive sorted on the join key. Two cursors then walk them once in parallel: advance whichever side holds the smaller key, and emit rows when the keys are equal. One pass over each input; the expensive part is getting the inputs sorted.

solid answer

~50 s

A merge join requires both inputs ordered on the join key under the same ordering rules. It keeps a cursor on each side and compares the current keys: smaller left key advances left, smaller right key advances right, equal keys emit the matching rows and step past that key group. Each input is read exactly once, so the merge itself is linear in the input sizes and needs almost no memory — no hash table. The cost lives almost entirely in producing the order. An explicit sort is O(N log N) and can spill to temp storage on large inputs; scanning an index whose leading columns match the join key gives the same order for free. A useful side effect: the output is itself sorted on the join key, so a downstream ORDER BY, grouping, or another merge join can reuse the order.

code

text · 3 lines
text
Merge Join  (join key: o.customer_id = c.id)
  ->  Index Scan on orders_customer_id_idx   (ordered by customer_id)
  ->  Index Scan on customers_pkey           (ordered by id)

go deeper

for a junior

Recall the picture: both sides sorted, two pointers, move the one that is behind, emit on equal keys.

for a middle

State the precondition precisely and separate merge cost from sort cost; mention that sorted output is a byproduct.

for a senior

Talk about where the sorts come from, spill behaviour, collation and leading-key agreement, and how the produced ordering feeds later operators.

for a principal

Frame it as the cost of establishing an ordering the whole plan can amortise — clustering and index design decide whether merge join is nearly free or a pair of external sorts.

## The operator A join operator takes two row streams and returns the pairs satisfying a join predicate. The sort-merge join is one of the three classical physical join algorithms, next to nested loop and hash join. Its defining precondition: both inputs arrive sorted on the join key. Given that, every match is found in one coordinated pass, exactly like the merge phase of merge sort. ## Algorithm Keep a cursor on each side. Compare the two current keys. If the left key is smaller, advance left — that row can never match anything further right, because the right stream only grows. If the right key is smaller, advance right. If they are equal, the matching group has been found: emit the pairs and advance past the group. Stop when either side runs out. Each row is visited once, so the merge is O(N+M) comparisons with O(1) working memory, apart from duplicate handling. ## Where the cost really is The merge is cheap; sorting is not. Sorting each side costs O(N log N) CPU, and when an input exceeds the memory the sort is given, it becomes an external sort: runs are written to temporary storage and merged back, adding full writes and reads of the data. So the honest cost model is sort(left) + sort(right) + one linear pass. The algorithm becomes attractive exactly when one or both sorts can be skipped because an access path already delivers sorted rows. ## Preconditions that actually bite The two orders must agree: same key columns in the same leading positions, same direction, same collation or comparison semantics. A multi-column join needs both sides sorted on the join columns as the leading prefix. Classic merge join handles equality predicates; extra non-equality conditions are usually applied as a filter on the matched rows rather than driving the merge. ## Memory and robustness Unlike hash join, merge join has no build side to hold in memory and no sensitivity to hash collisions or key skew in the hash function. Its memory profile is that of a sort, which degrades predictably: more data means more merge passes and sequential I/O, not a sudden fallback path. That predictability is a real operational advantage on large inputs. ## The free ordering Because the merge consumes sorted inputs, its output is sorted on the join key. Optimizers track such orderings and will sometimes choose a merge join specifically because a later operator wants that order, avoiding a second sort. This is why a merge join can win on total plan cost even when it loses on the join alone. ## Typical shape in a plan A merge join node has two children that either are sort nodes or are ordered scans of an index. Sorts on both sides hint that a hash join may have been cheaper; ordered index scans on both sides are the case where merge join shines.

  • What is the memory footprint of a merge join compared with a hash join?
    A hash join must hold the build side, or a partition of it, in memory and spills to disk when it does not fit. A merge join holds only the current key group during the merge, so its steady-state memory is tiny; any large memory demand comes from the sorts feeding it, and those degrade gracefully into external sorts with sequential I/O.
  • Why can a merge join be chosen even when it looks more expensive than the alternatives in isolation?
    Because it produces output sorted on the join key. If the query also needs that order for a later ORDER BY, grouping, or another merge join, the optimizer can drop a separate sort, so the total plan cost wins even though the join node alone is pricier.

Two alphabetised guest lists compared side by side: you run a finger down each, always moving the finger that is behind, and note every name that appears on both. One pass, nothing to hold.

saying these in an interview costs you the question

  • Saying a merge join sorts the data itself as part of the join — sorting is a separate step or comes from an ordered access path
  • Claiming the merge step is O(N log N) — the merge is linear, only the sorts are log-linear
  • Thinking merge join needs the whole input in memory like a hash build side
  • Assuming any index scan gives usable order — the index leading columns must match the join key and the scan must preserve order

context

resolving links…