Set Operation Plans for INTERSECT and EXCEPT #

A data-quality check compares two 40-million-row queries with EXCEPT and takes six minutes, spilling 9 GB of temporary files. Rewritten as NOT EXISTS, the same check runs in twenty seconds as a hash anti-join with no spill. Set operations are convenient to write and, on large inputs, are usually the most expensive way to express the question.

Sort and hash nodes are covered in sort and hash node analysis. This page covers the set-operation nodes built on them.

The Condition #

UNION, INTERSECT and EXCEPT (without ALL) remove duplicates and compare whole rows:

• UNION is typically executed as Append followed by HashAggregate on all output columns, or by a sort plus Unique.
• INTERSECT and EXCEPT are executed by a SetOp node. Its classic implementation requires both inputs sorted on every output column, so the plan usually contains two Sort nodes; PostgreSQL 18 adds a hashed variant that avoids them when the estimated result fits in the hash memory budget.
• UNION ALL does none of this: it is a plain Append and is always the cheapest of the four.

Three properties make set operations expensive on large inputs:

• They compare every column, so wide rows are sorted or hashed in full.
• They deduplicate, which costs even when the inputs contain no duplicates.
• They lose selectivity information: each branch is planned independently, so a filter that would be very selective in a join cannot be pushed across the set operation.

The usual rewrites are cheaper because they let the planner use join algorithms and push filters:

The join forms are compared in semi-join and anti-join plan shapes.

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS)
SELECT customer_id, sku FROM orders_current
EXCEPT
SELECT customer_id, sku FROM orders_archive;

SetOp Except  (actual time=298104.6..341204.2 rows=1204110 loops=1)
  ->  Sort  (actual time=298104.4..318402.6 rows=84020110 loops=1)
        Sort Key: "*SELECT* 1".customer_id, "*SELECT* 1".sku
        Sort Method: external merge  Disk: 9204118kB
        ->  Append  (actual rows=84020110 loops=1)
              ->  Seq Scan on orders_current  (actual rows=42010055 loops=1)
              ->  Seq Scan on orders_archive  (actual rows=42010055 loops=1)
Execution Time: 342108.4 ms
-- both inputs concatenated and sorted together: 84M rows, 9.2 GB spilled

The anti-join rewrite:

EXPLAIN (ANALYZE, BUFFERS)
SELECT DISTINCT c.customer_id, c.sku
FROM orders_current c
WHERE NOT EXISTS (
  SELECT 1 FROM orders_archive a
  WHERE a.customer_id = c.customer_id AND a.sku = c.sku
);

HashAggregate  (actual time=18402.6..19104.2 rows=1204110 loops=1)
  Group Key: c.customer_id, c.sku
  ->  Hash Anti Join  (actual time=8104.2..16204.8 rows=1402118 loops=1)
        Hash Cond: ((c.customer_id = a.customer_id) AND (c.sku = a.sku))
        ->  Seq Scan on orders_current c  (actual rows=42010055 loops=1)
        ->  Hash  (actual rows=42010055 loops=1)
              Buckets: 8388608  Batches: 8  Memory Usage: 262144kB
Execution Time: 19402.1 ms
-- one hash build, one probe pass, no sorting

Step-by-Step Resolution #

1. Identify the set operation in the plan — SetOp, or HashAggregate over an Append for UNION.

2. Check whether deduplication is needed. UNION ALL instead of UNION removes the aggregate entirely when branches are known disjoint, and is by far the most common easy win.

3. Rewrite EXCEPT as NOT EXISTS and INTERSECT as EXISTS, adding DISTINCT only if the source can contain duplicates.

4. Compare column counts. Set operations compare every selected column; the rewrite compares only the join keys, which is often far fewer.

5. Index the correlated columns on the inner side so the anti-join or semi-join has a cheap access path.

6. Size hash memory for the resulting join, following hash_mem_multiplier and the hash memory budget.

7. Verify the results match on a sample before replacing the query: NOT EXISTS and EXCEPT differ when the outer query can produce duplicates, and null handling differs from NOT IN.

Before and After #

-- BEFORE: EXCEPT over two 42M-row queries
SetOp Except → Sort (external merge, 9.2 GB) → Append                Execution Time: 342108.4 ms

-- AFTER: NOT EXISTS anti-join with DISTINCT
HashAggregate → Hash Anti Join  Batches: 8                            Execution Time: 19402.1 ms

When set operations are the right tool #

For small inputs, set operations are clear and cheap enough that rewriting them is not worth the loss of readability. UNION ALL in particular is a first-class construct: it is how partitioned views are expressed, it prunes like a partitioned table, and it adds essentially no cost over its branches — the pushdown rules are in predicate pushdown through UNION ALL views.

The cases worth rewriting are the large ones, and the signal is in the plan: a Sort of tens of millions of rows feeding a SetOp, or a HashAggregate deduplicating rows that were already unique. Both mean the query is paying for a general mechanism where a more specific one exists.

One caution when rewriting: EXCEPT deduplicates its left input, while SELECT … WHERE NOT EXISTS does not. Adding DISTINCT restores the semantics but reintroduces an aggregate; if the left input is known unique — a primary key projection, for example — the DISTINCT can be dropped, which is where most of the remaining time in the example above would go.

Checking equivalence before replacing a query #

Set operations and their join rewrites differ in three ways that matter, and each has a quick test. Duplicates: EXCEPT deduplicates its left input, so compare count(*) of both forms on a sample. Nulls: set operations treat nulls as equal for the purposes of matching rows, whereas a join condition a.col = b.col does not match two nulls — so a rewrite over nullable columns needs IS NOT DISTINCT FROM or explicit null handling. Column lists: set operations compare every selected column positionally, so a rewrite must join on all of them to mean the same thing.

Running both versions against a sample and comparing the results with an EXCEPT in both directions — ironically, the fastest use of the operator — is the reliable check before switching a production query.

Common Pitfalls #

Using UNION when UNION ALL would do. The deduplication is pure cost. Diagnostic signal: a HashAggregate above an Append removing no rows. Fix: UNION ALL.

Forgetting the left-side deduplication. EXCEPT deduplicates; NOT EXISTS does not. Diagnostic signal: more rows after the rewrite. Fix: DISTINCT, or confirm uniqueness.

Comparing wide rows. Set operations compare every column. Diagnostic signal: sorts far larger than the key columns would need. Fix: compare only the identifying columns.

No index on the inner side. The anti-join falls back to hashing everything. Diagnostic signal: a large hash build in the rewrite. Fix: index the correlated columns.

Frequently Asked Questions #

Why is EXCEPT slow in PostgreSQL? #

It executes both branches in full, sorts their combined output on every selected column, and compares the sorted streams in a SetOp node. On large inputs that sort dominates and frequently spills to disk.

Is NOT EXISTS faster than EXCEPT? #

Usually, on large inputs, because the planner can execute it as a hash or merge anti-join without sorting and can push filters into the branches. Remember that EXCEPT also deduplicates its left input, so add DISTINCT if the source can contain duplicates.

Should I use UNION or UNION ALL? #

UNION ALL whenever duplicates are impossible or acceptable, since UNION adds a deduplication step over the combined output that costs a sort or a hash aggregate.

Related #

• Sort and Hash Node Analysis — parent guide: the nodes underneath
• Semi-Join and Anti-Join Plan Shapes — the rewrite targets
• Predicate Pushdown Through UNION ALL Views — why UNION ALL is different

Up: Sort and Hash Node Analysis