What a planner pays to find out what to pay

What insurance against an estimate costs priced a planner that halves its row estimate before choosing between an index and a scan. At a read ratio of four and an error spread of 1.5, trusting the estimate expects to pay 1.215 times the better plan and risks 36.6; dividing the estimate by 1.5 expects 1.192 and risks 23.3. The insurance is nearly free and it removes most of the tail.

Every plate on that page fixes the error’s median and spread and asks what insurance they justify. A running system knows neither. It learns them: every executed query reveals one estimate and one true row count, and the log of their ratio is one draw from the error distribution. After enough queries a planner can fit the median and the spread and set its divisor from the fit.

That makes the insurance itself an estimate, with its own error, and it raises the question this page answers: how many executed queries a planner needs before its fitted divisor is worth having, and what it pays while it is finding out.

It is worth being clear about what is and is not being fitted, because there are two estimates in play now and they are about different things. The estimate a plan rests on is the row count: a planner’s guess at how many rows a predicate will match, wrong by a factor whose median and spread this page’s planner is trying to learn. The divisor is the planner’s response to that error. So the planner is estimating the error of its own estimator, from the only evidence available — the queries it has already run — and the plates below are about how much of that evidence it needs.

The fitted divisor, against the one that was known #

The curve falls to the oracle’s line, as it must — a fit to enough observations recovers the distribution it is fitted to. The part worth a page is where it starts.

A divisor fitted to one executed query costs 1.2629, and simply trusting the estimate costs 1.2145. Learning is worse than not learning, by four per cent, and stays worse until about sixteen queries have run. The reason is that the quantity being fitted is a spread, and a spread fitted to one observation is zero: the planner concludes the estimate is exact, chooses a divisor of one, and is then merely a trusting planner that has also made a mistake on the queries where its single sample happened to be unrepresentative. At two observations the spread is whatever the two happened to differ by, which is as likely to be far too small as far too large.

The modal choice tells the same story from the other side. From one and two observations the divisor chosen most often is 1 — no insurance at all — because a fitted spread near zero justifies none. From sixteen the modal choice is 2, overshooting the true optimum of 1.5; from 128 it is 1.5.

And thirty-two observed queries bring the fitted divisor within one per cent of the best one. That is the number the earlier page asked for. It is small — a planner sees thirty-two queries in a second — and it is the answer only for this pair of parameters, which the third plate is about.

That plate is the target the fits are aiming at, and it says why the target is hard to hit. The divisors are not separated by much in expectation — the whole range from 1 to 24 spans a few per cent at a read ratio of 2 — so a fitted divisor two steps away from the best one loses very little, which is why the first plate converges so quickly. But at a read ratio of 16 the same range spans forty per cent, so a fit that overshoots is expensive. The fitted divisor’s error matters in proportion to how steeply the regret rises on the wrong side of the optimum, and that steepness is a property of the device rather than of the estimator being fitted.

The tail is bought immediately #

The expected regret is not the only thing insurance is for, and on the other axis the arithmetic is completely different.

A planner that has seen one query has, in the worst case, already bought nearly everything insurance can buy. The worst case is decided by whether the planner has any insurance at a large enough estimate, and a fitted divisor is usually above one for any sample that contains two different values; it need not be the right divisor for the tail to be cut.

So the two axes give opposite advice about when to start learning. The expected regret says wait for sixteen queries; the worst regret says fit from the first one. A system that cares about its tail — one with a latency target, or one where a plan that costs thirty-six times the better one blocks everything behind it — should fit immediately and accept a four per cent worse mean for the first dozen queries. A system judged on throughput should not.

That is the shape distributions, not averages keeps producing on this collection, and it is sharper here than usual because the two statistics do not merely differ in size: they differ in sign over the first sixteen queries.

The three insured lines being close is the whole of why one observation is enough for the tail. A fitted divisor is some number above one; which number above one it is barely changes the worst case, over a wide range of spreads. The expected regret, by contrast, distinguishes the divisors — that is what the previous plate shows — so the statistic that a fit gets wrong early is the statistic the fit is judged on early.

Where learning is worth anything at all #

The convergence above is at one read ratio and one spread, and the earlier page’s central finding was that insurance stops being free as the read ratio rises.

The plate divides into three regions and the middle one is the interesting one.

Where insurance is worth a lot, learning pays immediately. At a read ratio of 2 and a spread of 2.5 the best divisor is 24, the trusting planner pays 1.737 and the oracle 1.241 — a gap of forty per cent. A fit to one query lands at 1.538, which is already far better than trusting, so the cold start costs nothing. A planner with a wild estimator and a cheap scan should fit from its first query.

Where insurance is worth nothing, learning is a permanent tax. At a read ratio of 16 the best divisor is 1: the earlier page found that at this ratio a conservative planner’s insurance costs six per cent in expectation and makes the worst case worse, so the oracle simply does not insure. A planner that fits then has a divisor above one whenever its sample says the estimate is noisy, which is most samples, and it pays 1.363 against 1.239 at one observation and 1.239 at 256 — it converges to doing nothing, having paid twenty-five per cent extra to get there. The column reads “never” for both of the narrow-spread cases at this ratio.

And in between, the cold start is a number. At a read ratio of 4 and a spread of 1, insurance is worth 0.1% and the crossing is at sixty-four queries; at a spread of 1.5 it is worth 1.9% and the crossing is at sixteen; at 2.5 it is worth eleven per cent and there is no crossing to wait for.

The rule that falls out is simple and is not the one a designer would guess. The crossing is not set by how noisy the estimate is; it is set by how much insurance is worth, and how much insurance is worth depends on the read ratio as much as on the spread. A planner cannot decide whether to learn by looking at its own estimator’s error. It has to look at the device.

Why fitting a spread is the hard half #

Both parameters of the error distribution are fitted from the same observations, and they are not equally hard to get.

The median is a mean of the log ratios, and its own spread falls as one over the square root of the sample: after sixteen observations at a spread of 1.5, the fitted median is within about 0.37 of the truth, which moves the estimate by a factor of 1.45 and the best divisor by less than one step of the grid.

The spread is a standard deviation, and a standard deviation fitted to a small sample is biased low and highly variable. At one observation it is zero by construction. At two it is the absolute difference of two draws divided by the square root of two, which has a mode at zero. The divisor’s whole job is to defend against the upper tail, and the upper tail is what a small sample is least likely to have seen — so the fitted divisor is systematically too small exactly when it is most uncertain.

Expected is not average is the standing distinction the two statistics on this page rest on, and there is a third one hiding inside the fit. The expected regret reported for a fitted divisor is an average over 120 independent fits, each of which produces one divisor and then pays whatever that divisor costs under the true distribution. It is not the regret of a planner that somehow uses the average divisor, which would be a different and better planner. On average is not a number is the same warning applied to a count; here it applies to a decision, and the difference matters because the divisors a small sample produces are not symmetric around the right one.

That asymmetry is why the curve on the first plate starts above the trusting planner rather than between the two lines. A planner fitting from a small sample is not making a random error around the right answer; it is making a directional one, towards no insurance, and paying the trusting planner’s regret plus the cost of having been wrong about which queries deserved insurance.

A system could correct for it — inflate the fitted spread by a factor that falls with the sample size, which is the standard repair for a biased variance estimate — and that is one line of arithmetic no plate here measures. The point of measuring the uncorrected version first is that it is what a system does when nobody thought about it.

What this says about learning a parameter at all #

The shape here is the same one what the queries know that the map does not found in a completely different structure: a rule that reads a system’s own history beats a fixed rule only where the history carries information the fixed rule does not already have, and it pays a fitting cost to find out.

The two cases differ in one way that is worth naming. There, the fixed rule read the map, and a uniform query distribution carried no information the map did not, so the learned rule converged to the fixed one and had spent millions of searches doing it. Here the fixed rule is a constant somebody chose, and the history does carry information about it — the error distribution genuinely is a property of the data and the estimator, and is genuinely unknown in advance. The learned rule is right to exist; it simply has to survive its own first few queries.

And that is a general form. A learned parameter is worth learning when the thing it is fitted to is both unknown and worth knowing, and the second condition is the one that gets assumed. The read ratio of 16 column is a system where the parameter is perfectly learnable and learning it is worth less than nothing.

The fixed alternative deserves one more word, because “a constant somebody chose” is usually a criticism on this collection and here it is not. The threshold somebody chose swept four constants written into real sorting code and found that none of them sat at an optimum; the complaint was that nobody had checked. A divisor of one — no insurance — is a constant too, and at a read ratio of 16 it is the right one, and a planner that replaces it with a fitted value has replaced a correct constant with a noisy estimate of it. Checking a constant is not the same as learning it.

What is not measured here #

One error distribution and one shape. The estimate’s error is lognormal with a fixed median and spread, and the planner fits exactly that family. A planner fitting the right family is the best case; a real estimator’s errors are not lognormal, and a fit to the wrong family does not converge to the oracle at any sample size.

Errors that do not drift. Every observation comes from the same distribution, so more observations are always better. A system whose data changes has a fitting window rather than a sample size, and the trade between a long window and a current one is not here.

No cost for the observation. Each executed query is assumed to reveal its true row count for free, which a system gets only if it counts rows as it returns them. It usually does.

One divisor for every query. The divisor is a single number applied to every estimate, as it was on the earlier page. A planner could fit a different divisor per table, per column or per predicate shape, which is more parameters fitted from the same queries — and every extra parameter lengthens the cold start the first plate measures.

Regret, not time. The unit is the chosen plan’s transfers over the better plan’s, as it has been throughout these measurements. The block that is not a block is the standing statement of what that model leaves out, and it bites here through the read ratio, which is the parameter the whole plane turns on: a device whose reads and writes cost the same has a read ratio of one, and a device with a queue and a prefetcher does not have a single read ratio at all.

One join order, one choice. The planner chooses between an index and a scan for one predicate. The join order is a guess measured a planner choosing between join orders on the same kind of estimate, where the regret compounds across several estimates rather than resting on one — and a divisor fitted from single-predicate observations has no obvious meaning there.

That is the mechanism behind the “never” column of the previous plate, and it is worth seeing because it is not a statement about estimation at all. Insurance moves a planner towards the scan. At a large read ratio a scan is dear, so moving towards it is dear, and the queries where it is dearest are the narrow ones an index answers in four transfers. A planner fitting a divisor from its queries will find a divisor above one whenever its estimator is noisy — which it is — and will apply it to exactly those queries.

The grid. The divisor is chosen from thirteen values rather than solved for, because the expected regret is a step function of the divisor and a system would search a grid anyway. A finer grid would move the oracle’s expected regret by less than the width of the plate’s lines.

Still open: a planner that knows how sure it is #

The fitted divisor on this page is a point estimate used as though it were certain, which is precisely the mistake the whole subject is about — the planner’s row estimate is also a point estimate used as though it were certain, and insurance exists because it is not. The same repair is available one level up.

A planner that has seen $m$ queries has not just a fitted spread but a confidence interval for it, and the interval is wide when $m$ is small in exactly the way that made the first plate start above the trusting planner. A divisor set from the upper end of that interval rather than from its centre would be too large early and would shrink to the right value as the sample grew — insurance against the insurance being wrong.

The measurement that follows sets the divisor from the fitted spread inflated by the one-sided confidence bound at a stated level, sweeps the level from none to ninety-nine per cent, and asks two things: whether the crossing at sixteen queries moves to one, and what the inflation costs once the sample is large enough that it is no longer needed. The second is the real question, because a correction that never switches itself off is a new constant somebody chose.