Merge Join

Think of Merge Join like zipping up two already-sorted stacks of cards: it is fast because it walks forward only, not back and forth.

Question: What is a merge join in SQL, and when would a database choose it?

Answer: A merge join is a join algorithm that compares two inputs in sorted order on the join key. It moves through both sides like two bookmarks in a book: when keys match, it outputs the joined rows; when one side is smaller, it advances that side. Databases like it when the rows are already ordered, often because of an index, or when sorting the inputs is still cheaper than other join methods.

Interview-Ready Answer: I’d say a merge join is a join strategy that works on sorted inputs. The engine scans both sides in order, compares keys, and advances whichever side is behind; when the keys match, it emits the joined rows, including duplicate combinations. It’s especially strong when the data is already ordered by an index, because then the join itself is basically a linear walk instead of repeated lookups or hashing.

What a Merge Join Is

A merge join is a join algorithm that assumes both inputs are sorted by the join key, or can be made sorted cheaply. The key idea is simple: if both sides are in order, you never need to restart from the beginning of either table. You just keep moving forward.

How It Works Under the Hood

1. The database gets two inputs, such as customers and orders, both sorted on customer_id.
2. It reads the current row from each side and compares the join keys.
3. If the left key is smaller, the left pointer moves forward because that row cannot match any later right row.
4. If the right key is smaller, the right pointer moves forward for the same reason.
5. If the keys are equal, the engine outputs the joined row(s).
6. If either side has duplicates for that key, the engine must produce the full matching set. That means one left row may match many right rows, or the reverse, so it may buffer one run of equal keys while it walks the other side.
7. The process continues until one input is exhausted.

This is why merge join is often described as a linear scan after sorting. The join step itself is efficient because the pointers only move forward.

When and Why to Use It

• Great when inputs are already sorted: An index on the join key can provide that order for free, so the database skips a separate sort.
• Good for large, matching sets: If both tables are big and many rows qualify, merge join can beat nested loops because it avoids repeated probes.
• Useful for some outer joins: Many engines can also use merge join for left, right, or full outer joins, not only inner joins.
• Less attractive for tiny tables: If one side is small, nested loops may be simpler and faster.

Comparison With Other Join Strategies

Performance and Complexity

If the inputs are already ordered, the merge step is roughly O(n + m) comparisons, where n and m are the row counts on each side. That is the big win. If the database must sort first, total cost becomes O(n log n + m log m) for the sorts, plus the linear merge step.

Memory use is usually modest during the merge itself, but duplicate groups may need temporary buffering. The real danger is the sort: if the sort does not fit in memory, the engine can spill to disk and slow down a lot. In PostgreSQL, for example, sort memory is controlled by work_mem and the default is often around 4 MB, though that varies by version and setup. Once data spills, you may see temp files and much higher latency.

Important Edge Cases and Gotchas

• Equality is the common case: Merge join is mainly used for equality joins on ordered keys.
• NULLs do not match: In normal SQL joins, NULL = NULL is not true, so rows with null join keys do not match.
• Duplicates multiply rows: If both sides have repeated keys, the result is the full cross-product of those duplicates for that key.
• Order must be usable: A function on the join key, like LOWER(email), can block index order unless the engine has a matching expression index.
• Not always the fastest: A merge join can look elegant, but if sorting is expensive and a hash join fits in memory, hash join may win.

Memory Hook: Picture two people walking down parallel library aisles, each reading sorted book labels. They never go backward; they only step forward until the labels match.

Real-World Story

Imagine a checkout service in an e-commerce company that runs a nightly reconciliation job: it matches payments to orders by order_id. For months, the job finishes in under a minute because both tables have indexes on order_id, so the optimizer can use a merge join with ordered reads.

Then the business grows, the tables get much larger, and someone changes the report query so the join key is wrapped in a function. The index order is no longer usable, the database adds a sort before the merge, and the job jumps from 45 seconds to 18 minutes. Customers notice delayed refund emails, and operations sees temp file spikes and disk-heavy load. In the logs, the smoking gun is usually an execution plan with Sort nodes feeding a Merge Join, plus messages about external merge or temp disk usage.

What goes wrong: the team thinks “merge join is fast,” but the real issue is that the inputs were no longer naturally ordered. The result is not a slow join algorithm by itself; it is a slow sort plus join pipeline.

Follow-up & Tricky Questions:

• When would the optimizer prefer merge join over hash join? Usually when both inputs are already ordered, or when an index can provide that order cheaply. If sorting is expensive and the hash table would fit in memory, hash join may still be better.
• Do merge joins require indexes? No, but indexes often make them attractive because they can deliver rows in sorted order without an extra sort. Without indexes, the engine may still sort both sides first.
• How are duplicates handled? The engine must output every matching pair, so duplicate keys can create a small burst of many output rows. One equal-key group on the left may match many rows on the right, or vice versa.
• Can merge join support outer joins? Yes, many databases can use it for left, right, and full outer joins when the plan fits. The engine still walks in order, but it preserves unmatched rows on the outer side.
• What happens if the data is not sorted? The optimizer may add a sort before the merge join, which can dominate the cost. That is why the execution plan matters more than the join name alone.
• Does NULL ever match NULL in a merge join? Not with normal SQL equality semantics. If you need null-safe matching, you must use a dialect-specific operator or rewrite the logic carefully.
• Is merge join always linear time? Only the merge step is linear. If sorting is needed first, the full operation is no longer linear overall.
• Can a merge join be used for inequality joins? Classic merge join is mainly for equality joins; many interviewers expect that answer. Some systems have special planning tricks, but the standard mental model is equality on ordered keys.

Tricky: Is merge join automatically the fastest join because it is simple? No. Simplicity is not the same as speed; if the data must be sorted from scratch, a hash join may be faster, especially for large unsorted tables.

Tricky: If both sides are sorted, does the database still need to compare every row? Yes, it still compares keys as it walks forward. The win is that it never restarts a scan from the top.

Tricky: If a key is duplicated on both sides, does merge join collapse duplicates? No, it expands them. Matching duplicate groups produce all valid combinations for that key.

Common Mistakes:

• Thinking merge join always means “fast.” Correction: It is fast only when ordering is already available or cheap to create.
• Forgetting that NULLs do not match. Correction: Normal SQL join equality does not join null to null.
• Ignoring duplicate explosions. Correction: A duplicate key on both sides can produce many rows, not one.
• Talking about the algorithm without mentioning the plan. Correction: In interviews, always mention whether the data is sorted, indexed, or requires a sort first.

Memory Hook: “Two sorted lines, one forward walk.” If the labels are already in order, merge join just walks them like two people reading street numbers on the same road.

Cheat Sheet:

• Merge join works best on sorted join keys.
• The join step is linear after sorting: O(n + m).
• If sorting is needed, total cost rises to O(n log n + m log m).
• Index order can make merge join attractive without an explicit sort.
• Duplicates multiply rows; NULL does not match NULL.
• Always check the execution plan before calling it “fast.”

Practice Tasks:

• Write an inner join where one customer has two orders and verify that the output has two rows for that customer.
• Change the query to a left join and confirm that an unmatched customer still appears with nulls from the right side.
• Use EXPLAIN in your database and see whether the optimizer picks merge join, hash join, or nested loops for the same query.