The estimate a plan rests on

The index that is not worth reading drew three plans for one query against the number of rows the query matches, and read the right choice off where the curves crossed. Every point on that plate had something no database has at the moment it chooses: the number of matching rows was known.

A planner does not know it. It has an estimate, computed from a histogram of the column built at some point in the past from a sample of the table, and combined across predicates by a rule that treats the columns as independent. The estimate is wrong, and it is wrong by a factor rather than by a margin, because selectivities multiply: two predicates each estimated within a factor of two give a combined estimate that may be out by four, and a third makes it eight.

So the crossing is not the useful measurement. The useful measurement is what the decision costs when its input is wrong — with the error held at a stated factor and the true answer swept across the whole range it could take.

Why the error is a factor rather than a margin #

It is worth a paragraph on why an estimate of a row count goes wrong multiplicatively, because the shape of every plate below depends on it.

A single predicate’s selectivity is read off a histogram: the column’s values are divided into buckets, the count in each bucket is stored, and a predicate that covers part of a bucket is assumed to cover that part of its count. The error from one bucket is a proportion of that bucket. A second predicate on a different column has its own histogram and its own proportional error, and the planner multiplies the two selectivities together because it has no record of how the columns relate. A filter has a selectivity is this collection’s theme for exactly that product, and every step of the product multiplies the error as well as the answer.

A histogram also summarises a column’s values and throws away everything about how those values sit relative to anything else — which rows they are in, what they co-occur with, in what order they arrived. The histogram that cannot see the order measures one thing a histogram of this kind is blind to, and a planner’s histogram is blind to the same thing for the same reason. So the natural unit for a planner’s error is a factor, and the question to ask of a decision is how it behaves when its input is multiplied by something it does not know.

The experiment, stated before it is run #

The model is the one this ladder has been using, with one addition, and each part of it is worth stating because the conclusions depend on it.

The file holds $n = 65{,}536$ rows in blocks of $B = 64$, so a scan reads 1,024 blocks. An unclustered index descends three levels and then reads each block that contains at least one matching row, once — which is the behaviour that bent the curve above, since past a few hundred matches most blocks contain one. The addition is a number $\rho$: a block fetched out of order costs $\rho$ times a block read in sequence. One access, eight kilobytes set up a model in which every transfer costs the same, which is the right model for counting and the wrong one for choosing, because the reason planners abandon indexes early is that scattered reads are slower than sequential ones.

The planner estimates the index’s cost with the right formula — the expected number of distinct blocks holding $\hat k$ matches, times $\rho$, plus the descent — and compares it with the scan. It is fed $\hat k$, the estimate, rather than $k$, the truth. That isolates the one thing being studied: the planner is not using a bad cost model, it is using the true cost model on a false input.

The chosen plan is then priced at the truth, and divided by the cost of whichever plan was actually cheaper. That ratio is the regret of the decision. A regret of one means the estimate’s error did not change the choice, or changed it between two plans that cost the same; a regret of four means the query did four times the work it needed to.

On this file with $\rho = 4$ the estimate switches from index to scan at 512 rows. Every line below holds the estimate wrong by one factor — always four times too high, say — and slides the true count from one row to sixteen thousand.

That crossing is worth comparing with the one the essay before this found. In a model where every transfer costs the same, the index did not lose to the scan until about a quarter of the file matched — some sixteen thousand rows. With a scattered read costing four sequential ones, the estimated crossing falls to somewhere between 256 and 512 rows, which is where a powers-of-two sweep first sees it. A single constant moved the decision by a factor of thirty or more.

That constant is the whole of the reason a planner abandons an index early, and it is not a property of the index or the query. It is a property of the storage underneath: the cliff where the data stops fitting measures the same step at the boundary between cache and main memory, where a read that leaves the current working set costs an order of magnitude more than one that stays inside it. A block on a disk is that boundary one level further down. So the planner’s decision is being made on two numbers, one of which is an estimate and the other of which is a fact about a device, and both are about to be varied.

Near the crossing, a small error costs little and the low side costs more #

The first thing the plate says is the expected thing: a factor of four near the crossing does very little damage on one side. An overestimate only changes the decision for queries whose true count is between 128 and 512, and in that band the scan and the index cost within about ten per cent of each other — so choosing wrongly there costs about ten per cent.

The second thing is less expected. The underestimate does more damage at the same factor — 2.55 against 1.09. At 1,024 true rows the planner believes 256 and reads the index, and the index at 1,024 rows touches around six hundred and fifty distinct blocks, each paying the scattered-read price, against a scan of 1,024 blocks read in order. The penalty for scattered reads that made the index look expensive in the first place is exactly what the wrong choice pays.

So for small errors the asymmetry runs one way. That is worth holding onto, because for large errors it runs the other.

The flatness near the crossing is not a coincidence of these numbers. Two plans whose costs cross must be close to each other near the crossing, so any decision rule that errs only in that neighbourhood errs cheaply — which is why a threshold chosen roughly is so often good enough, and why the flat bottom of a shallow curve finds a tuning parameter whose optimum is hard to locate and easy to live without. The same argument says nothing at all about an error large enough to carry the decision far from the crossing, and that is where the two sides of the plate stop resembling each other.

Far from the crossing, one side has a ceiling and the other does not #

The two sides of this plate are different kinds of curve, and the reason can be stated in one line each.

Choosing the index when the scan was right is bounded. An unclustered index reads each block at most once, because the model reads the distinct blocks holding matches and there are only 1,024 blocks. So however many rows actually match, the index cannot read more than the whole file plus its three-level descent — and each of those reads costs $\rho$. Its cost is therefore at most $\rho\,(n/B + h)$, and the scan costs $n/B$, so the regret of an index chosen in error is at most

$$\rho\left(1 + \frac{h}{n/B}\right) = 4 \times \left(1 + \frac{3}{1024}\right) = 4.01.$$

That is the dashed rule. No estimate, however low, can push the index’s regret over it, and the plate shows the sixty-four-times underestimate reaching the rule and flattening against it.

Choosing the scan when the index was right is not. A query matching $k$ rows costs the index about $\rho\,(k + h)$ and costs the scan $n/B$ whatever $k$ is. The regret is $(n/B) / (\rho\,(k+h))$, which is largest when $k$ is smallest and grows in proportion to the size of the file. Double the file and the overestimate’s peak doubles; the underestimate’s ceiling does not move.

Sixty-four is not a special number here; it is $1{,}024 / (4 \times 4)$, the whole file divided by the price of one scattered descent to one row. The overestimate’s regret is the ratio between the most expensive answer and the cheapest one, and a large file makes that ratio as large as anyone likes.

This is worth separating from the observation that a large error is bad. Every error is bad. What the plate distinguishes is an error whose damage is capped by a property of the plans — the index cannot read a block twice — and an error whose damage is capped only by the size of the data.

The saturation is the part a reader should take away from this plate. Between an estimate sixty-four times too low and one five hundred and twelve times too low, the regret does not change at all. Once the index has been chosen for a query that reads most of the file, the only thing left to lose is the scattered-read premium on that file, and it is already lost.

The ratio that sets the ceiling also sets the other side #

Everything above was drawn at $\rho = 4$, and $\rho$ is not a constant of nature. It is the ratio between reading a block out of order and reading the next one, which on a device with a moving head is large and on one without is close to one. The same decision can be priced at other ratios, and the shape of the regret changes with it.

Raising $\rho$ moves both sides at once, in opposite directions. It makes the index’s worst case worse, since every scattered read it cannot avoid is dearer; and it makes the scan’s worst case better, since the index it failed to use was itself expensive. At sixteen the two worst cases are 10.22 and 16.00, against 4.01 and 13.47 at four.

At $\rho = 1$ the picture inverts completely. The whole of the underestimate side collapses onto one, which is the finding of the essay this one follows: in a model where every transfer costs the same, an unclustered index is almost never much worse than a scan. And the overestimate is the only mistake left.

So “which mistake is dangerous” is not a property of estimates. It is a property of $\rho$, which is a property of the device — and it is decided by exactly the same constant that decides where the crossing is. A planner tuned for one storage medium carries, inside its cost constants, a risk profile for a different one.

What a planner could do with the two shapes #

The shapes suggest a policy that the crossing alone does not. If the estimate is known to be unreliable by up to some factor, the choice could be made on the worst regret it risks rather than on the estimated cost.

At $\rho = 4$ with errors of up to sixty-four, the arithmetic is on the plates already. A planner that always reads the index has a worst-case regret equal to the dashed rule, 4.01, over every true row count, because the bound holds for every $k$. A planner that follows its estimate has a regret of one whenever the estimate is right — and a worst case of 13.47 on this sweep when it is sixty-four times too high. So a planner that expects errors this large and cares about its worst case should be biased towards the index, deliberately, beyond what its own estimate says.

At $\rho = 16$ that argument vanishes. Always reading the index risks 16.05; following the estimate under the same errors risks 16.00. The bias buys nothing, and the estimate might as well be trusted. There is no universal answer to how conservative a planner should be, and the threshold somebody chose found the same thing about the tuning constants inside sorting routines — the shipped value encodes a machine, and moving the machine moves the right value.

The single-operator decision is also the easy case, and it is easy for a reason that does not survive a larger query. Two ways to join, and the ratio that decides chose between join methods whose costs were known exactly once the input sizes were known, and this page chose between two access paths whose costs depend on one estimated number. A query that joins three tables depends on estimated intermediate sizes that feed further estimates, and its plans differ in how much of their cost the choice even controls. The join order is a guess measures that case, and the answer there is that a regret over the whole plan can look harmless while the part of the plan that was actually decided is wrong by a factor of forty.

Two more things follow and neither needs a new measurement.

The direction of real errors matters as much as their size. When two predicates are positively correlated — a city and a postcode, a model and a manufacturer — multiplying their selectivities as though they were independent makes the product too small. Correlation therefore pushes estimates low, which on this decision is the bounded side. A planner whose errors come mostly from an independence assumption is making its common mistake on the side with a ceiling, and that is a property of the combining rule rather than of any histogram.

A regret is a ratio and needs its denominator named. Every number on this page divides by the cost of the better of the two plans for the same query, and none divides by anything larger. A sixth of what, exactly is this collection’s standing warning about reading a ratio without its base, and it bites hardest in the next rung up, where a query has several decisions in it and a ratio over the whole plan can hide a decision that was badly wrong.

What the model leaves out #

The measurement is of one decision in isolation, and several simplifications hold it there.

The error is held fixed on each line. Real errors are a distribution, not a factor, and a planner facing a distribution cares about its expected regret as well as its worst one. Expected is not average is the argument for keeping the two apart, and here they recommend different policies: expected regret favours trusting the estimate whenever it is usually right, while worst-case regret favours the bounded choice.

$\rho$ is one number. A real device’s cost for a scattered read depends on how far the head or the flash translation layer has to go, and on what is already cached. The plates treat it as a single ratio because the argument is about how the shape depends on it, and the argument survives any ratio; the specific numbers do not.

There is no clustered index and no covering index. An index in the file’s own order has no scattered-read penalty and is never worse than a scan, so it removes the decision rather than informing it. An index that holds the queried columns avoids reading the file at all. Both are real and both sit outside the question this page asks, which is what happens when the choice is a real one.

And the estimate’s formula is exactly right. The planner here errs only in its input. A real planner also errs in its model — it may not know $B$, or may assume matches fall in distinct blocks well past the point where they share — and an error in the model does not have either shape above, because it can move the crossing rather than merely feed it a wrong count. A limit is not a prediction measures how far a formula that is correct in the limit can be from a finite case, and a planner’s cost model is such a formula.

Where this ladder goes next: the plan chosen on its worst case #

The last section argued a policy from two plates and did not measure it.

The measurement is direct and this ladder has the pieces. Draw estimation errors from a stated distribution — a log-normal factor, say, skewed low the way correlated predicates skew — and price three planners against the same queries: one that trusts its estimate, one that always reads the index, and one that shifts its crossing by the error it expects, choosing the scan only when the estimate divided by that factor still clears 512 rows. Report each planner’s expected regret and its worst regret, at several values of $\rho$.

The prediction from this page is specific enough to be wrong. At a small read ratio the shifted crossing should cost almost nothing in expectation and remove the unbounded tail; at a large one the three should converge, because the two worst cases already have. If the shifted planner’s expected regret turns out to be large — if trusting a good estimate is worth more than insuring against a bad one — then the conservative bias common in practice is paying an insurance premium this model can put a number on, and that number is the next rung.