A Correlated Subquery is an inner query block that references outer query attributes (outer column variables). Unlike uncorrelated subqueries which can be evaluated once prior to outer scanning, a correlated subquery logically executes once for every candidate row evaluated by the outer query block.
SubPlan nodes.Correlated subqueries naturally express queries that require group-relative or historical boundary comparisons:
In relational algebra, correlation introduces a parameter dependency $\theta(r)$ into the inner selection:
\[\sigma_{\text{Predicate}(r, S)}(R) = \bigcup_{r \in R} \{ r \mid \text{Predicate}(r, \sigma_{\theta(r)}(S)) \}\]| For an outer relation $R$ containing $ | R | = N$ tuples and an inner relation $S$ containing $ | S | = M$ tuples, naive evaluation requires scanning or indexing $S$ $N$ times. Without optimization, the time complexity scales as: |
-- ANSI SQL Correlated Subquery: Departmental Salary Benchmark
SELECT
e.emp_id,
e.emp_name,
e.dept_id,
e.hire_date
FROM employes e
WHERE e.hire_date = (
-- Inner Correlated Subquery referencing outer e.dept_id
SELECT MIN(d_emp.hire_date)
FROM employes d_emp
WHERE d_emp.dept_id = e.dept_id -- Correlation Predicate!
);
Visualizing row-by-row correlation:
Outer Loop: Scan 'employes' table row by row (N rows)
├─ Row 1: emp_id=1, dept_id=1
│ └─ Execute Subquery: SELECT MIN(hire_date) WHERE dept_id = 1 -> '2023-01-15'
│ └─ Evaluates: '2023-01-15' = '2023-01-15'? TRUE -> Keep Row 1
├─ Row 2: emp_id=3, dept_id=1
│ └─ Execute Subquery: SELECT MIN(hire_date) WHERE dept_id = 1 -> '2023-01-15'
│ └─ Evaluates: '2022-11-10' = '2023-01-15'? FALSE -> Filter Out
└─ Row 3: emp_id=11, dept_id=2
└─ Execute Subquery: SELECT MIN(hire_date) WHERE dept_id = 2 -> '2020-04-11'
└─ Evaluates: '2020-04-11' = '2020-04-11'? TRUE -> Keep Row 3
r1.dept_id) are passed into the inner subquery execution state as constant parameters.WHERE condition.In modern cost-based optimizers, correlated subqueries are initially parsed as SubPlan nodes. The query rewriter attempts Subquery Unnesting / Decorrelation:
d.dept_id = e.dept_id is pulled up out of the subquery and converted into an explicit JOIN condition.GROUP BY dept_id), executed once, and joined via Hash Join ($\mathcal{O}(N + M)$).PostgreSQL plan demonstrating a naive SubPlan (correlated nested loop):
Seq Scan on employes e (cost=0.00..62.50 rows=3 width=40) (actual time=0.045..0.215 rows=5 loops=1)
Filter: (hire_date = (SubPlan 1))
Buffers: shared hit=22
SubPlan 1
-> Aggregate (cost=1.22..1.23 rows=1 width=4) (actual time=0.003..0.003 rows=1 loops=50)
Buffers: shared hit=20
-> Seq Scan on employes d_emp (cost=0.00..1.22 rows=2 width=4) (actual time=0.001..0.002 rows=2 loops=50)
Filter: (dept_id = e.dept_id)
SubPlan 1: Indicates row-by-row execution.loops=50: The subquery was physically re-evaluated 50 separate times!Buffers: shared hit=22: Buffer hits scale linearly with the outer table row count.| Engine | Decorrelation Engine | SubPlan Caching |
Manual Rewrite Urgency |
|---|---|---|---|
| PostgreSQL 16+ | Unnests EXISTS/IN correlation; may retain SubPlan for scalar aggregates. |
Caches recent correlation parameter values in memory. | High if plan shows SubPlan with high loops. |
| MySQL 8.0+ | Subquery materialization engine decorrelates IN and EXISTS. |
Limited scalar caching. | High for complex aggregate correlations. |
| SQL Server 2022 | Advanced decorrelation engine (Apply to Join rewrites). |
Maintains cached parameter tables. | Medium (Optimizer decorrelates most standard queries). |
| Oracle 23c | Automatic Complex View Merging & Decorrelation. | Scalar Subquery Caching (hash table of inner results). | Low (Engine decorrelates aggressively). |
Executing a correlated subquery where the inner table lacks an index on the correlated column forces a full table scan on the inner table for every outer row ($\mathcal{O}(N \times M)$ disk operations).
-- ❌ NAIVE: Correlated Subquery (O(N * M))
SELECT e.emp_id, e.emp_name, e.dept_id
FROM employes e
WHERE e.hire_date = (
SELECT MIN(sub.hire_date)
FROM employes sub
WHERE sub.dept_id = e.dept_id
);
-- ✅ OPTIMIZED: Pre-aggregated Derived Table Join (O(N + M))
SELECT e.emp_id, e.emp_name, e.dept_id
FROM employes e
JOIN (
SELECT dept_id, MIN(hire_date) AS min_hire
FROM employes
GROUP BY dept_id
) d_min ON e.dept_id = d_min.dept_id AND e.hire_date = d_min.min_hire;
loops in EXPLAIN ANALYZE.Uber calculates whether a driver’s earnings on a trip exceeded the historical average earnings for that driver’s vehicle class during peak hours:
SELECT
t.trip_id,
t.driver_id,
t.fare_amount
FROM completed_trips t
WHERE t.fare_amount > (
SELECT AVG(sub.fare_amount)
FROM completed_trips sub
WHERE sub.vehicle_class = t.vehicle_class -- Correlation on Vehicle Class
AND sub.trip_date >= CURRENT_DATE - INTERVAL '30 days'
);
When an optimizer fails to decorrelate a query, it is usually because the subquery contains side-effect operators, non-deterministic functions (RANDOM(), CLOCK_TIMESTAMP()), or complex inequality correlation predicates. Converting the query into a CTE or Window Function explicitly forces decorrelation.
Answer: An uncorrelated subquery has zero dependencies on the outer query and is evaluated once as an InitPlan. A correlated subquery references outer table attributes and logically executes repeatedly (once per outer tuple) as a SubPlan, unless unnested by the optimizer into a Join operator.
| Property | Uncorrelated Subquery | Correlated Subquery |
|---|---|---|
| Outer Column Dependency | None | Yes (e.dept_id) |
| Execution Frequency | 1 Time (InitPlan) |
$N$ Times (SubPlan per outer row) |
| Time Complexity | $\mathcal{O}(N + M)$ | $\mathcal{O}(N \times M)$ (if unoptimized) |
| Decorrelation Target | Not Applicable | Essential for high-volume datasets |