Nested Query

A nested query (subquery) is just an inner SELECT whose result the planner must materialize or evaluate before the outer query can use it — and the single fact that decides everything about its cost is whether the inner query references a column from the outer query (correlated, re-run once per outer row) or not (uncorrelated, run once and reused).

That split is the whole topic. An uncorrelated subquery is a constant expression: the engine computes it a single time and substitutes the value (or value-set) into the outer predicate. A correlated subquery is a function of the current outer row — conceptually it executes again for every row the outer query examines, which is why a sloppy correlated subquery turns an O(N) scan into O(N×M). Real optimizers fight this by unnesting the subquery into a join when they legally can, so the same SQL can run as a nested loop or as a hash join depending on the planner. We will trace all three shapes against concrete rows.

The data we will trace

Two tables. We want the names of students who scored above 92 in at least one subject.

Note that Dia (id 4) has no exam rows at all — that absence is what breaks the NOT IN rewrite later.

Shape 1 — uncorrelated IN-subquery (runs once)

SELECT student_name
FROM   Students
WHERE  student_id IN (
    SELECT student_id
    FROM   Exam_Results
    WHERE  score > 92
);

The inner query mentions no column of Students, so it is evaluated once, producing a set. The outer query then tests each row's student_id for membership in that set.

1. Inner runs first: scan Exam_Results, keep score > 92 → rows (1, Math, 95) and (3, Chemistry, 93). Project student_id → set {1, 3}. Computed one time.
2. Outer scan, membership test against {1, 3}: Asha(1) ∈ → keep. Ben(2) ∉ → drop. Chen(3) ∈ → keep. Dia(4) ∉ → drop.
3. Result: Asha, Chen.

Total inner executions: 1. This is the cheap shape.

Shape 2 — correlated subquery in SELECT (runs per row)

Same idea applied to a count-per-customer. Here the inner query references Customers.CustomerID — the outer row — so it is correlated:

SELECT c.Name,
       (SELECT COUNT(*)
        FROM   Orders o
        WHERE  o.CustomerID = c.CustomerID) AS OrderCount
FROM   Customers c;

Conceptually the engine walks each Customers row and runs the inner COUNT(*) once with that row's CustomerID bound in. With 10,000 customers that is 10,000 inner executions. The fix is almost always to rewrite it as an aggregate join, which the planner may also do for you:

SELECT c.Name, COALESCE(o.cnt, 0) AS OrderCount
FROM   Customers c
LEFT JOIN (
    SELECT CustomerID, COUNT(*) AS cnt
    FROM   Orders
    GROUP BY CustomerID
) o ON o.CustomerID = c.CustomerID;

Both return the same numbers, but the join scans Orders once and hashes it — O(N+M) instead of O(N×M). The correlated form is fine for a handful of rows and a poison pill at scale.

Shape 3 — scalar subquery in WHERE

A scalar subquery must return exactly one row, one column. "Salary above the company average":

SELECT Name, Salary
FROM   Employees
WHERE  Salary > (SELECT AVG(Salary) FROM Employees);

The inner AVG is uncorrelated, so it is computed once into a single number and the comparison reuses it for every outer row. If a scalar subquery ever returns two rows, the engine raises a runtime error (e.g. Postgres: "more than one row returned by a subquery used as an expression") — not a wrong answer, a hard failure.

The optimizer rewrites IN into a join

You wrote an IN-subquery, but on most engines the planner does not run a separate inner query and a membership test — it unnests the subquery into a semi-join. A semi-join returns each outer row at most once as soon as one match is found, which is exactly IN / EXISTS semantics. So your Shape-1 query is typically executed as:

-- logically what the planner runs (DISTINCT avoids row duplication)
SELECT s.student_name
FROM   Students s
JOIN   (SELECT DISTINCT student_id FROM Exam_Results WHERE score > 92) r
       ON r.student_id = s.student_id;

This is why "IN vs EXISTS vs JOIN" rarely matters for performance on a modern optimizer for the uncorrelated, NULL-free case — they collapse to the same plan. It starts to matter the moment NULLs or correlation enter, which is the next section. Read the plan with EXPLAIN rather than trusting the syntax you typed.

Pitfalls

• NOT IN with a NULL in the set returns nothing. If the subquery's value-set contains even one NULL, x NOT IN (set) can never be true — it evaluates to UNKNOWN for every row, so the whole query returns zero rows. Reason: x NOT IN (1, NULL) means x <> 1 AND x <> NULL, and x <> NULL is UNKNOWN. Why the naive version is wrong:

  -- Looks like "students with no high score". Returns ZERO rows
  -- if ANY Exam_Results.student_id is NULL.
  SELECT student_name FROM Students
  WHERE student_id NOT IN (SELECT student_id FROM Exam_Results);
  
  -- Correct: NOT EXISTS is immune to the NULL trap
  SELECT student_name FROM Students s
  WHERE NOT EXISTS (
      SELECT 1 FROM Exam_Results e WHERE e.student_id = s.student_id);

  In our data Dia (id 4) is the intended answer; NOT EXISTS returns Dia, NOT IN returns nothing the instant a NULL student_id appears.
• Plain IN with NULLs silently drops, not errors. x IN (1, NULL) is true if x=1, else UNKNOWN (treated as not-matched). So IN is usually "safe" but never matches a NULL x — the asymmetry between IN and NOT IN is the bug everyone hits once.
• Correlated subquery in SELECT = hidden N+1. It looks like one query but executes the inner block once per output row. Catches people who paginate: the cost scales with rows returned, not rows stored.
• Scalar subquery returning >1 row is a runtime error, not a truncation. A query that passed in dev (one matching row) crashes in prod (two). Add LIMIT 1 with an explicit ORDER BY, or fix the join key.
• The optimizer's rewrite is not guaranteed. Correlated subqueries, subqueries inside OR, or those wrapped in non-trivial expressions often cannot be unnested and stay as nested loops. Always confirm with EXPLAIN (ANALYZE) instead of assuming.

Takeaways

• Correlated vs uncorrelated is the cost model. Uncorrelated runs once; correlated conceptually runs per outer row. Spot the outer-table reference and you know which you have.
• Prefer EXISTS/NOT EXISTS over IN/NOT IN when NULLs are possible — NOT IN over a nullable column is the classic "returns nothing" footgun.
• A correlated subquery in SELECT is an N+1 in disguise; rewrite as a grouped LEFT JOIN when the row count grows.
• The SQL shape you write is not the plan that runs. Modern planners unnest IN/EXISTS into semi-joins; verify with EXPLAIN, don't argue from syntax.

Re-authored and deepened for this guide. Sources: PostgreSQL 16 documentation — "Subquery Expressions" and "Comparison Functions and Operators" (three-valued logic / NULL behavior of IN and NOT IN); the SQL:2016 standard's treatment of UNKNOWN and quantified comparison predicates; Markus Winand, SQL Performance Explained (semi-joins and subquery unnesting); and Joe Celko, SQL for Smarties (correlated subqueries and the NOT IN NULL trap). The original examples (IN-subquery, scalar > AVG, correlated OrderCount) were correct and are preserved; the execution mechanism, NULL semantics, and optimizer-rewrite material were added.

🎯 STRICT STANDOUT: Why / worked / when-not / failure / drills — Nested Query

Why this concept exists (judgment chain)

Subquery cost is dominated by correlation: uncorrelated runs once; correlated is conceptual N×M until the planner unnests to a semi-join/hash join. NOT IN with NULL is a semantic landmine; EXISTS/NOT EXISTS is the safe anti-semi-join form. Always verify with EXPLAIN.

Worked example with numbers or traced steps

Students 1..4; Exam scores: Asha Math95, Chen Chem93; Dia has no exams.
Uncorrelated IN score>92 → inner set {1,3} once → Asha,Chen.
Correlated COUNT orders per customer: 10k customers ⇒ ~10k inner plans unless rewritten to GROUP BY join.
NOT IN (SELECT student_id …) with a NULL student_id → entire outer result empty (UNKNOWN).
NOT EXISTS for Dia correctly returns Dia even if other NULLs exist.
Planner may rewrite IN to Hash Semi Join — syntax ≠ plan.

When NOT to use / named alternative

Keep a scalar uncorrelated AVG subquery when it is clear and the set is small. Prefer JOIN/EXISTS for large correlated patterns. Do not use IN when the subquery can return NULL keys. Scalar subqueries need cardinality 1 — use LIMIT 1+ORDER BY or aggregate.

Failure / ops fingerprint

Latency cliff when row count grows (hidden N+1). Mystery zero rows from NOT IN+NULL. Runtime error: more than one row returned by scalar subquery. Ops: EXPLAIN (ANALYZE) looking for Nested Loop with inner re-exec; track NOT IN in SQL linters.

Hostile-panel Q&As (model answers)

Q1. Correlated vs uncorrelated test?
Model answer: Does the inner SELECT reference an outer column? Yes → correlated.

Q2. Why NOT EXISTS over NOT IN?
Model answer: NOT IN becomes UNKNOWN if the set contains NULL; NOT EXISTS is true when no matching row exists, immune to that trap.

Q3. Is IN always slower than JOIN?
Model answer: Not on modern optimizers for uncorrelated NULL-free cases — they unnest to the same semi-join. Measure the plan.