Join Algorithms Nested Loop Hash Merge: Database Engineering Guide

1. Introduction and Core Concepts

Join algorithms are the fundamental execution strategies that relational database engines use to combine rows from two or more tables based on a related column. While SQL makes joins appear declarative and simple — SELECT * FROM R JOIN S ON R.id = S.id — the database optimizer must choose a physical algorithm to execute that logical operation efficiently. The three classical join algorithms — Nested Loop Join, Hash Join, and Sort-Merge Join — form the backbone of query execution in every major system from PostgreSQL and MySQL to Oracle, SQL Server, and modern distributed engines like Spark and Presto.

Understanding join algorithms nested loop hash merge is essential for database engineering because join performance often dominates overall query time. In analytical workloads, a single poor join choice can turn a query that should run in milliseconds into one that runs for hours. The optimizer's cost model evaluates table sizes, available indexes, memory budget, data distribution, and sort order to select the algorithm with the lowest estimated I/O and CPU cost. No single algorithm is optimal for all scenarios, which is why all three coexist in production engines.

At a conceptual level, all three algorithms solve the same relational algebra problem: given relations R and S, compute R ⋈_p S where p is the join predicate (typically an equi-join like R.a = S.b). They differ radically in how they access data, use memory, and exploit ordering or hashing. Nested Loop Join is the most general and simplest, working for any predicate including non-equi joins. Hash Join is optimized for equi-joins on large, unsorted datasets and is often the fastest when memory is sufficient. Sort-Merge Join excels when inputs are already sorted or when the result needs to be sorted, and it handles very large datasets that exceed memory through external sorting.

Why Join Algorithm Selection Matters

From an engineering perspective, join algorithms directly affect throughput, latency, memory pressure, and disk I/O. A web application serving thousands of concurrent OLTP queries benefits from Index Nested Loop Joins that leverage primary key indexes. A data warehouse scanning billion-row fact tables benefits from Hash Joins that avoid sorting overhead. A merge-heavy ETL pipeline benefits from Sort-Merge Joins that can stream sorted inputs without materializing hash tables.

Modern query optimizers use statistics, histograms, and cardinality estimates to choose automatically, but engineers who understand the underlying mechanics can design better schemas, create appropriate indexes, write more optimizable SQL, and diagnose slow queries using EXPLAIN ANALYZE plans. This guide provides a deep, implementation-oriented view of each algorithm.

2. How It Works

To understand join algorithms nested loop hash merge, it is helpful to view them as different strategies for reducing the naive Cartesian product. A naive join would compare every row of R with every row of S, testing the predicate — an O(|R| * |S|) operation that is prohibitively expensive. Each algorithm introduces a different technique to prune unnecessary comparisons.

Nested Loop Join (NLJ)

Nested Loop Join is the most intuitive algorithm. It iterates over an outer relation R and, for each outer tuple, scans the inner relation S to find matches. Conceptually it is two nested for-loops. The basic variant, Simple Nested Loop Join, scans S from scratch for every R tuple, resulting in |R| * |S| + |R| page reads in the worst case. Despite its simplicity, it is the only algorithm that supports arbitrary join predicates including inequality (R.a < S.b), range, and complex expressions without requiring hashing or sorting.

The optimizer always attempts to make the smaller relation the outer loop to reduce iterations, and if an index exists on the inner relation's join key, it can perform an Index Nested Loop Join where the inner scan becomes an efficient index lookup instead of a full table scan. This transforms the inner loop from O(|S|) to O(log |S|) or O(1) per outer row.

Hash Join

Hash Join is a two-phase algorithm designed specifically for equi-joins. In the Build Phase, the engine scans the smaller relation (the build input), hashes the join key of each tuple, and inserts it into an in-memory hash table. In the Probe Phase, it scans the larger relation (the probe input), hashes each probe tuple's join key, and looks up matching buckets in the hash table. Only tuples that hash to the same bucket need to be compared, which dramatically reduces comparisons when the hash function distributes keys uniformly.

Hash Join is non-blocking for the build phase but requires the entire build table's hash table to fit in memory for the classic in-memory variant. When it does not fit, the engine falls back to Grace Hash Join or Hybrid Hash Join, which partition both relations to disk using the same hash function and then join partition pairs independently.

Sort-Merge Join (SMJ)

Sort-Merge Join, also called Merge Join, assumes or creates sorted order on the join keys. First, both relations are sorted by the join key if they are not already sorted (using an external merge sort if they exceed memory). Then, a single synchronized linear scan merges the two sorted streams: two cursors advance through R and S, emitting matches when keys are equal and skipping ahead when one key is smaller than the other. Because both inputs are sorted, each relation is scanned at most once after sorting.

The merge phase itself is extremely efficient — O(|R| + |S|) — but the sort cost dominates if sorting is required. This makes Sort-Merge Join ideal when an index already provides sorted order, when the query requires sorted output (e.g., ORDER BY on the join key), or when dealing with very large inputs where hash tables would spill to disk repeatedly.

3. Implementation

Implementing these algorithms in Python clarifies their control flow, memory behavior, and edge cases. The following examples operate on in-memory lists of tuples for clarity, but the same logic extends to disk-based pages, iterators, and vectorized execution.

Simple Nested Loop Join

This baseline implementation works for any predicate and requires only O(1) extra memory. It is easy to reason about but scales poorly.

def nested_loop_join(R, S, key_r=0, key_s=0):
    """
    Simple Nested Loop Join for equi-join R.key_r == S.key_s
    R, S: lists of tuples
    Returns list of combined tuples
    """
    result = []
    # Choose smaller relation as outer to reduce iterations
    if len(R) > len(S):
        R, S = S, R
        key_r, key_s = key_s, key_r

    for i in range(len(R)):
        # i < len(R) guaranteed
        r = R[i]
        for j in range(len(S)):
            # j < len(S)
            s = S[j]
            if r[key_r] == s[key_s]:
                result.append((r, s))
    return result

# Example relations: (id, value)
R = [(1, 'A'), (2, 'B'), (3, 'C')]
S = [(2, 'X'), (3, 'Y'), (4, 'Z')]
print(nested_loop_join(R, S))  # [((2, 'B'), (2, 'X')), ((3, 'C'), (3, 'Y'))]

Block Nested Loop Join

Real databases read data in pages or blocks, not individual tuples. Block Nested Loop Join loads a block of outer tuples into memory at once, reducing I/O by scanning the inner relation once per block instead of once per tuple.

def block_nested_loop_join(R, S, block_size=2, key_r=0, key_s=0):
    """
    Block Nested Loop Join - I/O optimized variant
    block_size: number of outer tuples per block
    """
    result = []
    # Iterate over R in blocks
    for block_start in range(0, len(R), block_size):
        block_end = min(block_start + block_size, len(R))
        # block_end <= len(R)
        outer_block = R[block_start:block_end]

        # Scan inner relation once per block
        for s in S:
            for r in outer_block:
                if r[key_r] == s[key_s]:
                    result.append((r, s))
                # Support non-equi predicate example:
                # if r[key_r] < s[key_s]: result.append((r, s))
    return result

def index_nested_loop_join(R, S_index, key_r=0):
    """
    Index Nested Loop Join - inner lookup via hash index
    S_index: dict mapping join key -> list of S tuples
    """
    result = []
    for r in R:
        matches = S_index.get(r[key_r], [])
        # matches may be empty if no key >= 0 found
        for s in matches:
            result.append((r, s))
    return result

Hash Join (Build and Probe)

Hash Join is the workhorse for large equi-joins. The build table should be the smaller relation to minimize hash table memory. This implementation handles duplicate keys by storing lists in buckets.

from collections import defaultdict

def hash_join(R, S, key_r=0, key_s=0):
    """
    In-memory Hash Join (Build + Probe)
    Best when R is smaller (build side). O(|R| + |S|) average.
    """
    # Choose build side: smaller relation minimizes memory
    if len(R) > len(S):
        R, S = S, R
        key_r, key_s = key_s, key_r
        swapped = True
    else:
        swapped = False

    # Build phase: hash smaller relation
    hash_table = defaultdict(list)
    for r in R:
        key = r[key_r]
        hash_table[key].append(r)

    # Probe phase: stream larger relation
    result = []
    for s in S:
        key = s[key_s]
        # Probe hash table - only tuples with matching hash are compared
        if key in hash_table:
            for r in hash_table[key]:
                # Handle hash collisions: verify actual key equality
                if r[key_r] == s[key_s]:
                    if swapped:
                        result.append((s, r))
                    else:
                        result.append((r, s))
    return result

# Grace Hash Join partitioning sketch for large data
def partition_relation(relation, key_idx, num_partitions=4):
    partitions = [[] for _ in range(num_partitions)]
    for tup in relation:
        # Partition via hash - same hash ensures matching keys go to same partition
        pid = hash(tup[key_idx]) % num_partitions
        partitions[pid].append(tup)
    return partitions

Sort-Merge Join

Sort-Merge Join requires sorted inputs. After sorting, the merge phase handles duplicate keys correctly by buffering groups with the same key.

def sort_merge_join(R, S, key_r=0, key_s=0):
    """
    Sort-Merge Join for equi-join
    Handles duplicate keys by cross-product of matching groups
    """
    # Sort phase - O(n log n) if not already sorted
    R_sorted = sorted(R, key=lambda x: x[key_r])
    S_sorted = sorted(S, key=lambda x: x[key_s])

    result = []
    i = j = 0

    # Merge phase - O(|R| + |S|) linear scan
    while i < len(R_sorted) and j < len(S_sorted):
        r_key = R_sorted[i][key_r]
        s_key = S_sorted[j][key_s]

        if r_key == s_key:
            # Collect all R tuples with this key
            r_group = []
            while i < len(R_sorted) and R_sorted[i][key_r] == r_key:
                r_group.append(R_sorted[i])
                i += 1
            # Collect all S tuples with this key
            s_group = []
            while j < len(S_sorted) and S_sorted[j][key_s] == s_key:
                s_group.append(S_sorted[j])
                j += 1
            # Cross product of groups (handles many-to-many)
            for r in r_group:
                for s in s_group:
                    result.append((r, s))
        elif r_key < s_key:
            i += 1
        else:  # r_key > s_key
            j += 1

    return result

# Already sorted inputs allow skipping sort - index merge optimization
def merge_join_sorted(R_sorted, S_sorted, key_r=0, key_s=0):
    """Assumes inputs already sorted - pure merge, no sort overhead"""
    return sort_merge_join(R_sorted, S_sorted, key_r, key_s)

4. Step-by-Step Example

Consider two relations from an e-commerce database. Relation R is Orders(order_id, customer_id, amount) and Relation S is Customers(customer_id, name). We want to compute R JOIN S ON R.customer_id = S.customer_id.

Let R contain: (101, 1, 250), (102, 2, 120), (103, 1, 75), (104, 3, 300) and S contain: (1, 'Alice'), (2, 'Bob'), (4, 'Diana'). Note that customer 3 has no match in S and customer 4 has no orders in R.

Nested Loop Execution Trace

With R as outer, the algorithm picks Order 101 (customer 1), scans S: compares 1==1 (match → emit (101, Alice)), 1==2 (no), 1==4 (no). Next Order 102 (customer 2): scan S again, match with Bob. Order 103 (customer 1): again matches Alice. Order 104 (customer 3): full scan of S finds no match. Total comparisons: 4 outer * 3 inner = 12. With Block Nested Loop and block size 2, S is scanned only twice (once per block of 2 orders) instead of four times, halving I/O.

Hash Join Execution Trace

Build Phase: Choose S as build (smaller, 3 rows). Hash table buckets: hash(1) → [(1, Alice)], hash(2) → [(2, Bob)], hash(4) → [(4, Diana)]. Probe Phase: Stream R. Order 101 hash(1) → bucket hit → emit match. Order 102 hash(2) → hit → emit. Order 103 hash(1) → hit → emit. Order 104 hash(3) → miss → no output. Only 4 probes and 4 hash lookups, no cross-product scans. This illustrates why hash join is O(|R|+|S|) average case.

Sort-Merge Execution Trace

Sort Phase: R sorted by customer_id becomes (101,1), (103,1), (102,2), (104,3). S is already sorted by customer_id (primary key). Merge Phase: i points to R's first 1, j to S's 1 → keys equal → buffer R group [101,103] and S group [Alice] → emit two rows. Advance both pointers. Now i at 2 (Bob's id), j at 2 → match → emit one row. Next i at 3, j at 4 → 3 < 4 → advance i past end → termination. Merge required only one pass over each sorted list. If both tables had clustered indexes on customer_id, the sort phase would be skipped entirely, making this the cheapest option.

This example also highlights handling of duplicates and non-matches. Orders 101 and 103 both join to the same customer, producing a one-to-many result. Sort-Merge correctly buffers groups to generate the cross-product, and Hash Join naturally handles duplicates via bucket lists. All three correctly produce an inner join result of three rows, excluding unmatched keys.

5. Complexity Analysis

Complexity analysis for join algorithms must consider both CPU and I/O, as database joins are often I/O-bound. We analyze in terms of |R| = n and |S| = m, with B(R) and B(S) as the number of disk blocks, M as available memory blocks, and h as hash table overhead.

Nested Loop Join has no extra memory overhead but pays in repeated scans. Simple Nested Loop does n * m tuple comparisons and B(R) + n * B(S) block I/Os. Block Nested Loop improves I/O to B(R) + (B(R)/M) * B(S) by buffering outer blocks. Index Nested Loop reduces inner cost to O(log m) per lookup if a B-tree index exists, yielding O(n log m) total.

Hash Join's average case is linear: O(n + m) to build and probe, with O(n) space for the hash table (where n is build size). Worst case degrades to O(n * m) if every key hashes to the same bucket (pathological hash function or highly skewed data) and all keys are equal, requiring full cross-product comparison within a single bucket. Space is O(n) for in-memory, or O(n + m) with partitioning to disk.

Sort-Merge Join's cost is dominated by sorting: O(n log n + m log m) for sorting plus O(n + m) for merging. If inputs are already sorted or indexed, sorting is avoided and cost drops to O(n + m) with O(1) extra space for merging (or O(n) if buffering duplicates). External sort adds I/O factor: O(B log_M B) passes over data.

In practice, the constant factors matter enormously. Hash Join's O(n + m) hides hash computation and bucket chaining overhead but benefits from excellent cache locality during probing. Sort-Merge's O(n log n) sort is highly optimized in modern engines using radix sort or timsort and can be parallelized. Nested Loop's simplicity makes it CPU-efficient per comparison, but its quadratic scaling makes it unsuitable for large inputs without an index.

Memory considerations often decide the winner. If the build table for Hash Join exceeds available memory, partitioning spills to disk and cost approaches sorting. If Sort-Merge can leverage an existing clustered index, it avoids both hashing and sorting memory pressure entirely, making it the most memory-efficient choice for indexed equi-joins.

6. Variations and Optimizations

Production databases rarely use the textbook versions directly. Decades of research have produced optimized variants that address I/O, skew, and memory limitations.

Nested Loop Optimizations

Block Nested Loop Join is the first optimization, buffering M-2 blocks of outer relation and one block each for inner and output. Even more effective is Index Nested Loop Join, which is the default for OLTP systems: if the inner relation has a B-tree or hash index on the join key, each outer tuple performs an index seek rather than a scan. PostgreSQL's EXPLAIN will show "Nested Loop" with an "Index Scan" on the inner side when this path is chosen. Another variant, Dependent Join or Correlated Nested Loop, is used for lateral joins and subqueries.

Hash Join Optimizations

Grace Hash Join handles memory overflow by partitioning both relations into k disk partitions using hash function h1, then joining each partition pair in memory using a second hash function h2. Hybrid Hash Join improves on this by keeping the first partition in memory during partitioning, avoiding I/O for that partition. Modern engines also implement Parallel Hash Join, building concurrent hash tables per thread, and use Bloom Filters to skip probe tuples that have no match in the build side before probing — a huge win when the join is selective.

Skew handling is critical: if one key is extremely frequent (e.g., NULL or default values), its bucket becomes huge and causes imbalance. Techniques like skew-aware partitioning, histogram-based rebalancing, and using separate handling for heavy hitters prevent a single partition from dominating runtime.

Sort-Merge Optimizations

Sort-Merge benefits from eliminating sorts. If an index provides order, or if the optimizer can share a sort with an ORDER BY or GROUP BY on the same key, the sort cost is amortized. External Merge Sort is optimized with replacement selection to create longer initial runs and with double buffering to overlap I/O and CPU. Some engines implement Zig-Zag Merge Join for band joins and use prefix merging to handle multiple join keys.

Choosing among optimizations is the optimizer's job, but engineers can influence it: create indexes to enable Index Nested Loop, ensure adequate work_mem (PostgreSQL) or join_buffer_size (MySQL) to keep hash tables in memory, and maintain table statistics so the optimizer correctly estimates build vs. probe sizes.

7. Real-World Applications

Join algorithms are not confined to traditional RDBMSs; they appear wherever datasets must be correlated.

In transactional web servers, an e-commerce platform's request handler might execute SELECT orders.*, users.email FROM orders JOIN users ON orders.user_id = users.id WHERE orders.id = ? thousands of times per second. Here Index Nested Loop Join dominates because the outer table is highly selective (one order) and the inner lookup uses the primary key index on users.id, yielding single-digit millisecond latency without touching most of the users table.

In analytical data warehouses and data lakes, Hash Join is the default for star schema queries. A fact table with billions of sales rows joining to dimension tables (product, store, date) uses Hash Join with the small dimension as build side. Systems like Amazon Redshift, Snowflake, and Apache Spark broadcast the small dimension's hash table to all nodes, enabling parallel probe of the large fact table without shuffling it.

Sort-Merge Join shines in ETL pipelines, log processing, and time-series databases where data is naturally ordered. Merging two sorted event streams — for example, joining web clickstream logs sorted by timestamp with ad impression logs sorted by timestamp for attribution — can be done with a streaming merge without materializing either dataset. Google's MapReduce and Hadoop's reduce-side join historically relied on sorting to co-locate matching keys.

Network routers and stream processors also use join-like algorithms to correlate packets across streams within time windows, often implementing a variant of hash join with expiring buckets. Even in application code outside the database, understanding these algorithms helps when joining in-memory collections in Python, Java, or JavaScript — choosing between nested loops for small lists and hashing for large ones can yield order-of-magnitude speedups.

8. Comparison with Alternatives

No join algorithm dominates universally. The optimal choice depends on data size, sort order, index availability, join predicate type, memory budget, and whether the join is equi-join or theta-join.

Nested Loop is the most general but least scalable. Hash Join is fastest for unsorted equi-joins when memory suffices but cannot handle inequality predicates and suffers with skew. Sort-Merge is robust for large, sortable equi-joins and is the only one that can efficiently produce sorted output, but it pays sorting cost if data is unsorted. Alternative strategies like Index Join, Semi-Join, and Anti-Join optimizations build on these primitives for EXISTS and NOT EXISTS queries.

Query optimizers use cost models that estimate these trade-offs. For example, PostgreSQL's optimizer will prefer Hash Join when effective_cache_size suggests the hash table fits in memory and no index exists, Sort-Merge when enable_mergejoin is on and inputs are indexed, and Nested Loop when the outer cardinality is tiny. Engineers can inspect decisions with EXPLAIN (ANALYZE, BUFFERS) and influence them with hints or by creating/dropping indexes, updating statistics with ANALYZE, or adjusting memory parameters.

9. Common Mistakes and Best Practices

Even experienced engineers make mistakes that cause the optimizer to pick a suboptimal join strategy or cause joins to perform poorly regardless of algorithm.

A frequent mistake is joining on non-indexed columns in OLTP workloads and expecting Nested Loop to be fast. Without an index, Nested Loop degrades to a full scan per outer row. Best practice: ensure join keys are indexed, especially foreign keys. In PostgreSQL, MySQL, and SQL Server, foreign keys are not automatically indexed — you must create the index explicitly. Another mistake is using functions on join keys, like ON LOWER(R.name) = LOWER(S.name), which prevents index and hash optimizations and forces a Nested Loop with expression evaluation per pair. Instead, store normalized keys or use functional indexes.

Memory misconfiguration is another pitfall. Setting work_mem too low forces Hash Joins to spill to disk via Grace partitioning, turning an O(n+m) operation into a multi-pass disk-heavy operation. Setting it too high causes memory pressure and OOM kills under concurrency. Best practice: size memory per query type, monitor EXPLAIN ANALYZE for "Hash Join" with "Batches: 1" (in-memory) vs. multiple batches (spilled), and use connection pooling to limit concurrent memory usage.

Data skew and cardinality misestimation cause poor algorithm choice. If statistics are stale, the optimizer may think the build table is small and choose Hash Join, only to discover at runtime that it is huge and spills. Regular ANALYZE or UPDATE STATISTICS and the use of histograms for skewed columns mitigate this. For known skew (e.g., a status column where 90% of rows are 'ACTIVE'), consider filtering before joining or using skew-aware hints.

• Do: Create indexes on join keys and keep statistics up to date. Use EXPLAIN to verify the chosen algorithm matches expectations.
• Do: Choose the smaller table as build side for Hash Join; let the optimizer do this, but help it with accurate row counts.
• Do: Prefer equi-joins over non-equi predicates when possible — they enable Hash and Merge optimizations.
• Do: Use covering indexes or index-only scans to avoid heap lookups during Index Nested Loop.
• Don't: Join on unindexed, unhashed, unsorted large tables without considering the quadratic cost of Nested Loop.
• Don't: Ignore sort order — if your query has ORDER BY join_key, Sort-Merge may be free.
• Don't: Use SELECT * in joins that only need a few columns — wider rows increase I/O and hash table size.

Finally, avoid joining in application code when the database can do it more efficiently. Pulling two large tables into Python and joining with nested loops bypasses the database's optimized hash tables, parallel execution, and I/O pipelining. Push joins to the database, or if you must join in memory, use hash-based approaches (Python dict/set) rather than double loops.

10. Interview Questions

Join algorithms are a favorite topic in database and backend engineering interviews because they test understanding of algorithms, systems trade-offs, and practical optimization.

Q1: When would you choose Hash Join over Sort-Merge Join, and vice versa?

Answer: Choose Hash Join when you have an unsorted equi-join and the smaller (build) table fits in memory — it is O(n+m) average and avoids sorting overhead, making it ideal for warehouse fact-dimension joins. Choose Sort-Merge when inputs are already sorted (via clustered index or prior sort), when you need sorted output, when data is too large for a hash table and would spill repeatedly, or when handling band/inequality joins that hash cannot support. If both tables are huge and unsorted, the decision hinges on memory: Hash Join with Grace partitioning and Sort-Merge with external sort have similar I/O, but Sort-Merge is less sensitive to skew.

Q2: Why is Nested Loop Join still used if its worst case is O(n*m)?

Answer: Because with an index on the inner table, Nested Loop becomes Index Nested Loop with O(n log m) cost, which is optimal for highly selective OLTP queries where n is tiny (e.g., 1-100 outer rows). It also is the only algorithm that supports arbitrary theta-joins (non-equi predicates like R.a < S.b), requires minimal memory (O(1)), and has no setup cost (no hash table build or sort). For small tables or when the outer table is filtered to few rows, its simplicity and low overhead beat the setup cost of hashing or sorting.

Q3: What happens when the hash table does not fit in memory? How does Grace Hash Join solve this?

Answer: Classic in-memory Hash Join fails or spills inefficiently. Grace Hash Join partitions both relations to disk using the same hash function h1 into k partitions such that each build partition fits in memory. It then joins each partition pair (R_i, S_i) independently in memory using a second hash function h2. This guarantees that matching keys are in the same partition pair, so no cross-partition comparisons are needed. Hybrid Hash Join optimizes further by keeping one partition in memory during partitioning to avoid writing and reading it. The cost becomes partitioning I/O plus k independent hash joins.

Q4: How do you diagnose and fix a slow join in production?

Answer: Start with EXPLAIN (ANALYZE, BUFFERS) to see the actual algorithm chosen, estimated vs. actual row counts, buffer hits vs. reads, and whether Hash Join spilled (Batches > 1) or Sort-Merge performed an external sort. Check for missing indexes on join keys, stale statistics (run ANALYZE), and memory settings (work_mem). Fixes include: creating an index to enable Index Nested Loop, increasing memory to keep hash tables in-memory, rewriting predicates to be sargable (avoid functions on join keys), filtering early with WHERE clauses to reduce input sizes, and for skew, handling heavy hitters separately. In distributed systems, check for data skew causing one partition to be much larger than others.

Q5: Can you implement a Hash Join that handles duplicate keys correctly?

Answer: Yes — the hash table must map each key to a list of build tuples, not a single tuple, because the build side may have duplicates. During probing, each probe tuple must be matched against all build tuples in its bucket, and key equality must be rechecked to handle hash collisions. For many-to-many joins, this produces the cross-product of duplicate groups. The Python implementation in Section 3 demonstrates this with defaultdict(list) for buckets and a nested loop over hash_table[key] during probing. An alternative for high-cardinality duplicates is to buffer groups during Sort-Merge, as shown in the merge implementation.