What insurance against an estimate costs

The estimate a plan rests on held a planner’s row estimate wrong by one fixed factor at a time and priced the index-or-scan decision at the truth. It found the two directions of error behave differently. Guessing too few rows makes the planner read an index where it should have scanned, and that mistake has a ceiling: an index cannot cost more than $\rho$ scans, where $\rho$ is what a scattered read costs against a sequential one. Guessing too many makes it scan where an index would have answered in a handful of reads, and that mistake has no ceiling but the size of the file.

From those two shapes the essay argued a policy and left it unmeasured. A planner that knows its estimates are unreliable could insure itself: lean towards the bounded mistake by shifting its crossing, choosing the scan only when the estimate divided by some factor still clears the point where the two plans cost the same. The argument predicted the premium would be small at a small read ratio and the benefit would vanish at a large one, because at a large one the two worst cases have already met.

This page puts numbers on that. Real errors are a distribution rather than a factor, so the planners here face one, and each planner’s regret is computed exactly over it rather than sampled.

The error, stated #

The file and the cost model are the ones the earlier essay used: 65,536 rows in blocks of 64, so a scan reads 1,024 blocks; an unclustered index descends three levels and reads each block holding a match once, each read costing $\rho$ times a sequential one. The planner uses the true cost formula on a false input.

The false input is the true row count multiplied by $e^{\mu + \sigma Z}$, with $Z$ a standard normal. The median error is the factor $e^{\mu}$, and $\sigma$ sets how widely errors spread around it: at $\sigma = 1.5$ an estimate is within a factor of 4.5 of its median two times in three and within a factor of 20 nineteen times in twenty. The earlier essay argued that errors from combining predicates as though they were independent run low — correlated columns make the true combined selectivity larger than the product — so the main plates use a median of $e^{-1}$, an estimate that typically sees about a third of the true rows.

Four planners face the same errors. One trusts its estimate. Two are insured by factors of two and of eight: they divide the estimate by that factor before comparing plans. One always reads the index, which is insurance by an infinite factor.

Each planner is given two numbers. Expected regret is its average cost against the better plan, taken exactly over the error distribution for each true row count from 4 to 16,384, with every row count weighted equally — a statement about the mix of queries, and the one the note on every plate repeats. Worst regret is the largest cost against the better plan at any of those row counts, for any error within three standard deviations. Expected is not average is the case for keeping those two numbers apart, and on this question they point in opposite directions.

Unbiased errors first #

The cleanest case is an estimate that is right on median and spread by $\sigma = 1$.

Each row of the plate is a small frontier, and the rows are not alike.

At a read ratio of one, the index is never the wrong answer. An index that reads each block once is a scan in a different order when a scattered read costs no more, so always reading it expects 1.000 and risks 1.00, and any planner that ever chooses the scan is only adding risk. That is the earlier essay’s result at $\rho = 1$, restated as a policy: on such a device the estimate is not worth consulting.

At two, insurance by a factor of two is free. Trusting the estimate and halving it before deciding both expect 1.057, to three places, and halving cuts the worst regret from 7.76 to 4.10. Insurance by eight costs nine per cent of the expected regret and cuts the worst to 2.01, which is the index’s own ceiling. A planner on such a device that expects errors this wide should insure, and should do it heavily.

At four, insurance starts to cost. Insuring by two raises the expected regret by two per cent and nearly halves the worst; insuring by eight raises it by a quarter and brings the worst down to the ceiling of 4.01. That is a real choice rather than an obvious one. Mild insurance has the shape the flat bottom of a shallow curve found for tuning constants — nearly as good as the best on the average, and different mainly in the tail — and heavy insurance does not.

At sixteen, insurance makes things worse on both counts. Trusting the estimate expects 1.086 and risks 10.22. Insuring by two expects 1.146 and risks 14.02; by eight, 1.703 and 16.05. The ceiling on the index’s mistake has risen to 16.05 and is now above the worst the trusting planner risks, so leaning towards the index leans towards the larger tail. The earlier essay predicted the planners would converge at a large read ratio; they do more than converge — the insured ones overtake.

Why insurance by two is free, and where the tails change places #

Two numbers from the model explain the unbiased plate, and both can be computed before any query runs.

The first is where the planner switches plans. Its estimated crossing is at 1,024 rows when a scattered read costs two sequential ones, 512 at four and 64 at sixteen. Insurance by two moves each of those up by a factor of two, and it changes a decision only for estimates that land between the old crossing and the new one. Those are queries whose true size is somewhere near the crossing, where the index and the scan cost nearly the same — the flat region the earlier essay found around every crossing. Moving a decision inside that region costs almost nothing, which is why halving the estimate at a read ratio of two leaves the expected regret unchanged to three places. What it does buy is protection for the queries far below the crossing whose estimates came out far above it, and those are exactly the ones whose regret has no ceiling.

The second number is the size of each tail. Choosing the index wrongly costs at most $\rho\,(1 + h/(n/B))$, the ceiling the earlier essay derived: 2.01 at a read ratio of two, 16.05 at sixteen. Choosing the scan wrongly is worst for the narrowest query, and for the four-row queries at the bottom of these plates it costs the whole scan divided by four scattered reads and the descent: 73.14 at a read ratio of two, 36.57 at four and 9.14 at sixteen. The first tail rises with $\rho$ and the second falls, and they are equal near $\rho = 12$. Below that, the scan is the dangerous mistake and insurance leans the right way; above it, the index is, and insurance leans towards the larger tail — which is the reversal at sixteen.

That crossing point is not a constant. The scan’s tail grows with the size of the file and the index’s does not, so the ratio at which they meet grows with the square root of the file: at a million rows instead of 65,536 it moves from about 12 to about 45. A planner on a fast device and a small table should not insure; the same planner on a large table on the same device may need to. The policy is a function of the data’s size as well as the device.

Estimates that run low #

Low estimates change the price of insurance, not its value. The tails removed are the same kind as before — at two, insuring by eight takes the worst regret from 15.06 to 2.19 — but the premium is larger everywhere, because a planner whose estimates already run low is already choosing the index more often than it should, and insurance pushes it further in the same direction. At a read ratio of four, insuring by eight now costs 32% of the expected regret, where with unbiased errors it cost 25%; at sixteen it doubles the expected regret and buys nothing at all, since every planner’s worst is 16.05.

This is the case the earlier essay was most interested in, and it answers the question that essay closed on. If trusting a good estimate is worth more than insuring against a bad one, a conservative planner is paying a premium the model can price. On a device with a read ratio of four, facing errors that run low with this spread, the premium is a third of the expected regret, paid to remove a tail that reaches 13.47.

Where the premium is paid #

Expected regret averaged over row counts hides where it comes from, and this plate unfolds it.

For narrow queries, insurance does exactly what it is for and costs nothing: the insured planner never scans a file for four matching rows, and its expected regret is 1.00. But the trusting planner’s expected regret for narrow queries is only 1.01 to 1.13, because with estimates running low an overestimate large enough to trigger a scan is rare. The tail the insurance removes is real — it is the 13.47 on the previous plate — and it is improbable.

For wide queries, the premium is paid in full. At 4,096 matching rows the trusting planner expects 1.41, because its low estimates sometimes pick the index wrongly; the insured planner, which divides an already low estimate by eight, picks the index far more often and expects 2.81. The ceiling that makes the index the safe mistake is 4.01, and a planner that keeps making the safe mistake keeps paying for it.

So the insurance transfers cost from narrow queries, where the bad outcome is dramatic and rare, to wide ones, where it is moderate and common. What randomising the pivot buys found the same shape in quicksort, which trades a tail of bad inputs for a tail of bad runs; here a tail of disastrous queries is traded for a broad band of mildly expensive ones.

How wide the errors are #

The trusting planner’s expected regret rises steadily with the spread of its errors; the heavily insured planner’s barely moves, because it is making the index-leaning choice almost regardless of the estimate. Insurance by eight is a flat line at about 1.6. The lines cross at a spread of about two and a half, where insuring by two has become cheaper in expectation than trusting — so only when errors are this wide — wrong by an order of magnitude a large part of the time — does mild insurance start paying for itself on the average as well as in the tail.

The worst case says something the expected case cannot: insurance is sized for a spread, and a larger spread defeats it. Insurance by eight holds the worst regret at the index’s ceiling of 4.01 for spreads up to 1.5 and then fails in two steps, to 13.47 and then 36.57, as errors large enough to overcome a factor of eight come inside three standard deviations. Only the planner that ignores its estimate entirely has a worst case that does not depend on how wrong the estimate is.

At small spreads the ordering reverses: trusting a nearly right estimate risks 2.56, and insuring it risks the index’s full ceiling, because insurance pushes wide queries onto the index even when the estimate was right. Insurance against errors that do not happen is a cost with no benefit, which is obvious stated and easy to forget when the insurance is a constant built into a planner and the errors are a property of the data it happens to meet.

Which way the errors run #

The last plate shows what insurance is. When estimates run low, insurance compounds the bias and trusting is best. When estimates are right on median, mild insurance is already slightly better in expectation — 1.196 against 1.215 — because the two mistakes are not symmetric and a small lean towards the bounded one pays. When estimates run high, insurance by eight beats trusting by a wide margin, 1.225 against 1.466, because dividing the estimate by eight is correcting a bias the planner did not know it had.

Insurance and bias correction are the same dial. A planner that divides its estimate by a constant is making an assumption about the direction and size of its own errors, whether or not anyone wrote the assumption down. If the assumption matches the errors, the “insurance” is free or better than free; if it runs the same way as the errors, it is a premium; and nothing in the planner can tell which, because the errors are a property of the data and the device, measured after queries run.

What a planner can take from this #

The read ratio decides whether to insure at all. At one, always read the index. At two, insure heavily: it costs a tenth of the expected regret at most and removes a tail of fifteen. At four, insure mildly or measure first. At sixteen, do not insure — trusting the estimate has the smaller worst case as well as the smaller expected cost. The cliff where the data stops fitting is the reminder that the ratio between a scattered and a sequential read is a property of where the data lives, and it changes when the data moves.

The direction of the errors decides the price. A planner whose errors come from an independence assumption, and so run low, pays more for the same insurance than one whose errors are unbiased, and one whose errors run high is paid to insure. The skew a few counters cannot repair found the same property in a join estimate built from heavy-value counters: it errs low by construction, and every wrong choice it made leaned the same way.

Both numbers can be measured, and the policy follows from them. A system that records its estimated and actual row counts has the error distribution; a system that times its reads has the ratio. With both, the insurance factor is a choice read off a plate like the ones above rather than a constant somebody chose, and the threshold somebody chose is the collection’s standing evidence of how rarely such constants are revisited once they ship.

What the model leaves out #

Every true row count is weighted equally. A workload dominated by narrow lookups makes the tail the insurance removes far more important and the premium cheaper; one dominated by wide reports does the reverse. The expected-regret plates are about this mix and would move under another.

The error is log-normal and the same at every row count. Real estimation errors grow with the number of predicates combined and differ between narrow and wide queries. The shape of the conclusion — insurance and bias correction are one dial, and the read ratio sets its value — does not depend on the distribution, but the numbers do.

One decision, one device, no feedback. A real planner makes many dependent decisions per query, and a system that observes a wrong estimate can re-plan. The join order is a guess measured how a single wrong estimate propagates through a three-way plan, where an error’s damage is not bounded by any read ratio at all.

Still open: learning the insurance from the queries #

Every plate here fixed the error’s median and spread and asked what insurance they justify. A running system knows neither in advance. It learns them from its own history: each executed query reveals one estimate and one true count, and after enough queries the planner could fit $\mu$ and $\sigma$ and set its insurance from them.

That makes the insurance itself an estimate, with its own error, and raises a question the plates can answer with one more measurement. How many observed queries does a planner need before insurance set from their fitted error distribution is within a few per cent of the expected regret that insurance set from the true distribution would achieve — and what does it pay, in expected and worst regret, during the queries it spends learning? The cold start is where a planner with a constant is likely to beat one that learns, and where that stops being true is a number a system designer would want before choosing between them.