When the Join Strategy Is the Bottleneck
Nested loop, hash join and merge join are each optimal somewhere and catastrophic elsewhere. The planner picks one from a row estimate, so a wrong estimate does not make the query slightly slower — it makes the engine choose an algorithm built for a different problem size.
Frame the diagnosis
Performance work starts from a symptom and a signal — never from a resource dashboard.
Three algorithms, three cost curves
A join is not one operation. Nested loop scans the outer input and probes the inner one once per row, so its cost is outer_rows x probe_cost — superb when the outer side is tiny and the probe is an index lookup, ruinous when the outer side turns out to be forty thousand rows. Hash join builds a hash table from the smaller input and streams the larger through it, paying a build cost once and then one probe per row — the workhorse for large unsorted inputs, provided the hash table fits in working memory. Merge join walks two sorted inputs in lockstep, which is nearly free if both are already ordered and expensive if either needs a sort first.
The planner chooses between them using estimated row counts. This is the crucial mechanical detail: the choice is made *before* execution, from a model of the data. When the model is right, all three choices are reasonable. When the model is wrong by three orders of magnitude, the planner does not pick a slightly worse plan — it picks an algorithm designed for a completely different problem size, and the result is the difference between 40 ms and 40 seconds.
So the diagnosis question is never "is a nested loop bad?". It is "was the input size the planner expected anywhere near what actually arrived?". A nested loop over twelve rows is the best plan available. The same nested loop over forty-one thousand rows is the same plan, executing forty-one thousand times.
| Strategy | Cost shape | Best when | Symptom when wrong |
|---|---|---|---|
| Nested loop | outer rows x probe cost | Outer input is small and the inner probe is an indexed lookup | Huge loops= count on the inner node; time scales with outer rows |
| Hash join | build smaller side, then one probe per row | Both inputs large, no useful ordering, equality predicate | Batches: 17 — the hash table spilled to disk because work memory was too small |
| Merge join | one pass over two sorted inputs | Both inputs already sorted on the join key, or an index provides order | A Sort node feeding it that spills: external merge Disk: 84MB |
| Any of them | proportional to real input size | The estimate matched reality | Estimate/actual divergence of 10x or more at the input node |
Reading the failure in the plan
The plan below is the nested-loop blowup in its natural habitat. Two readings identify it in seconds. First, the inner node says loops=41038: the engine executed that index scan forty-one thousand times, and its innocuous 0.07 ms per execution multiplies out to most of the runtime. Second, the outer node estimated twelve rows and produced forty-one thousand, which is exactly why the loop strategy was chosen.
The second plan shows the other common failure, which is subtler because the strategy is correct. A hash join was the right choice, but the hash table did not fit in working memory, so the engine partitioned it into batches and spilled them to storage. Batches: 17 and the Disk: figure are the tell. Here the fix is memory or fewer rows, not a different strategy — and raising working memory globally is dangerous because it is allocated per sort or hash node, per connection, so a pool of a hundred connections can multiply it into an out-of-memory event.
Both cases share a diagnostic discipline worth stating plainly: read loops=, read Batches:, read estimate against actual. Those three readings distinguish "wrong algorithm" from "right algorithm, insufficient memory" from "genuinely a lot of data", and the three have different fixes.
A. WRONG STRATEGY (estimate off by 3400x)
Nested Loop (actual time=0.04..3187.22 rows=41038 loops=1)
-> Index Scan on orders o
(cost=... rows=12) (actual rows=41038 loops=1) <- 12 estimated
-> Index Scan using customers_pkey on customers c
(actual time=0.061..0.071 rows=1 loops=41038) <- 41038 executions
0.07ms x 41038 = 2.9s
B. RIGHT STRATEGY, NOT ENOUGH MEMORY
Hash Join (actual time=812.4..9044.1 rows=2841002 loops=1)
Hash Cond: (oi.product_id = p.id)
-> Seq Scan on order_items oi (actual rows=2841002 loops=1)
-> Hash (actual rows=482000 loops=1)
Buckets: 65536 Batches: 17 Memory Usage: 4096kB <- spilled: 17 batches
-> Seq Scan on products p (actual rows=482000 loops=1)
Batches > 1 means the hash table did not fit in work_mem and
was written to and re-read from disk. The join algorithm is
correct; the memory budget is not.Fixing the estimate beats forcing the strategy
Most engines offer a way to push the planner toward a strategy — session flags, optimizer hints, restructured queries that make one path unavailable. These work, and they are the wrong first choice, because they freeze a decision that was supposed to adapt. The data that made a nested loop wrong today will change again, and a forced hash join will be wrong in a different direction next quarter, silently, with nobody watching.
The durable fix is to make the estimate right. Underestimates usually come from one of three sources: stale statistics on a table that grew, correlated predicates that the planner assumes are independent, or a predicate the planner cannot reason about at all (a function result, a parameter it has not seen). Extended statistics address the correlation case directly and improve every query over those columns, not just this one.
When the estimate is right and the join is still expensive, the answer is upstream: join fewer rows. Filter before joining rather than after, aggregate on one side first, or question whether the query needs to join at scale at all — a denormalized read path or a precomputed rollup removes the join instead of tuning it. That last option is the one that survives data growth, and it is the one that costs a migration (Denormalization on Purpose).
| Evidence | Cause | Durable fix | What it costs |
|---|---|---|---|
| Estimate 12, actual 41,038 at the input | Stale statistics on a growing table | Refresh statistics; raise the statistics target on that column | Slower analyze; helps every query over the column |
| Estimate wrong on two correlated predicates | Planner assumes independence and multiplies selectivities | Extended statistics on the correlated column pair | Extra planning work; engine support varies |
Batches: 17, Disk: on the hash | Hash table exceeds working memory | Reduce joined rows, or raise work memory for that statement only | Memory is per node per connection — global raises are dangerous |
Sort node spilling under a merge join | No index provides the required order | Index on the join key to supply ordering, or let it hash instead | Write cost of another index |
| Estimates correct, volumes genuinely huge | The query really does join millions of rows | Filter earlier, pre-aggregate, or denormalize the read path | Migration, storage, and a consistency story |
| Correct plan, called thousands of times per request | Not a join problem — The Comb: N+1 as a Visible Shape | Batch at the application layer | Eager-loading discipline |
Key points
- The planner picks a join strategy from estimated row counts, before execution — a wrong estimate selects an algorithm built for a different problem size.
loops=on the inner node is the nested-loop blowup signature: a fast probe multiplied by tens of thousands of executions.Batches: > 1on a hash node means the hash table spilled to storage; the strategy is right and the memory budget is wrong.- Forcing a strategy with hints freezes a decision that was meant to adapt; fixing statistics improves every query over those columns.
- When estimates are right and the join is still expensive, join fewer rows — filter earlier, pre-aggregate, or denormalize the read path.
Follow the diagnosis
The causal chain, hop by hop — and the readings that invite the wrong conclusion.
- 1Endpoint → statement: the orders list endpoint spends 3.2 s in a single joined query; other statements are flat.
- 2Plan → node: time is concentrated in one Nested Loop node, not spread across the scans feeding it.
- 3Node → signature: the inner index scan reports
loops=41038at 0.07 ms each, accounting for roughly 2.9 s of the 3.2 s. - 4Signature → cause: the outer input was estimated at 12 rows and produced 41,038, so the planner chose a strategy that is optimal only for small outer inputs.
- 5Cause → root cause: statistics on
ordersare three weeks stale while a backlog of pending rows accumulated, so the date-plus-status predicate is badly misestimated.
- • "Nested loops are slow, force a hash join." Nested loops are optimal for small outer inputs; the estimate is what was wrong.
- • "The join needs an index." The plan already uses one on the inner side — that is why each probe is fast and the count is the problem.
- • "Raise work memory to stop the spilling." It is allocated per hash or sort node per connection; a global raise multiplied by the pool can exhaust the host.
- • "The hash join is slow because hashing is expensive." With
Batches: 17the cost is disk I/O from spilling, not hashing. - • "Adding a hint fixed it." It fixed today's data distribution and disabled the adaptation that would have handled tomorrow's.
Measure, fix, validate
An optimization is not finished until the metric that motivated it has moved.
- • The join node in `EXPLAIN (ANALYZE, BUFFERS)`: strategy, estimated versus actual rows, and `loops=` on the inner input.
- • `Batches:` and `Memory Usage:` on hash nodes, and `Sort Method:` on any sort feeding a merge join, to detect spilling.
- • Per-statement total time before and after, so a strategy change that helps one parameter value and hurts another is visible.
- • Statistics age and estimated-versus-actual ratios on the tables involved, tracked over time rather than sampled during an incident.
- • Correct the estimate: refresh statistics, raise the statistics target on the misestimated column, add extended statistics for correlated predicates.
- • Reduce joined volume: apply selective filters before the join, pre-aggregate the larger side, or paginate the result rather than joining everything.
- • Give the correct strategy what it needs: an index that supplies join-key ordering for a merge join, or a statement-scoped memory increase for a hash join that spills.
- • Restructure the query when the shape forces a bad plan — a lateral join or a CTE that materializes a small intermediate set can make the good strategy the obvious one.
- • Escalate to the data model only with evidence: denormalize the read path or maintain a rollup when the join is inherently large and on the critical path ([[denormalization]]).
- • Re-run the plan and confirm the strategy or the `loops=` count changed — a timing improvement alone can be a warm cache.
- • Test with at least two parameter values of different selectivity, because a plan tuned for one can be badly wrong for the other.
- • Watch total time for that statement family in the statement view, not just a single execution.
- • If working memory was raised, check host memory under peak concurrency, not in isolation.
- • Extended statistics improve estimates and add planning overhead on every query touching those columns.
- • Statement-scoped memory increases avoid the global blast radius and require the statement to be issued through a path that can set them.
- • Pre-aggregation and denormalization remove the join and add a freshness contract plus a maintenance path ([[cache-invalidation]] is the same problem in a different layer).
- • Plan assertions in CI catch regressions and also fail on benign planner upgrades.
- • Statistics maintenance sized to table growth, with a monitor on statistics age for the largest tables.
- • An alert on estimated-versus-actual ratio for critical statements — plan flips announce themselves here first.
- • A CI plan assertion for the few joins on the critical path, run against a production-shaped dataset.
Accuracy
Performance numbers are conditional. These are the conditions.
- DATABASE-SPECIFICAvailable strategies differ: MySQL 8 has no merge join, and InnoDB clustering changes probe costs. Plan text is PostgreSQL 16.
- ILLUSTRATIVERow counts, batch counts and timings are constructed to show recognizable shapes, not captured from a benchmark.
- WORKLOAD-SPECIFICWhich strategy is correct depends on data distribution, ordering and cache state; the same join deserves different plans for different parameter values.