Hash join versus sort-merge join

WHAT THIS TESTS The interviewer probes nuanced selection between the two big join algorithms based on memory, sortedness, and predicate type.

A GOOD ANSWER COVERS A hash join works only for equality joins. It builds an in-memory hash table on the smaller input keyed on the join column, then probes it with each row of the larger input. It is very fast when the build side fits in memory, with roughly linear cost, but it degrades when memory is insufficient and it must partition and spill to disk, and it cannot handle inequality or range predicates. A sort-merge join sorts both inputs on the join key, then advances two pointers through the sorted streams emitting matches in a single merge pass. Its cost is dominated by sorting, but it shines in several cases: when one or both inputs are already sorted, for example coming off a B-Tree index in key order, the sort is cheap or free; when inputs are enormous, since external sort handles data larger than memory more gracefully than hash spilling; when the join involves a non-equality condition that hashing cannot express; and when the query also needs the output sorted, since the merge already produces ordered rows. Prefer hash join for unsorted equality joins with adequate memory; prefer sort-merge for pre-sorted inputs, very large or skewed data, non-equality joins, or when ordered output is required downstream.

COMMON WRONG ANSWERS Using a hash join for range or inequality joins, which it cannot do. Forgetting hash join spills under memory pressure. Ignoring that sort-merge can reuse index ordering or feed an ORDER BY for free. Claiming one is universally faster.

LIKELY FOLLOW-UPS What happens when a hash join exceeds memory; how does index ordering make sort-merge cheap; which handles data skew better; can sort-merge do inequality joins.

ONE CONCRETE EXAMPLE Joining two large tables both already clustered by customer_id favors a sort-merge join: the inputs arrive sorted, so it merges directly with no sort cost and yields output ordered by customer_id for a following ORDER BY. If instead the join is on an unsorted, unindexed key and the smaller side fits in RAM, a hash join is faster because it avoids sorting altogether.