Definition
- Correlated subquery – An inner query that references a column from the outer query, causing it to logically execute once per outer row.
- Near-quadratic cost – On a million-row table, a correlated aggregate means a million grouped scans.
- CTE / derived table rewrite – Pre-compute the aggregate with
GROUP BYin a CTE and JOIN it back, reducing N dependent sub-plans to one aggregate plus one join. - Semantic equivalence – The rewrite must handle NULL groups and empty groups identically to the original.
- INNER vs LEFT JOIN – Use INNER JOIN when empty groups should drop rows (matches correlated subquery returning NULL). Use LEFT JOIN with COALESCE to keep them.
- Optimizer decorrelation – Modern planners may do this automatically, but the explicit rewrite is clearer, more portable, and guaranteed.
Checking which National Bank of India accounts hold more than their own branch's average balance: the slow way is to re-add every balance in that branch from scratch for every single account. The fast way is to compute each branch's average once, write it on a sticky note, then compare each account to its sticky note. Rajesh (SAV2001) and Priya (CUR3001) each get compared against one precomputed number instead of forcing a full recomputation.
Understanding the Concepts
What is a correlated subquery?
A correlated subquery references a column from the outer query. This means the inner query logically executes once for every row in the outer query, because its result depends on the current outer row's values.
-- Correlated subquery: accounts above their branch average
-- The inner query references a.branch from the outer query
SELECT a.account_id, a.holder_name, a.balance, a.branch
FROM accounts a
WHERE a.balance > (
SELECT AVG(balance)
FROM accounts
WHERE branch = a.branch -- correlated: references outer a.branch
);
Why is it slow?
For each of the N outer rows, the database logically runs the inner aggregation query, scanning all rows in that branch. On a million-row table with 100 branches, that is a million grouped scans – near-quadratic work.
Correlated subquery execution (logical): Row 1 (branch=Mumbai): AVG of all Mumbai balances → compare Row 2 (branch=Delhi): AVG of all Delhi balances → compare Row 3 (branch=Mumbai): AVG of all Mumbai balances → compare (AGAIN!) ... Row N (branch=Pune): AVG of all Pune balances → compare Mumbai's average is recomputed for EVERY Mumbai account. Total work: O(N * rows-per-branch)
How do you rewrite it as a JOIN?
Pre-compute the aggregate once in a CTE (Common Table Expression), then JOIN it back to the base table.
-- FAST: CTE computes branch averages once, then JOIN
WITH branch_avg AS (
SELECT branch, AVG(balance) AS avg_balance
FROM accounts
GROUP BY branch
)
SELECT a.account_id, a.holder_name, a.balance, a.branch, b.avg_balance
FROM accounts a
JOIN branch_avg b ON a.branch = b.branch
WHERE a.balance > b.avg_balance
ORDER BY a.balance DESC;
Expected output:
account_id | holder_name | balance | branch | avg_balance
------------+----------------+------------+----------------+------------
SAV2001 | Rajesh Kumar | 500000.00 | Mumbai-Central | 250000.00
CUR3001 | Priya Sharma | 350000.00 | Mumbai-Central | 250000.00
SAV5001 | Pankaj Gupta | 450000.00 | Delhi-Central | 300000.00
How does the execution plan improve?
Correlated subquery plan:
Seq Scan on accounts
Filter: balance > (SubPlan 1)
SubPlan 1: Aggregate on accounts WHERE branch = a.branch
→ For each outer row, a new sub-plan runs. O(N * M).
CTE + JOIN plan:
CTE Scan → HashAggregate on accounts (one pass, GROUP BY branch)
Hash Join: accounts a JOIN branch_avg b ON a.branch = b.branch
Filter: a.balance > b.avg_balance
→ One aggregate pass + one hash join. O(N + M).
What about NULL groups and empty groups?
Verify the rewrite is semantically identical. A correlated subquery returning NULL (empty group, e.g., a branch with no other accounts) makes balance > NULL unknown, dropping the row. An INNER JOIN also drops it (no matching branch_avg row), so they agree.
-- If a branch has only one account, AVG is that account's balance.
-- balance > own_balance is FALSE, so the row is correctly excluded.
-- If you need to KEEP rows where the group is empty:
SELECT a.account_id, a.balance, COALESCE(b.avg_balance, 0) AS avg_balance
FROM accounts a
LEFT JOIN branch_avg b ON a.branch = b.branch
WHERE a.balance > COALESCE(b.avg_balance, 0);
Can you use a derived table instead of a CTE?
Yes. A derived table (subquery in FROM) achieves the same result. CTEs are more readable for complex queries.
-- Derived table version (equivalent)
SELECT a.account_id, a.holder_name, a.balance, b.avg_balance
FROM accounts a
JOIN (
SELECT branch, AVG(balance) AS avg_balance
FROM accounts
GROUP BY branch
) b ON a.branch = b.branch
WHERE a.balance > b.avg_balance;
How do you implement this in Java?
package com.bank.service;
import java.math.BigDecimal;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.sql.SQLException;
import java.util.ArrayList;
import java.util.List;
public class AboveAverageReportService {
private static final String SQL = """
WITH branch_avg AS (
SELECT branch, AVG(balance) AS avg_balance
FROM accounts
GROUP BY branch
)
SELECT a.account_id, a.holder_name, a.balance, a.branch, b.avg_balance
FROM accounts a
JOIN branch_avg b ON a.branch = b.branch
WHERE a.balance > b.avg_balance
ORDER BY a.balance DESC
""";
public List<String> findAboveAverageAccounts(Connection conn) throws SQLException {
List<String> results = new ArrayList<>();
try (PreparedStatement ps = conn.prepareStatement(SQL);
ResultSet rs = ps.executeQuery()) {
while (rs.next()) {
String line = String.format("%s (%s): Rs.%s (branch avg: Rs.%s)",
rs.getString("holder_name"),
rs.getString("branch"),
rs.getBigDecimal("balance"),
rs.getBigDecimal("avg_balance"));
results.add(line);
}
}
return results;
}
}
What other correlated subqueries can be rewritten?
Any pattern where the inner query aggregates a group that the outer row belongs to can be pre-computed and joined back: MAX, MIN, COUNT, SUM, and even window functions.
-- Correlated: employees earning more than department average
SELECT e.emp_name, e.salary, e.dept_id
FROM employees e
WHERE e.salary > (SELECT AVG(salary) FROM employees WHERE dept_id = e.dept_id);
-- Rewrite: CTE + JOIN
WITH dept_avg AS (
SELECT dept_id, AVG(salary) AS avg_salary
FROM employees GROUP BY dept_id
)
SELECT e.emp_name, e.salary, d.avg_salary
FROM employees e
JOIN dept_avg d ON e.dept_id = d.dept_id
WHERE e.salary > d.avg_salary;
What should a senior engineer know?
A senior engineer knows to recognize correlated subqueries in slow queries, to rewrite them as CTE-plus-JOIN for clarity and performance, to verify semantic equivalence for NULL and empty groups, and that modern optimizers may decorrelate automatically but the explicit rewrite is more portable and guaranteed.
Visual Overview
┌─────────────────────────────────────────────────────┐ │ Correlated Subquery vs CTE + JOIN │ ├─────────────────────────────────────────────────────┤ │ │ │ Correlated (slow): │ │ ┌──────────────────────────────────────┐ │ │ │ For EACH outer row: │ │ │ │ Row 1 → scan branch → AVG → cmp │ │ │ │ Row 2 → scan branch → AVG → cmp │ │ │ │ Row 3 → scan branch → AVG → cmp │ O(N*M) │ │ │ ... │ │ │ │ Row N → scan branch → AVG → cmp │ │ │ └──────────────────────────────────────┘ │ │ │ │ CTE + JOIN (fast): │ │ ┌──────────────────────┐ │ │ │ Step 1: ONE aggregate │ GROUP BY branch │ │ │ → branch_avg table │ (one pass) │ │ └──────────┬───────────┘ │ │ │ │ │ ▼ │ │ ┌──────────────────────┐ │ │ │ Step 2: Hash JOIN │ accounts ⟕ branch_avg │ │ │ + Filter balance > │ (one pass) O(N+M) │ │ │ avg_balance │ │ │ └──────────────────────┘ │ │ │ └─────────────────────────────────────────────────────┘
Key Takeaway
A correlated subquery references a column from the outer query, so the database logically evaluates it once for every outer row. When the inner query computes a group aggregate, this turns a simple comparison into near-quadratic work on large tables. The fix is to pre-compute the aggregate exactly once as a CTE or derived table with GROUP BY, then JOIN that small result back to the base table on the group key.
In Rajesh's nightly report at National Bank of India, the original query flagging accounts above their branch average recomputed the branch average per account and timed out across ten million rows. He rewrote it as a CTE that aggregates the average per branch in a single hash aggregate, then joined it back so the planner does one aggregate and one hash join instead of millions of dependent scans.
The semantic detail to verify is NULL and empty group handling. A correlated subquery returning NULL for an empty group makes balance > NULL unknown and drops the row. An INNER JOIN also drops it, so they agree. Use a LEFT JOIN with COALESCE when empty groups must be kept.
Modern optimizers may decorrelate automatically, but the explicit CTE-plus-JOIN rewrite is clearer, more portable, and guaranteed to work across all database engines.
Remember one sentence: Compute the group aggregate once in a CTE, then JOIN – never recompute per row.
---