Join Algorithms

Reading Query Execution Plans listed Hash Join, Nested Loop, and Merge Join as node types without explaining what distinguishes them. All three implement the same SQL join and return exactly the same rows for the same query — the difference is entirely in how much work each does to get there.

Nested loop join: simple, and sometimes exactly right#

For every row in one input (the outer table), scan the other (the inner table) looking for matches:

for each row in orders:    for each row in customers:        if orders.customer_id == customers.id:            emit joined row

Without an index, this costs roughly rows(orders) × rows(customers) — prohibitive at scale. With an index on customers.id, the inner loop becomes an index lookup instead of a full scan, and the cost drops to roughly rows(orders) × log(rows(customers)) — which is exactly why a nested loop join is often the correct choice when the outer input is small and the inner one is indexed on the join key, rather than a naive algorithm to be avoided.

Hash join: built for large, unindexed equi-joins#

Build a hash table from the smaller input's join key (the build side), then scan the larger input (the probe side), looking each row up in the hash table:

build_table = hash_table(customers, key=id)     # smaller inputfor each row in orders:                          # larger input    matches = build_table.lookup(row.customer_id)    emit joined rows

This costs roughly rows(orders) + rows(customers) — no index required on either side — at the price of needing enough memory to hold the build side's hash table. A hash join is the usual choice for a large equi-join (a.key = b.key, not an inequality) between two tables where a suitable index does not already exist.

Sort-merge join: cheap when both sides are already sorted#

Sort both inputs by the join key, then advance through both simultaneously like merging two sorted lists:

sorted_orders    = orders sorted by customer_idsorted_customers = customers sorted by id
advance through both lists together, matching customer_id == idas each pointer moves forward

If both inputs are already sorted — because each has an index whose sort order matches the join key, for instance — this join costs almost nothing extra beyond the merge itself. If neither is sorted, the sort step itself can be expensive enough that a hash join wins instead; the optimizer weighs this trade-off using the cost estimates covered next.

Why join order matters more than which algorithm#

With three or more tables, the order joins happen in changes how large each intermediate result is — joining the two smallest, most selective tables first, then joining the (already filtered-down) result against a third large table, can be dramatically cheaper than the reverse order, even using the identical set of join algorithms throughout. Cost-Based Optimization covers how the optimizer searches through possible join orders to find a cheap one — and why that search itself becomes expensive as the number of tables grows.

Common mistakes#

Assuming the join algorithm doesn't affect correctness#

It doesn't — all three return identical rows for the same query. The mistake is assuming that means the choice doesn't matter; it changes cost by orders of magnitude without changing the result at all.

Filtering after joining instead of before#

Joining two full, unfiltered tables and applying a WHERE clause afterward forces the join to process every row from both sides, even ones that could have been filtered out first. Most optimizers push filters down below the join automatically when possible — but a filter expressed in a way that defeats predicate pushdown (a wrapped column, a non-deterministic function) can silently prevent that from happening.

Manually forcing a join algorithm without evidence#

Some databases allow hinting a specific join algorithm. Doing so based on intuition rather than an actual EXPLAIN ANALYZE comparison risks locking in a worse plan than the one the optimizer would have chosen — hints are a tool for a confirmed, measured problem, not a default habit.

Further reading#

• Hash join, Nested loop join, and Sort-merge join — full descriptions of all three algorithms.
• Join (relational algebra) — the operation every one of these algorithms implements.
• Reading Query Execution Plans — how to identify which algorithm a real query actually used.

See also#