What are the semi-join and anti-join operators, and how does each differ from an ordinary inner join in the shape and the cardinality of its result?

## The two operators Given relations `R` and `S` and a join condition: - **Semi-join**, `R SEMIJOIN S`: every tuple of `R` for which **at least one** tuple of `S` satisfies the condition. - **Anti-join**, `R ANTIJOIN S`: every tuple of `R` for which **no** tuple of `S` satisfies it. They are exact complements with respect to `R`: `(R SEMIJOIN S) UNION (R ANTIJOIN S) = R`, and the two are disjoint. That is a useful check and a useful mental model — the pair is a partition of the left relation according to "does a partner exist". ## What makes them different from an inner join ### Schema: filtering, not combining An inner join is a **combining** operator: its result has the attributes of both operands, and the point is to bring the right side's data into the row. Semi- and anti-join are **filtering** operators: the result schema is exactly `R`'s. The right relation is consulted and then discarded. This is why semi-join is the right operator for questions of the form "which customers have placed an order" and inner join is right for "customer name with each order amount". The first wants a filtered customer list; the second wants a combination. ### Cardinality: no fan-out An inner join multiplies. If a customer has 40 orders, an inner join with orders yields 40 rows for that customer. A semi-join yields one — the customer's own row, unchanged, appearing exactly as often as it did in `R`. This is the property people reach for a `DISTINCT` to recover after writing the join, and it is the wrong fix twice over. First, `DISTINCT` deduplicates the whole row set, which may collapse legitimately distinct rows if the projection is narrower than a key. Second, it turns a streaming plan into a blocking one, after having already done the work of generating rows only to throw them away. ### Early termination Because only existence matters, evaluation of a semi-join may stop scanning the right side as soon as one match is found for a given left tuple, and an anti-join may abandon a left tuple as soon as one match is found. An inner join has no such option — it must produce every matching combination. On a right relation with heavy skew (one key with a million matches), this difference is not marginal. ## Set semantics versus bag semantics The classic identity is ``` R SEMIJOIN S = pi R-attrs ( R JOIN S ) ``` and it is true **under set semantics**, where duplicates collapse. Under the bag semantics that real engines use, the two sides differ: the join multiplies each `R` tuple's multiplicity by its number of matches, and the projection sums rather than eliminates. Only the semi-join preserves `R`'s original multiplicities. This is the single most consequential fact about semi-join, because it explains an entire class of real bugs. "Rewrite this existential subquery as a join, it will be faster" is unsound in general: it is valid only if the join key is unique on the probed side, or if an explicit duplicate elimination is added. When the key **is** unique — a foreign key to a primary key, the common case — no fan-out is possible and the rewrite is safe. Optimizers rely on exactly this uniqueness inference. The corresponding identity for anti-join involves difference, which is the formal reason anti-join cannot be built from monotone operators: `R ANTIJOIN S = R - (R SEMIJOIN S)`. Adding tuples to `S` can only remove tuples from an anti-join's result, and only difference-like operators are non-monotone. ## Anti-join specifics Anti-join is the operator behind every "find the orphans" question: customers with no orders, records with no matching reference, items missing from a target system during a reconciliation. It is inherently harder to evaluate than a semi-join in one respect — you cannot conclude that a left tuple qualifies until the **entire** relevant portion of `S` has been checked, whereas a semi-join concludes on the first hit. It can still abandon early in the negative direction: one match is enough to disqualify. Anti-join is also where null handling becomes treacherous in practice, because a formulation that treats an unknown comparison as a non-match behaves differently from one that treats the presence of any null as poisoning the whole test. The algebra itself is clean — no match means no match — but the surface predicates used to express it are not all equivalent, which is why practitioners have a strong preference among them. ## Cardinality and cost intuition - `0 <= |R SEMIJOIN S| <= |R|` - `0 <= |R ANTIJOIN S| <= |R|` - `|R SEMIJOIN S| + |R ANTIJOIN S| = |R|` Because the output is bounded by `|R|` regardless of how large `S` is, a semi-join is a **reducer**: it can only shrink. That is why semi-joins are valuable early in a plan and why distributed query processing uses semi-join reduction — shipping only the join-key values of one side to filter the other before moving any real data. ## Interview framing Define both, state the two structural differences (schema, no fan-out), give the partition identity, and then land the bag-semantics point about when the join rewrite is unsound. Mentioning early termination and the reducer property shows you have thought about evaluation, not just notation.