Join algorithms: nested loops, sort-merge, hash

A join pairs the rows of two inputs whose join keys match, and database engines have three ways to do it. A nested loop join takes each row, or block of rows, of the outer input and finds its matches in the inner input, by scanning it or through an index. A sort-merge join sorts both inputs on the key and walks them together. A hash join loads the smaller input into a hash table on the key and looks up every row of the other input in it. Which one is fastest depends on the sizes of the inputs, the memory, the indexes and the order the rows arrive in, and the planner prices each candidate before it chooses. This lesson prices all three on one example in page I/Os, then shows SQLite’s nested loops at work in your browser.

Three ways to pair rows

Nested loops come in three forms. The simple nested loop reads the whole inner input once for every outer row. The block nested loop holds B − 2 pages of the outer input in memory and scans the inner input once per block. The index nested loop looks each outer row up in an index on the inner join key.

A sort-merge join sorts both inputs on the join key, unless an index or an earlier step already delivers them in that order, then merges them in one pass over each. Rows with equal keys on both sides must all be paired, so the merge reads a group of equal keys on one side again for every matching row on the other.

A hash join builds a hash table on the smaller input, the build side, and probes it with each row of the larger one. When the table does not fit in memory, a Grace hash join first splits both inputs into partitions by a hash of the key, so that matching rows always land in the same pair of partitions, and then joins the pairs one at a time. A hybrid hash join keeps the first partition in memory while it splits, which saves writing and reading it.

What each join costs in page I/Os

For an outer input of M pages with p rows a page, an inner input of N pages and B pages of memory:

The program prices them for orders, 1,000 pages of 100 rows, joined to customers, 500 pages, with B = 102:

"""Page I/Os of the classic join algorithms for orders (1,000 pages) joined to customers (500 pages), B = 102."""

from math import ceil

ORDERS, CUSTOMERS = 1_000, 500          # pages
ORDERS_PER_PAGE = 100                   # rows per page of orders
B = 102                                 # buffer pages


def block_nested_loop(outer: int, inner: int) -> int:
    """Read the outer input B - 2 pages at a time; scan the inner input once per block."""
    return outer + ceil(outer / (B - 2)) * inner


def sort_passes(pages: int) -> int:
    runs, passes = ceil(pages / B), 1
    while runs > 1:
        runs, passes = ceil(runs / (B - 1)), passes + 1
    return passes


costs = {
    "nested loop, one outer row at a time": ORDERS + ORDERS * ORDERS_PER_PAGE * CUSTOMERS,
    "nested loop, one outer page at a time": ORDERS + ORDERS * CUSTOMERS,
    "block nested loop, orders outside": block_nested_loop(ORDERS, CUSTOMERS),
    "block nested loop, customers outside": block_nested_loop(CUSTOMERS, ORDERS),
    # Sort both inputs completely (each pass reads and writes the file), then read both once to merge.
    "sort-merge, sorting each input fully": sum(2 * p * sort_passes(p) + p for p in (ORDERS, CUSTOMERS)),
    # 10 + 5 sorted runs fit in one merge (at most B - 1 = 101): the join merges the runs directly.
    "sort-merge, merging the runs in the join": 3 * (ORDERS + CUSTOMERS),
    # Partition both inputs into B - 1 partitions, write them, read them back pair by pair.
    "Grace hash join": 3 * (ORDERS + CUSTOMERS),
}
print(f"orders {ORDERS:,} pages, customers {CUSTOMERS:,} pages, B = {B} buffer pages\n")
for name, ios in sorted(costs.items(), key=lambda kv: kv[1]):
    print(f"{name:<42}{ios:>12,} page I/Os")
print(f"\nGrace hash join needs each customers partition to fit: {ceil(CUSTOMERS / (B - 1))} pages <= {B - 2}")

orders 1,000 pages, customers 500 pages, B = 102 buffer pages

sort-merge, merging the runs in the join         4,500 page I/Os
Grace hash join                                  4,500 page I/Os
block nested loop, customers outside             5,500 page I/Os
block nested loop, orders outside                6,000 page I/Os
sort-merge, sorting each input fully             7,500 page I/Os
nested loop, one outer page at a time          501,000 page I/Os
nested loop, one outer row at a time        50,001,000 page I/Os

Grace hash join needs each customers partition to fit: 5 pages <= 100

Grace hash join and the sort-merge join that merges both inputs’ runs at once tie at 4,500 page I/Os. The block nested loop costs 5,500 with customers outside and 6,000 with orders outside, so the smaller input belongs outside. Taking one outer row at a time, the simple nested loop needs 50 million I/Os, which is why no engine runs it on large inputs. The index nested loop is not in the list because its cost depends on how many outer rows there are: it wins when only a few survive a filter.

SQLite: every join is a nested loop

SQLite has no hash join and no merge join: its documentation says that it implements every join as nested loops. When the inner table has no index on the join key, it can build one for the query:

-- 600 customers with a pincode each, and 500 pincodes with their districts. pincodes has no index at all.
CREATE TABLE customers (id INTEGER PRIMARY KEY, name TEXT NOT NULL, pincode INTEGER NOT NULL);
CREATE TABLE pincodes (pincode INTEGER NOT NULL, district TEXT NOT NULL);
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 600)
INSERT INTO customers SELECT i, 'customer ' || i, 411000 + i % 50 FROM n;
WITH RECURSIVE n(i) AS (SELECT 0 UNION ALL SELECT i + 1 FROM n WHERE i < 499)
INSERT INTO pincodes SELECT 411000 + i, 'district ' || (i % 7) FROM n;

-- 1. SQLite's plan: an outer loop over customers and an inner loop that searches an index built for this query.
EXPLAIN QUERY PLAN
SELECT c.name, p.district FROM customers AS c JOIN pincodes AS p ON p.pincode = c.pincode;

-- 2. With automatic indexes switched off, the inner loop scans all 500 pincodes for every customer.
PRAGMA automatic_index = OFF;
EXPLAIN QUERY PLAN
SELECT c.name, p.district FROM customers AS c JOIN pincodes AS p ON p.pincode = c.pincode;

-- 3. Both plans return the same 600 rows.
SELECT count(*) AS joined_rows FROM customers AS c JOIN pincodes AS p ON p.pincode = c.pincode;

┌────┬────────┬─────────┬─────────────────────────────────────────────────────┐
│ id │ parent │ notused │                       detail                        │
├────┼────────┼─────────┼─────────────────────────────────────────────────────┤
│ 3  │ 0      │ 216     │ SCAN c                                              │
│ 7  │ 0      │ 0       │ BLOOM FILTER ON p (pincode=?)                       │
│ 17 │ 0      │ 53      │ SEARCH p USING AUTOMATIC COVERING INDEX (pincode=?) │
└────┴────────┴─────────┴─────────────────────────────────────────────────────┘
┌────┬────────┬─────────┬────────┐
│ id │ parent │ notused │ detail │
├────┼────────┼─────────┼────────┤
│ 3  │ 0      │ 216     │ SCAN c │
│ 5  │ 0      │ 216     │ SCAN p │
└────┴────────┴─────────┴────────┘
┌─────────────┐
│ joined_rows │
├─────────────┤
│ 600         │
└─────────────┘

The first plan scans customers in the outer loop and searches pincodes through an AUTOMATIC COVERING INDEX in the inner one. SQLite builds such an index only when it expects the lookups to repay the work of building it, keeps it for that one statement, and describes it as almost the same thing as a hash join with a B-tree in place of the hash table. The BLOOM FILTER line is a quick membership test, added to SQLite’s planner in version 3.38.0, that skips the index search for a pincode that cannot be in the table. With automatic indexes switched off, the second plan scans all 500 pincodes for each of the 600 customers: 300,000 row comparisons for the same 600 rows.

Exercise

"""Which join is cheaper for two inputs of known size and a given number of buffer pages?"""

from math import ceil


def best_join(r_pages, s_pages, b):
    """(name, page_ios) of the cheaper of a block nested loop join and a Grace hash join."""
    return ("block nested loop", 0)

from choose import best_join


def test_lesson_example():
    """1,000 and 500 pages with 102 buffer pages: the hash join's 4,500 I/Os beat the nested loop's 5,500"""
    assert best_join(1000, 500, 102) == ("grace hash", 4500)
    assert best_join(500, 1000, 102) == ("grace hash", 4500)


def test_small_input_fits():
    """When the smaller input fits in one block, the nested loop reads each input once"""
    assert best_join(1000, 50, 102) == ("block nested loop", 1050)


def test_partitions_too_big():
    """With 12 pages, partitions of 10,000 pages cannot fit, so only the nested loop is left"""
    assert best_join(10_000, 10_000, 12) == ("block nested loop", 10_010_000)


def test_partition_boundary():
    """With 12 pages, 110 pages split into 11 partitions of 10 pages, which fit; 115 pages do not"""
    assert best_join(110, 200, 12) == ("grace hash", 930)
    assert best_join(115, 200, 12) == ("block nested loop", 2515)


def test_tie_prefers_hash():
    """When both cost the same, the answer is the hash join: 40 and 40 pages with 10 buffer pages cost 240 either way"""
    assert best_join(40, 40, 10) == ("grace hash", 240)

Check yourself

Nested loops in depth: blocks, indexes and the lookups that add up Pro: opens with a Pro, Premium or Ultimate pass

Sort-merge and hash joins: duplicates, partitions and skew Pro: opens with a Pro, Premium or Ultimate pass

Choosing a join with numbers, and steering PostgreSQL to test it Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Nested loops find matches for each outer row or block, sort-merge walks two sorted inputs together, and a hash join probes a table built on the smaller input.
• Block nested loop costs M + ⌈M / (B − 2)⌉ × N: put the smaller input outside. Grace hash join costs 3 × (M + N) when its partitions fit.
• An index nested loop wins only when few outer rows survive, and the other two win for large unordered inputs.
• SQLite runs every join as nested loops and builds automatic indexes when they pay off; PostgreSQL chooses among Nested Loop, Merge Join and Hash Join by cost.