Correlated Subqueries, EXISTS and NOT EXISTS

Concept

A correlated subquery references a column from the outer query. It cannot be run on its own, and conceptually it is evaluated once per outer row - which makes it powerful and potentially expensive.

Syntax

SELECT columns
FROM   outer_table o
WHERE  EXISTS (SELECT 1
               FROM   inner_table i
               WHERE  i.foreign_key = o.id);   -- the correlation

Example

-- Customers who have placed at least one order
SELECT c.name, c.country
FROM   customers c
WHERE  EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id);

-- Customers who have never ordered
SELECT c.name, c.country
FROM   customers c
WHERE  NOT EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id);

-- Employees paid more than their own department average
SELECT e.first_name, e.dept_id, e.salary
FROM   employees e
WHERE  e.salary > (SELECT AVG(e2.salary)
                   FROM   employees e2
                   WHERE  e2.dept_id = e.dept_id)
ORDER BY e.dept_id, e.salary DESC;

Explanation

The last query cannot be written with a plain uncorrelated subquery: the threshold is different for every row, because it depends on that row's department. The inner query reads e.dept_id from the outer row, which is what makes it correlated.

EXISTS asks a yes or no question: does at least one matching row exist? It stops at the first match, so it never counts and never cares how many matches there are. That is why SELECT 1 is conventional inside it - the select list is completely ignored. SELECT *, SELECT 1 and SELECT NULL all behave identically.

Why EXISTS is NULL safe

-- NOT IN: breaks if dept_id contains NULL
SELECT name FROM departments
WHERE  id NOT IN (SELECT dept_id FROM employees);          -- returns nothing

-- NOT EXISTS: correct regardless of NULLs
SELECT d.name FROM departments d
WHERE  NOT EXISTS (SELECT 1 FROM employees e WHERE e.dept_id = d.id);

EXISTS returns only TRUE or FALSE, never UNKNOWN. For department 40, the inner query finds no row where e.dept_id = 40 - the row with NULL simply does not match - so EXISTS is FALSE and NOT EXISTS is TRUE. There is no third value to poison the logic.

Cost, and when to rewrite

-- Correlated: conceptually one inner query per customer
SELECT c.name,
       (SELECT COUNT(*) FROM orders o WHERE o.customer_id = c.id) AS order_count
FROM   customers c;

-- Set based: one pass, then a join
SELECT c.name, COALESCE(oc.order_count, 0) AS order_count
FROM   customers c
LEFT JOIN (SELECT customer_id, COUNT(*) AS order_count
           FROM   orders
           GROUP BY customer_id) oc ON oc.customer_id = c.id;

Both are correct. On four customers the difference is invisible; on four million it is the difference between a report that runs and one that does not. Modern optimisers often rewrite the correlated form into a join automatically, but they cannot always do it, especially when the subquery is in the select list.

Important rules

• A correlated subquery cannot be executed on its own - that is the test for whether it is correlated.
• EXISTS and NOT EXISTS never return UNKNOWN, which makes them the safe anti join.
• The select list inside EXISTS is ignored entirely.
• A correlated subquery in the select list must be scalar.
• Correlation makes the inner query dependent, so it usually needs an index on the correlated column to be efficient.

Common mistakes

• Using NOT IN where NOT EXISTS was needed.
• Writing COUNT(*) > 0 in a subquery instead of EXISTS - it counts every matching row when one would have been enough.
• Putting a correlated subquery in the select list of a query over millions of rows.
• Forgetting the correlation condition, turning it into an uncorrelated subquery that is always true.

Best practices

• Use EXISTS for "does it exist", NOT EXISTS for "does it not", and a join when you need the matching data itself.
• Index the column the subquery correlates on - usually the foreign key.
• Rewrite select list subqueries as pre aggregated joins when the outer table is large.
• Write SELECT 1 inside EXISTS; it signals to the reader that the columns are irrelevant.

Practice

1. Find every department that has at least one employee earning over 100000, using EXISTS.
2. Find every product never included in any order, using NOT EXISTS.
3. Rewrite SELECT c.name, (SELECT SUM(total) FROM orders o WHERE o.customer_id = c.id) FROM customers c as a pre aggregated left join.