A planner that knows how sure it is

What a planner pays to find out what to pay gave a query planner the job of learning its own insurance. The planner chooses between an index and a scan on an estimate of how many rows will match, and the estimate is wrong by a factor drawn from a distribution — the error the estimate a plan rests on measured. Dividing the estimate by a constant before deciding — insuring against overestimates — pays when the distribution is wide. The planner does not know the distribution. It fits its median and spread to the errors it has seen on executed queries, and sets its divisor from the fit.

That page found that the fit is worse than doing nothing for the first sixteen queries. A spread fitted to a small sample comes out too small more often than too large, so the planner concludes its estimates are more reliable than they are and under-insures. It named the standard repair and left it unmeasured: use not the fitted spread but the upper end of a confidence interval on it, which is wide when the sample is small and narrows as the sample grows. That is insurance against the insurance being wrong.

The page predicted the repair would move the crossing — the number of queries after which fitting beats trusting — from sixteen towards one. This page measures it. The crossing moves the other way.

The bound, and what it inflates #

With $m$ observations of a normally distributed log error, the sample variance $s^2$ satisfies $(m-1)s^2/\sigma^2 \sim \chi^2_{m-1}$. So the true spread lies below

$$\sigma_L = s\,\sqrt{\frac{m-1}{\chi^2_{1-L,\;m-1}}}$$

with probability $L$, where $\chi^2_{1-L,\,m-1}$ is the lower $(1-L)$ quantile of the chi-square distribution. At $L = 0$ the factor is one and the planner is exactly the one the previous page fitted. At $L = 0.95$ and two observations the factor is 15.9; at eight observations it is 1.80; at 256 it is 1.079. The quantiles are computed rather than looked up, and they match published tables to four significant figures.

One observation gives no bound at all, since a spread cannot be estimated from one number, so the sweep starts at two queries. Every level sees the same observations — each trial draws its sample once and hands it to all of them — so a gap between two lines on a plate is the level’s doing and not the sample’s.

The setting is the one the previous page’s first plate used: a read ratio of four, meaning a random read costs four times a sequential one, and a true error spread of 1.5 in natural-log units, around a median error of one. The best divisor for that distribution is 1.5 and expects 1.1915 times the better plan’s cost. Trusting the estimate expects 1.2145.

The crossing moves later #

Every level of confidence makes the early planner worse, and the higher the level the worse. After two queries, the plain fit expects 1.26 times the better plan. The 95% bound expects 1.74, which is 43% worse than never insuring at all. The fitted planner matches trusting from sixteen queries, the 75% bound from thirty-two, and the 95% and 99% bounds from sixty-four.

The previous page’s diagnosis was right: the fitted spread is biased low, and the fitted planner under-insures. The repair overshoots by far more than the bias it corrects. At two observations the 95% factor multiplies the fitted spread by sixteen. A spread of 1.5 fitted to two draws comes out, on average, around 1.2. Sixteen times that is a spread of nineteen natural-log units, which describes an estimator that is wrong by a factor of $e^{19}$. The planner believes it, and the divisor that is best against an estimator that bad is the largest on the grid, 64. It chose 64 most often after two and four queries at the 95% level.

Dividing an estimate by 64 makes almost every query look narrow, so a divisor of 64 sends almost every query to the index. On the wide queries — a few hundred to a few thousand rows, past the crossing the index that is not worth reading located, where a scan reads 1,024 transfers and the index’s scattered reads cost several times that — this is expensive, and it is paid on every wide query for as long as the sample stays small.

The tail is bought at once #

The same planners, scored on the other statistic insurance exists for:

After two queries, the 95% bound holds the worst case to 6.2 times the better plan, where the fitted spread holds it to 22.4 and the best divisor for the true distribution to 23.3. The bound’s early planner has a better worst case than the planner that knows the distribution exactly. That is not a contradiction. The best divisor is best in expectation, and a planner optimising expectation accepts a bad tail if the tail is rare enough. The bounded planner is doing something else. A spread of nineteen log units makes the planner insure everything, and a planner that sends everything to the index can never make the expensive mistake — a scan of 1,024 transfers on a query the index answers in a handful. Its worst case is the index on a wide query, and that is bounded by the read ratio, 4, plus the index’s few levels of descent.

As the sample grows the bound shrinks, the divisor falls back towards 1.5, and the worst case rises to meet the best divisor’s. At 256 queries every level has the same tail.

So the two plates say the same thing from opposite ends. The confidence level does not move the planner towards the right divisor faster. It moves it towards a different planner — one that minimises the worst case — and the sample size moves it back.

A dial, not a correction #

At eight queries the four levels lie along a line: each step up in confidence costs expected regret and buys worst regret. From the fitted spread to the 95% bound, the expected cost rises by 13% and the worst case halves. From 95% to 99% the expected rises another 15% and the worst falls by 40%.

None of them reaches the best divisor, which sits below and to the left of the whole line — better on both statistics than the fitted spread and better on expectation than any level. That point is not available to a planner that has seen eight queries, at any level. The bound does not compensate for the missing information. It chooses how the planner is wrong: too trusting, which is cheap on average and dear in the tail, or too cautious, which is the reverse.

This is the useful way to read the confidence level, and it is not how the repair was proposed. As a correction for a biased estimator, a 95% bound is an over-correction by a factor of sixteen at two observations. As a statement of how much tail a system will pay to avoid, it is a well-defined dial. Past 99% it barely moves the tail further, because the planner has already reached the divisor at the top of the grid.

Even the gentlest correction costs #

The 50% level is worth a paragraph of its own, because it is the one that answers the previous page’s diagnosis most directly. A 50% bound multiplies the fitted spread by the factor that makes it median-unbiased: the inflated spread is as likely to fall above the truth as below it. It is the smallest correction that removes the bias the previous page blamed for the early planner’s trouble, and at eight queries it multiplies the spread by 1.05.

It makes the planner worse. After eight queries the fitted spread expects 1.220 and the median-unbiased one 1.223. The margin is small, but the direction is the point, and on the shared observations it holds at every sample size from two to sixteen. If the early planner’s trouble were bias, removing the bias would help. It does not, so the trouble was something else.

The something else is noise. A spread fitted to eight queries ranges widely from one sample to the next, and the divisor chosen from it ranges with it. Some samples come out too small and choose no insurance; others come out too large and choose a divisor of 3 or 4 where 1.5 was right. The two errors do not cost the same. At this read ratio the curve of best divisors climbs steeply above the true spread and is nearly flat below it, so a spread that comes out too large costs more than one that comes out equally too small. A correction that shifts every sample’s spread upward removes some of the cheap errors and enlarges all of the expensive ones.

That is why no level of the bound can reach the best divisor at eight queries. A bound shifts the whole spread of estimates up or down. What a small sample needs is a narrower spread of estimates, and a bound cannot supply one. Only more queries can, or information that did not come from these queries at all.

Why the bound hurts here and helps elsewhere #

Whether overstating the spread is expensive depends on what the overstated spread asks for, and that is a property of the device.

A planner that overstates its spread moves to the right along its read ratio’s curve, and the three curves are three different stories.

At a read ratio of 16 the curve is flat at 1. No spread justifies any insurance, because at that ratio every scattered index read costs sixteen sequential ones, and pushing queries onto the index is the expensive mistake whatever the estimate’s error. An overstated spread changes nothing about the divisor. It does change how much weight the planner puts on its fitted median. With a wide spread, a median fitted a little above zero no longer tempts the planner into a small divisor to correct it, and the bounded planner sits on the right answer — no insurance — more reliably than the fitted one.

At a read ratio of 4 the curve climbs steeply through the truth. The right divisor at the true spread is 1.5. At twice the spread it is 12, and at two and a half times it is 64. An overstated spread walks the planner up that curve to a divisor several times too large, and at this ratio over-insurance is paid on every wide query it pushes onto the index.

At a read ratio of 2 the curve is steepest of all, but so is the penalty for under-insuring. At a true spread of 2.5 the best divisor is 24, the trusting planner pays 1.74 times the better plan, and a planner that overshoots to 64 is closer to the right answer than one that undershoots to 3.

Nine settings #

The plane divides the way the curves predict.

At a read ratio of 16 the bound is better in all three rows, by 1% at a spread of 1 and 4% at a spread of 2.5. It matches trusting sooner than the plain fit — from sixteen queries rather than sixty-four at the widest spread. Here the planner’s only real decision is to leave its estimate alone, and a planner convinced its errors are wide is the one most likely to do so.

At a read ratio of 2 and a spread of 2.5 the bound is better by 5.5%, because insurance is worth so much there — the trusting planner pays 74% over the best divisor — that erring towards too much of it is erring in the right direction.

Everywhere else it costs, and the cost is largest exactly where the previous page found learning most delicate. At a read ratio of 4 and a spread of 1.5, the bounded planner expects 1.620 after four queries against the plain fit’s 1.227. At a read ratio of 4 and a spread of 1, where insurance is worth a tenth of a per cent, the bound turns a planner that would match trusting after sixty-four queries into one that needs 256.

The rule is the one what insurance against an estimate costs found for insurance itself, one level up. Insurance is cheap where the scan is cheap and dear where it is dear. Insurance against the insurance being wrong inherits the same dependence on the device, sharpened by the size of the overstatement. A confidence bound is worth using where the answer at a wide spread is the answer at the true spread, and that is a fact about the read ratio, not about the estimator.

How slowly it switches itself off #

The previous page closed on the question that decides whether a correction like this is acceptable: what it costs once the sample is large enough that it is no longer needed. A correction that never switches off is a new constant somebody chose.

It does switch off, but slowly. The inflation factor falls as one over the square root of the sample: 1.437 at sixteen queries, 1.174 at sixty-four, 1.079 at 256, 1.038 at 1,024, 1.019 at 4,096. It never reaches one. At 256 queries the 95% bound still costs 0.22% over the best divisor, twice the fitted spread’s 0.10%, and it still chooses a divisor of 2 more often than the right 1.5. At 1,024 queries it has returned to 1.5 and the excess is under a tenth of a per cent.

A planner sees a thousand queries in a second, so the tail of this curve is short in time. But at the steady state the bound is still paying something. A system that sets a confidence level once and leaves it has added a small permanent charge in exchange for protection during a start-up it passed long ago. One that lets the level fall as the sample grows, or turns it off past some count, has re-introduced exactly the kind of threshold the previous page warned about — the kind the threshold somebody chose found written into four sorting libraries.

What was predicted and what happened #

The prediction was that inflating the spread would move the crossing from sixteen queries towards one, because the early fitted planner’s trouble was under-insurance. That was the wrong reading of the early planner’s trouble. Its expected regret at small samples was high not because it under-insured on average but because its divisor was noisy. Some samples gave a spread near zero and a divisor of one, others a spread well above the truth and a divisor of 3 or 4. Inflating every sample’s spread by the same large factor removes the first kind of error and multiplies the second, and at a read ratio of four the second is the more expensive.

What the bound does buy is real and was not in the prediction: a worst case far below the best divisor’s own, from the second query. Distributions, not averages is this collection’s name for the finding that an average and a tail can give opposite advice. Here the two statistics are optimised by two different planners, and the confidence level chooses between them.

The limits of the measurement #

One family, fitted exactly. The errors are lognormal and the planner fits a lognormal, so the chi-square bound is exact for the spread it inflates. A real estimator’s errors are not lognormal, and a bound computed as though they were covers the true spread at some other rate than the one stated.

Only the spread is bounded. The fitted median is used at its centre. A planner could bound the median too — shifting its estimate towards overestimation, which is the direction insurance guards against — and the two bounds interact.

One grid. The divisor is chosen from thirteen values between 1 and 64, and the bounded planner’s early behaviour is pinned to the top of that grid. A grid reaching 1,024 would let the early bounded planner insure even harder, and at a read ratio of 4 would make its expected regret worse still.

Regret in transfers. The unit is the chosen plan’s block transfers over the better plan’s, as in every measurement of this planner. The block that is not a block is the standing note on what that leaves out. It bites here through the read ratio, the parameter the whole plane divides on.

Still open: a planner that starts from what planners usually see #

The bound failed because two observations say almost nothing about a spread, and a chi-square interval states that honestly by being enormous. A planner is rarely that ignorant in practice. The errors of a row estimator are not a fresh unknown on every system: they come from the same few causes — independence assumed between correlated columns, and uniformity assumed on skewed ones, which the join order is a guess and the skew a few counters cannot repair measured — and their spread across many systems is itself a distribution somebody could measure.

The measurement that follows gives the planner a prior on the spread instead of a bound: a distribution over σ, centred on a typical value and as wide as the variation between systems, updated by each executed query. At small samples the posterior spread is close to the prior’s typical value rather than to zero or to nineteen. The prediction is that a prior centred within a factor of two of the truth moves the crossing to within the first few queries, which is what the bound was supposed to do. The question the measurement has to answer is what a prior centred in the wrong place costs, and for how many queries — a prior is a constant somebody chose, stated as a distribution, and the sweep over where it is centred is the whole of the result.