Set Operations in SQL

A relational query's result is formally a relation instance, but SQL implementations return it as an ordered list of rows that may repeat — a bag (multiset), not a set. The set operators `UNION`, `INTERSECT`, and `EXCEPT` (called `MINUS` in some dialects such as Oracle) take two such bags, produced by two `SELECT` statements, and combine them positionally by column, not by name. For this to be meaningful, the two operand queries must be union-compatible: they must return the same number of columns, and each corresponding pair of columns must have compatible types (the same type, or types with an implicit conversion, such as `INT` and `DECIMAL`). Column names in the output are taken from the first `SELECT`. By default, all three operators enforce set semantics: the result contains no duplicate rows, even if the inputs did. `UNION` computes the set union (rows appearing in either input), `INTERSECT` computes the set intersection (rows appearing in both), and `EXCEPT` computes the set difference (rows in the first input but not the second). Each operator additionally has an `ALL` form that instead enforces bag (multiset) semantics, preserving and combining duplicate counts using specific rules given below. Two rows are considered "the same" for these purposes using a notion of equality that treats two `NULL` values as matching each other — this is a deliberate, documented exception to the usual three-valued `NULL` logic used in `WHERE` predicates, adopted so that duplicate elimination and multiset matching behave predictably. Formally, if $r_1$ and $r_2$ are the multiset results of the two operand queries, and $c_1(t)$, $c_2(t)$ denote the multiplicity (count of occurrences) of a distinct row $t$ in each, the multiplicity of $t$ in the combined result is defined as:

The plain (non-`ALL`) operators are recovered by first computing the above and then capping every nonzero multiplicity at 1 — equivalently, `UNION` = distinct rows with multiplicity $\ge 1$ in either, `INTERSECT` = distinct rows with multiplicity $\ge 1$ in both, `EXCEPT` = distinct rows in $r_1$ whose multiplicity in $r_2$ is 0.

Conceptually every set operation is evaluated in three phases: (1) evaluate the left `SELECT`, (2) evaluate the right `SELECT`, (3) combine the two intermediate bags according to the operator's rule. The interesting engineering question is how an engine efficiently determines, for each row, its multiplicity in each side, without a naive $O(n \cdot m)$ pairwise comparison. Two standard implementation strategies exist, mirroring the two classical strategies for duplicate elimination and for joins: sort-based and hash-based.

Sort-based strategy. Sort both intermediate results on all columns (a total order, treating `NULL` as a value that sorts consistently, e.g., lowest). Then perform a single merge-like pass, similar to merging two sorted runs in external sort or to a sort-merge join, simultaneously counting how many consecutive equal rows occur on each side (their local multiplicities), and applying the arithmetic rule from above to decide how many copies of that row (if any) go to the output.

Hash-based strategy. Build an in-memory (or partitioned, if data is large) hash table over one input, mapping each distinct row to its multiplicity. Then scan the other input, probing the hash table and updating counts, again applying the arithmetic rule. This mirrors hash-based duplicate elimination and hash joins. ``` // Sort-based evaluation of a binary set operator // op ∈ { UNION, UNION ALL, INTERSECT, INTERSECT ALL, EXCEPT, EXCEPT ALL } function EVALUATE_SET_OP(op, Q1, Q2): R1 <- SORT(EXECUTE(Q1)) // sort on all columns, NULL treated as a value R2 <- SORT(EXECUTE(Q2)) result <- empty list i <- 0; j <- 0 while i < len(R1) or j < len(R2): // Determine the next distinct row value 't' to consider if j >= len(R2) or (i < len(R1) and R1[i] < R2[j]): t <- R1[i]; side <- LEFT_ONLY else if i >= len(R1) or (j < len(R2) and R2[j] < R1[i]): t <- R2[j]; side <- RIGHT_ONLY else: t <- R1[i]; side <- BOTH // Count consecutive occurrences of t on each side c1 <- 0 while i < len(R1) and R1[i] == t: c1 <- c1 + 1; i <- i + 1 c2 <- 0 while j < len(R2) and R2[j] == t: c2 <- c2 + 1; j <- j + 1 // Apply the operator's multiplicity rule m <- MULTIPLICITY(op, c1, c2) append t to result, m times return result function MULTIPLICITY(op, c1, c2): if op == UNION ALL: return c1 + c2 if op == UNION: return 1 if (c1 + c2) > 0 else 0 if op == INTERSECT ALL: return min(c1, c2) if op == INTERSECT: return 1 if min(c1, c2) > 0 else 0 if op == EXCEPT ALL: return max(c1 - c2, 0) if op == EXCEPT: return 1 if max(c1 - c2, 0) > 0 else 0 ``` Walking through the algorithm: after sorting, all equal rows are contiguous, so a single linear merge pass (the same technique as merging two sorted lists) suffices to discover, for every distinct row value that appears in either input, its exact multiplicity on each side. The `MULTIPLICITY` function is a pure lookup table implementing the four formulas from the previous section; the plain operators are simply the "at most 1" clipping of their `ALL` counterparts. Real engines often fuse this with an existing sort that was already needed (e.g., for an `ORDER BY`) or substitute the hash-based version when one input is small enough to fit in memory, avoiding the sort entirely — this is directly analogous to the choice between sort-merge join and hash join for the Nested Subqueries machinery that also needs to compare tuples for equality.

Time complexity. Let $n = |R_1|$ and $m = |R_2|$ be the sizes of the two operand results, and let $k$ be the number of columns (the tuple width). The sort-based strategy pays $O(n \log n)$ and $O(m \log m)$ to sort each side (each comparison costs $O(k)$, typically treated as a constant factor for fixed schemas), plus a single $O(n + m)$ linear merge pass. Total: $O((n \log n + m \log m)\cdot k)$. The hash-based strategy pays expected $O(n)$ to build a hash table on the smaller side and expected $O(m)$ to probe with the other, giving expected $O(n + m)$ time — asymptotically better, at the cost of worst-case hash-collision degradation and the requirement that one side fit comfortably in memory (or be partitioned recursively, as in hybrid hash join, when it does not).

Space complexity. The sort-based approach needs $O(n + m)$ space if done in memory, or $O(\text{page count})$ auxiliary space if implemented as an external merge sort spilling to disk. The hash-based approach needs $O(\min(n, m))$ space for the hash table (build the table on the smaller input to minimize memory footprint), plus whatever streaming buffer is used for the probe side.

Correctness argument. The proof of correctness is essentially an invariant on the merge loop. After sorting, define the invariant: at the start of each loop iteration, every distinct row strictly less than both `R1[i]` and `R2[j]` (under the sort order) has already been fully processed and emitted with the correct multiplicity, and no row has been double-counted. This holds initially (vacuously, before any row is processed) and is preserved by each iteration, because the loop always selects the globally smallest remaining distinct row value `t` — whichever of `R1[i]`, `R2[j]` is smaller, or both if equal — and consumes all contiguous copies of `t` on both sides before moving on (this is safe precisely because both arrays are sorted, so equal values are guaranteed contiguous). Since `c1` and `c2` as computed are exactly the true multiplicities of `t` in the full remaining suffixes of `R1` and `R2` (not just prefixes), the `MULTIPLICITY(op, c1, c2)` formula computes the operator's defining arithmetic exactly, matching the mathematical definitions of $c_{\text{UNION ALL}}$, $c_{\text{INTERSECT ALL}}$, and $c_{\text{EXCEPT ALL}}$ given earlier. Termination follows because each iteration strictly advances `i` or `j` (by at least one), and the loop halts once both pointers reach the end, having then visited every element of both arrays exactly once.

Tradeoffs. The default (non-`ALL`) operators require a full duplicate-elimination pass, which costs the $O(n\log n)$ sort or hash build even when the caller does not actually care about duplicates in their own data — if the operand queries are already known to be duplicate-free (e.g., selecting a primary key), `UNION ALL` is strictly cheaper and semantically identical to `UNION`, and query authors should prefer it whenever duplicates are impossible or irrelevant. Conversely, using `UNION ALL` when duplicates can occur silently changes the answer, which is the most common real-world bug with these operators (see pitfalls below). There is no way to avoid at least an $O(n+m)$ pass over both inputs, since correctness requires inspecting every row at least once — this lower bound is unavoidable for any correct algorithm, matching the trivial fact that you cannot correctly compute a function of the entire input without reading the entire input.

Consider two small tables from a university database.

Enrolled_DB (students in Databases)

Enrolled_OS (students in Operating Systems)

(Assume `Cy` appears twice in `Enrolled_DB` because of a duplicate lab-section join upstream, and `Bo` appears twice in `Enrolled_OS` for the same reason — this is realistic when the operand queries themselves are joins that can produce duplicates.) Multiplicities: `c1(Amy)=1, c1(Bo)=1, c1(Cy)=2, c1(Dee)=0`; `c2(Amy)=1, c2(Bo)=2, c2(Cy)=0, c2(Dee)=1`. ```sql SELECT student FROM Enrolled_DB UNION SELECT student FROM Enrolled_OS; ```

Result: `{Amy, Bo, Cy, Dee}` — 4 rows, no duplicates, even though `Bo` and `Cy` had multiplicities greater than one in the inputs. ```sql SELECT student FROM Enrolled_DB UNION ALL SELECT student FROM Enrolled_OS; ``` Result multiplicities: `Amy: 1+1=2`, `Bo: 1+2=3`, `Cy: 2+0=2`, `Dee: 0+1=1`. Total 8 rows — exactly $|R_1| + |R_2| = 4 + 4$, as expected, since `UNION ALL` never removes anything. ```sql SELECT student FROM Enrolled_DB INTERSECT SELECT student FROM Enrolled_OS; ``` Only rows with `min(c1,c2) > 0`: `Amy` (min(1,1)=1), `Bo` (min(1,2)=1). `Cy` has `c2=0` so it is excluded, `Dee` has `c1=0` so it is excluded. Result: `{Amy, Bo}`. ```sql SELECT student FROM Enrolled_DB EXCEPT SELECT student FROM Enrolled_OS; ``` Rows in `Enrolled_DB` whose multiplicity in `Enrolled_OS` is exhausted: `max(c1-c2,0)`. `Amy: max(1-1,0)=0` (excluded). `Bo: max(1-2,0)=0` (excluded). `Cy: max(2-0,0)=2`, capped to 1 for plain `EXCEPT`. Result: `{Cy}` — the student enrolled in Databases but not Operating Systems, exactly matching intuition despite the duplicate `Cy` row. ```sql SELECT student FROM Enrolled_DB EXCEPT ALL SELECT student FROM Enrolled_OS; ``` `Cy: max(2-0,0)=2` — both copies of `Cy` survive here, illustrating the key difference from plain `EXCEPT`: `EXCEPT ALL` preserves the "leftover" multiplicity rather than collapsing it to a single row. Result: `{Cy, Cy}`. This trace deliberately used asymmetric duplicate counts on both sides, which is exactly the scenario that exposes bugs in a naive mental model of these operators as simple `WHERE IN` / `WHERE NOT IN` rewrites.

The set operators trace directly to the relational model's foundation in set theory, formalized for query languages through relational algebra and then standardized into SQL.

Set operators appear constantly in production analytics and application code. Data warehouses use `UNION ALL` to stitch together partitioned fact tables (e.g., monthly sales tables) into one logical stream without deduplication overhead, since partitioning already guarantees disjointness. ETL and data-reconciliation pipelines use `EXCEPT`/`MINUS` to find records present in a staging table but missing from a production table (or vice versa), a standard technique for incremental loads and audits. Reporting tools use `INTERSECT` to compute overlap analyses — customers who bought both product lines, users active in both of two time windows. Test suites for database migrations frequently compare `old_query EXCEPT new_query` and `new_query EXCEPT old_query` together to prove two rewritten queries are exactly equivalent. Query optimizers themselves exploit the algebraic laws of these operators (e.g., distributing selection over union) to rewrite plans, and the same sort/hash machinery described here underlies `DISTINCT`, `GROUP BY`, and join processing throughout the engine. These composed queries are commonly wrapped into a named Views in SQL object so that application code can query "customers eligible for both promotions" as a simple named relation instead of repeating the set-operator logic everywhere.

Ask the tutor: How would you rewrite `A EXCEPT B` using a `NOT IN` or `NOT EXISTS` subquery, and what changes if columns can contain `NULL`?