Nested Subqueries

A nested subquery is a `SELECT` statement embedded within another SQL statement, appearing wherever the surrounding syntax expects a value, a set of values, or a table. The enclosing statement is the outer query; the embedded one is the inner query or subquery. Subqueries can nest inside `WHERE` clauses (the most common case), inside `FROM` clauses (called derived tables or inline views), inside `HAVING` clauses, and even inside the `SELECT` list as a scalar subquery. The crucial classification is correlation. An uncorrelated subquery contains no reference to any column of the outer query; it can be evaluated exactly once, independently, and its result (a scalar, a set, or a table) is then used by the outer query as if it were a constant. A correlated subquery references at least one column from the enclosing query — for example `WHERE EXISTS (SELECT 1 FROM Enrolled E WHERE E.ID = S.ID)` inside a query over `Student S`. Semantically, a correlated subquery is a function of the current outer row: each candidate outer row induces a different inner-query result, so the inner query must, at least conceptually, be re-evaluated once per outer row. This is precisely analogous to a closure capturing a free variable from an enclosing scope in a programming language. SQL provides several predicate forms for consuming a subquery's result: `IN` / `NOT IN` (set membership), `EXISTS` / `NOT EXISTS` (non-emptiness test), `= ANY` / `<> ALL` and friends (quantified comparison), and bare scalar comparison (`=`, `<`, etc., valid only when the subquery is guaranteed to return at most one row). Each of these has precise, three-valued (`TRUE`/`FALSE`/`UNKNOWN`) semantics under SQL's `NULL` handling, and the differences between them — especially around `NULL` — are a frequent source of subtle bugs, discussed below.

Evaluating a scalar subquery. A subquery used where a single value is expected (e.g., `WHERE salary > (SELECT AVG(salary) FROM Employee)`) must produce exactly one row and one column; if it produces zero rows the result is `NULL`, and if it produces more than one row the query raises a runtime error (a cardinality violation). Conceptually: ``` function EVAL_SCALAR_SUBQUERY(inner_query, outer_row, correlation_vars): bind correlation_vars using outer_row // no-op if uncorrelated result_rows := EXECUTE(inner_query) if COUNT(result_rows) == 0: return NULL if COUNT(result_rows) > 1: raise ERROR "subquery returned more than one row" return result_rows[0].the_single_column ```

Evaluating `IN` / `NOT IN`. Here the inner query yields a set $V$ of values (nulls possibly included). ``` function EVAL_IN(expr, inner_query, outer_row): bind correlation_vars using outer_row V := { row.col for row in EXECUTE(inner_query) } if expr in V: return TRUE else if NULL in V: return UNKNOWN // NOT IN over this V will also be UNKNOWN else: return FALSE function EVAL_NOT_IN(expr, inner_query, outer_row): return NOT( EVAL_IN(expr, inner_query, outer_row) ) // three-valued NOT ``` The three-valued `NOT` is the source of the famous `NOT IN` pitfall: `NOT(UNKNOWN) = UNKNOWN`, and a row is kept only when its predicate evaluates to `TRUE` — `UNKNOWN` rows are discarded, exactly like `FALSE` rows.

Evaluating `EXISTS` / `NOT EXISTS`. This is purely a cardinality test, immune to the `NULL`-poisoning problem above (it asks "is the row set nonempty", not "is my value among these values, some of which might be unknown"). ``` function EVAL_EXISTS(inner_query, outer_row): bind correlation_vars using outer_row result_rows := EXECUTE(inner_query) return COUNT(result_rows) > 0 // strictly TRUE or FALSE, never UNKNOWN function EVAL_NOT_EXISTS(inner_query, outer_row): return NOT EVAL_EXISTS(inner_query, outer_row) ```

Evaluating quantified comparisons (`ANY`/`ALL`). `x = ANY (subquery)` is equivalent to `x IN (subquery)`; `x <> ALL (subquery)` is equivalent to `x NOT IN (subquery)`. More generally `x op ANY (Q)` is true if `x op v` is true for some row `v` of `Q`, and `x op ALL (Q)` is true if `x op v` holds for every row `v` of `Q` (vacuously true if `Q` is empty). ``` function EVAL_ALL(x, op, inner_query, outer_row): bind correlation_vars using outer_row V := { row.col for row in EXECUTE(inner_query) } if V is empty: return TRUE // vacuous truth saw_unknown := FALSE for v in V: r := APPLY(op, x, v) // TRUE / FALSE / UNKNOWN (NULL involved) if r == FALSE: return FALSE if r == UNKNOWN: saw_unknown := TRUE return UNKNOWN if saw_unknown else TRUE ```

Overall outer-query evaluation. The naive but semantically faithful execution strategy for a `WHERE`-clause correlated subquery is nested-loop style, one inner evaluation per outer candidate row: ``` function EVALUATE_OUTER_QUERY(OuterFrom, OuterPred, Subquery): output := empty set for row in OuterFrom: // one row at a time truth := EVAL_PREDICATE(OuterPred, row, Subquery) // may itself invoke // EVAL_EXISTS / EVAL_IN / ... if truth == TRUE: output.add(PROJECT(row)) return output ```

Derived tables. A subquery in `FROM` is materialized (or streamed) as an ordinary table with its own schema, then joined, filtered, or aggregated exactly like any base table: ``` SELECT D.dept_name, D.avg_sal FROM (SELECT dept_name, AVG(salary) AS avg_sal FROM Employee GROUP BY dept_name) AS D WHERE D.avg_sal > 50000 ``` This turns any query result into an input for further Joins in SQL or Aggregation and the GROUP BY Clause, which is why derived tables are the natural stepping stone to full Query Optimization Fundamentals — a correlated `WHERE`-subquery and a derived-table join can express the same answer set, and the optimizer's job is to prove that rewrite is safe.

Correctness argument. The semantics above are defined so that a query with a subquery is equivalent to its unfolding in relational calculus. For a correlated `EXISTS` subquery, `WHERE EXISTS (Q(outer_row))` is true for an outer row $r$ exactly when the relational-calculus formula $\exists t \in Q(r)$ holds — this is a direct restatement of the existential quantifier, so `EXISTS` correctly implements "there exists a matching inner tuple." Symmetrically, `NOT EXISTS (Q1) AND NOT EXISTS (Q2)` composed twice is the standard idiom for relational-calculus universal quantification ("for all"): to test "student $s$ has taken every course $c$", rewrite $\forall c\, (\text{taken}(s,c))$ as $\neg\exists c\, (\neg\text{taken}(s,c))$, i.e. ``` SELECT S.name FROM Student S WHERE NOT EXISTS ( SELECT C.course_id FROM Course C WHERE NOT EXISTS ( SELECT 1 FROM Enrolled E WHERE E.ID = S.ID AND E.course_id = C.course_id ) ) ``` This double-negation pattern is provably correct because it is literally the De Morgan translation $\forall x\,\phi(x) \equiv \neg\exists x\,\neg\phi(x)$ applied at the level of tuples, not an ad hoc trick — any course $c$ for which the inner `NOT EXISTS` is true is a counterexample course the student hasn't taken, and the outer `NOT EXISTS` says no counterexample exists. For `IN`/`NOT IN`/`ANY`/`ALL`, correctness reduces to showing `EVAL_IN` above matches the SQL standard's three-valued logic table for membership, and that `NOT` is applied under three-valued logic (`NOT TRUE = FALSE`, `NOT FALSE = TRUE`, `NOT UNKNOWN = UNKNOWN`), and that a `WHERE` clause keeps a row iff its predicate is exactly `TRUE` (both `FALSE` and `UNKNOWN` reject the row). This last rule is what produces the `NOT IN` pitfall discussed below, and it is not a bug — it follows deterministically from the standard's definition of `WHERE`.

Complexity. Let the outer query range over $n$ rows and the (uncorrelated part of the) inner query range over $m$ rows.

• Uncorrelated subquery: computed once, cost $C_{\text{inner}}(m)$, then reused for all $n$ outer rows — typically $O(n + m)$ total if the result is materialized into a hash set or sorted array for $O(1)$ or $O(\log m)$ membership tests per outer row, giving $O(n \log m + m \log m)$ with sorting or $O(n+m)$ expected with hashing.
• Correlated subquery, naive nested-loop evaluation: the inner query genuinely depends on the outer row, so a literal implementation re-executes it $n$ times, each costing up to $O(m)$ (a full scan or an indexed lookup at $O(\log m)$) — total $O(n \cdot m)$ naively, or $O(n \log m)$ with an index on the correlation column.
• Optimizer rewrite: because many correlated subqueries (especially `EXISTS`/`IN`/`NOT EXISTS`/`NOT IN` used as filters) are semantically equivalent to a semi-join or anti-join, a real optimizer rewrites them into a join executed via hashing or sort-merge, achieving $O(n + m)$ (hash join) or $O(n\log n + m\log m)$ (sort-merge join) instead of $O(nm)$. This rewrite is why understanding subqueries is a direct prerequisite to Query Optimization Fundamentals: the SQL text does not dictate the execution plan, only the required output.
• Space: an uncorrelated subquery's result must be held (as a set, hash table, or sorted list) in $O(m)$ space; a correlated subquery evaluated naively needs no extra buffering beyond one inner result at a time, i.e. $O(1)$ extra space per outer row (though a rewritten join plan may need $O(m)$ for a hash table).

The honest tradeoff: correlated subqueries are the most expressive and the easiest to write correctly, but are the easiest to write inefficiently, since a naive engine re-executes the inner query per row. Modern relational engines almost always attempt the join rewrite, but ORMs and hand-written SQL against weaker engines can still hit the $O(nm)$ path — this is why "avoid correlated subqueries in hot paths" persists as folklore advice, even though it is really "avoid correlated subqueries the optimizer can't decorrelate."

Consider a simplified university schema: ``` Student(ID, name) Course(course_id, title) Enrolled(ID, course_id) ``` Data:

Query: find students who have taken every course. ``` SELECT S.name FROM Student S WHERE NOT EXISTS ( SELECT C.course_id FROM Course C WHERE NOT EXISTS ( SELECT 1 FROM Enrolled E WHERE E.ID = S.ID AND E.course_id = C.course_id ) ) ``` Trace the nested-loop evaluation exactly as `EVALUATE_OUTER_QUERY` would:

Result: `{Amy}` — exactly the student enrolled in both `CS101` and `CS202`. The trace shows the double-negation mechanism concretely: Bo is rejected the moment a single course (`CS202`) is found for which no `Enrolled` row exists, which is precisely the counterexample that falsifies "Bo has taken every course."

Second case — the `NOT IN` NULL trap, using the same `Enrolled` table but suppose one row has a `NULL` course_id (e.g., a withdrawn enrollment recorded as `(2, NULL)`): ``` SELECT name FROM Student WHERE ID NOT IN (SELECT ID FROM Enrolled WHERE course_id IS NULL OR TRUE) ``` More precisely, consider the classic form: ``` SELECT S.name FROM Student S WHERE S.ID NOT IN (SELECT E.ID FROM Enrolled E WHERE E.course_id = 'CS202') ``` if the subquery's result set (the set of IDs who took CS202) happens to include a `NULL` ID value (e.g., a malformed row `(NULL, 'CS202')`), then $V = \{1, \text{NULL}\}$. For Cy (ID=3): `EVAL_IN` checks `3 in {1, NULL}` → not literally present, but `NULL ∈ V` → returns `UNKNOWN`; then `NOT IN` = `NOT(UNKNOWN)` = `UNKNOWN`; the `WHERE` clause discards Cy even though intuitively "Cy never took CS202." This happens for every row once a single `NULL` contaminates $V$ — the entire `NOT IN` becomes vacuously empty. Replacing `NOT IN` with `NOT EXISTS` (a pure cardinality test, never poisoned by `NULL` values) restores the intended anti-join semantics.

The relational model and its calculus-based query languages, which nested subqueries directly implement, trace back to Codd's relational algebra and calculus, with SQL itself (originally SEQUEL) designed at IBM to make that calculus usable by non-mathematicians.

Nested subqueries underlie almost every non-trivial analytical or transactional query written in production systems: reporting dashboards that compute "customers above the regional average" use scalar subqueries; fraud-detection and recommendation pipelines use correlated `EXISTS`/`NOT EXISTS` for anti-join patterns like "users who registered but never purchased"; data warehouses built on engines such as PostgreSQL, Oracle, SQL Server, Snowflake, and BigQuery rely on cost-based optimizers whose central job is deciding whether to decorrelate a subquery into a semi-join or anti-join versus executing it as written. ORMs (object-relational mappers) frequently generate correlated subqueries automatically when translating object-graph queries, making an understanding of correlation cost essential for diagnosing slow application queries. The "for all" double-negation idiom appears throughout constraint-checking logic (e.g., verifying referential completeness, checking that every order line references a valid product) and is a standard interview and exam pattern precisely because it exercises quantifier reasoning that later resurfaces in Set Operations in SQL (where `EXCEPT` gives an alternative, often clearer, way to express the same "for all" queries) and in the cost-based rewriting rules central to Query Optimization Fundamentals.

Ask the tutor: How would you rewrite a correlated `NOT EXISTS` "for all" query into an equivalent query using `GROUP BY`/`HAVING COUNT(*)` and a derived table, and when might the optimizer prefer one form over the other?