Database Join Algorithms: How Nested Loop, Sort-Merge, and Hash Joins Work Internally

Joins are ubiquitous across transactional databases (PostgreSQL, MySQL), analytical data warehouses (Amazon Redshift, Google BigQuery), and distributed computation frameworks like Apache Spark. Because SQL is a declarative language, developers specify what data they require rather than how to retrieve it:

SELECT users.name, COUNT(*)
FROM blogs
INNER JOIN users ON blogs.user_id = users.id
GROUP BY users.name
ORDER BY COUNT(*) DESC;

Under the hood, the database’s query optimizer evaluates table statistics, available indexes, and memory constraints to transform this declarative statement into an optimal physical execution plan. At the heart of this plan sits one of three foundational join algorithms:

1. Nested Loop Join
2. Sort-Merge Join (Merge Join)
3. Hash Join

Understanding how these algorithms operate internally illuminates how databases scale and why certain queries run orders of magnitude faster than others.

---

1. Nested Loop Join

The Core Mechanism

As the name implies, a Nested Loop Join is fundamentally a for loop nested inside another for loop. The engine designates one relation as the outer relation (driving table) and the other as the inner relation.

For every single tuple in the outer relation, the engine scans through every tuple in the inner relation to test whether the join predicate matches.

Outer Table (R) ──▶ For each row r in R
                      │
                      ▼
Inner Table (S) ──▶   For each row s in S
                        │
                        ▼
                      If r.key == s.key: Emit (r, s)

Pseudocode

def nested_loop_join(outer_table, inner_table, join_condition):
    result = []
    for outer_row in outer_table:
        for inner_row in inner_table:
            if join_condition(outer_row, inner_row):
                result.append(combine(outer_row, inner_row))
    return result

Step-by-Step Example

Consider two relations:

• users (outer table): 2 rows ({id: 1, name: 'Arpit'}, {id: 2, name: 'Aria'})
• blogs (inner table): 5 rows (3 blogs written by user_id = 1, 2 written by user_id = 2)

1. Pick the first row from users (id = 1).
2. Scan through all 5 rows of blogs:
   • Row 1: user_id == 1 -> Match! Add to result set.
   • Row 2: user_id == 1 -> Match! Add to result set.
   • Row 3: user_id == 1 -> Match! Add to result set.
   • Row 4: user_id == 2 -> No match.
   • Row 5: user_id == 2 -> No match.
3. Pick the second row from users (id = 2).
4. Scan through all 5 rows of blogs again, emitting matches for rows 4 and 5.

Performance & Trade-offs

• Time Complexity: $O(|R| \times |S|)$ where $|R|$ and $|S|$ are the row counts of the outer and inner tables.
• Space Complexity: $O(1)$ auxiliary memory (streamed execution).
• When it shines: Extremely small relations (e.g., small lookup tables) or when the inner table has an index on the join column (Index Nested Loop Join). With an index on the inner relation, the inner loop cost drops from $O(|S|)$ to $O(\log |S|)$, bringing total complexity down to $O(|R| \log |S|)$.
• When it struggles: Unindexed large tables. Joining two million-row tables using a naive nested loop join requires $10^{12}$ comparisons, grinding the database to a halt.

---

2. Sort-Merge Join (Merge Join)

The Core Mechanism

The Sort-Merge Join is inspired by the merge step in Merge Sort. Computations on ordered datasets are inherently more efficient because ordering eliminates the need to perform redundant scans.

A Merge Join operates in two distinct phases:

1. Sort Phase: Ensure both relations are sorted on the join key.
2. Merge Phase: Maintain pointers to both relations and advance them sequentially down the sorted keys, emitting joined rows whenever keys match.

flowchart LR
    subgraph Sorted Users
        U1["ID: 1"]
        U2["ID: 2"]
    end

    subgraph Sorted Blogs
        B1["User_ID: 1"]
        B2["User_ID: 1"]
        B3["User_ID: 1"]
        B4["User_ID: 2"]
        B5["User_ID: 2"]
    end

    U1 -. Match .-> B1
    U1 -. Match .-> B2
    U1 -. Match .-> B3
    U2 -. Match .-> B4
    U2 -. Match .-> B5

Pseudocode

def sort_merge_join(table_r, table_s, key_r, key_s):
    # Phase 1: Sort
    sorted_r = sort(table_r, by=key_r)
    sorted_s = sort(table_s, by=key_s)
    
    # Phase 2: Merge
    ptr_r, ptr_s = 0, 0
    result = []
    
    while ptr_r < len(sorted_r) and ptr_s < len(sorted_s):
        curr_r = sorted_r[ptr_r]
        curr_s = sorted_s[ptr_s]
        
        if curr_r[key_r] == curr_s[key_s]:
            # Match found: emit and handle duplicates
            result.append(combine(curr_r, curr_s))
            ptr_s += 1
        elif curr_r[key_r] < curr_s[key_s]:
            ptr_r += 1
        else:
            ptr_s += 1
            
    return result

Why Ordering Matters

Because both relations are sorted, equal join keys are contiguous. Once the merge pointer advances past all user_id = 1 rows in blogs, the engine knows with mathematical certainty that no subsequent row will ever have user_id = 1. It never needs to backtrack or rescan prior rows.

Performance & Trade-offs

• Time Complexity:
  • Sorting phase: $O(|R| \log |R| + |S| \log |S|)$
  • Merge phase: $O(|R| + |S|)$ for distinct keys (worst-case $O(|R| \times |S|)$ if all keys are identical duplicates).
  • Overall: Dominated by the sort phase unless the data is already pre-sorted by an underlying B-Tree index or clustering key.
• Space Complexity: $O(1)$ during the merge phase, but external sorting may require disk spooling if working memory (work_mem in PostgreSQL) is exceeded.
• When it shines: Large datasets that are already sorted (e.g., indexed queries or sequential scans over clustered tables), or queries requesting sorted output (ORDER BY matching the join key).

---

3. Hash Join

The Core Mechanism

Hash Joins eliminate full-table rescanning and sorting by trading memory for constant-time lookups. A Hash Join requires an equality predicate (an equi-join, such as blogs.user_id = users.id).

The algorithm executes in two phases:

flowchart TD
    subgraph Build Phase
        BuildInput["Build Relation (Typically Smaller Table)"] -->|Hash Join Key| HashTable[("In-Memory Hash Table")]
    end

    subgraph Probe Phase
        ProbeInput["Probe Relation (Larger Table)"] -->|Read Row by Row| HashProbe[Hash Join Key]
        HashProbe -->|Lookup Key| HashTable
        HashTable -->|Collision Check & Match| Result["Emit Joined Tuples"]
    end

1. Build Phase: The engine reads the smaller relation (the build input) into memory and inserts every row into a hash table where the hash key is the join attribute.
2. Probe Phase: The engine streams the larger relation (the probe input) row by row. For each row, it hashes the join attribute, looks up the corresponding bucket in the hash table, resolves potential hash collisions by verifying the exact attribute equality, and emits the matching joined rows.

Pseudocode

def hash_join(build_table, probe_table, build_key, probe_key):
    # Phase 1: Build
    hash_table = {}
    for row in build_table:
        key = row[build_key]
        if key not in hash_table:
            hash_table[key] = []
        hash_table[key].append(row)
        
    # Phase 2: Probe
    result = []
    for row in probe_table:
        key = row[probe_key]
        if key in hash_table:
            for matching_row in hash_table[key]:
                result.append(combine(matching_row, row))
                
    return result

Performance & Trade-offs

• Time Complexity: $O(|R| + |S|)$ assuming a uniform hash function with minimal collisions.
• Space Complexity: $O(|R|)$ auxiliary memory to store the hash table of the build relation.
• When it shines: Large, unsorted datasets joining on equality predicates where the build table fits comfortably within working memory.
• Vulnerabilities:
  • Memory Limits: If the build table exceeds memory limits, the engine must partition the hash table to disk (Grace Hash Join / Hybrid Hash Join), significantly increasing I/O overhead.
  • Data Skew & Hash Collisions: A non-uniform hash function or heavily skewed keys result in long bucket chains, degrading lookup performance from $O(1)$ toward $O(N)$.
  • Predicate Restrictions: Only supports equi-joins (=). Range joins (<, >, BETWEEN) cannot use hash joins.

---

Comparison of Join Algorithms

Algorithm	Time Complexity (Best/Average)	Auxiliary Space	Best Suited For	Critical Limitations
Nested Loop Join	$O(	R	\times	S
Sort-Merge Join	$O(	R	\log	R
Hash Join	$O(	R	+	S

---

How Query Optimizers Decide

Relational engines do not hardcode a single join strategy. Instead, the Query Optimizer inspects metadata and cost models before executing a query:

1. Table Statistics and Cardinality: The optimizer queries the database catalog for estimated row counts, column value distributions, and histogram statistics.
2. Available Indexes: If an index exists on the join key of the larger table, an Index Nested Loop Join is frequently preferred.
3. Memory Budgets: The engine inspects available execution memory (e.g., PostgreSQL’s work_mem). If the smaller table exceeds memory, sort-merge or multi-pass disk-based hash joins are considered.
4. Downstream Operations: If an outer ORDER BY clause matches the join key, the optimizer may choose a Sort-Merge Join even if a Hash Join is slightly faster, avoiding an explicit subsequent sorting phase.

By leveraging cost models against table statistics, the database ensures optimal data flow across diverse workloads.