Subquery decorrelation

What does decorrelation really buy, and why is NOT IN slow where NOT EXISTS is fast?

CaseConstructed case · Ananya at Kiranamart

NOT IN takes 40 minutes, NOT EXISTS 2 seconds

Ananya compares four pairs of queries that mean the same thing to a human.

... WHERE customer_id NOT IN (SELECT customer_id FROM refunds) takes 40 minutes. The NOT EXISTS version takes 2 seconds. That is a 1,000× difference for the same result.
WHERE year(order_ts) = 2024 scans every partition. WHERE order_ts >= '2024-01-01' AND order_ts < '2025-01-01' reads one year.
A CTE that is referenced twice was fast in one database version and slow in the next.
A materialized view that stores daily revenue exists, is fresh, is correct, and is never used by the queries it should answer.

All four are the planner declining a rewrite it is not allowed to make, or making a choice that does not pay off.

This is the highest-leverage rewrite in the planner, and its value is often described wrongly.

A correlated subquery is, in its meaning, a nested loop: for each row of the outer query, evaluate the inner query. The language has put an execution strategy into the specification. The obvious harm is the cost O(|outer| × cost(inner)). The real harm is structural: a nested plan is opaque to the optimizer. You cannot reorder joins across the nesting boundary, push predicates through it, or apply any of the machinery above to what is inside. Correlation splits the plan space into pieces that cannot be searched together.

So the correct way to see it is: the value of decorrelation is not the speedup. It is that decorrelation returns the query to the search space. The speedup is a consequence.

The mechanics and the corner in each

EXISTS becomes a semi-join (return a row of the outer side if at least one match exists on the other side). NOT EXISTS becomes an anti-join (return it if no match exists). Both are clean.
IN becomes a semi-join. NOT IN becomes an anti-join only if the system can prove the subquery produces no NULLs. The reason: x NOT IN (1, 2, NULL) is never TRUE. For any x, the comparison with NULL gives UNKNOWN, so the whole NOT IN is FALSE or UNKNOWN, and no rows are returned at all. An anti-join would return the rows that have no match, which is a different answer. If non-nullability cannot be proved, the rewrite is illegal. This is why NOT IN on a nullable column is reliably slow across engines while NOT EXISTS is fast. The difference is not execution. It is whether the rewrite was legal.

-- Slow when refunds.customer_id is nullable: the rewrite to an anti-join is not allowed
SELECT * FROM customers WHERE id NOT IN (SELECT customer_id FROM refunds);

-- Fast: NOT EXISTS has no NULL trap, so it becomes an anti-join
SELECT * FROM customers c
WHERE NOT EXISTS (SELECT 1 FROM refunds r WHERE r.customer_id = c.id);

Scalar aggregate subqueries become a group-by plus a left outer join. This carries the count bug. A correlated SELECT COUNT(*) returns 0 for an outer row with no matching inner rows. A left outer join with group-by gives NULL for such a row (there is no group). So naive decorrelation changes the answer from 0 to NULL. Kim identified the problem in 1982, Dayal corrected it, and it is still the standard example of a rewrite that is legal except where it is not.
The general case. Neumann and Kemper showed how to unnest arbitrary correlated queries by pushing a dependent join down until the dependency is resolved. They also showed that every correlated query without non-deterministic functions can, in principle, be flattened.

Why engines differ

The practical consequence is the largest quality separator between optimizers. Coverage of this rewrite varies by orders of magnitude between engines. The same query text can differ 1000× in runtime across systems with identical execution engines, purely because one of them flattened it and the other did not.

It is not unconditional

If the outer side has 3 rows and the inner side has a selective index, the nested loop touches 3 index entries. The decorrelated form materializes the whole inner relation once. So decorrelation belongs to the middle category from From SQL text to a plan: a heuristic applied as a rule, right almost always, not costed, occasionally wrong.

In one sentence: correlation is an execution strategy written into the query language; the real payoff of decorrelation is a flat search space again; and its corners are all places where SQL's NULL and empty-group meaning differs from the join that replaces it.