How do the SQL predicates IN, EXISTS and NOT EXISTS correspond to the semi-join and anti-join operators of relational algebra, and where does that correspondence break down?

## Why there is a correspondence at all A subquery predicate in a filter position has a very particular shape: it tests each candidate outer row and returns a boolean. It cannot add columns to the outer row and it cannot cause an outer row to appear twice. That is precisely the contract of the semi-join and anti-join operators — filtering, non-widening, non-duplicating. So every existential subquery predicate denotes one of those two operators, and optimizers exploit this by rewriting the subquery into a single algebra node instead of evaluating it per row. This rewrite is called **decorrelation** or **subquery unnesting**, and it is one of the highest-value transformations in a modern optimizer. Without it, a correlated subquery is a per-row loop; with it, the whole thing becomes one operator that can be evaluated by hashing or merging over the two inputs. ## The mapping **`EXISTS (correlated subquery)` is a semi-join.** The correlation predicate becomes the join condition; the outer relation is the left operand; the subquery's source is the right. `EXISTS` short-circuits on the first row it finds, which mirrors the semi-join's early termination exactly. The `SELECT` list of an `EXISTS` subquery is irrelevant for this reason — nothing is read from it, only existence is tested. **`x IN (subquery)` is a semi-join** whose condition is equality between `x` and the subquery's single output column. Structurally identical to `EXISTS` with an equality correlation. A subtlety worth knowing: `IN` is *duplicate-insensitive* on the inner side, which is another way of saying it is a semi-join — however many times a value appears in the subquery result, the outer row appears once. **`NOT EXISTS (...)` is an anti-join.** Keep the outer rows for which the correlated search finds nothing. It short-circuits in the negative direction: one inner match is enough to disqualify the outer row. **`NOT IN` is the awkward one.** See below. ## Where the correspondence breaks ### NOT IN and the unknown comparison `NOT IN` is defined as a conjunction of inequality comparisons against every row the subquery returns. If any of those comparisons is **unknown** rather than false — which happens when the subquery produces a null in the compared column — the whole conjunction can never be true, only unknown, and a filter keeps only rows for which the predicate is true. The consequence is stark: a single null anywhere in the subquery's output makes `NOT IN` return **no rows at all**, regardless of the data. That behaviour is not an anti-join. An anti-join asks "does any partner exist"; `NOT IN` asks "is this value different from every produced value, with certainty". They coincide only when nulls cannot occur on either side. An optimizer that wants to turn `NOT IN` into an anti-join must first prove non-nullability, and when it cannot, it is stuck with a more expensive plan that has to track whether a null was seen. Both the correctness surprise and the plan degradation are reasons production code overwhelmingly uses `NOT EXISTS` for anti-join intent. ### The inner-join rewrite The most common wrong "optimization" is turning an `EXISTS` predicate into an inner join with the inner relation, on the grounds that a join is simpler than a subquery. Under bag semantics this changes the answer: the join reproduces each outer row once per matching inner row, whereas the semi-join reproduces it once. The rewrite is sound only when the join key is unique on the inner side — for example a foreign key pointing at a primary key — or when a duplicate elimination is added afterwards, which reintroduces a blocking operator and usually costs more than the semi-join would have. ### Aggregates and the anti-join impostor Another formulation people reach for is an outer join followed by a filter for the null-extended rows. Logically this does compute the anti-join, and some engines even implement anti-join that way internally. Written by hand it is worse: it forces the full join to be materialised before the filter discards most of it, and it loses the early termination that a real anti-join gets. Treat it as an implementation detail an optimizer may choose, not as a query-writing style. ## Why the distinction is worth holding Once you see these predicates as names for algebra operators, several practical rules stop needing memorisation: - **Choosing between them** is choosing an operator. Want a filtered outer relation? Semi-join, so `EXISTS` or `IN`. Want the inner side's columns too? That is genuinely a join, and the fan-out is the correct behaviour. Want orphans? Anti-join, so `NOT EXISTS`. - **Reading a plan** becomes easier: the plan node will say semi-join or anti-join, and you can check it against the operator you intended. A plan showing a plain join where you expected a semi-join means the optimizer proved uniqueness — or that your query really does fan out. - **Correctness reviews** get a checklist: does this predicate duplicate outer rows? Does the subquery column admit nulls? Is the intent existence or combination? ## Interview framing Give the four-row mapping, explain why existential subqueries have the semi/anti shape at all (filtering, non-widening, non-duplicating), then name the two breakdowns: `NOT IN` with nulls and the inner-join rewrite under bag semantics. Mentioning decorrelation as the optimizer's motivation for caring shows you know why the correspondence exists rather than merely that it does.