Correlated Subqueries Versus Non-Correlated Subqueries

• Non-correlated subquery – self-contained; references nothing from the outer query; the database executes it once and reuses the single result for all outer rows.
• Correlated subquery – references a column from the outer query; its result depends on the current outer row; logically re-executes once for each row the outer query produces.
• Performance risk – the naive execution of a correlated subquery runs the inner query per outer row, which is O(N x M) without an index.
• Remedies – an index on the correlated predicate column and rewriting to a join or window function.
• EXISTS / NOT EXISTS – the most common correlated patterns; EXISTS short-circuits on the first match.

What is a non-correlated subquery?

A non-correlated subquery stands alone. It references nothing from the outer query, so the database can evaluate it once and reuse the result. This is efficient because the inner query runs exactly once regardless of how many outer rows there are.

-- Non-correlated: the inner query runs once
-- "Accounts with balance above the bank-wide average"
SELECT account_id, holder_name, balance
FROM   accounts
WHERE  balance > (SELECT AVG(balance) FROM accounts);

 account_id | holder_name  | balance
------------+--------------+-----------
 SAV2001    | Rajesh Kumar | 150000.00
 SAV2003    | Pankaj Gupta | 320000.00

The inner query computes one number (the overall average). That number does not change per outer row.

What is a correlated subquery?

A correlated subquery references a column from the outer query inside the inner query. Its value changes for each outer row, so it is conceptually re-evaluated for each outer row.

-- Correlated: the inner query depends on the outer row's account_id
-- "Transactions above their own account's average"
SELECT t.id, t.account_id, t.amount
FROM   transactions t
WHERE  t.amount > (
    SELECT AVG(x.amount)
    FROM   transactions x
    WHERE  x.account_id = t.account_id   -- references outer t
);

For each transaction t, the inner query computes the average for that specific account. A transaction for Rajesh's account is compared to Rajesh's average, and a transaction for Priya's account is compared to Priya's average.

How do you tell them apart?

The simplest tell is whether the inner query mentions a table alias from the outer query. If it does, it is correlated. If it can run independently, it is non-correlated.

-- Non-correlated: inner query has no reference to outer tables
WHERE balance > (SELECT AVG(balance) FROM accounts)

-- Correlated: inner query references outer alias 't'
WHERE t.amount > (SELECT AVG(x.amount) FROM transactions x
                   WHERE x.account_id = t.account_id)

Why are correlated subqueries slow on large tables?

The naive execution model walks each outer row and runs the inner query for that row. If the outer query returns 1 million rows and the inner query scans a table each time, that is 1 million inner executions. Without a supporting index, each inner scan is expensive.

-- 1 million transactions, each triggers an inner AVG scan
-- Without an index: each inner query scans the full transactions table
-- Total work: 1M x full_scan = extremely slow

SELECT t.id, t.amount
FROM   transactions t
WHERE  t.amount > (
    SELECT AVG(x.amount)
    FROM   transactions x
    WHERE  x.account_id = t.account_id  -- no index on account_id = slow
);

How do you fix the performance?

Two remedies: an index on the correlated column, and rewriting to a join or window function.

-- Remedy 1: index on the correlated predicate
CREATE INDEX idx_txn_account ON transactions (account_id);
-- Now each inner query does a cheap index seek instead of a full scan

-- Remedy 2: rewrite with a window function (one pass, no per-row query)
SELECT id, account_id, amount
FROM (
    SELECT t.*,
           AVG(amount) OVER (PARTITION BY account_id) AS acct_avg
    FROM   transactions t
) sub
WHERE amount > acct_avg;

 id | account_id | amount
----+------------+---------
  1 | SAV2001    | 80000.00   (Rajesh's avg: 55000)
  5 | SAV2002    | 95000.00   (Priya's avg: 60000)

The window function computes each account's average once for all its rows in a single pass, which is dramatically faster.

When is a correlated subquery the right choice?

EXISTS and NOT EXISTS are the most common correlated patterns, and they are often the best choice for semi-join semantics. EXISTS short-circuits on the first match, so it can be faster than a JOIN plus DISTINCT.

-- EXISTS: accounts that have at least one high-value transaction
SELECT a.account_id, a.holder_name
FROM   accounts a
WHERE  EXISTS (
    SELECT 1
    FROM   transactions t
    WHERE  t.account_id = a.account_id
      AND  t.amount > 100000
);

-- Equivalent JOIN (may need DISTINCT if account has multiple matches)
SELECT DISTINCT a.account_id, a.holder_name
FROM   accounts a
JOIN   transactions t ON t.account_id = a.account_id
WHERE  t.amount > 100000;

How does the optimizer handle correlated subqueries?

Modern optimizers often decorrelate the subquery, rewriting it into a join internally. You can verify this by reading the EXPLAIN plan. If the plan shows a join instead of a nested loop with a sub-plan, the optimizer successfully decorrelated.

EXPLAIN ANALYZE
SELECT t.id, t.amount
FROM   transactions t
WHERE  t.amount > (
    SELECT AVG(x.amount) FROM transactions x
    WHERE  x.account_id = t.account_id
);

-- Look for: Hash Join or Merge Join (decorrelated)
-- Bad sign: Nested Loop with SubPlan (not decorrelated)

How do you implement this in Java?

Rajesh runs the "transactions above own account average" query from a Spring service.

package com.bank.service;

import java.math.BigDecimal;
import java.sql.Connection;
import java.sql.PreparedStatement;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.List;

public class AboveAverageTransactionService {

    // Window function approach (preferred)
    private static final String SQL =
        "SELECT id, account_id, amount FROM (" +
        "  SELECT t.*, AVG(amount) OVER (PARTITION BY account_id) AS acct_avg" +
        "  FROM transactions t" +
        ") sub WHERE amount > acct_avg";

    public List<String> getAboveAverageTransactions(Connection conn) throws Exception {
        List<String> results = new ArrayList<>();
        try (PreparedStatement ps = conn.prepareStatement(SQL);
             ResultSet rs = ps.executeQuery()) {
            while (rs.next()) {
                results.add(rs.getString("account_id")
                    + " : " + rs.getBigDecimal("amount"));
            }
        }
        return results;
    }
}

What should a senior engineer know?

• The simplest tell for a correlated subquery is the presence of an outer table alias in the inner query.
• EXISTS is often the best correlated pattern because it short-circuits on the first match.
• For per-group aggregate comparisons, prefer a window function over a correlated subquery.
• Always verify with EXPLAIN whether the optimizer decorrelated the subquery; if not, rewrite manually.
• NOT EXISTS is safer than NOT IN when NULLs are possible.

What are common interview follow-up questions?

• Can a correlated subquery appear in the SELECT list? (Yes, as a scalar correlated subquery that produces one value per outer row.)
• How does a LATERAL join relate to a correlated subquery? (LATERAL lets you reference the outer query in a FROM-clause subquery, combining derived table and correlation.)
• What is the O() complexity of a naive correlated subquery? (O(N x M) where N is outer rows and M is inner scan cost.)