A colleague rewrites an existential subquery into an inner join, claiming it is 'the same thing but simpler'. Under what conditions does that rewrite change the answer, and what has to be added to make it equivalent?
answer
- semi-join filters; inner join combines and multiplies
- identity holds for sets, fails for bags
- safe if inner-side key is unique, or add dedup on outer key
- dedup is blocking; semi-join streams and stops early
- stray DISTINCT = fan-out confession
basics
~20 sIt changes the answer whenever an outer row matches more than one inner row: the semi-join returns that row once, the inner join returns it once per match. Equivalence requires either a proof that the join key is unique on the inner side, or an explicit duplicate elimination on the outer row's identity after the join.
solid answer
~60 sAn existential subquery denotes a **semi-join**: filter the outer relation, keep each qualifying row exactly once. An inner join **combines**: it emits one result row per matching pair. The two coincide only when each outer row has at most one match. So the rewrite is safe when: - the join key is **unique on the inner side** — a primary key or unique constraint, or a preceding grouping that guarantees one row per key; or - a duplicate elimination is applied after the join on a key of the outer relation. It is unsafe otherwise, and the failure is silent: no error, just inflated row counts and — much worse — inflated downstream `COUNT` and `SUM` values that look plausible. Cost matters too. Even when the dedup makes it correct, it is usually slower: you generate rows in order to throw them away, and the dedup is a blocking, memory-consuming step, whereas a semi-join streams and can stop at the first match per outer row. The right advice: keep the existential form and let the optimizer choose.
code
text · 5 linesCust = { (1, ann) : 1 } Ord for cust 1 = 40 rows
semi-join -> { (1, ann) : 1 }
pi cust-attrs (join) -> { (1, ann) : 40 }
COUNT(*) above the join -> 40 instead of 1go deeper
Recognise that joining to a child table can repeat parent rows, and that an existential filter does not.
State the operator mismatch and the count arithmetic, and name deduplication or inner-side uniqueness as the fixes.
Add why the corrected rewrite is still usually slower — blocking dedup, lost early termination, unbounded intermediate — and how decorrelation makes the manual rewrite pointless.
Turn it into a review standard: multiplicity-sensitive consumers, uniqueness metadata as the licence for the rewrite, and treating a stray DISTINCT as a signal of an upstream fan-out.
## The claim and why it is half true "An existential subquery is just a join" is a very common belief, and it comes from a real identity — but one that holds under **set** semantics, where duplicate rows collapse automatically: ``` R SEMIJOIN S = pi R-attrs ( R JOIN S ) -- true for sets ``` Real query engines evaluate **bag** semantics, where every row carries a multiplicity and projection sums multiplicities rather than eliminating them. Under bags the identity fails: ``` count in join = count_R * (number of matching S rows) count in semi-join = count_R ``` The rewrite therefore preserves *which* outer rows appear but not *how many times* they appear, and any consumer that is sensitive to multiplicity sees a different answer. ## Concretely `Cust` has one row for customer 1. `Ord` has 40 rows for customer 1. - Semi-join: 1 row. "Customer 1 has ordered." - Inner join projected back to customer columns: 40 identical rows. Now put an aggregate above it. `COUNT(*)` reports 40 customers instead of 1. `SUM(credit_limit)` reports forty times the true figure. Nothing errors; the numbers are simply wrong, and they are wrong in a way that looks like a data-volume story rather than a bug. This is the classic "our dashboard revenue is 4x too high" incident, and its root cause is almost always a fan-out join upstream of an aggregate. A `LIMIT` above the join is a second sensitive consumer: the duplicates crowd out the rows that should have appeared, so the result set changes in content, not merely in length. ## The two conditions for equivalence ### 1. Uniqueness on the inner side If the join key is unique in the inner relation, no outer row can match twice, so multiplication by one is the identity and the rewrite is sound with nothing added. This is the case whenever the join follows a foreign key **into** a primary key — child to parent. It is exactly what an optimizer proves before turning a semi-join into a plain join, using primary-key and unique-constraint metadata, and it is why the same rewrite that is safe in one direction of a relationship is unsafe in the other. A common source of confusion is that both directions look identical in query text; only the constraint metadata distinguishes them. A preceding aggregation also establishes uniqueness: grouping the inner relation by the join key yields one row per key by construction. This is the honest way to write "customer with their order total" — aggregate first, then join one-to-one. ### 2. Explicit duplicate elimination Adding a distinct on a key of the outer relation restores the correct multiplicity. Two cautions: - It must deduplicate on something that identifies an outer row. Deduplicating a projected subset of columns can collapse genuinely distinct outer rows that happen to agree on the projected attributes — turning a fan-out bug into a data-loss bug. - It is a **blocking** operator. The plan must materialise or sort the fanned-out intermediate before it can emit anything, which destroys pipelining and can spill to disk on a large intermediate. ## Why the rewrite is usually slower even when correct A semi-join has two structural advantages the inner-join form gives up: 1. **Early termination.** Once one match is found for an outer row, the rest of the probe can be abandoned. With skewed keys — one value with a million matching rows — that is the difference between reading one row and reading a million. 2. **Bounded output.** A semi-join's result is bounded by the outer relation's cardinality regardless of the inner relation's size, so it can only shrink the data flowing upward. The join-plus-dedup form first inflates and then shrinks, paying for rows it will discard. The usual justification for the rewrite — "joins are faster than subqueries" — is a folk belief from an era when some optimizers really did execute correlated subqueries row by row. Modern optimizers decorrelate existential subqueries into semi-join operators automatically, so the written form is not what determines the plan. Writing the join manually does not unlock a faster plan; it removes the optimizer's freedom to choose the semi-join. ## The reverse direction The opposite rewrite — replacing a join plus distinct with an existential predicate — is generally a good one, for exactly the reasons above, provided nothing above needs the inner relation's columns. That last condition is the giveaway for which operator was intended: if the query genuinely uses inner columns in its output, it was never a semi-join and the fan-out is correct behaviour, not a bug. ## How to review for this A short checklist that catches most instances: - Does the query use any column from the inner relation in its output? If not, it wanted a filter, not a join. - Is the join key unique on the inner side, by constraint or by a preceding grouping? If you cannot answer immediately, assume it is not. - Is there an aggregate or a limit above the join? Those are the multiplicity-sensitive consumers where the bug becomes visible. - Is there a distinct that appears to exist only to "fix" row counts? That is a fan-out confession, and the fix is usually to restore the existential form. ## Interview framing Name the operator mismatch — semi-join versus join — give the count arithmetic under bag semantics, state the two conditions for equivalence, and finish on the cost argument and the decorrelation point. The strongest version adds the review checklist, because it converts the theory into something a team can apply.
- The rewrite has a DISTINCT added, so it is correct. Is it now a good idea?Usually not. The plan generates the fanned-out rows and then discards them, and the deduplication is a blocking step that must materialise or sort the intermediate before emitting anything. The semi-join form streams, is bounded by the outer relation's size, and can stop probing at the first match, so it does strictly less work.
- Someone argues that joins are faster than correlated subqueries, so the rewrite is worth it. How do you respond?That belief comes from optimizers that executed correlated subqueries row by row. Modern optimizers decorrelate existential subqueries into semi-join operators, so the written form does not dictate the plan. Writing the join by hand does not unlock a better plan; it removes the option of the semi-join and, without a uniqueness guarantee, changes the answer.
- How would you tell from a query alone whether a join or a semi-join was intended?Look at whether any column of the inner relation is used above the join. If none is, the inner relation is being used purely as a filter and the intent was a semi-join. If inner columns appear in the output or in an aggregate, the query genuinely needs the combination and the fan-out is correct behaviour.
Asking "has this customer ever ordered?" versus "list this customer's orders". Answer the first with the second and you get the customer's name printed once per order — then someone counts the names.
saying these in an interview costs you the question
- Asserting the rewrite is always equivalent because 'a semi-join is just a join with a projection'
- Adding DISTINCT to fix row counts without asking why the fan-out happened
- Deduplicating on a projected subset of columns rather than on a key of the outer relation
- Believing correlated subqueries are inherently executed once per outer row in modern engines
- Assuming a foreign-key join is one-to-one in both directions