Semi- and Anti-Join Patterns

## The question behind the question "Customers who have placed at least one order" sounds like it needs both tables, and beginners reach for a join because orders are mentioned. But look at the requested result: it lists **customers**, and each customer appears once or not at all. Nothing from `orders` is projected. The orders table is only being consulted to answer a yes/no question per customer. That shape — filter the left table by whether a match exists on the right — is the **semi-join**, and SQL spells it with a predicate, not with a `JOIN` keyword. ## What a join is defined to do `FROM customers c JOIN orders o ON o.customer_id = c.id` conceptually forms every combination of a customer row with an order row and keeps the combinations where the `ON` predicate is TRUE. If customer 1 has five orders, five combinations survive, and the output has five rows whose `c.name` is identical. This row multiplication (sometimes called fan-out) is the entire point of a join — it is how you get order lines next to their customer. It only looks like a bug when you did not want the order columns in the first place. A useful mental check: **the cardinality of an inner join is unbounded by either input** — it can be larger than both tables. The cardinality of a semi-join is bounded: at most one output row per left row. ## Writing the semi-join ```sql SELECT c.id, c.name FROM customers c WHERE EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id); ``` `EXISTS` takes a subquery and yields TRUE if that subquery would produce **at least one row**, FALSE otherwise. It never yields UNKNOWN, and it never contributes rows or columns to the outer query. The subquery is correlated: `c.id` inside it refers to the customer row currently being tested. The select list inside `EXISTS` is irrelevant — `SELECT 1`, `SELECT *`, `SELECT NULL` all behave identically, because only the presence of rows matters. `SELECT 1` is the conventional spelling. One thing you must *not* write there is an aggregate: `EXISTS (SELECT COUNT(*) FROM orders o WHERE ...)` is always TRUE, because an unqualified aggregate query always returns exactly one row, even when the count is zero. The uncorrelated `IN` form expresses the same semi-join: ```sql SELECT c.id, c.name FROM customers c WHERE c.id IN (SELECT o.customer_id FROM orders o); ``` It is also duplicate-free: `IN` is a predicate over the current customer row, so a customer whose id appears 500 times in the subquery result still passes the predicate once. Both forms answer the question; which reads better is mostly style, and the negative forms (`NOT IN` vs `NOT EXISTS`) are where the two genuinely diverge. ## Why DISTINCT is a patch, not the fix ```sql SELECT DISTINCT c.id, c.name FROM customers c JOIN orders o ON o.customer_id = c.id; ``` This often returns the right rows, and you will see it everywhere. It is a patch because it changes the answer *after* the fact: the query still builds one row per order and then collapses identical projected rows. Two consequences follow. First, the moment you add a column from `orders` to the select list, the duplicates come back — the rows are no longer identical. Second, `DISTINCT` de-duplicates the whole projected row, so if `customers` legitimately contains two identical rows, the join-plus-`DISTINCT` version returns one and the `EXISTS` version returns two. Write what you mean: existence is a filter. ## Choosing between the two shapes Ask what the output row *is*. If one output row = one customer, you want a semi-join (`EXISTS` / `IN`). If one output row = one order (with its customer's name attached), you want the join, and the repetition of the customer name is correct and expected. If one output row = one customer but you also need a number derived from orders, that is a third shape: aggregate the orders, or use a scalar subquery in the select list. ## What the interviewer is checking They want to see that you reason about the **shape of the result set** rather than pattern-matching "two tables mentioned, therefore JOIN". Saying "the join is fine, I'll add DISTINCT" scores much lower than "the requirement is a filter, so I'll write EXISTS; a join would multiply rows because that is what joins do."