skip to content

When an optimizer flattens a WHERE EXISTS or WHERE IN subquery, what join shape does it produce, and how does that shape differ from an ordinary inner join?

level: middleimportance: must knowfreq 68%

answer

  1. EXISTS/IN = existential = semi-join
  2. semi-join: left columns only, no duplication
  3. short-circuit on first match
  4. inner join duplicates unless key unique
  5. NOT EXISTS/NOT IN -> anti-join

basics

~20 s

It produces a semi-join: for each outer row it checks whether at least one matching inner row exists, then emits the outer row once and stops probing. An inner join emits one output row per matching pair, so it can duplicate outer rows and it exposes inner columns.

solid answer

~60 s

`EXISTS` and `IN` are existential predicates: they ask whether a match exists, not how many there are. The matching physical operator is a **semi-join** - it joins two inputs but emits only columns from the left (outer) input, emits each qualifying outer row exactly once, and can stop scanning the inner side as soon as the first match is found (short-circuit). An inner join answers a different question: it produces every matching pair. If an outer row matches three inner rows, an inner join yields three output rows and the inner columns are visible. That is why replacing `EXISTS` with an inner join is only equivalent when the join key is unique on the inner side, or when you add `DISTINCT` - which usually costs a sort or hash. Semi-join gets the correct multiplicity for free, plus the early-exit optimization. Semi-joins have the usual physical implementations - hash semi join, merge semi join, nested-loop semi join with an index probe - so the optimizer still cost-picks among them and can often choose which input to build from.

code

sql · 7 lines
sql
-- semi-join intent: one row per order, no inner columns
SELECT o.id, o.total FROM orders o
WHERE EXISTS (SELECT 1 FROM order_items i WHERE i.order_id = o.id);

-- inner join: one row per matching item -> SUM(o.total) is inflated
SELECT o.id, o.total FROM orders o
JOIN order_items i ON i.order_id = o.id;

go deeper

for a junior

Say EXISTS/IN ask 'does a match exist', so each outer row appears at most once, unlike a join that repeats it per match.

for a middle

Name the semi-join operator, its left-only projection, single-emission and short-circuit, and the uniqueness condition under which an inner join is equivalent.

for a senior

Discuss physical variants (hash/merge/nested-loop semi join), estimation advantages, and how flattening lets the semi-join participate in join reordering.

for a principal

Argue for existential predicates as the default style because they encode multiplicity intent, and discuss where you would still force explicit joins for plan stability across engines.

## The existential question `WHERE EXISTS (...)` and `WHERE col IN (...)` both ask a yes/no question per outer row: is there at least one inner row that matches? Nothing about the answer depends on *how many* matches there are, and no inner column is needed in the result. ## The semi-join operator Relational engines have a dedicated operator for exactly that question. A **semi-join** of R and S on predicate p returns the rows of R for which at least one row of S satisfies p. Its defining properties: 1. **Output schema is the left input only.** Inner columns are consumed by the predicate, never projected. 2. **Multiplicity is preserved.** Each qualifying outer row appears exactly once regardless of how many inner rows matched - no duplicate explosion. 3. **Short-circuit.** Evaluation may stop at the first match, so a nested-loop semi join with an index on the inner key does one probe per outer row instead of retrieving the whole match set. Hash semi join builds a hash table on the inner keys and probes once per outer row. ## Compared with an inner join An inner join is a Cartesian product filtered by the predicate: every matching pair becomes an output row, and inner columns are available downstream. Consequences when someone "rewrites EXISTS as a join": - If the inner key is not unique, outer rows are duplicated. Any downstream `SUM`, `COUNT` or `AVG` is then wrong - the classic inflated-total bug. - Adding `DISTINCT` restores the row set but adds a hash or sort over the whole output, and it de-duplicates *all* columns, which can silently remove legitimately duplicate business rows. - If the inner key *is* unique (a primary key), the inner join and the semi-join produce the same rows, and good optimizers recognize this via uniqueness inference and treat them identically. ## The complementary transform `NOT EXISTS` and `NOT IN` flatten to an **anti-join**: emit each outer row that has *no* matching inner row. It also projects only the left input, also emits each outer row once, and also short-circuits - but inverted: it stops as soon as a match is found, and that outer row is discarded. `NOT IN` carries a nullability caveat that `NOT EXISTS` does not. ## Why it matters for performance Before flattening, `EXISTS` is a correlated subquery whose default execution is once per outer row. After flattening to a hash semi join, both inputs are scanned once. On large tables that is the difference between O(N x M) probes and O(N + M) work. The flattened form also participates in join reordering: the optimizer can decide the semi-join is best done early to reduce cardinality, or late if the inner side is expensive. ## When each form is the better thing to write - Need only a filter, no inner columns: write `EXISTS`/`IN` and let the engine choose a semi-join. This is the intent-revealing form and it cannot duplicate rows. - Need columns from the inner table in the output: you genuinely need a join, because a semi-join cannot project them. - Need to know *how many* matches: neither - you need an aggregate. ## Estimation notes Selectivity of a semi-join is bounded by the left cardinality - it can never exceed it - which is easier to estimate than an inner join's expansion factor. Un-flattened correlated subqueries are notoriously badly estimated by comparison, another reason the flattened shape yields better plans.

  • If you rewrite EXISTS as an inner join, when is the result still identical?
    When the join key is unique on the inner side - a primary key or a unique constraint - so each outer row can match at most one inner row and no duplication occurs. Optimizers infer this from constraint metadata and will treat the two as equivalent. Without that guarantee you need DISTINCT or a grouping to restore the row set, at extra cost.
  • What does a semi-join buy you at execution time that an inner join plus DISTINCT does not?
    It short-circuits: as soon as one match is found for an outer row, the inner probe stops, so it never materializes the full match set. It also never creates the duplicates in the first place, avoiding the hash or sort that DISTINCT requires. The result is less CPU, less memory and no risk of spilling on de-duplication.

A semi-join is a bouncer checking whether your name is on the list - one yes and you are in; an inner join hands you a copy of every matching line on the list.

saying these in an interview costs you the question

  • Saying EXISTS and an inner join are always interchangeable
  • Reaching for DISTINCT to fix duplicates instead of using a semi-join predicate
  • Claiming IN is always slower than EXISTS (or the reverse) as a universal rule
  • Believing a semi-join can project columns from the inner table
  • Assuming the optimizer cannot use an index for the inner side of a semi-join

context

resolving links…