Join Algorithms Under the Hood: Nested Loop, Hash Join & Sort-Merge Join Mechanics

Joining two database tables—users (100,000 rows) and orders (10,000,000 rows)—can execute in 45 milliseconds or 18 minutes depending entirely on which join algorithm the database query optimizer chooses.

SELECT users.name, orders.order_date, orders.total_amount
FROM users
JOIN orders ON users.id = orders.user_id;

Depending on the underlying join algorithm selected by the query optimizer, executing this single statement can take either 1.2 seconds or 45 minutes.

Why does the physical execution strategy make such a dramatic difference?

At its core, a relational join combines two sets of data tuples based on a matching join predicate. However, database storage engines must process datasets that rarely fit entirely into CPU L1/L2 caches.

To process joins efficiently, relational engines rely on three main families of join algorithms:

1. Nested Loop Joins (Simple, Index, Block)
2. Hash Joins (Classic In-Memory, Grace On-Disk)
3. Sort-Merge Joins

Let’s examine how each algorithm operates at the memory and byte level.

---

1. Nested Loop Joins (NLJ)

The Nested Loop Join is the conceptually simplest join strategy. It evaluates join conditions using nested iteration loops over an Outer Table (Driving Table) and an Inner Table.

A. Simple Nested Loop Join

The algorithm scans every single row in the outer table, and for every outer row, performs a full table scan over the inner table:

for outer_row in outer_table:           # M rows
    for inner_row in inner_table:       # N rows
        if outer_row.join_key == inner_row.join_key:
            emit(outer_row, inner_row)

• Time Complexity: $\mathcal{O}(M \times N)$
• I/O Disk Cost: If the inner table has $N$ pages and doesn’t fit in the Buffer Pool, the database must read $N$ disk pages from disk $M$ separate times!
• Verdict: Terribly slow for large datasets. Modern databases avoid Simple NLJ whenever possible.

---

B. Index Nested Loop Join (INLJ)

If the join key on the inner table is indexed (e.g., orders.user_id has a B+ Tree index), the engine replaces the inner full table scan with an efficient $\mathcal{O}(\log N)$ index B+ Tree point lookup:

[ Outer Row: user_id=42 ]
          |
          v
  [ B+ Tree Index Lookup on orders ] ---> Finds matching leaf nodes in O(log N)
          |
          v
  [ Emit Joined Tuple ]

• Time Complexity: $\mathcal{O}(M \log N)$
• Best Use Case: Primary join strategy when the outer table $M$ is small (filtered by a selective WHERE clause) and the inner table $N$ has a selective index on the join key.

---

C. Block Nested Loop Join (BNL)

What if no index exists on the inner table’s join column?

To avoid scanning the inner table $M$ times from disk, the engine allocates a memory region called a Join Buffer (join_buffer_size).

                              [ Outer Table (users) ]
                                         |
                                         v
                     +---------------------------------------+
                     |  Join Buffer Memory (Loads B Rows)    |
                     +---------------------------------------+
                                         |
                                         v  (Single Scan of Inner Table)
                              [ Inner Table (orders) ]

1. The engine reads a block of $B$ outer rows into the Join Buffer RAM at once.
2. It performs a single sequential scan of the inner table orders, matching every inner row against all $B$ outer rows in RAM simultaneously.
3. It clears the buffer, loads the next $B$ outer rows, and repeats.

• Time Complexity: $\mathcal{O}\left(M \times \left\lceil \frac{N}{B} \right\rceil\right)$
• I/O Reduction: Reduces inner table scans from $M$ down to $\left\lceil \frac{M}{\text{Buffer Capacity}} \right\rceil$.

---

2. Hash Joins

MySQL 8.0 introduced Hash Joins to replace Block Nested Loop joins for non-indexed join conditions, offering orders-of-magnitude performance gains.

A Hash Join executes in two distinct phases: The Build Phase and The Probe Phase.

[ Phase 1: Build Phase ]               [ Phase 2: Probe Phase ]

 Smaller Table (users)                  Larger Table (orders)
        |                                       |
        v Hash(user_id)                         v Hash(user_id)
 +--------------------+                  +--------------------+
 |  In-Memory Hash    | <--------------- | Probe Hash Table   |
 |  Table (RAM)       |  Match Found?    | Stream Row-by-Row  |
 +--------------------+                  +--------------------+

Phase 1: The Build Phase

• The engine scans the smaller outer dataset (Build Input).
• It calculates a hash value $h(k)$ on the join column for each row and inserts the tuple into an in-memory hash table in RAM.

Phase 2: The Probe Phase

• The engine streams rows from the larger inner dataset (Probe Input) one by one.
• For each row, it calculates the hash value $h(k)$ of its join key and performs an $\mathcal{O}(1)$ lookup against the in-memory hash table.
• If a hash match is found, it verifies key equality (handling hash collisions) and emits the joined tuple.

Time & Memory Complexity

• Time Complexity: $\mathcal{O}(M + N)$ linear execution!
• Memory Overhead: Requires enough RAM to hold the Build Input hash table.

Handling Overflow: Grace Hash Join

If the build table exceeds available RAM (join_buffer_size), the engine switches to a Grace Hash Join:

1. It partitions both the build input and probe input into matching pairs of disk bucket files using a secondary hash function $h_2(k)$.
2. It processes each partition pair sequentially in RAM, loading build buckets into memory one at a time.

---

3. Sort-Merge Joins

A Sort-Merge Join is most effective when join inputs are already ordered by the join column (for instance, when retrieving data directly from sorted B+ Tree leaf nodes).

It consists of two phases:

[ Input A (Unsorted) ] ---> Sort Phase ---> [ Sorted Stream A: 1, 3, 5, 8 ] 
                                                                  |
                                                            Merge Phase (Two Pointers)
                                                                  v
[ Input B (Unsorted) ] ---> Sort Phase ---> [ Sorted Stream B: 2, 3, 4, 8 ]

Phase 1: Sort Phase

Both input streams are sorted by their join keys. If an index already maintains order, this phase takes $\mathcal{O}(0)$ extra work. Otherwise, an external merge sort is performed ($\mathcal{O}(N \log N)$).

Phase 2: Merge Phase

The engine maintains two cursor pointers pointing to the top of each sorted input stream:

ptr_A = sorted_stream_A.first()
ptr_B = sorted_stream_B.first()

while ptr_A and ptr_B:
    if ptr_A.key == ptr_B.key:
        emit(ptr_A, ptr_B)
        ptr_B.advance()
    elif ptr_A.key < ptr_B.key:
        ptr_A.advance()
    else:
        ptr_B.advance()

• Time Complexity: $\mathcal{O}(M \log M + N \log N)$ for sorting, plus $\mathcal{O}(M + N)$ for the merge pass.
• Key Advantage: Efficient for range joins (e.g., ON a.val BETWEEN b.low AND b.high) where hash tables cannot perform equality lookups.

---

Complete Algorithmic Comparison Matrix

Join Algorithm	Time Complexity	Memory Requirement	Requires Indexed Join Key?	Best Used For
Index Nested Loop (INLJ)	$\mathcal{O}(M \log N)$	$\mathcal{O}(1)$ Low	Yes (Inner table)	Small filtered outer table matching selective inner B+ Tree index
Block Nested Loop (BNL)	$\mathcal{O}(M \times \lceil N/B \rceil)$	$\mathcal{O}(B)$ Join Buffer	No	Legacy fallback when no indexes exist (Replaced by Hash Join)
In-Memory Hash Join	$\mathcal{O}(M + N)$	$\mathcal{O}(M)$ Build Input	No	Equi-joins (=) without indexes where build input fits in RAM
Grace Hash Join	$\mathcal{O}(M + N)$	$\mathcal{O}(\text{Partition RAM})$	No	Large equi-joins without indexes that exceed system RAM
Sort-Merge Join	$\mathcal{O}(M + N)$*	$\mathcal{O}(1)$ if pre-sorted	No (But benefits if pre-sorted)	Large datasets already sorted by B+ Tree index or non-equality range joins

* Assuming inputs are pre-sorted by an index.

---

Summary & Next Steps

Choosing the right join algorithm determines whether a database query completes in milliseconds or minutes:

• Index Nested Loop leverages existing B+ Trees for fast point lookups on selective subsets.
• Hash Join converts complex multi-million row equi-joins into linear $\mathcal{O}(M+N)$ in-memory lookups.
• Sort-Merge Join excels when data streams are pre-ordered by index leaves or when handling range join predicates.

In the next article, we examine Composite & Covering Indexes: Maximizing Index-Only Scans and Avoiding Table Lookups.

References & Further Reading

1. Berenson, H., Bernstein, P., Gray, J., Melton, J., O’Neil, E., & O’Neil, P. (1995). A Critique of ANSI SQL Isolation Levels. ACM SIGMOD Record, 24(2), 1–10.
2. Adya, A., Liskov, B., & O’Neil, P. (2000). Generalized Isolation Level Definitions for OLTP Systems. Proceedings of ICDE, 67–78.

---