Exercises — Subqueries — correlated vs uncorrelated

Uncorrelated. Read the inner query alone: SELECT AVG(salary) FROM employee. It names no outer column — you could copy-paste it into a fresh editor and it would run and return one number. Because nothing changes between outer rows, it is logically evaluated once.

Correlated. The inner query mentions e.dept_id, and e is the outer table's alias. Run the inner query alone and the database screams "unknown column e.dept_id" — proof of correlation. The threshold (AVG per department) changes with each outer row, so it is logically evaluated once per outer row.

Correlated. o.customer_id = c.id reaches out to c.id (outer). EXISTS almost always signals correlation, because its whole purpose is to ask a per-outer-row yes/no question.

Uncorrelated. The inner query filters orders by a literal constant 100, not by any outer column. It builds one fixed list of customer_ids, then each outer id is membership-tested against that list.

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

Why uncorrelated: the average is a single global constant for the whole table, so compute it once and compare each row against it. Strictly above means > (not >=).

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);

Why correlated: the threshold is not one number — it depends on e.dept_id, which differs per row. The inner alias e2 is a second, independent copy of employee so the inner filter can compare against the outer row's department. See Aggregate Functions GROUP BY — the key idea you need from there is that GROUP BY dept_id with AVG(salary) produces one average per department in a single pass, which is the uncorrelated alternative to this per-row recompute (used in Exercise 4.2).

SELECT c.name
FROM   customer c
WHERE  EXISTS (SELECT 1
               FROM   orders o
               WHERE  o.customer_id = c.id
                 AND  o.amount > 100);

Why this matches: "customer whose id is in the list of order-owners with amount > 100" is logically the same as "customer for whom there exists at least one such order." SELECT 1 is a convention: EXISTS cares only whether a row comes back, never about its contents, so we return a dummy 1. The key idea from EXISTS vs IN vs ANY you need here: EXISTS stops at the first matching row (short-circuits) and, unlike IN, never does an equality test against a NULL in a list — so it stays predictable (this saves you in Exercises 3.2–3.3).

Inner list = {10, 10, 20, NULL}.

• id = 10 → matches 10 → returned.
• id = 20 → matches 20 → returned.
• id = 30 → not equal to 10 or 20. Now the NULL: 30 IN (..., NULL) evaluates 30 = NULL, which is UNKNOWN, not FALSE. But since a real match (a TRUE) was needed and none exists, and one comparison is UNKNOWN, the whole IN is UNKNOWN → treated as not-satisfied → customer 30 excluded. Returned: customers 10 and 20. Here the NULL happens not to change the answer, but it makes the truth-value murky. The one fact you need from NULL handling in SQL: any comparison with NULL yields UNKNOWN (a third truth value), and only a TRUE passes a WHERE.

Intuitively we want customers with no order: only customer 30. But watch the logic. 30 NOT IN (10, 10, 20, NULL) means 30 <> 10 AND 30 <> 10 AND 30 <> 20 AND 30 <> NULL. The last term 30 <> NULL is UNKNOWN. TRUE AND TRUE AND TRUE AND UNKNOWN = UNKNOWN. UNKNOWN is not TRUE, so customer 30 is excluded too. Returned: none — the empty set! This is the infamous NOT IN + NULL bug.

Use a correlated NOT EXISTS:

SELECT c.name
FROM   customer c
WHERE  NOT EXISTS (SELECT 1 FROM orders o
                   WHERE o.customer_id = c.id);

Why it works: EXISTS asks "did any row come back?" — a pure yes/no. For customer 30, the inner query looks for orders with customer_id = 30; the NULL-owner row has customer_id = NULL, and NULL = 30 is UNKNOWN, so that row is filtered out and simply doesn't count as a match. No rows come back → NOT EXISTS is TRUE → customer 30 is returned. Returned: customer 30. EXISTS never does a <> NULL on the outer value the way NOT IN does, so the trap disappears.

SELECT DISTINCT c.name
FROM   customer c
JOIN   orders o ON o.customer_id = c.id;

Why equal: an inner join keeps every customer row that has at least one matching order — exactly the customers for whom the order "exists." The one fact you need from Joins — inner outer cross: an inner join emits one output row for every matching pair of left/right rows. The subtlety — you must add DISTINCT. Because the inner join emits one row per matching pair, a customer with 3 orders appears 3 times, whereas EXISTS (a semi-join, defined above) yields the customer once. DISTINCT restores that one-row-per-customer behaviour. This "check existence without multiplying rows" is exactly why optimizers implement EXISTS as a semi-join — see Query Optimizer Execution Plans.

SELECT e.name, e.salary
FROM   employee e
JOIN   (SELECT dept_id, AVG(salary) AS avg_sal
        FROM   employee
        GROUP  BY dept_id) d
  ON   d.dept_id = e.dept_id
WHERE  e.salary > d.avg_sal;

Why this is now uncorrelated: the subquery d names no outer column — it computes all department averages once in a single GROUP BY pass (the very idea recapped in Exercise 2.2 from Aggregate Functions GROUP BY). Then a plain join attaches each employee to its department's precomputed average, and WHERE filters. We traded "re-run the average per employee" for "compute all averages once, then join" — often exactly what the optimizer does for you anyway.

(a) Uncorrelated $=c+N\cdot k=200+10,000\times 1=10,200$ units. (b) Correlated $=N\cdot c+N\cdot k=10,000\times 200+10,000\times 1=2,000,000+10,000=2,010,000$ units. (c) Ratio $=\frac{2,010,000}{10,200}\approx 197.06$. So the correlated form is naively ~197× heavier — dominated by the $N\cdot c$ term, i.e. re-running the expensive inner query 10,000 times.

The collapse, one term at a time. Start from the naive correlated cost: ${\text{Correlated}}_{\text{naive}}=N\cdot c+N\cdot k.$ The term $N\cdot c$ says "build the inner result once for every one of the $N$ outer rows." But the inner result (the set of matching keys) does not depend on the outer row's identity — only the probe into it does. So the optimizer builds a hash table of that inner result exactly once: $\underset{\text{re-build per row}}{\underbrace{N\cdot c}}⟶\underset{\text{build hash once}}{\underbrace{c}}.$ What remains is the per-row work: each of the $N$ outer rows still does one cheap probe/comparison, i.e. $N\cdot k$ (unchanged). Adding the surviving pieces: ${\text{Correlated}}_{\text{rewritten}}=c+N\cdot k.$ Now plug in $c=200,N=10,000,k=1$: $=200+10,000\times 1=200+10,000=10,200\text{units}.$ That is identical to the uncorrelated form (Exercise 5.1a), so: $\text{ratio}=\frac{10,200}{10,200}=1.0.$ Lesson: the naive 197× penalty was a property of the logical semantics, not of reality. Once the optimizer recognises that the inner set can be built once and probed per row (a semi-join, defined in Exercise 4.1), correlated performance equals uncorrelated. This is exactly the steel-man from the parent recap: don't assume slowness — read the execution plan (Query Optimizer Execution Plans).

Set the ratio to 100: $\frac{Nc+Nk}{c+Nk}=100.$ Substitute $N=10,000,k=1$: $\frac{10,000c+10,000}{c+10,000}=100.$ Cross-multiply (multiply both sides by the denominator $c+10,000$): $10,000c+10,000=100(c+10,000).$ Expand the right side: $10,000c+10,000=100c+1,000,000.$ Collect the $c$ terms on the left and the constants on the right: $10,000c-100c=1,000,000-10,000,$ $9,900c=990,000.$ Divide both sides by $9,900$: $c=\frac{990,000}{9,900}=100.$ Check: correlated $=10,000\times 100+10,000=1,010,000$; uncorrelated $=100+10,000=10,100$; ratio $=1,010,000/10,100=100$. ✓

• Solid on L1–L2 → you can spot and write both kinds. Good baseline.
• Solid through L3 → you understand the NULL / NOT IN / EXISTS correctness pitfalls.
• Solid through L4 → you can convert between correlated subqueries, joins, and derived tables.
• Solid through L5 → you reason about cost and know when the optimizer erases it. Mastery.