A query joining two tables runs in 8 milliseconds in staging and 40 seconds in production. Same query, same schema, same indexes. The plan is different, and specifically the join algorithm is different, because the planner estimated the row counts differently against different data.
There are three ways to join two sets of rows. Each is dramatically better than the others in the right circumstances and dramatically worse in the wrong ones, which is why join choice is where query performance most often falls off a cliff.
What changed in 2026
- Parallel hash joins became widespread. Distributing the build and probe phases across workers made hash joins viable on much larger inputs.
- Adaptive execution spread. Some engines now switch join strategy mid-query when actual row counts diverge from estimates, which limits the worst-case damage.
- Extended statistics got better support. Correlated columns — a common source of catastrophic underestimates — became easier to describe to the planner.
- Columnar engines changed the calculus. Vectorised execution over columnar storage favours hash joins strongly, which shifted defaults in analytical systems.
The three algorithms
Nested loop. For each row on the outer side, look up matching rows on the inner side. With an index on the inner join column, each lookup is fast. Cost is roughly outer rows × cost per lookup.
Brilliant when the outer side is small — a handful of rows, each doing an indexed lookup, is about as fast as a join gets. Catastrophic when the outer side is large, because you do that lookup a million times.
Hash join. Build a hash table from the smaller input, then scan the larger input once, probing the hash table for each row. Cost is roughly the sum of both inputs, not the product.
Excellent for large inputs and equality joins. Needs memory for the hash table — if it does not fit, the join spills to disk and gets substantially slower.
Merge join. Sort both inputs by the join key, then walk them in parallel like a zip. Cost is the sort plus one pass.
Excellent when both inputs are already sorted, typically because an index provides the order. When a sort is required it is often the worst option, since sorting is expensive.
|
Nested loop |
Hash join |
Merge join |
| Best when |
Outer side is tiny |
Large inputs, equality |
Inputs already sorted |
| Cost shape |
Product of sides |
Sum of sides |
Sort + one pass |
| Needs memory |
Little |
Hash table |
Sort space |
| Handles inequality |
Yes |
No |
Limited |
| Worst case |
Huge outer side |
Hash spills to disk |
Unnecessary sorts |
Bad estimates pick bad algorithms
Almost every disastrous join is a planner estimate that was wrong.
The classic case: the planner estimates a filter will produce 12 rows, so it picks a nested loop — 12 indexed lookups, trivially fast. The filter actually produces 400,000 rows, so the query does 400,000 lookups and takes minutes.
Note what happened. The planner did not choose badly given its information. Its information was wrong, and the algorithm it chose amplifies that error enormously — nested loop is the most sensitive to a row-count mistake because its cost scales with the product.
EXPLAIN ANALYZE shows both estimated and actual rows per node, and the diagnostic is finding where they diverge. A node estimating 12 and returning 400,000 explains the whole problem — see query planners for reading the output.
The usual causes: stale statistics after a bulk load, correlated columns the planner assumes are independent, and expressions it cannot see through.
Fixing it properly
Refresh statistics first. The most common cause and the cheapest fix. After significant data change, the planner is reasoning about a table that no longer exists.
Add extended statistics on correlated columns. When two filtered columns are related — city and postcode, status and type — the planner multiplies their selectivities and badly underestimates. Telling it they are correlated fixes the estimate at the source.
Check for a missing index. A hash join chosen because no index supports a nested loop may become a much better plan once the index exists — though verify, since a hash join over large inputs is often correct.
Give the hash join enough memory. A join spilling to disk is dramatically slower. If a hash join is the right plan and it is spilling, the working-memory setting is the lever.
Hints that force a join method should be a last resort. They pin a decision that was right for today's data and will be wrong when the distribution changes, and they hide the estimate problem rather than fixing it.
Common mistakes
- Reading only the top of a plan. The bad estimate is usually at a leaf.
- Using EXPLAIN without ANALYZE. No actual row counts, no way to see the divergence.
- Forcing join methods. Freezes a choice that data change will invalidate.
- Not refreshing statistics after bulk loads. The single most common trigger.
- Ignoring hash spills. A correct plan performing badly for a memory reason.
- Assuming nested loop is always bad. It is the fastest option for small outer sides.
- Testing on small data. Join choice at a thousand rows tells you nothing about a million.
FAQ
Why did my query get slow with no code change?
Data grew or shifted, the estimate changed, and the plan flipped to a different join algorithm. This is the single most common cause of sudden query regressions, and plan-change monitoring catches it before users do.
Does join order matter as much as algorithm?
Yes, and the planner chooses both together. Joining in an order that keeps intermediate results small matters enormously in multi-table queries — and it depends on the same row estimates.
Are joins slower than denormalising?
Not inherently; databases are built for this. Denormalisation trades read simplicity for write complexity and consistency risk, and it is worth reaching for only when a measured join is genuinely the bottleneck.
How does this work across shards?
Much worse, because rows must move between nodes. Distributed joins are dominated by data movement rather than algorithm, which is why partition key choice matters so much — see database sharding explained.
Where to go next
For reading plans and diagnosing estimates, read query planners. For the indexes join strategies depend on, database indexing explained, and for partial indexes that improve selectivity estimates, partial indexes.