Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Cardinality estimate — where it appears

A query planner's estimate of how many rows an operation will produce, computed from summaries of the data before it runs. Its errors are multiplicative, since estimates of combined predicates and joins multiply, and every plan decision downstream inherits them.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

11010010³10⁴12510rows the query actually matchescost ÷ the better plan's costrho plus the descent, 4.01estimate ÷64estimate ÷8estimate ×8estimate ×64n = 65,536, B = 64, M = 4,096 (M/B = 64), scattered read ×4dotted: the estimate switches at 512 rows

The estimate a plan rests on

A planner chooses between an index and a scan on how many rows it thinks will match, and the number it has is wrong by a factor. Guess sixty-four times too many on a narrow query and the scan it picks costs 13.5 times the index. Guess sixty-four times too few on a wide one and the index costs at most 4.01 times the scan — a ceiling that can be named before any query runs.

applied · Transfer 1×2×5×10×20×50×00.40.811.2skew of the join columnratio, logarithmicestimate off byregret, decided partregret, whole planR 4,000, S 40,000, T 2,000 rows, B = 64, M = 4,096 (M/B = 64)every order writes the same output

The join order is a guess

Three tables, two orders, and an estimate of the first intermediate result that assumes the join column is uniform. When the column is skewed the estimate is out by seventy-two times, and the plan chosen on it costs 1.49 times the better one — which sounds tolerable until the shared output is taken away, and the part of the cost the order actually decided turns out to be 43.9 times worse.

applied · Transfer 1×2×5×10×20×50×100×200×00.250.50.7511.251.51.752skew of the join columnregret of the decided part, logarithmicuniform estimate4 counters a side16 counters a side64 counters a side256 counters a sideR 4,000, S 40,000, T 2,000 rows · 64-record blocks, 4,096 in memoryMisra–Gries on each side of the join column

The skew a few counters cannot repair

A join order chosen on the textbook estimate costs 243.9 times the better order at a Zipf exponent of two, and two counters a side are enough to fix it. At an exponent of one half the estimate is out by less than a factor of two, the plan it picks costs 1.37 times the better one, and no number of counters up to 256 changes that. The easy case is the extreme one, and the reason the moderate one is hard is a series that stops converging at exactly one half.

applied · Transfer trusts the estimateinsured ×2insured ×8always the index11.5235expected regret, logarithmic · label: worst within three standard deviationsrho 14.42.51.11.0rho 215.17.82.22.0rho 413.57.54.04.0rho 1616.016.016.016.0σ = 1.5, median error e^-1, 65,536 rowsexact over the error distribution

What insurance against an estimate costs

A planner that trusts its row estimate expects to pay 1.057 times the better plan and risks 7.76. One that insures itself by halving its estimate before it decides expects 1.057 and risks 4.10 — the insurance is free. At a read ratio of sixteen the same insurance costs six per cent in expectation and makes the worst case worse. Whether a conservative planner is paying a sensible premium depends on two numbers the planner can measure and usually does not — its device's read ratio and the direction its own errors run.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Block transferEstimatorQuery planRegretRelative errorIndependence assumptionCrossoverHeavy hitterJoinMisra–GriesSelectivityTrade off

All concepts