Why can a query engine usually turn a NOT EXISTS subquery into a plain anti-join, while a NOT IN subquery over a nullable column often cannot be flattened the same way?
answer
- NOT EXISTS -> clean anti-join
- NOT IN = AND-chain of <>, three-valued
- one NULL inside -> whole predicate never TRUE -> empty result
- optimizer needs NOT NULL proof to flatten
- otherwise null-aware anti-join or per-row
basics
~20 sNOT EXISTS is a clean 'no matching row' test, which maps directly onto an anti-join. NOT IN uses three-valued comparison: a single NULL in the subquery makes the predicate UNKNOWN for every outer row, so the engine must either prove both columns are NOT NULL or emit a costlier null-aware anti-join.
solid answer
~50 sAn **anti-join** emits outer rows that have no matching inner row - exactly the meaning of `NOT EXISTS`, so the transform is direct and the operator can short-circuit as soon as one match is found. `NOT IN` is not the same predicate. It expands to a chain of inequality comparisons combined with AND, and comparing anything to NULL yields UNKNOWN rather than TRUE or FALSE. So if the subquery produces even one NULL, no outer row can ever satisfy the predicate - the result is empty regardless of data. A plain anti-join would return rows, so the transform is unsound. The optimizer's options: prove non-nullability from schema metadata (`NOT NULL` constraints or an added `IS NOT NULL` filter) and then flatten normally; or emit a **null-aware anti-join** (sometimes called a null-aware left anti semi join), which cannot short-circuit as cheaply and often degrades to something close to per-row evaluation. Practical rule: prefer `NOT EXISTS`, or declare the columns `NOT NULL`, and the plan you want appears.
code
sql · 12 lines-- flattens to a plain anti-join
SELECT c.id FROM customers c
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id);
-- returns ZERO rows if orders.customer_id contains any NULL
SELECT c.id FROM customers c
WHERE c.id NOT IN (SELECT o.customer_id FROM orders o);
-- guarded form the optimizer can flatten
SELECT c.id FROM customers c
WHERE c.id NOT IN (SELECT o.customer_id FROM orders o
WHERE o.customer_id IS NOT NULL);go deeper
Know that NOT EXISTS is the safe form and that a single NULL can make NOT IN return nothing.
Explain the AND-chain expansion and UNKNOWN, and say the optimizer needs proven non-nullability to emit a plain anti-join.
Add the null-aware anti-join fallback, how to spot it in a plan, and that NOT NULL constraints are optimizer inputs enabling the transform.
Position it as a schema-design argument: nullable keys cost both correctness clarity and whole classes of rewrites; set a convention and enforce it.
## Two predicates that look alike `NOT EXISTS (SELECT 1 FROM s WHERE s.k = r.k)` asks: are there zero matching rows? The answer is TRUE or FALSE, never UNKNOWN, because `EXISTS` is a cardinality test on the subquery result. `r.k NOT IN (SELECT k FROM s)` is defined as `NOT (r.k = k1 OR r.k = k2 OR ...)`, equivalently `r.k <> k1 AND r.k <> k2 AND ...`. Each comparison sits in three-valued logic, where a comparison with NULL evaluates to UNKNOWN rather than TRUE or FALSE. WHERE keeps only rows whose predicate is TRUE. ## The consequence for the rewrite If any `ki` is NULL, then `r.k <> ki` is UNKNOWN. An AND chain containing UNKNOWN is either FALSE (if some other conjunct is FALSE) or UNKNOWN - it can never be TRUE. So the whole `NOT IN` predicate is unsatisfiable and the query returns zero rows, for every outer row, whatever the data. A plain anti-join, which returns outer rows with no matching key, would return a non-empty result. The two are not equivalent, so the optimizer is forbidden from making that substitution. The same asymmetry does not affect the positive form: `IN` and `EXISTS` both flatten to a semi-join, because a NULL in the inner set simply fails to match and drops out - it cannot flip a TRUE to something else. ## What the optimizer can do instead 1. **Prove non-nullability.** If the subquery column is declared `NOT NULL`, or the subquery carries an `IS NOT NULL` filter, and the outer column is likewise known non-null, the three-valued hazard disappears and the optimizer legally emits a normal anti-join. This is why schema constraints are optimizer inputs, not just data-integrity rules. 2. **Emit a null-aware anti-join.** A special operator that tracks whether the inner side produced any NULL and, if so, returns nothing (and handles NULLs on the outer side per row). It is more expensive: the classic hash anti-join fast paths do not apply cleanly, some engines fall back to a nested-loop-like evaluation per outer row, and on large inputs the difference is orders of magnitude. 3. **Leave it un-flattened**, evaluating the subquery per outer row - the worst outcome. ## Diagnosing it The symptoms are recognizable: a `NOT IN` query is dramatically slower than the equivalent `NOT EXISTS`; the plan shows a null-aware or 'not-in' flavoured anti-join, or a subplan re-executed per row; and adding `WHERE k IS NOT NULL` inside the subquery flips the plan to a hash anti-join. A second symptom is a correctness surprise: the query returns zero rows and someone concludes the data is missing, when in fact one NULL poisoned the predicate. ## Guidance - Default to `NOT EXISTS` for anti-join intent. It has no NULL hazard, it flattens cleanly, and it expresses 'no matching row' directly. - If you must use `NOT IN`, add the `IS NOT NULL` filter inside the subquery, or rely on a declared `NOT NULL` column, so the optimizer can prove safety. - Treat `NOT NULL` constraints as performance features: they let the rewriter apply transforms that are otherwise unsound. A nullable column that is never actually null still blocks the transform, because the optimizer reasons from the schema, not the data. - An outer-join-plus-`IS NULL` formulation (join then keep rows where the inner key is NULL) is a third way to express anti-join intent; it is flatten-friendly but verbose and easy to get wrong when the inner column itself can be NULL. ## Cost intuition With both columns non-null, anti-join costs about the same as a semi-join - one pass over each input plus a hash build. Null-aware handling adds either a global NULL check that can abort the whole result or per-row special casing; when it degrades to re-evaluation you are back to outer_rows x inner_cost.
- Does the same NULL hazard apply to the positive IN form?No. With IN, a NULL in the inner set simply never matches, so it cannot turn a TRUE into UNKNOWN in a way that changes which rows qualify. IN and EXISTS both flatten to a semi-join. The asymmetry exists only because negation turns 'no match found' into a claim that must hold for every inner row.
- How would a NOT NULL constraint on the subquery column change the plan?It gives the optimizer a proof that no NULL can appear, so the three-valued hazard vanishes and it can emit an ordinary hash or merge anti-join with short-circuiting. This is a concrete case where a data-integrity constraint is also a performance feature. Without the constraint the optimizer must assume NULLs are possible even if the table currently has none.
saying these in an interview costs you the question
- Claiming NOT IN and NOT EXISTS are always interchangeable
- Saying the NULL problem only matters if the outer column is NULL
- Thinking 'there are no NULLs in the data today' is enough for the optimizer to flatten
- Explaining the empty result as a bug in the engine rather than three-valued logic
- Believing an anti-join cannot use an index on the inner key