Duplicate Elimination

When users write SELECT DISTINCT ... in SQL, they're asking a deceptively simple question: "Give me each unique combination of values exactly once." Behind this simple request lies a fundamental computational challenge—how do we efficiently identify and remove duplicates from potentially billions of tuples?

Duplicate elimination is one of the most common operations in database systems, appearing not just in explicit DISTINCT queries but implicitly in UNION (without ALL), subquery optimization, and various internal operations. Understanding its physical implementation reveals deep connections to aggregation, sorting, and set theory.

Duplicate elimination removes tuples that have identical values across all projected columns. Conceptually, it transforms a multiset (bag) into a set—preserving one instance of each unique tuple and discarding all copies.

Formal Definition:

Given a relation R with tuples t₁, t₂, ..., tₙ, the duplicate elimination operation δ(R) produces a relation where:

• Every tuple that appears in R appears exactly once in δ(R)
• No tuple appears in δ(R) that doesn't appear in R
• |δ(R)| ≤ |R| (the result has at most as many tuples as the input)

SQL Syntax and Semantics:

-- Explicit duplicate elimination with DISTINCT
SELECT DISTINCT column1, column2, column3
FROM table_name;

-- Implicit duplicate elimination with UNION
SELECT a, b FROM table1
UNION
SELECT a, b FROM table2;   -- DISTINCT applied automatically

-- Explicit preservation of duplicates
SELECT ALL column1, column2  -- ALL is default, usually omitted
FROM table_name;

Why Duplicates Arise:

Duplicates in query results typically come from several sources:

1. Projection: Projecting to a subset of columns can create duplicates even from a unique table
2. Joins: A join can multiply tuples, creating duplicates in the result
3. Union: Combining results from multiple sources may have overlap
4. Denormalized Data: Real-world data may contain actual duplicate records

The Computational Challenge:

For n input tuples, we must determine which are duplicates. A naive approach of comparing every tuple pair requires O(n²) comparisons—prohibitively expensive for large tables. Database systems use smarter strategies that reduce this to O(n) average case (hash-based) or O(n log n) worst case (sort-based).

Hash-based duplicate elimination is the most common strategy in modern databases. It uses a hash table to track which tuples have already been seen, outputting each tuple only on its first occurrence.

Basic Algorithm:

HASH_DISTINCT(input_relation):
    seen = empty hash set
    
    for each tuple t in input_relation:
        if t not in seen:
            seen.add(t)
            output t
    
    // No finalization needed—output is produced incrementally

This algorithm is remarkably simple and efficient:

• Time Complexity: O(n) average case (hash operations are O(1) amortized)
• Space Complexity: O(d) where d is the number of distinct tuples
• I/O Cost: Single scan of input data

Implementation Considerations:

1. Hashing Strategy:

The hash function must hash the entire tuple (all DISTINCT columns). For multi-column DISTINCT, we compute a composite hash:

hash(t) = combine(hash(col1), hash(col2), ..., hash(colN))

Common combination strategies include XOR with rotation, MurmurHash3's finalization, or CRC-based combination.

2. Hash Collision Handling:

Hash collisions must be handled carefully—two different tuples may hash to the same bucket. We must store the actual tuple values (or a secondary hash) to detect true duplicates vs collisions:

// On hash match, verify actual equality
if hash(t) == existing_hash:
    if t == existing_tuple:  // actual duplicate
        discard t
    else:  // collision, not duplicate
        insert t at next slot

3. Memory Layout:

For efficiency, hash sets typically store:

• A hash table of bucket entries (hash + pointer/offset)
• A separate buffer holding actual tuple data
• This allows compact bucket arrays with cache-efficient probing

When the number of distinct tuples exceeds available memory, hash-based duplicate elimination must spill to disk. The strategy mirrors external hash aggregation: partition, then process each partition independently.

Partition-Based External DISTINCT:

Phase 1: Partition Input

• Use hash function h₁ to partition all input tuples into P partitions
• Each tuple goes to partition h₁(tuple) mod P
• Write partitions to temporary files on disk

Phase 2: Deduplicate Each Partition

• For each partition i:
  • Read partition i into memory
  • Build in-memory hash set using different hash function h₂
  • Output unique tuples from this partition
  • Clear hash set for next partition

Key Insight: Since we partition by hash value, all copies of any given tuple land in the same partition. Deduplicating each partition independently yields correct overall results.

I/O Cost Analysis:

Let N be the number of input pages:

• Phase 1 (Partitioning):

  • Read input: N pages
  • Write partitions: N pages (assuming no compression)

• Phase 2 (Deduplication):

  • Read partitions: N pages
  • Write output: D pages (where D ≤ N is the distinct result size)

Total I/O: 3N + D page operations

Note that unlike aggregation (which computes summaries), duplicate elimination must output the full tuple data, so output size can be significant.

Sort-based duplicate elimination uses a simple but elegant principle: after sorting, all duplicate tuples are adjacent, making elimination trivial.

Algorithm:

SORT_DISTINCT(input_relation):
    sorted_input = external_sort(input_relation)
    
    previous = null
    
    for each tuple t in sorted_input:
        if t ≠ previous:
            output t
            previous = t
    
    // Only need to track ONE previous tuple—constant memory for dedup phase

The beauty of this approach is that after sorting, the deduplication scan requires only O(1) memory—we compare each tuple to its predecessor. All the complexity is front-loaded into the sorting phase.

I/O Cost Analysis:

The cost is dominated by the external sort:

• Sorting Cost: O(2N × (1 + ⌈log_(B-1)(N/B)⌉)) where B is buffer pages
• Deduplication Scan: N pages (one sequential pass)

For typical memory sizes and data volumes:

• Small data (fits in memory): ~2N I/O (sort) + N I/O (scan) = ~3N
• Medium data (2-3 merge passes): ~6N (sort) + N (scan) = ~7N
• Large data (multiple passes): Sorting dominates

When Sort-Based Wins:

1. Input is already sorted: Cost drops to just N I/O (single scan)
2. Output must be sorted: Sorting cost is amortized across both requirements
3. Very high distinct count: More predictable memory behavior than hash
4. Memory is extremely limited: Sort's merge can use minimal buffers

Query optimizers must choose between hash-based and sort-based duplicate elimination, weighing multiple factors including memory, data characteristics, and downstream requirements.

Key Decision Factors:

1. Available Memory vs Distinct Cardinality

• If estimated distinct tuples fit in memory → Hash (typically wins)
• If distinct set >> memory → Sort may have more predictable performance

2. Input Order

• Input already sorted on DISTINCT columns → Sort (just scan)
• Unsorted input → Hash usually faster

3. Output Ordering Requirements

• ORDER BY matches DISTINCT columns → Sort (amortize cost)
• No ordering needed → Hash (no sorting overhead)

4. Parallelism

• Shared-memory parallel → Both can be parallelized
• Distributed → Hash with exchange by partition key

Cardinality Estimation Importance:

The optimizer's choice heavily depends on estimating how many distinct values exist. This is challenging because:

1. Distinct count ≠ Row count: A million-row table might have anywhere from 1 to 1 million distinct combinations
2. Column correlations matter: DISTINCT(A, B) isn't simply DISTINCT(A) × DISTINCT(B)
3. After filtering: Predicates may substantially change the distinct count

Statistics Used:

• Column distinct count (NDV - Number of Distinct Values)
• Histograms showing value distribution
• Multi-column statistics for correlated columns
• Sampling for up-to-date estimates

Beyond basic algorithms, database systems employ sophisticated optimizations to improve duplicate elimination performance.

1. Projection Pushdown:

Before duplicate elimination, project only the columns involved in DISTINCT. This reduces tuple width, allowing more tuples in memory and less I/O:

-- Original
SELECT DISTINCT a, b FROM table WHERE ...;

-- Optimized plan:
-- Scan → Project(a, b) → DISTINCT
-- Not: Scan (all columns) → DISTINCT → Project

2. Predicate Pushdown:

Apply filters before DISTINCT to reduce input cardinality. Fewer input tuples means less work for deduplication:

-- Push filter before DISTINCT
SELECT DISTINCT customer_id FROM orders WHERE amount > 100;
-- Plan: Scan(orders WHERE amount>100) → Project(customer_id) → DISTINCT

3. Early Duplicate Elimination:

In multi-stage pipelines, eliminating duplicates early can dramatically reduce data flow:

Query: SELECT DISTINCT a FROM (SELECT a FROM t1 UNION ALL SELECT a FROM t2)

-- Naive: Full union, then single DISTINCT
-- Better: DISTINCT on each source, then DISTINCT on combined result
--   - Reduces data volume flowing through union
--   - Each partial DISTINCT may be smaller and fit in memory

4. Lazy (Late) Elimination:

Conversely, sometimes deferring DISTINCT is beneficial:

• If subsequent operators will further reduce output (e.g., LIMIT)
• If duplicate checking is expensive (complex expressions)
• If downstream needs full multiset semantics (then discard)

5. Approximate DISTINCT with HyperLogLog:

For analytical queries where exactness isn't required:

-- PostgreSQL example
SELECT approximate_count_distinct(user_id)
FROM events
WHERE event_date > '2024-01-01';

-- Uses HyperLogLog: O(1) memory, ~2% error
-- Can process billions of rows with kilobytes of state

In distributed and parallel database systems, duplicate elimination requires coordinating across multiple nodes. The challenge is ensuring that duplicate tuples on different nodes are correctly identified and reduced to one.

Partition-Based Distributed DISTINCT:

The standard approach uses hash partitioning:

1. Hash-Partition by DISTINCT columns: Each tuple is sent to a node determined by hash(DISTINCT columns). All copies of any tuple land on the same node.

2. Local DISTINCT on each node: Each node performs in-memory or external DISTINCT on its partition.

3. Output union: Results from all nodes form the complete answer (no further dedup needed since partitioning guaranteed no cross-node duplicates).

Optimization: Partial Distinct Before Shuffle

Network transfer is typically the bottleneck in distributed systems. We can reduce data movement by performing local duplicate elimination before reshuffling:

1. Each node: Local DISTINCT on its original partition
2. Shuffle: Send locally-distinct tuples to hash-determined nodes
3. Each node: Final DISTINCT on received tuples

This adds CPU work but can dramatically reduce network I/O when local data has high duplication.

Broadcast Optimization:

For small distinct sets, broadcasting may beat partitioning:

• If estimated distinct count is very small (e.g., 100 tuples)
• Broadcast all tuples to all nodes
• Each node maintains local dedup state
• Final aggregation merges (small) results

This avoids the overhead of hash partitioning for trivially small result sets.