Two ways to join, and the ratio that decides

Two collections of records, each with a key. Produce every pair whose keys agree. That is a join, it is the operation a relational database spends most of its time on, and it is the one place in this field where the two primitives already established — a scan and a sort — are assembled into something larger.

There are three standard ways to do it and every serious system implements all three. The interesting thing is not that one of them is best. It is that which one is best is not decided by how large the inputs are.

That is worth dwelling on before any of the plans is described, because it is the difference between a rule and a rule of thumb. A rule of thumb says something like use a hash join above ten thousand rows, and ten thousand rows is a number about the machine the person saying it last measured on. The rule the plate supports is that the plan changes at about three times memory — a dimensionless quantity, the same on every machine, and computable from two numbers a system already holds.

Three methods, and what each one is afraid of #

The block nested loop holds as much of one collection in memory as will fit, then scans the other past it. Every row of the resident chunk is compared against every row streamed by, so nothing is missed, and the cost is one scan of the outer collection plus one scan of the inner per chunk: $\lceil R/B \rceil + \lceil R/(M-2B) \rceil \cdot \lceil S/B \rceil$.

The whole of its behaviour is in that ceiling. If $R$ fits in memory the ceiling is one and the join costs two scans, which is the cheapest anything can be — a join has to read both inputs. If $R$ is twice memory the ceiling is two and the inner collection is read twice. The cost is not quadratic in the sizes; it is linear in the number of chunks, and the number of chunks is $R/M$.

The partitioned hash join hashes both collections on the key so that matching rows are guaranteed to land in matching partitions, writes each partition out, and then joins the pairs one at a time. Two rows with the same key have the same hash, so a partition of $R$ and the corresponding partition of $S$ contain between them every match involving those keys, and no other partition can. The cost is one read and one write of both collections to partition them, then one read of both to join: three scans of each, independent of how large either is — as long as a partition of $R$ fits in memory.

The sort–merge join sorts both collections by key and then walks them together. The cost is two external sorts and a merge pass, which is the dearest of the three when nothing is sorted, and it produces a sorted result, which none of the others does.

Read those three descriptions side by side and a pattern appears that is worth naming, because it is the one this whole field is about. None of the three does less work than the others in any sense a comparison count would recognise: all three examine every row of both inputs, and the hash join and the sort–merge join examine several of them more than once. What separates them is entirely how many times the data crosses the boundary between memory and everything else. One access, eight kilobytes opened this field with that observation on a single loop; a join is the same observation on an operator large enough that a system has three implementations of it.

The measurement, and what it is checked against #

The numbers below are one collection of 16,384 rows joined against a key side of growing size, at a block of sixty-four rows and a memory of five hundred and twelve.

The last column is the check and it is the reason this measurement can be believed. Three methods sharing no code beyond the block counter produce the identical number of matching pairs at every row, and that is not a formality: a hash join whose partitioning function disagreed with itself between the two inputs would lose matches, report a low cost, and produce a plate that looked exactly like this one. The gate requires the three to agree and requires them not to cost the same, since three identical costs would mean there was nothing to choose between them.

That is the same discipline Prim and Kruskal are held to in the graph field — two algorithms with nothing in common agreeing on a number is the strongest evidence available — and it is the only kind of check that catches a silent loss.

One row of that table deserves reading on its own. At half of memory the nested loop costs 260 transfers, and two scans of the inputs — the floor for any join, since both have to be read — is $\lceil 256/64 \rceil + \lceil 16384/64 \rceil = 260$. The plan is exactly at the floor, to the transfer, and it is at the floor because when the key side fits in memory there is nothing left for a join to spend anything on. That is the case every other plan is paying to avoid and none of them can beat.

Why the deciding quantity is a ratio #

Set the nested loop’s cost against the hash join’s and the sizes mostly cancel. The nested loop is about $\frac{R}{B} + \frac{R}{M}\cdot\frac{S}{B}$ and the hash join is about $3\left(\frac{R}{B} + \frac{S}{B}\right)$, so the comparison turns on whether $\frac{R}{M}$ — the number of chunks — exceeds a small constant. Below about three chunks the nested loop wins; above it the hash join does, and it wins by a factor that grows without limit while the hash join’s cost stays flat.

Everything else has cancelled. $B$ has cancelled. The absolute sizes have cancelled except through the ratio $S/R$, which shifts the constant. The decision is about how many times the key side has to be swept past memory, and nothing else.

That is worth contrasting with the previous rung, because it is the opposite shape. The index that is not worth reading turns on a quantity — the selectivity — that the query supplies and the planner has to estimate. This one turns on a quantity the system already knows exactly: the size of a table and the size of its own buffer pool. A join plan chosen on this basis is chosen on facts rather than on a histogram, which is why join order is the part of query planning that goes wrong and join method is not.

There is a further consequence, and it is about how a system should be tuned rather than about how it should choose. A buffer pool that grows moves every join on the machine leftward along the same axis, and the improvement it buys is not smooth: joins whose key side sits just above three times memory improve by a large factor when memory doubles, and joins whose key side sits at thirty times memory improve by almost nothing, because they were on the flat part of the curve already. Adding memory helps the joins that were nearly fitting and does very little for the ones that were not, which is a distribution question rather than an average one — the same shape the cliff where the data stops fitting measures for a working set crossing a cache.

What each plan needs that the others do not #

The transfer counts hide three preconditions and each of them has cost a real system a correctness bug or a performance cliff.

The hash join needs the partitions to fit. If a partition of $R$ is still larger than memory after one pass, it must be partitioned again — and the recursion is on data that has already been shown to hash into one bucket, which is to say, on data whose keys are skewed. A hash join over a column where one value covers a third of the rows does not partition that value at all, and the standard repair is to detect it and fall back to a nested loop for that partition. So the flat line on the plate is flat only for keys that spread, and the whole of a hash join’s engineering is about the keys that do not.

The nested loop needs nothing and that is its entire justification. It works on any predicate, not merely equality — an inequality join or a range overlap has no hash and no sort order to exploit — and it is the only one of the three that does. A plan that costs $\frac{R}{M}$ scans of $S$ is a bad plan and it is sometimes the only plan.

And the sort–merge join needs a sort order that means something. It is the plan that wins when one side is already sorted, which is exactly the case when the join is on a clustered index’s key or when the previous operator in the plan produced sorted output. Its cost on the plate is the cost with neither side sorted, which is its worst case rather than its typical one, and a plan that arrives with $S$ already in key order costs one sort and a merge instead of two sorts and a merge.

The skew case is worth one more sentence because it is where a measured plate is most misleading. Every key set on this page is drawn uniformly, which is the best case for partitioning and the case its analysis assumes. Real join columns are not uniform — a foreign key into a table of countries has a few values covering most of the rows — and the partition holding the popular value is as large as the skew. The transfer count of a hash join on skewed keys is therefore not the flat line drawn here but something between it and the nested loop’s, and which end it lands nearer is a property of the data. A hash is a family, not a function makes the general version of the point: what a hash does to a key set is a fact about the pair, not about the hash.

The partitioning is the interesting half #

The nested loop and the sort–merge join are assemblies of things this field already had. The hash join contains one idea that is genuinely new here, and it is worth isolating because it recurs.

The problem a join has to solve is that a match can be between any row of one collection and any row of the other, so a naive method must consider $R \times S$ pairs. Partitioning replaces that with a guarantee: two rows that match are in the same partition, because the partition is a function of the key alone and matching rows have equal keys. So the $R \times S$ pairs collapse to $\sum_i R_i \times S_i$, and with $p$ partitions of even size that is $RS/p$ — a factor of $p$ from one pass over the data.

That is exactly the move a q-gram filter makes on strings and a Bloom filter makes on membership: spend a cheap pass computing a function of each item, and use the fact that the function agrees on anything that could match to avoid comparing things that cannot. The candidates a filter cannot avoid is the same argument for approximate matching, and the failure mode is the same too — the guarantee is one-sided, so the partitions may still contain non-matching pairs and the join has to check.

The economics of it are worth stating in the field’s own unit. One pass over both inputs costs $(R+S)/B$ transfers and buys a factor of $p$ on the pair count, where $p$ is roughly $M/B$ — the number of output blocks that can be held at once. So the exchange is one scan for a factor of $M/B$, which at the parameters on the plate is one scan for a factor of eight, and it is available exactly once: partitioning twice costs a second scan and buys a second factor of eight, which is why the recursion terminates almost immediately and why a hash join is described as a two-pass algorithm rather than as a logarithmic one.

What is unusual here is that the partitioning is not an optimisation but a reduction: it turns one large join into many small ones, and the small ones are solved by the plan the large one could not use. A hash join’s inner loop is a nested loop, run on data small enough that the nested loop’s problem has gone away.

What this does not measure, and one of the omissions is large #

No plan here produces output. Every count above is the cost of finding the matches, and a join that finds four thousand pairs has to write four thousand pairs somewhere. That output cost is the same for all three plans, so it does not change the ordering — but it does change the ratios, and on a join whose output is larger than either input it dominates everything on this page.

The costs are counts and not durations. All three plans read and write in long sequential runs, which is the case a device is best at, so the counts here are unusually good predictors of relative cost — but they are still counts, and the count is not the time is the standing rule. The one asymmetry worth flagging is that the hash join’s partitioning writes are scattered across $p$ output streams rather than sequential, so its middle scan is the least device-friendly transfer on this page and is charged the same as the others.

Nothing is parallel. All three plans partition beautifully across machines and they do not partition equally well: the hash join’s partitions are independent by construction and are the standard unit of distribution, while a nested loop must broadcast one side to every worker. That difference is the reason a distributed system’s plan choices look nothing like a single machine’s, and no count taken here can see it.

And nothing here is an index join. A fourth plan exists and this field already has the machinery for it: walk one collection and probe an index on the other, one descent per row. Its cost is $S/B + R \cdot h$ with $h$ the index height, which beats everything on this page when $R$ is small and loses to everything when $R$ is large — and the crossing is the selectivity arithmetic of the previous rung wearing a different name. It is left off the plate because it needs an index to exist, which is a precondition none of the three plans here has.

And the keys are distinct on one side. The measurement uses a key side with no repeats — a primary key — so every row of the other collection matches at most one row. With duplicates on both sides the three methods have to be written to enumerate pairs rather than to test membership, the nested loop’s hash set stops being adequate, and the agreement check that makes this whole page trustworthy would need re-establishing on a harder case. That is a real gap and it is recorded rather than papered over.

Where this ladder goes next: the join that has three inputs #

Everything above is a join of two collections, and the arithmetic that makes the choice a ratio depends on there being exactly two.

A query joining four tables has a shape as well as a set of methods: which pair is joined first, what the intermediate result is, and what its size will be. The number of shapes grows faster than exponentially in the number of tables, the cost of each depends on intermediate sizes that must be estimated rather than known, and the estimates compound — this is the part of query planning that is genuinely hard, and it is hard for a reason this field can state precisely.

The two-table decision on this page is between plans whose costs are known exactly. The multi-table decision is between plans whose costs depend on quantities that will not exist until the plan runs. That is a different kind of problem, and the natural next rung is not another join method. It is a measurement of how wrong an intermediate-size estimate has to be before it changes which shape wins — the same question the previous rung ended on, asked where the answer matters more, because a join order chosen on a bad estimate can be wrong by orders of magnitude rather than by the bounded factor a single-operator choice risks.