skip to content

How do the relational algebra's union, intersection and difference map onto SQL's UNION, INTERSECT and EXCEPT, and where does SQL's behaviour differ from pure set semantics?

level: middleimportance: must knowfreq 55%

answer

  1. ∪ ∩ − ↔ UNION / INTERSECT / EXCEPT (MINUS in Oracle)
  2. default forms dedupe = true set semantics
  3. ALL: m+n, min(m,n), max(m−n,0)
  4. UNION ALL pipelined; others sort or hash
  5. INTERSECT binds tighter; EXCEPT is left-associative

basics

~20 s

UNION, INTERSECT and EXCEPT correspond to ∪, ∩ and −, and all three eliminate duplicates, matching set semantics. The ALL variants (UNION ALL, INTERSECT ALL, EXCEPT ALL) keep multiplicities instead, giving bag semantics the algebra has no equivalent for.

solid answer

~50 s

The mapping is direct: `∪` → `UNION`, `∩` → `INTERSECT`, `−` → `EXCEPT` (spelled `MINUS` in some dialects). All three require union-compatible operands, and all three **deduplicate**, so they genuinely behave as set operators. The divergence is the `ALL` family, which exists because SQL tables are bags: - `UNION ALL` concatenates and adds multiplicities — no dedup, no sort, cheapest of the family. - `INTERSECT ALL` keeps `min(m, n)` copies of a row. - `EXCEPT ALL` keeps `max(m − n, 0)` copies. Two further points. Matching is by **not-distinct-from**, so two rows that are null in the same column count as duplicates — unlike a `WHERE` comparison with `=`. And precedence: `INTERSECT` binds tighter than `UNION` and `EXCEPT`, which are left-associative, so mixed expressions need parentheses to be readable and correct. Use `UNION ALL` whenever you know the branches are disjoint — the deduplication is pure cost.

code

sql · 8 lines
sql
-- set semantics: one row per distinct id
SELECT id FROM a UNION SELECT id FROM b;

-- bag semantics: multiplicities added, no sort/hash
SELECT id FROM a UNION ALL SELECT id FROM b;

-- INTERSECT binds tighter than UNION: parenthesise to say what you mean
(SELECT id FROM a UNION SELECT id FROM b) INTERSECT SELECT id FROM c;

go deeper

for a junior

State the three-to-three mapping and the single most important fact: the plain forms remove duplicates, the ALL forms do not.

for a middle

Add the multiplicity arithmetic for the ALL variants, the cost difference between a pipelined UNION ALL and a sorting/hashing UNION, and INTERSECT's precedence.

for a senior

Bring in the not-distinct-from matching rule for nulls, spill risk on large deduplications, and how you justify a UNION ALL with a real disjointness invariant.

for a principal

Discuss where set semantics belong in a pipeline — enforce uniqueness with constraints upstream so downstream unions can be ALL — and the dialect variation you must design around.

## The one-to-one mapping | Algebra | SQL | Result | |---|---|---| | `R ∪ S` | `SELECT … UNION SELECT …` | tuples in either, duplicates removed | | `R ∩ S` | `SELECT … INTERSECT SELECT …` | tuples in both, duplicates removed | | `R − S` | `SELECT … EXCEPT SELECT …` | tuples in the left and not the right, duplicates removed | All three require union-compatible operands: equal column counts with compatible types in corresponding positions, matched **positionally**, with result column names taken from the first branch. Because the default forms deduplicate, these three keywords are the corner of SQL that actually honours set semantics. Everything else in SQL is bag-shaped. ## The ALL variants and multiplicity arithmetic SQL tables are multisets, so the standard also defines bag versions. If a given row appears `m` times on the left and `n` times on the right: - `UNION ALL` → `m + n` copies. - `INTERSECT ALL` → `min(m, n)` copies. - `EXCEPT ALL` → `max(m − n, 0)` copies. The default (non-ALL) forms are equivalent to computing the ALL form and then collapsing every row to one copy. The `min`/`max` arithmetic is worth memorising: it is a favourite follow-up, and it is the correct semantics for reconciliation tasks where the *number* of occurrences matters (e.g. two ledgers that should each contain a payment exactly twice). ## Cost model - `UNION ALL` is a pure concatenation — pipelined, no sorting, no hashing, no memory growth. It is the cheapest possible way to stitch results together. - `UNION`, `INTERSECT`, `EXCEPT` all need to identify equal rows, so the engine sorts both inputs and merges, or builds a hash table on one side. That means memory proportional to distinct rows and a possible spill to temporary storage on large inputs. Hence the standing advice: if you *know* the branches cannot overlap — different date ranges, different source tables with disjoint keys, a partition-by-partition union — write `UNION ALL`. Writing `UNION` "just in case" buys a deduplication you did not need and pays for it on every execution. Conversely, using `UNION ALL` when the branches *can* overlap silently doubles rows and corrupts downstream counts. ## Distinctness, not equality Set operators compare whole rows using an equivalence relation usually described as "is not distinct from". The practical effect concerns nulls: - `UNION` treats two rows that are null in the same positions as duplicates and keeps one. - `EXCEPT` removes a left row that has a null where the right row also has a null in that position. This is different from a comparison predicate, where a null comparison yields unknown rather than true. The set operators need a total notion of "same tuple" to define duplicate elimination at all, so they use distinctness. Expect this as a follow-up whenever nulls are in play. ## Precedence, associativity, and ordering - `INTERSECT` has **higher precedence** than `UNION` and `EXCEPT`. So `A UNION B INTERSECT C` means `A UNION (B INTERSECT C)`. - `UNION` and `EXCEPT` are evaluated **left to right**. Since difference is not associative, `A EXCEPT B EXCEPT C` means `(A EXCEPT B) EXCEPT C`, which is not the same as `A EXCEPT (B EXCEPT C)`. Parenthesise mixed expressions. It costs nothing and removes an entire class of subtle bugs. An `ORDER BY` attached to such an expression applies to the whole result, not to a branch — the branches are unordered relations, consistent with the algebra, where ordering is not part of the model at all. ## Dialect notes The standard spelling of difference is `EXCEPT`; Oracle historically spells it `MINUS` and, in recent versions, also accepts `EXCEPT`. Support for the `ALL` variants of `INTERSECT` and `EXCEPT` is less universal than `UNION ALL`, so check before relying on `min`/`max` multiplicity behaviour in a specific engine. ## The interview-ready summary Say: the three keywords are the algebra's three set operators, they require union-compatible operands matched by position, and they deduplicate by default — which is exactly set semantics. SQL then adds `ALL` variants because its tables are bags, with `m + n`, `min(m, n)` and `max(m − n, 0)` multiplicity rules. Add the cost point (`UNION ALL` is pipelined; the others sort or hash), the null-distinctness rule, and the precedence of `INTERSECT`. That covers everything an interviewer is likely to probe.

  • A row appears 5 times on the left and 2 times on the right. How many copies does each ALL variant produce?
    UNION ALL gives 7 (5 + 2), INTERSECT ALL gives 2 (the minimum), and EXCEPT ALL gives 3 (5 − 2, floored at zero). The non-ALL forms of all three would give exactly 1, because they collapse to distinct rows. These multiplicity rules are the standard's definition of bag set operators.
  • When would you deliberately choose UNION ALL over UNION, and what is the risk?
    Whenever the branches are known to be disjoint — separate date partitions, separate source systems with non-overlapping keys — because the deduplication in plain UNION costs a sort or hash build and buys nothing. The risk is that if the disjointness assumption is wrong, overlapping rows appear more than once and every downstream count or sum is inflated, with no error to warn you. The assumption should be backed by a constraint or a documented invariant, not a hunch.
  • Do the SQL set operators treat two rows containing nulls in the same column as duplicates?
    Yes. Set operators compare rows by distinctness rather than by the equality predicate, so two rows that are null in the same positions count as the same row: UNION keeps one of them, and EXCEPT will remove such a left row when a matching right row exists. This differs from a WHERE clause, where comparing two nulls yields unknown and the row is filtered out.

saying these in an interview costs you the question

  • Believing UNION keeps duplicates and UNION ALL removes them — the reverse of the truth.
  • Assuming UNION ALL and UNION cost the same because they return similar data.
  • Thinking EXCEPT is symmetric, or that chained EXCEPTs group right-to-left.
  • Expecting nulls never to match under set operators because null = null is unknown.
  • Reaching for UNION defensively on branches that are provably disjoint.

context

resolving links…