Semi and anti joins

Semi-join: “does a match exist?” — yes/no, no fan-out

Often you don’t want the matched rows from the other table; you only want to know whether a match exists. “Users who have placed at least one order.” A plain JOIN answers this badly: if a user has 50 orders, the join emits that user 50 times, and you have to bolt on DISTINCT to undo the damage. That’s a fan-out followed by a cleanup.

A semi-join is the right tool: it returns each qualifying left row exactly once, regardless of how many matches it has on the right. SQL spells it EXISTS or IN:

-- Users who have at least one order — each user once, never duplicated
SELECT u.id, u.name
FROM users u
WHERE EXISTS (
  SELECT 1 FROM orders o WHERE o.user_id = u.id
);

-- Equivalent semi-join via IN
SELECT u.id, u.name
FROM users u
WHERE u.id IN (SELECT user_id FROM orders);

EXISTS stops scanning the inner side as soon as it finds the first matching row — it’s a short-circuit boolean, not a count. That’s why a semi-join is usually cheaper than JOIN ... DISTINCT: it never builds the duplicated intermediate result just to collapse it again. The planner even shows this as a dedicated Semi Join node in EXPLAIN (the databases track’s join-algorithms lesson covers how it’s executed).

Anti-join: “has no match” — the complement

The mirror of a semi-join is the anti-join: return the left rows that have no match. “Users who have never ordered.” Spelled NOT EXISTS or NOT IN:

-- Users who have never ordered (anti-join via NOT EXISTS)
SELECT u.id, u.name
FROM users u
WHERE NOT EXISTS (
  SELECT 1 FROM orders o WHERE o.user_id = u.id
);

This is the same set as the LEFT JOIN ... WHERE o.id IS NULL pattern from the previous lesson, and the planner often executes them identically (an Anti Join node). NOT EXISTS is the clearest way to express it and is immune to the NULL trap below.

The NOT IN + NULL trap — the reason this lesson exists

NOT IN looks like the natural anti-join, and it works fine — until the subquery returns even one NULL. Then it silently returns zero rows, exactly the production bug from the hook.

-- DANGEROUS: if any order has a NULL user_id, this returns NOTHING
SELECT u.id FROM users u
WHERE u.id NOT IN (SELECT user_id FROM orders);

The cause is three-valued logic. x NOT IN (a, b, NULL) expands to x <> a AND x <> b AND x <> NULL. The last comparison x <> NULL is UNKNOWN, never true, so the whole AND can never be true — at best it’s UNKNOWN, which WHERE discards. One NULL in the list makes the predicate un-satisfiable for every row. There’s no error; the result set just collapses.

NOT EXISTS does not have this flaw: it asks “is there a correlated matching row?” per left row, and a NULL on the right simply fails to match, which is the correct anti-join behavior. Production rule: never write NOT IN against a subquery whose column can be NULL — use NOT EXISTS. (Plain IN is safe; the trap is specific to NOT IN.) If you must keep NOT IN, guard it with WHERE user_id IS NOT NULL inside the subquery — but NOT EXISTS is simpler and faster.