What makes a subquery "correlated", and why does a correlated subquery risk being executed once per row of the enclosing query?
answer
- references an outer column = correlated
- f(outer_row), re-evaluated per row
- uncorrelated = evaluate once, reuse
- flatten to join / semi-join / anti-join
- plan tell: loop count == outer rows
basics
~20 sA correlated subquery references a column from the enclosing query, so its result depends on the current outer row and logically must be re-evaluated for each one. An uncorrelated subquery is self-contained: computed once, reused for every row.
solid answer
~50 sA subquery is **correlated** when its body references a column supplied by the enclosing query block. That makes it a parameterized query: for outer row A it may return one answer, for outer row B another. The textbook execution model runs it once per outer row - a loop with a query inside the loop - so an N-row outer scan costs N executions of the inner query. An **uncorrelated** subquery names nothing from outside, so its result is constant for the statement. The engine evaluates it once, materializes or caches it, and reuses it. Optimizers do not accept the per-row model as final. In the rewrite phase they try to **decorrelate** (flatten) the correlated form into a join, semi-join or anti-join: the correlation reference becomes an ordinary join predicate, the inner table is scanned once, and hash or merge matching does the work in a single pass. Repeated per-row execution is the fallback when flattening is illegal.
code
sql · 8 lines-- uncorrelated: inner result is constant
SELECT * FROM orders
WHERE customer_id IN (SELECT id FROM customers WHERE country = 'DE');
-- correlated: references o.customer_id from the outer block
SELECT * FROM orders o
WHERE EXISTS (SELECT 1 FROM customers c
WHERE c.id = o.customer_id AND c.country = 'DE');go deeper
Define correlation precisely (references an outer column) and state the per-row consequence with a rough cost multiplier.
Add that the optimizer normally flattens it into a join or semi-join, and name the plan evidence you would look for.
Frame it as a rewrite-phase decision: semantics are nested loops, execution is a join when flattening is legal; discuss what blocks it and the resulting cost multiplier.
Discuss it as a portability and predictability issue - which engines flatten which shapes, and when you would standardize on explicit joins so plans stay stable across engines and versions.
## The two shapes A subquery is a query nested inside another. It sits in a predicate (`IN`, `EXISTS`, `= (...)`), in the projection list (a *scalar* subquery returning one row, one column), or in the `FROM` clause (a derived table). What drives optimizer behaviour is whether the subquery is self-contained. - **Uncorrelated**: every column it names resolves inside itself. Its result is a constant relation for the whole statement. - **Correlated**: at least one column resolves to the *outer* query block. The subquery is therefore a function of the outer row - conceptually `f(outer_row)`. ## Why correlation implies repetition SQL's semantics are defined over a nested-loop evaluation: for each candidate outer row, evaluate the predicate, which means evaluating the subquery with that row's values substituted. If the outer table has one million rows and the subquery costs one index probe, that is one million probes. If the subquery costs a table scan, it is one million scans - the difference between milliseconds and hours. Uncorrelated subqueries have no such multiplier: their answer cannot change between rows, so a single evaluation suffices and the engine can even build a hash table from it once. ## Decorrelation: turning the loop into a join The semantics are nested loops; the *execution* need not be. In the rewrite/normalization phase an optimizer tries to **flatten** the correlated subquery into a join-shaped operator over the same two relations, with the correlation column promoted to a join predicate. Once the query is a join, the optimizer's whole cost-based machinery applies: it can choose hash join, merge join or index nested loop, reorder the inputs, and pick which side to build from. A hash-based plan touches each table once - O(N + M) instead of O(N x M). The common flattenings are: `EXISTS`/`IN` predicates become semi-joins, `NOT EXISTS`/`NOT IN` become anti-joins, and scalar aggregate subqueries become an outer join against a pre-grouped aggregate. ## What you see in a plan A plan that failed to decorrelate shows the inner query as a separate subplan attached to a filter, often labelled a subplan, filter subquery, or a nested-loop whose inner side re-executes; the tell is an operator whose actual loop/execution count equals the outer row count. A decorrelated plan shows a join operator (hash semi join, merge anti join, nested loop semi join) with each input scanned once. Reading loop counts in a plan is how you tell which one you got. ## Practical consequences 1. Correlated subqueries are not automatically slow. On a modern optimizer most of them flatten and perform identically to the hand-written join. Rewriting them by hand out of superstition adds noise. 2. But flattening is not guaranteed. Certain constructs block it (row-limiting clauses, non-equality or `OR`-ed correlations, volatile functions, some outer-join positions), and then you are back to per-row execution. 3. Correlated *and* uncorrelated subqueries can both be cached: a correlated subquery whose parameter repeats may be served from a per-execution memo, which softens but does not remove the cost. 4. The fix when flattening fails is usually to write the join, semi-join or aggregate-then-join form yourself, so the plan cannot fall back to a loop. ## Cost intuition Think of the multiplier explicitly: cost approximately equals outer_rows x inner_cost for the un-flattened form, versus outer_cost + inner_cost + join_cost for the flattened one. Deciding whether a correlated subquery matters is a matter of estimating that multiplier: 50 outer rows with an index probe inside is fine; 5 million outer rows with a scan inside is a production incident.
- If both forms are logically equivalent, why do people still report that rewriting a correlated subquery as a join made a query fast?Usually because the optimizer failed to decorrelate the original, so the plan really was re-executing the inner query per outer row. Hand-writing the join removes the construct that blocked flattening. It can also happen when the rewrite changes estimates enough to pick a better join order. It is not a general rule that joins beat subqueries.
- How do you tell from an execution plan whether decorrelation happened?Look for a join-shaped operator (semi join, anti join, hash join) with each input scanned once. If instead you see the inner query as an attached subplan or filter, or a nested-loop inner side whose execution/loop count equals the outer row count, the subquery is being re-executed per row.
Uncorrelated is looking up one address before you leave the house; correlated is phoning the office again at every doorstep. Decorrelation is asking for the whole address list once and matching it in one pass.
saying these in an interview costs you the question
- Claiming every correlated subquery is executed once per row on a modern optimizer
- Saying subqueries are always slower than joins as a blanket rule
- Confusing correlated with 'nested' - depth of nesting is not correlation
- Thinking a derived table in FROM can never be correlated (LATERAL/APPLY forms are)
- Assuming the engine caches the correlated result across all rows regardless of the parameter