Where the index comes from: nested loop, hash and sort-merge

Is the join's index built now, built earlier or replaced by order, and what does each choice cost in memory and I/O?

A join is a decision about where the index comes from

Relational operators described what a join demands. This article answers one question: given "find the rows of S that match this row of R", how do you avoid scanning S once for every row of R?

There are exactly three answers, and they cover all the possibilities:

1. Build a lookup structure now, for this query, and throw it away. This is the hash join.
2. Use a lookup structure someone already built and paid for. This is the indexed nested loop.
3. Impose a common order on both sides, so that matching becomes a linear walk. This is the sort-merge join.

The naive nested loop is the fourth entry and the null answer: do not avoid the scan; pay |R|·|S|.

Distributed execution adds a second question: how do candidate matches end up on the same machine? The answers are again few:

• replicate the small side everywhere (broadcast);
• repartition both sides by key (shuffle);
• use a partitioning that already exists (co-partitioned);
• or move information about the data instead of the data (sideways information passing). This is a different category, and it is the most interesting one.

A structural observation to keep: the distributed algorithms are the local algorithms with the memory bound replaced by a network bound. An in-memory hash join is to a Grace hash join (defined below) as a broadcast join is to a shuffle join. Same recursion, different scarce resource.

The core tension

The hash join is the default in every analytic engine. Its linear cost rests on exactly two assumptions: the predicate is equality, and the keys are roughly uniform.

Look at the remaining items in order. Range joins, interval joins and as-of joins exist because equality failed. Skew handling exists because uniformity failed. The catalogue is not a list of techniques. It lists the two ways the default breaks.

The lattice of join algorithms

(Here M is memory, c_probe is the cost of one index lookup, and the build side is the input that goes into the hash table. The other input, which streams through it, is the probe side.)

Two columns carry more weight than they appear to. "Provides order" is what the enforcer idea predicts will matter: sort-merge is the only algorithm that hands a usable ordering to the next operator, which is how it earns back the log factor it paid. "Reads all of S" has exactly one "no". That single entry is why the indexed nested loop has not been replaced in forty years.

Nested loop: the only algorithm with no assumptions

Naive nested loop rescans S for every row of R.

Block nested loop buffers R in chunks of M pages and scans S once per chunk, so the I/O is |R| + ⌈|R|/M⌉·|S|. The chunk size is memory, and the fixed cost being shared is a full pass over S. It is the plainest case of fixed cost sets the batch size.

Notice what happens when |R| ≤ M: the cost is |R| + |S|, the same as a one-pass hash join. Block nested loop is asymptotically optimal whenever one side fits in memory, and it makes no assumption about the predicate. That is its permanent niche. Any condition a function can evaluate (a geographic predicate, string similarity, a UDF, an inequality with three terms) falls back to it, and nothing better exists in the general case.

Indexed nested loop replaces the inner scan by a probe. The cost is |R| × c_probe. Compared with |R| + |S| it wins when |R| < |S| / c_probe. The whole question is c_probe, and c_probe is a random access. So the real coefficient is the ratio of random to sequential throughput on the storage:

• On rotating disks that ratio was about 100×. That is why analytic systems abandoned the indexed nested loop.
• On NVMe SSDs (fast flash drives) at high queue depth it is closer to 2–10×, which quietly widened the algorithm's range again.
• On object storage there is no ratio, just a per-request latency floor of tens of milliseconds and a per-request price. That pushes the range out again.

The break-even point of this algorithm has moved by three orders of magnitude across storage generations, in both directions. "Indexed nested loop is for OLTP (transaction processing) and hash join is for analytics" is true of one decade's hardware, not of the algorithms.

Its unique property: it is the only join whose cost is sublinear in |S|. Every other algorithm reads both inputs at least once, so |R| + |S| is their floor. The indexed nested loop never reads most of S. When selectivity is high enough, that is not a constant-factor advantage but a different complexity class, and no amount of vectorization closes it.

Hash join: a disposable index, and the one place recursion fails

Build a hash table on the smaller side, then stream the larger side through it. The cost is |R| + |S|, and the memory is proportional to the build side.

# Hash join in 6 lines (in memory)
table = {}
for s in S:                       # build phase: blocking
    table.setdefault(s.key, []).append(s)
for r in R:                       # probe phase: streaming
    for s in table.get(r.key, []):
        emit(r, s)

Three properties come from the structure, not from the implementation:

1. The build is blocking and the probe is streaming. A hash join is half a pipeline breaker. Because the probe side streams through untouched, it keeps its ordering and its partitioning. So choosing the build side is not only a size decision: putting the already-partitioned side on the probe side keeps a property that would otherwise be re-enforced later.
2. The load factor (how full the hash table is, ρ) is the queueing curve inside the operator. Probe cost rises like 1/(1−ρ) with open addressing (a hash table design that stores entries directly in the slot array). That is why engines size tables for ρ around 0.5, and why underestimating the build size makes cost grow faster than linearly.
3. Null keys can be dropped at build time, because they never match (Relational operators).

When the build side does not fit: Grace hash

Grace hash join partitions both sides with a hash function h₁ into p partitions, writes (spills) them to disk, then joins each pair of partitions separately with a second hash function h₂. The extra I/O is 2(|R|+|S|): one write and one read of each side.

Two limits bound p:

• p must be at least |build| / M, so that one build partition fits in memory;
• p must be at most the fan-out F = M/B that the I/O block size allows (one buffer per open partition).

Together: recursion begins when |build| > M²/B. This is the same threshold as external merge sort (see Why a query has many plans). With M = 16 GB and B = 8 MB that is 32 TB of build side per instance.

Why the second hash function matters. If h₁ were reused inside a partition, every key in that partition would share the same h₁ value, so they would all collide in the inner hash table, which would degenerate into a list.

Hybrid hash: a ramp, not a cliff

Hybrid hash keeps partition zero resident in memory throughout, so M bytes are never written or read back. The transition from in-memory to spilled is a linear ramp, not a cliff. If the build side has size m > M, the spilled fraction is (m−M)/m. The ramp is measured against a fully spilled join; against the in-memory join, even a small spill is a cliff, because each spilled byte costs the memory-to-disk bandwidth ratio more.

The dead end

If the rows of a single key exceed M, no value of p helps. Partitioning divides the key space, and one key is an atom of that space: h₁ maps one value to one partition by definition. Recursive partitioning, the escape that rescues every other out-of-core algorithm here, is unavailable. This is not a tuning failure. It is the whole reason skew handling is a separate topic.

Sort-merge: paying a log factor for two things hash cannot sell

Sort both inputs on the join key, then walk through them together with two pointers. Against the hash join's |R| + |S| this looks like a plain loss, and on a single machine in memory it often is. It buys two things.

1. Constant memory in the merge phase. The hash join's memory is proportional to the build side. The merge's memory is proportional only to the largest run of duplicate keys. When memory is the binding constraint (usually true in a multi-tenant engine), sort-merge cannot blow up. That is why it is the fallback when a memory request is refused.

2. An ordering on the join key in the output. A later aggregation, window function or second merge join on the same key uses it for free. That is where the log factor is earned back. And the reverse matters more: if either input is already sorted (a clustered index, a sorted bucketed table, LSM-ordered files (files kept sorted by a log-structured merge tree, explained in Sorting), the output of an earlier merge), half or all of the sort was pre-paid, and merge join beats hash join outright. The merge itself is linear with O(1) memory. The algorithm that requires the property the data already has is the cheap one.

Two liabilities:

• A many-to-many merge must buffer the run of equal keys on one side and re-walk it for each matching row on the other. If the run is large, it spills. So skew hurts merge join as well, through the duplicate run instead of the partition.
• The sort destroys any earlier ordering on anything except the join key.

A note on folklore. "Hash join always beats sort-merge" comes from single-machine, row-oriented systems with narrow SIMD (instructions that process several values at once). The research on in-memory joins has gone back and forth for a decade, and the answer changes with vector width, NUMA layout (how memory is attached to CPU sockets) and key width. At single-node level it is genuinely unsettled. In a distributed engine the question barely matters, because the shuffle dominates both and the local algorithm is noise.