Subqueries — correlated vs uncorrelated

HOW to tell them apart (the test)

Worked Example 1 — Uncorrelated (scalar)

Worked example Employees earning above company average

SELECT name, salary
FROM   employee
WHERE  salary > (SELECT AVG(salary) FROM employee);

Why this step?

The inner SELECT AVG(salary) FROM employee mentions no outer column → uncorrelated.
It runs once, returns a single number, say 50000.
The query effectively becomes WHERE salary > 50000.
Why correct: the average is a fixed property of the whole table, so computing it once is right and efficient.

Worked Example 2 — Uncorrelated (list with IN)

Worked example Customers who placed at least one order

SELECT name
FROM   customer
WHERE  id IN (SELECT customer_id FROM orders);

Why this step?

Inner query produces a list of customer_ids — independent of the outer row → uncorrelated.
Built once, then each outer id is membership-tested against it.

Worked Example 3 — Correlated (EXISTS)

Worked example Customers who placed at least one order — correlated version

SELECT c.name
FROM   customer c
WHERE  EXISTS (SELECT 1
               FROM   orders o
               WHERE  o.customer_id = c.id);   -- c.id is from the OUTER query!

Why this step?

The inner query references c.id (outer) → correlated.
For each customer row, the DB asks: "is there any order with this customer's id?" EXISTS stops at the first match (short-circuits), so it can be very fast.
Why EXISTS over IN here: EXISTS handles NULLs safely and can short-circuit; IN with a NULL in the list can give surprising results.

Worked Example 4 — Correlated (per-row aggregate)

Worked example Employees earning above

their own department's average

SELECT e.name, e.salary
FROM   employee e
WHERE  e.salary > (SELECT AVG(e2.salary)
                   FROM   employee e2
                   WHERE  e2.dept_id = e.dept_id);  -- depends on e.dept_id

Why this step?

The threshold is different per row (it depends on the row's department) → must be correlated.
Compare with Example 1: there the threshold was a single global constant (uncorrelated). The question dictates the kind.

Formula The cost model (logical semantics)

Let the outer query scan $N$ rows and one inner-query evaluation cost $c$ . $\text{Uncorrelated cost} = c + N\cdot k$ $\text{Correlated cost (naive)} = N\cdot c + N\cdot k$ where $k$ is the cheap per-row comparison. Derivation from first principles: uncorrelated runs the inner query exactly once ( $c$ ) then does $N$ comparisons ( $N\cdot k$ ). Correlated re-evaluates the inner query for each of the $N$ outer rows ( $N\cdot c$ ) plus the comparisons. Hence correlated is naively a factor $\sim c/k$ heavier — unless the optimizer rewrites it (e.g. as a hash semi-join), collapsing $N\cdot c$ toward $c$ .

Recall Feynman: explain to a 12-year-old

Imagine a worksheet. Uncorrelated: the teacher writes one number on the board (say, the class average), and you compare your score to that same number — the board is written once. Correlated: every student must look up their own group's average from a different table each time — so the lookup happens again for each student. Same idea, but one is a shared answer and the other is a personal answer per row.

Flashcards

What single test distinguishes a correlated from an uncorrelated subquery?

Whether the inner query references a column/alias from the outer query. If yes → correlated; if no → uncorrelated.

How many times is an uncorrelated subquery logically evaluated?

Once, before the outer query uses its result.

How many times is a correlated subquery logically evaluated?

Once per row of the outer query (semantically — optimizers may rewrite it).

Why can't you write WHERE salary > AVG(salary) directly without a subquery?

WHERE is evaluated per-row before aggregation; you need the aggregate computed first, which the (uncorrelated) subquery provides.

Why is EXISTS often preferred over IN for correlated existence checks?

EXISTS short-circuits at the first match and behaves predictably with NULLs, whereas IN with NULLs can yield surprising/empty results.

Steel-man: are correlated subqueries always slow?

No — that is only the logical semantics; optimizers frequently rewrite them into joins/semi-joins, so performance can equal an uncorrelated query.

Give the naive cost of a correlated subquery with N outer rows and inner cost c.

~N·c (plus per-row comparisons), versus ~c for uncorrelated.

"Find employees above their own department's average" — correlated or uncorrelated, and why?

Correlated — the threshold depends on each row's dept_id, so the inner aggregate must be recomputed per row.

Connections

Joins — inner outer cross — correlated subqueries can often be rewritten as joins.
Aggregate Functions GROUP BY — subqueries are how you compare rows against aggregates.
EXISTS vs IN vs ANY — choosing the right correlation operator.
Query Optimizer Execution Plans — how the DB decides whether to loop or rewrite.
NULL handling in SQL — why IN can misbehave where EXISTS is safe.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, subquery ka matlab hai ek query ke andar dusri query. Sabse bada sawaal yeh hai: kya andar wali (inner) query bahar wali (outer) query ke current row par depend karti hai? Agar nahi karti, to woh uncorrelated hai — usko sirf ek baar chalao, answer nikaalo, aur use kar lo. Jaise "company ka average salary" ek hi number hai, to use ek baar compute karke compare kar lo.

Agar inner query outer ka koi column use karti hai (jaise e.dept_id), to woh correlated hai — ab har outer row ke liye inner query dobara-dobara chalegi, kyunki har row ka apna dept alag hai, alag average. Soch lo jaise loop chal raha ho jo har baar alag argument ke saath function call karta hai.

Test simple hai: inner query ko alag se copy karke chalao. Agar woh akele chal jaaye → uncorrelated. Agar "unknown column" error de kyunki use outer ka column chahiye → correlated. EXISTS waale correlated checks aksar fast hote hain kyunki pehla match milte hi ruk jaate hain.

Ek galatfehmi: log sochte hain correlated hamesha slow hota hai. Yeh sirf logical model hai — asli mein database ka optimizer ise join/semi-join mein badal deta hai, to speed barabar ho sakti hai. Isliye assume mat karo, execution plan padho. Yeh concept interviews aur real reporting queries (jaise "har department ke top earners") mein bahut kaam aata hai.

Subqueries — correlated vs uncorrelated

WHY do subqueries exist?

WHAT exactly is each kind?

HOW to tell them apart (the test)

Worked Example 1 — Uncorrelated (scalar)

Worked Example 2 — Uncorrelated (list with IN)

Worked Example 3 — Correlated (EXISTS)

Worked Example 4 — Correlated (per-row aggregate)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Databases

Connections