The join order is a guess

Two ways to join, and the ratio that decides chose between join methods for two collections whose sizes were known, and found the decision was a ratio between the smaller collection and memory. It ended by pointing out that a query joining more than two tables has a shape as well as a method — which pair is joined first — and that the shape is chosen on the sizes of intermediate results that do not exist until the plan runs.

This page measures the smallest version of that problem. Three relations, $R$, $S$ and $T$. $S$ joins $R$ on a column $a$ and joins $T$ on a column $b$. There are two orders: join $R$ with $S$ first and then bring in $T$, or join $S$ with $T$ first and then bring in $R$. Both return exactly the same rows. The planner chooses between them on its estimate of the first intermediate result, and the estimate is made the way a textbook planner makes it: the product of the two sizes divided by the number of distinct values in the join column, which is exactly right when every value is equally common.

The experiment then makes the values unequally common.

The instance, and what the estimate assumes #

The sizes are chosen to make the decision a real one. $R$ has 4,000 rows, $S$ has 40,000 and $T$ has 2,000. Column $a$ has 1,000 distinct values and column $b$ has 500. So the uniform estimate for $R \bowtie S$ is $4{,}000 \times 40{,}000 / 1{,}000 = 160{,}000$ rows, and the estimate for $S \bowtie T$ is $40{,}000 \times 2{,}000 / 500 = 160{,}000$ as well.

Those two estimates being equal is deliberate. It means the planner thinks the two orders are close — its estimated costs are within a few per cent of each other — and it means any difference in the true costs is created entirely by how wrong the estimates are. Column $b$ stays uniform throughout, so the estimate for $S \bowtie T$ stays right. Column $a$ is drawn from a Zipf distribution with an exponent that is swept from zero, where it is uniform, upwards.

Every plan is priced in block transfers with blocks of 64 records and memory of 4,096, using a hash join at each step, and its cost is split into two parts that matter separately. One part is the output: every order ends by producing the same final result, and writing that result costs the same whichever order produced it. The other part is everything else — building and probing the intermediate result — and that part is what the order decides.

What the planner believes, and how sure it sounds #

The estimate produces a cost for each order as well as a size, and those costs deserve a look before the true ones do, because they are what a planner would print if asked to explain itself.

On this instance the planner prices joining $R$ with $S$ first at 16,345 transfers and joining $S$ with $T$ first at 18,220. It prefers the first by about eleven per cent. That margin does not change as the skew is swept, because nothing the estimate reads changes: the row counts and the distinct-value counts are the same at every exponent, and only the distribution of the values moves.

An eleven per cent margin sounds like a close call, and a planner that reported it would sound appropriately cautious. It is not a confidence. It is the difference between two numbers computed under an assumption, and it says nothing about how far either number is from the truth when the assumption fails. The outlined bars in the plates below stay the same length throughout while the solid bars — the true costs — grow by a factor of seventy and change order. A small estimated margin can sit on top of an enormous true one in either direction, and nothing in the estimate can tell which.

That is the same structure the estimate a plan rests on found for a single access path, one level up. There the decision’s input was one estimated number; here it is an estimated number fed into a cost formula whose output is compared with another estimated cost. The comparison inherits the error of both, and the margin between them is not measured in the same units as the error.

When the column is uniform, the estimate is right and nothing is lost #

The uniform case is the control and it behaves as a control should. The estimate is within a fraction of a per cent; the chosen order is the better one; and the outlined bars — the estimated costs — are the right size relative to each other, even though a planner’s cost formula never reproduces the true transfer count exactly.

The split is worth looking at before it becomes the subject. Here the shared output is small, about ten thousand transfers, because the final result is modest; the decided part is most of each bar. That will not stay true.

When the column is skewed, the estimate is out by seventy-two #

Two things happened at once, and the second one hides the first.

The intermediate result exploded. Under skew, the most common values of $a$ are common in both $R$ and $S$, because both columns were drawn from the same distribution. The size of a join is the sum over values of the product of their counts, and a sum of products is dominated by the values that are frequent on both sides. The uniform estimate replaces every count by the average, and the product of two averages is far below the average of the products whenever the same values are frequent in both. At an exponent of 1.2 the gap is a factor of 71.6.

The shared output exploded too. The final result contains every combination produced by the heavy values, so it grew with the same skew, and writing it now costs 712,984 transfers in both plans. That cost is identical in the two bars, and it is large.

So the regret over the whole plan — the ratio anyone would compute first — is 1.49. A planner that is off by seventy-two times on its most important estimate chose a plan that costs half again as much as the best one. That reads as a moderate miss.

The part of the plan the planner actually decided — build the huge intermediate result, or build a small one and join the heavy side last — costs 43.9 times as much in the chosen order as in the better one. The 1.49 is not wrong; it is a ratio with a denominator that includes a large cost no choice could have changed. A sixth of what, exactly is this collection’s standing warning about a ratio whose denominator is unstated, and this is the cleanest instance of it on the site: two correct ratios from the same run, 1.49 and 43.9, differing only in what they are divided by.

The sweep: the whole-plan regret saturates and the decided regret does not #

The three curves have different shapes, and the shapes are the argument.

The estimate’s error rises steeply with skew, as the sum-of-products argument says it must. The decided regret rises with it, a little below it, because the cost of building an intermediate result is roughly proportional to its size and the order that builds the huge one is paying for exactly the rows the estimate did not expect.

The whole-plan regret flattens at about one and a half. It flattens because as skew grows the shared output grows as fast as the decided cost does — both are driven by the same heavy values — so their ratio approaches a constant. Past a point, making the estimate worse makes the plan’s total worse only by making the unavoidable part larger too.

The extension makes the divergence stark. Between an exponent of 1.2 and one of 2, the estimate got about five and a half times worse, the decided regret got five and a half times worse, and the whole-plan regret changed in the second decimal place.

If a planner’s quality were judged by the ratio of chosen plan to best plan — the obvious metric, and the one a benchmark reports — this planner would look nearly as good at an exponent of two as at one of 1.2. It is two hundred and forty times worse at the thing it is responsible for.

Which denominator a planner should be judged by #

Both ratios are correct, so the question is which one answers the question being asked, and there are two honest questions.

“How much slower was this query than it needed to be?” The whole-plan ratio answers that, and 1.50 is the right answer. A user waiting for the query waited half again as long as the best plan would have made them wait. For a person running one query, that is the number that matters, and it is reassuringly small.

“How good is this planner at choosing orders?” The whole-plan ratio does not answer that at all, because it mixes the planner’s choice with a cost the planner had no choice about. A planner that chose orders at random would also score close to 1.50 on this query at high skew, since any order writes the same enormous output. The decided ratio isolates the choice, and 243.9 is the answer to the second question.

The error names its denominator is the theme for exactly this, and three savings in three currencies is the essay that measures it in a different setting — three savings each correct in its own unit and incomparable across them. The whole-plan ratio and the decided ratio are two currencies for the same mistake. Reporting only the first is how a planner that is wrong by two orders of magnitude on its central estimate can look, in a table of end-to-end timings, like one that is doing reasonably well.

There is a further consequence for anyone comparing planners on a benchmark. Queries whose outputs are large compress every planner’s regret towards one, and queries whose outputs are small let every difference show. A benchmark dominated by large outputs will rank planners as nearly equal whatever their estimates are like, and that ranking is a property of the benchmark’s queries rather than of the planners. A saving quoted without its collection makes the same point about compression ratios: a number summarising a method is a number summarising a method on something, and the something decides it.

When the other join is the expensive one #

A last variation says what the size of the decided regret depends on. Making column $b$ nearly as unselective as the skewed column makes the other order expensive too, so the order matters less and the decided regret falls to 4.7 at the same estimate error. The estimate is exactly as wrong as before; the choice it corrupts is smaller.

So the damage an estimation error does is not a function of the error alone. It is the error multiplied by how different the alternatives are, which is a property of the whole query. The same point was made about a single access path in the estimate a plan rests on, where the damage depended on the ratio between scattered and sequential reads; here it depends on the ratio between the two intermediate results the orders build.

Why the estimate is wrong in exactly this way #

The uniform estimate is a formula with an assumption hidden in the word “distinct”. Dividing by the number of distinct values treats every value as having the average frequency, and a join’s size is not a function of average frequencies. For two columns with count functions $f_R(v)$ and $f_S(v)$ it is $\sum_v f_R(v)\,f_S(v)$ — a second moment when the two distributions are the same — and a second moment is dominated by the largest counts.

That makes the error predictable in direction. For two columns skewed the same way the estimate is always too low, and the error grows with how concentrated the heaviest values are.

The sum of products has a name elsewhere in this collection. When the two count functions are the same, $\sum_v f(v)^2$ is the second frequency moment of the column, and the estimate that squares the stream measures a sketch that estimates exactly that quantity in a single pass with a handful of counters — the tug-of-war sketch, whose original motivation was estimating the sizes of joins. So the quantity a uniform estimate gets wrong is not an exotic one. It is the best-studied quantity a stream summary estimates, and a planner that kept two such sketches per join column could estimate the size of the join between them from the sketches alone, with an error bound that does not depend on skew. For two columns whose heavy values are different — frequent in one table, rare in the other — the error can run the other way. The independence assumption behind the formula, the same one the estimate a plan rests on found pushing single-table estimates low, is here an assumption that frequency is unrelated to identity, and in real data it is not: the popular products are popular in the orders table and the reviews table at once.

It also says what information would repair it. The second moment is dominated by the heavy values, so an estimate that knew the counts of the heaviest few values in each column — and assumed uniformity only for the rest — would capture most of the sum. That is exactly the summary the items that survive k counters computes in one pass over a stream with $k$ counters: the frequent items with guaranteed error bounds. A planner that kept such a summary per join column would be spending a few hundred counters to fix the quantity that decided this query.

An error measured against the answer makes the complementary point about what those counters promise: an additive error on counts is small relative to the heavy values and enormous relative to the light ones. For a join estimate that is the right promise, since the light values contribute little to a sum of products.

What the model leaves out #

One intermediate, two orders. A query with more joins has more intermediates, each estimated from estimates, and errors in a product compound multiplicatively. The decided regret on this page is what one error does to one choice; a four-way join makes several choices on errors that multiply, and the number of orders grows faster than exponentially.

One join method. Every step here is a hash join. A planner also chooses methods, and a wrong size estimate can choose a nested-loop join for an input it thinks is small, which fails far more dramatically than a wrong order: the method that is right for a hundred rows can be quadratic on eleven million.

Skew in one column only, and the same skew on both sides of it. That is the case that maximises the estimate’s error. Real columns are skewed in different ways and to different extents, and correlation between tables is what decides how large the product of counts is.

No runtime correction. Modern systems can observe an intermediate result’s true size and re-plan the rest of the query. That repairs exactly this failure after it has cost one intermediate, which on this instance is most of the decided cost.

Where this ladder goes next: the heavy values a join estimate needs #

The repair sketched above is concrete enough to measure, and this collection already has the summary it needs.

Keep a Misra–Gries summary with $k$ counters for each join column. Estimate a join’s size as the exact sum of products over the values both summaries report as heavy, plus the uniform estimate over the remaining rows and remaining distinct values. Then sweep the same skews and ask two questions of the result: how much of the 43.9 — and of the 243.9 — does the corrected estimate remove, and how does that depend on $k$?

The prediction is that a few dozen counters remove nearly all of it, because the sum of products at high skew is carried by a handful of values. The more interesting prediction is where it fails: at a moderate exponent the heavy values are not heavy enough to dominate, the summary’s additive error is comparable to their counts, and the corrected estimate may be no better than the uniform one. Where that crossing falls, in counters against skew, is a number a planner designer would want, and it is the natural next measurement on this ladder.