How Does the Merge Join (Sort-Merge Join) Algorithm Work?
Learn how sort-merge join walks two sorted inputs with two pointers, when it beats hash join, and how it handles range predicates.
Expected Interview Answer
A merge join, also called a sort-merge join, works by taking two inputs that are already sorted on the join key (or sorting them first), then walking both sorted streams simultaneously with two pointers, advancing whichever pointer has the smaller key until matches align, which produces the joined output in a single linear pass.
Because both inputs are sorted on the join key, the algorithm never needs to jump back or rescan: it compares the current row of each side, advances the pointer with the lower key when they differ, and emits matched pairs (handling duplicate keys as small groups) when they are equal. This makes merge join extremely efficient when the inputs are already sorted, for example from an index on the join column, since no separate sort step or hash table build is needed. When inputs are not pre-sorted, the database must sort both sides first, which adds cost and can make a hash join cheaper instead.
- Linear-time join when both inputs are already sorted
- Low, predictable memory usage compared to hash join
- Naturally supports range and inequality join predicates
- Produces output already sorted on the join key, useful for further ORDER BY
AI Mentor Explanation
Imagine two officials each holding a stack of cards sorted by player squad number — one stack of team-sheet cards, one stack of fitness-report cards — and they walk down both stacks together, comparing the top card of each pile. Whichever pile shows the lower squad number is advanced one card, and when both top cards match the same number, that pairing is recorded before both piles move on. A merge join performs this exact two-pointer walk over two inputs that are already sorted by the join key.
Step-by-Step Explanation
Step 1
Ensure both inputs are sorted
Use an existing index on the join key, or sort both inputs explicitly before the join.
Step 2
Initialize two pointers
Start one cursor at the first row of each sorted input.
Step 3
Advance the lower key
Compare the current rows; move forward whichever pointer holds the smaller join-key value.
Step 4
Emit matches and continue
When both pointers reference equal keys, emit the joined rows (handling duplicate-key groups), then advance both and repeat until either input is exhausted.
What Interviewer Expects
- Clear description of the two-pointer walk over sorted inputs
- Awareness that pre-sorted inputs (e.g. via an index) make merge join cheap
- Recognition that unsorted inputs require an extra sort step
- Comparison with hash join on memory usage and predicate types supported
Common Mistakes
- Assuming merge join never requires any sorting
- Forgetting merge join can support inequality predicates, unlike hash join
- Confusing merge join with simple concatenation of two result sets
- Not mentioning that duplicate keys on either side require careful group handling
Best Answer (HR Friendly)
“A merge join lines up two tables that are already sorted by the join column and walks through both at the same time, like reading two sorted lists side by side. It moves forward in whichever list has the smaller value until the values match, then records that match and keeps going. It is fast and memory-light, but only works well when the inputs are already sorted or can be sorted cheaply.”
Code Example
SELECT e.emp_id, e.name, p.review_score
FROM Employees e
JOIN PerformanceReviews p
ON e.emp_id = p.emp_id
ORDER BY e.emp_id;
-- If Employees.emp_id is the primary key (already sorted)
-- and PerformanceReviews has an index on emp_id, the optimizer
-- can merge-join the two sorted streams in a single pass
-- instead of building a hash table or nested-loop scanning.Follow-up Questions
- When does a merge join outperform a hash join?
- How does merge join handle duplicate keys on one or both sides?
- Why can merge join support range join conditions but hash join cannot?
- What is the cost if the database must sort both inputs before merging?
MCQ Practice
1. What precondition makes a merge join especially cheap to execute?
If both inputs are already sorted (e.g. via an index), merge join avoids a separate sort step and runs in a single linear pass.
2. How does a merge join process its two sorted inputs?
Merge join uses a two-pointer technique, advancing the pointer on the smaller key until matching keys align.
3. Compared to hash join, merge join can additionally support which kind of predicate?
Because both sides are ordered, merge join can naturally handle range comparisons (e.g. <, >), unlike hash join which requires equality.
Flash Cards
What is another name for merge join? — Sort-merge join.
What precondition does merge join rely on? — Both inputs being sorted on the join key, either already or via an added sort step.
How does merge join advance through its inputs? — With two pointers, always moving the one pointing at the smaller join-key value.
What predicate type can merge join handle that hash join cannot? — Range and inequality join conditions, since both sides remain ordered.