Set Operations

The mathematical foundations of relational databases rest on set theory—relations are sets of tuples, and operations on relations have clear set-theoretic counterparts. UNION, INTERSECT, and EXCEPT (also called MINUS or DIFFERENCE) are the direct SQL equivalents of set union, intersection, and difference operations.

These operations are fundamental to combining query results, finding common records across tables, and identifying records that exist in one dataset but not another. Despite their simple conceptual definitions, their physical implementations involve subtle algorithmic choices and significant optimization opportunities.

SQL provides three set operations that combine the results of two query expressions:

UNION (∪): Returns all tuples that appear in either input relation (or both)

INTERSECT (∩): Returns only tuples that appear in both input relations

EXCEPT (−): Returns tuples that appear in the first relation but not the second

Compatibility Requirement:

For any set operation, the two input relations must be union-compatible (also called type-compatible):

1. Same number of columns
2. Corresponding columns have compatible data types

The result schema typically inherits column names from the first (left) input.

UNION is the most common set operation, combining results from multiple queries. Its implementation depends on whether duplicates should be eliminated (UNION) or preserved (UNION ALL).

UNION ALL (Bag Union):

UNION ALL is trivially implemented—simply concatenate the two input streams:

UNION_ALL(R, S):
    for each tuple t in R:
        output t
    for each tuple t in S:
        output t

This requires no comparison, hashing, or duplicate tracking. It's an extremely efficient operation:

• Time Complexity: O(|R| + |S|)
• Space Complexity: O(1) additional memory
• I/O Cost: Read R + Read S (no extra writes)

UNION ALL maintains full pipelining—tuples flow through without buffering.

UNION (Set Union):

UNION with duplicate elimination requires more sophisticated implementation. The operation is essentially: DISTINCT(R UNION ALL S).

Hash-Based UNION:

HASH_UNION(R, S):
    seen = empty hash set
    
    for each tuple t in R:
        if t not in seen:
            seen.add(t)
            output t
    
    for each tuple t in S:
        if t not in seen:
            seen.add(t)
            output t

This processes inputs sequentially, outputting each unique tuple on first encounter.

Sort-Based UNION:

SORT_MERGE_UNION(R, S):
    sorted_R = sort(R)
    sorted_S = sort(S)
    
    r = next tuple from sorted_R (or NULL)
    s = next tuple from sorted_S (or NULL)
    last_output = NULL
    
    while r ≠ NULL or s ≠ NULL:
        if s == NULL or (r ≠ NULL and r < s):
            if r ≠ last_output:
                output r
                last_output = r
            r = next from sorted_R
        elif r == NULL or (s ≠ NULL and s < r):
            if s ≠ last_output:
                output s
                last_output = s
            s = next from sorted_S
        else:  // r == s
            if r ≠ last_output:
                output r
                last_output = r
            r = next from sorted_R
            s = next from sorted_S

After sorting, merge with deduplication produces the union in sorted order.

INTERSECT returns only tuples that appear in both input relations. This is conceptually equivalent to a natural join on all columns, but with set or bag semantics.

Hash-Based INTERSECT:

The algorithm is similar to hash join:

HASH_INTERSECT(R, S):
    // Phase 1: Build hash table from R
    hash_table = {}
    for each tuple t in R:
        if t in hash_table:
            hash_table[t].count += 1
        else:
            hash_table[t] = {count: 1, outputted: false}
    
    // Phase 2: Probe with S
    for each tuple t in S:
        if t in hash_table and not hash_table[t].outputted:
            output t
            hash_table[t].outputted = true  // For set semantics
            // For INTERSECT ALL: output and decrement count instead

For set semantics, each matching tuple is output exactly once. For INTERSECT ALL, we track counts and output up to min(count_R, count_S) copies.

Sort-Based INTERSECT:

SORT_MERGE_INTERSECT(R, S):
    sorted_R = sort(R)
    sorted_S = sort(S)
    
    r = next tuple from sorted_R
    s = next tuple from sorted_S
    
    while r ≠ NULL and s ≠ NULL:
        if r < s:
            r = next from sorted_R
        elif s < r:
            s = next from sorted_S
        else:  // r == s, found match
            output r  // or s, they're equal
            r = next from sorted_R
            s = next from sorted_S
            // For set semantics: skip remaining duplicates of this value
            // For ALL semantics: output min(count_R, count_S) copies

Sort-merge intersection is elegant: advance through both sorted inputs, outputting when they match, skipping when they don't.

Cost Analysis:

• Hash-Based: O(|R|) to build + O(|S|) to probe = O(|R| + |S|)
• Sort-Based: O(|R| log|R| + |S| log|S|) for sorting + O(|R| + |S|) for merge

Hash-based is typically faster unless inputs are already sorted.

EXCEPT (or MINUS in some SQL dialects) returns tuples from the left relation that don't appear in the right relation. Unlike UNION and INTERSECT, EXCEPT is not commutative—order matters.

Hash-Based EXCEPT:

Build a hash table from the right relation, then probe with the left:

HASH_EXCEPT(R, S):  // R EXCEPT S
    // Phase 1: Build hash set from S (what to exclude)
    exclude_set = {}
    for each tuple t in S:
        exclude_set.add(t)
        // For EXCEPT ALL, track counts: exclude_set[t].count++
    
    // Phase 2: Output R tuples not in exclude set
    seen = {}  // For set semantics: avoid outputting duplicates
    for each tuple t in R:
        if t not in exclude_set:
            if t not in seen:  // Set semantics
                output t
                seen.add(t)
        // For EXCEPT ALL: output if count not exhausted, decrement

The key insight: we must fully process S before outputting from R, because any tuple in R might be excluded by a later tuple in S.

Sort-Based EXCEPT:

SORT_MERGE_EXCEPT(R, S):  // R EXCEPT S
    sorted_R = sort(R)
    sorted_S = sort(S)
    
    r = next from sorted_R
    s = next from sorted_S
    last_output = NULL
    
    while r ≠ NULL:
        if s == NULL or r < s:
            // r has no match in S, output it (with dedup)
            if r ≠ last_output:  // Set semantics
                output r
                last_output = r
            r = next from sorted_R
        elif r > s:
            // s is behind, advance s
            s = next from sorted_S
        else:  // r == s
            // Match found, r is excluded
            r = next from sorted_R
            s = next from sorted_S

After sorting, we scan both inputs in parallel. When left tuple has no match on right, output it. When they match, skip both.

When input relations exceed available memory, set operations must spill to disk. The strategies mirror those for external hashing and sorting.

External Hash-Based Set Operations:

The approach uses partitioning:

1. Partition Phase: Hash both R and S into P partitions using the same hash function

   • Each tuple goes to partition h(tuple) mod P
   • R partitions: R₀, R₁, ..., Rₚ₋₁
   • S partitions: S₀, S₁, ..., Sₚ₋₁

2. Process Phase: For each partition pair (Rᵢ, Sᵢ):

   • Load both partitions into memory
   • Perform in-memory set operation
   • Output results

Since we use the same hash function for R and S, matching tuples land in corresponding partitions. Each partition pair can be processed independently.

I/O Cost for External Set Operations:

Let |R| = N_R pages and |S| = N_S pages:

Partitioning:

• Read R: N_R pages
• Read S: N_S pages
• Write partitions: N_R + N_S pages

Processing:

• Read partitions: N_R + N_S pages
• Write output: O_output pages (operation-dependent)

Total: 3(N_R + N_S) + O_output page operations

External Sort-Based Set Operations:

Alternatively, sort both inputs and merge:

1. External sort R → sorted_R
2. External sort S → sorted_S
3. Merge-based set operation on sorted inputs

Cost: Sorting cost + single merge pass. This is O(2N log N) for sorting plus O(N) for merge.

Database optimizers apply various transformations to improve set operation performance.

1. Push Down Selections:

Apply filters before set operations to reduce input sizes:

-- Before optimization
(SELECT * FROM orders WHERE year = 2024)
UNION
(SELECT * FROM archived_orders WHERE year = 2024)

-- After: Predicates already pushed down
-- (This is often the user's intent, but optimizer ensures it)

2. Push Down Projections:

Project only necessary columns before set operations:

-- Original: SELECT DISTINCT a FROM (SELECT * FROM R UNION SELECT * FROM S)
-- Optimized: SELECT a FROM R UNION SELECT a FROM S
-- Benefits: Narrower tuples, possibly fewer distinct values

3. Merge Adjacent Operations:

Multiple set operations can sometimes merge:

-- Original
(R UNION S) UNION T

-- Optimized: Single 3-way union
-- Process R, S, T with shared hash table
-- Avoids materializing intermediate result

4. Convert to Joins When Beneficial:

INTERSECT and EXCEPT can often be rewritten as joins:

-- INTERSECT as semi-join
SELECT a, b FROM R INTERSECT SELECT a, b FROM S
-- Equivalent to:
SELECT DISTINCT R.a, R.b FROM R WHERE EXISTS (SELECT 1 FROM S WHERE S.a = R.a AND S.b = R.b)

-- EXCEPT as anti-join  
SELECT a, b FROM R EXCEPT SELECT a, b FROM S
-- Equivalent to:
SELECT DISTINCT R.a, R.b FROM R WHERE NOT EXISTS (SELECT 1 FROM S WHERE S.a = R.a AND S.b = R.b)

Join-based rewrites can exploit indexes that set operations cannot.

In distributed database systems, set operations require coordinating across nodes. The strategies depend on how data is partitioned across the cluster.

Distributed UNION:

UNION ALL is trivial in distributed settings—no coordination needed:

Distributed UNION ALL:
    Each node outputs its local data
    Results are concatenated at coordinator

For UNION with deduplication:

1. Option A: Centralized Dedup

   • All nodes send data to one node
   • Single node performs deduplication
   • Problem: Single point of bottleneck

2. Option B: Distributed Dedup

   • Hash-partition combined data across all nodes
   • Each node deduplicates its partition
   • Results union without further dedup

Optimization: Co-located Set Operations

If R and S are already co-partitioned on the same hash key and that key comprises all columns:

• Each node can compute the set operation locally
• No data shuffling required
• Massive network I/O savings

This is why physical data layout choices (like table partitioning) are so important for analytical query performance.

Handling Skew:

Skewed data causes load imbalance—some nodes process much more data than others. Mitigations include:

1. Partial aggregation before shuffle: Eliminate duplicates locally first
2. Dynamic load balancing: Reassign work from overloaded nodes
3. Virtual partitioning: Split hot partitions across multiple nodes