Semi-Join and Anti-Join Plan Shapes #

A cleanup query — find accounts with no orders — has run for twenty minutes, and its plan shows a single Seq Scan on accounts with a Filter: (NOT (hashed SubPlan 1)), or worse, Filter: (NOT (SubPlan 1)) with the subquery executed once per account. The same logic written with NOT EXISTS finishes in four seconds as a Hash Anti Join. The difference is not style; it is which queries the planner is allowed to turn into joins.

Semi- and anti-joins are part of the join list described in join order and collapse limits, which means they can be reordered and given any join algorithm — but only after the planner has converted the subquery. This page covers when that conversion happens.

The Planner Condition #

Semi-join — “return the outer row once if at least one inner row matches.” Produced from:

Anti-join — “return the outer row if no inner row matches.” Produced from:

Not converted — kept as a SubPlan filter:

A SubPlan is either hashed — the subquery runs once and its results go into an in-memory hash table sized against work_mem — or plain, re-executed for every outer row. The planner uses a hashed SubPlan only when it expects the result to fit in work_mem; otherwise it falls back to per-row execution, which is where the twenty-minute runtimes come from.

Which subqueries become joins Three SQL forms on the left route to plan shapes on the right. EXISTS and IN become a semi join. NOT EXISTS becomes an anti join. NOT IN stays a SubPlan filter, which is hashed when the result fits in work_mem and executed once per outer row when it does not. EXISTS / IN (subquery) NOT EXISTS NOT IN (subquery) Hash / Merge / Nested Loop Semi Join Hash / Merge / Nested Loop Anti Join Filter: NOT (SubPlan) hashed if it fits work_mem, else per row only the join shapes take part in join-order search and algorithm choice

Annotated EXPLAIN Evidence #

The unconverted form:

EXPLAIN (ANALYZE, BUFFERS)
SELECT a.id FROM accounts a
WHERE a.id NOT IN (SELECT o.account_id FROM orders o);
Seq Scan on accounts a  (actual time=1204210.6..1204388.1 rows=18220 loops=1)
  Filter: (NOT (SubPlan 1))                         -- not hashed: re-run per account
  Rows Removed by Filter: 2381780
  SubPlan 1
    ->  Materialize  (actual time=0.01..0.49 rows=… loops=2400000)
          ->  Seq Scan on orders o  (actual rows=94022110 loops=1)
Execution Time: 1204392.8 ms
-- Materialize loops=2400000 → the stored orders list was searched once per account row
-- the planner declined a hashed SubPlan because 94M account_ids would not fit in work_mem

The converted form:

EXPLAIN (ANALYZE, BUFFERS)
SELECT a.id FROM accounts a
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.account_id = a.id);
Hash Right Anti Join  (actual time=3310.2..4102.7 rows=18220 loops=1)
  Hash Cond: (o.account_id = a.id)
  ->  Seq Scan on orders o  (actual rows=94022110 loops=1)
  ->  Hash  (actual rows=2400000 loops=1)
        Buckets: 4194304  Batches: 1  Memory Usage: 117188kB
        ->  Seq Scan on accounts a  (actual rows=2400000 loops=1)
Execution Time: 4118.4 ms
-- "Right" → the hash is built on accounts (the preserved side), orders probes it
-- unmatched hash entries are emitted at the end

With an index on orders(account_id) and a small outer set, the planner may pick Nested Loop Anti Join with an Index Only Scan on the inner side instead — the same logical operation with different physical costs, described in merge join vs nested loop.

Four lines that tell the shapes apart Four plan lines are annotated. Filter NOT SubPlan means the subquery was not converted. Materialize with 2.4 million loops means per-row evaluation. Hash Right Anti Join means the conversion happened. Hash Cond shows the join key used. Filter: (NOT (SubPlan 1)) not converted to a join Materialize (loops=2400000) evaluated once per outer row Hash Right Anti Join converted; hash built on accounts Hash Cond: (o.account_id = a.id) one pass over each side

Step-by-Step Resolution #

  1. Find SubPlan in a Filter. Search plan text for SubPlan or hashed SubPlan. A non-hashed SubPlan with loops= equal to the outer row count is the urgent case.

  2. Check nullability of the subquery column.

    SELECT attnotnull FROM pg_attribute
WHERE attrelid = 'orders'::regclass AND attname = 'account_id';
SELECT count(*) FROM orders WHERE account_id IS NULL;

  3. Rewrite NOT IN as NOT EXISTS. If the column is non-nullable, the results are identical. If it is nullable, decide which semantics you actually wanted — almost always the NOT EXISTS behaviour, where null order rows simply do not match any account.

    SELECT a.id FROM accounts a
WHERE NOT EXISTS (SELECT 1 FROM orders o WHERE o.account_id = a.id);

  4. Confirm the join shape. Look for Anti Join in the node name and the join condition in Hash Cond, Merge Cond or the inner Index Cond.

  5. Make the inner side cheap. For a nested-loop anti-join, an index on the correlated column makes each probe an index-only lookup. For a hash anti-join, check Batches: on the Hash node; spills behave exactly like the hash join batch spills of an inner join.

Per-row subquery versus one join pass Top row: each of 2.4 million account rows triggers its own pass over the orders subquery result, drawn as many small repeated boxes. Bottom row: accounts are hashed once and orders are scanned once to probe the hash, drawn as two single boxes. NOT IN · SubPlan … × 2,400,000 passes NOT EXISTS · Anti Join hash accounts once scan orders once 1,204,393 ms → 4,118 ms on the same data

Before and After #

-- BEFORE: NOT IN, non-hashed SubPlan
Seq Scan on accounts  Filter: (NOT (SubPlan 1))  Materialize loops=2400000     Execution Time: 1204392.8 ms

-- AFTER: NOT EXISTS
Hash Right Anti Join  Hash Cond: (o.account_id = a.id)  Batches: 1         Execution Time: 4118.4 ms

Common Pitfalls #

Changing results by rewriting a nullable NOT IN. If the subquery really returns nulls, NOT IN returns zero rows and NOT EXISTS returns some. Diagnostic signal: the “fixed” query returns rows that the original never did. Fix: decide the intended semantics explicitly; add WHERE o.account_id IS NOT NULL inside the original if you must preserve NOT IN meaning while enabling analysis.

The LEFT JOIN … IS NULL form on a nullable column. The anti-join rewrite requires that the tested column is null only because no match occurred. Diagnostic signal: a Hash Left Join with Filter: (o.account_id IS NULL) instead of an anti-join. Fix: test a non-nullable column of the inner table, such as its primary key, or use NOT EXISTS.

Hashed SubPlans that stop being hashed as data grows. A hashed SubPlan is chosen only while the planner expects it to fit in work_mem. Diagnostic signal: a query that slows by orders of magnitude after a table crosses a size, with hashed disappearing from the plan. Fix: rewrite to a join form, which can spill to disk gracefully instead of falling back to per-row execution.

Semi-join estimates that drive a bad order. Semi-join selectivity depends on distinct counts of the join key, so an underestimated n_distinct distorts it. Diagnostic signal: a Semi Join whose rows= is far below actual rows. Fix: check n_distinct and consider an override.

Frequently Asked Questions #

Why is NOT IN slower than NOT EXISTS in PostgreSQL? NOT IN behaves differently when the subquery can return NULL, so the planner cannot rewrite it into an anti-join. It runs as a SubPlan, hashed when the result fits in memory and re-executed per row when it does not.

What does Hash Right Anti Join mean? The hash table is built on the preserved outer side and the other side probes it, emitting unmatched entries at the end. PostgreSQL 16 added it so the smaller side can be hashed; PostgreSQL 18 added the semi-join equivalent.

Are IN and EXISTS planned the same way? Mostly. Both become semi-joins. IN (subquery) can additionally be planned by making the subquery’s output unique and running an inner join, visible as a HashAggregate or Unique under the join.

Up: Join Order and Collapse Limits