The index that is not worth reading

A query asks for the rows matching some condition. There are three ways to answer it and every database implements all three: read the whole file and test each row; walk an index and fetch each matching row from wherever it happens to be; or, if the file is stored in the index’s own order, walk the index and read the matching rows in a run.

Which one is chosen is not a property of the query. It is a decision taken by a component that exists for no other purpose, and the decision is arithmetic in the unit this field counts.

It is also the one decision in a database that is taken twice about the same query and can be taken differently each time — once when a plan is chosen, and again by the operating system and the device underneath it, which decide independently whether a request is worth reading ahead for. The two decisions are made in different units by components that cannot see each other, and the arithmetic below is only the first of them.

The three plans, priced #

The scan reads every block of the file once. Its cost is $\lceil n/B \rceil$ and it does not depend on the query at all: 1,024 transfers over 65,536 rows at sixty-four rows to the block, for one matching row or for all of them. It is the only plan whose cost is known before the query is examined.

The unclustered index descends a B-tree to find the first matching key, walks the leaf level to collect the row identifiers, and then fetches each row. The descent is three transfers here, the leaf walk is a scan of a much smaller structure, and the fetches are the cost. Each one is a row at an address the index does not control, so each is a transfer — until enough rows are being fetched that two of them start landing in the same block.

The clustered index is the same descent onto a file that is stored in key order, so the matching rows are contiguous. The fetches become a scan of $\lceil k/B \rceil$ blocks. At sixty-four matching rows that is one block; at a quarter of the file it is a quarter of the scan.

Those are the numbers, and the ranking they produce is not the one the rule of thumb gives.

Two of the three costs depend on the answer and one does not, which is already enough to make the comparison a curve rather than a table. It is worth noticing which way each one depends. The unclustered plan’s cost rises with $k$ and is therefore worst on the queries a user is least surprised by — the broad ones. The clustered plan rises with $k$ too but divided by $B$, so it stays under the scan for every query short of the whole table. And the scan does not rise at all, which makes it the only plan whose behaviour a person can predict without knowing anything about the data. There is a real argument for preferring predictable plans to fast ones in a system that has to meet a deadline, and it is an argument these curves can support and no single number can.

One further thing about the descent, because it is a cost that gets rounded to zero and should not be. Three transfers to reach the first matching key is more than the whole clustered plan spends on sixty-four rows, and it is a dependent chain — each level’s address comes from the level above, so no two of the three can be issued at once. On a device where a scattered read costs a millisecond, the descent alone is three milliseconds of latency before a single row is produced, and a scan that streams at a gigabyte a second has read four megabytes in that time. The counts on this page cannot express that, and it is the reason a plan that looks strictly better in transfers can lose on a small table.

The crossover the arithmetic predicts #

The standard reasoning is one line and it is on every page that discusses this. The index costs one transfer per matching row and the scan costs $n/B$, so they meet at $k = n/B$ — at 1,024 rows here, a selectivity of 1.6%. Above that, use the scan.

Every part of that is correct as arithmetic and the conclusion is wrong, and the way it fails is instructive.

At $k = 1{,}024$ rows the measured index cost is 654 transfers, not 1,024. The reason is that “one transfer per row” stops being true precisely when the rows become numerous: $k$ rows drawn at random from $n/B$ blocks touch about $\frac{n}{B}\left(1 - (1 - B/n)^k\right)$ distinct blocks, which is close to $k$ while $k$ is small against $n/B$ and saturates at $n/B$ as $k$ grows. At $k = n/B$ exactly, the expected number of distinct blocks is $(1-e^{-1})n/B$, or 63% of the file — so the index is still a third cheaper than the scan at the point where the rule of thumb says they are equal.

Push further and the index approaches the scan from below and does not pass it by much: 1,013 transfers at 6% selectivity, 1,027 at 25%, and 1,027 at 100%. In transfers, an unclustered index is essentially never worse than reading the file — the worst it can do is read the file plus the height of the tree.

The saturation is worth stating as a formula because it is the part of the behaviour nobody quotes. Fetching $k$ rows at random from a file of $n/B$ blocks is the coupon-collector’s problem in reverse: the expected number of distinct blocks is $\frac{n}{B}(1 - (1-B/n)^k)$, which is $k$ for small $k$, $0.63\,n/B$ at $k = n/B$, and $0.86\,n/B$ at $k = 2n/B$. The curve on the plate is that expression, measured rather than plotted from it — the simulation replays the actual addresses through a resident set — and the two agree, which is the check that the resident set is being modelled rather than assumed.

So why does a planner abandon the index at a few per cent? #

Because it is not counting transfers. It is counting something the model on this page sets to a constant, and the something is the difference between a sequential transfer and a scattered one.

A scan reads blocks in address order. Every device built in the last fifty years is faster at that than at reading the same number of blocks in random order — a spinning disk by two or three orders of magnitude, an SSD by a factor of several, main memory by whatever the prefetcher can predict. A planner’s cost model has two constants for this, usually called something like a sequential page cost and a random page cost, and their ratio is typically set between two and forty.

Put a ratio $\rho$ into the arithmetic and the crossover moves to where $\rho$ times the index’s block count equals the scan’s, which at $\rho = 4$ is around 6% and at $\rho = 20$ is around 1.5%. The rule of thumb is right about the number and wrong about which quantity produces it. It is not $n/B$ that puts the crossover at a few per cent; it is the read-cost ratio, and $n/B$ arrives at the same neighbourhood by coincidence at typical parameters.

The general form of that observation is one this collection keeps arriving at. A cost model is a set of exchange rates between quantities, and a conclusion is only as good as the rate it leans on hardest. One run, four counts, four answers makes the point about comparisons and swaps in a sorting routine: the ranking is a function of the rate, and the rate has to be argued for rather than assumed. Here the rate is between a sequential transfer and a scattered one, this field has set it to one, and a planner sets it to somewhere between two and forty — which is why two careful calculations of the same crossing land an order of magnitude apart.

That is a genuine limit of this field’s instrument rather than a criticism of it, and it is the one the block that is not a block names first: a transfer is not a duration, the spread between the cheapest and dearest kinds is four orders of magnitude, and any conclusion resting on two transfer counts that differ by less than that spread is a conclusion this counter cannot support. Here the two plans differ by under a factor of two across most of the interesting range, which is exactly the regime where the count does not decide.

The clustered plan, which is a different kind of answer #

The third line on the hero plate never crosses. A clustered index costs $\lceil k/B \rceil$ plus the descent, so it is below the scan by construction for every $k$ short of the whole file, and at 6% selectivity it costs sixty-seven transfers against the scan’s 1,024.

That looks like it settles the question, and it does not, for a reason that is about the file rather than about the query: a table has one physical order, so it can be clustered on one index. Every other index on the same table is unclustered and behaves like the middle curve. So the clustered plan is not a plan a query chooses; it is a property the table was given once, in advance, on the strength of a guess about which queries would matter.

That is the same shape as every other parameter in this field. A tree with nodes the size of a block is built around a $B$ somebody looked up; the layout that is told nothing is the attempt to avoid having to; and a clustering choice is the same commitment made about the workload instead of the hardware. All three are decisions taken before the data arrives, and all three are invisible in any statement of what the structure costs.

There is a second reason a clustered plan is not simply the answer, and it is about what “in key order” costs to preserve. A file in key order is a file whose insertion point is determined by the key rather than by the end, so it fragments: pages fill, split, and leave gaps, and the sequential run the whole plan depends on becomes a sequence of runs with holes in it. The measured cost of the clustered plan on the plate is the cost on a file that has just been built. On a file that has been written to for a year it is somewhere between that and the unclustered plan, and where exactly is a property of the insertion pattern rather than of the structure.

Maintaining it is not free either. Rows arriving in key order extend the file; rows arriving out of order have to be inserted into the middle of it, which is a B-tree insertion carrying the whole row rather than a pointer — so the write amplification measured in the writes nobody counted applies to the row rather than to an identifier, and is larger by whatever ratio a row bears to a pointer.

It is worth putting one more plan beside these three, because it is the one that makes the trade explicit rather than implicit. A covering index stores the columns the query needs inside the index, so no row fetch happens at all: the cost becomes the descent plus a scan of the relevant part of the leaf level, which is the clustered plan’s shape without the clustering commitment. What it costs is space — the columns are stored twice — and update time, since every write now maintains a second copy. An index has a size is the theme this collection has for exactly that exchange, and the covering index is its cleanest instance in this field: a query plan bought outright with bytes.

What the index costs before any query arrives #

None of the three plans above has been charged for the index’s existence, and two of them depend on it.

An index over $n$ rows is a B-tree with $n$ leaf entries, so it occupies about $n/B'$ blocks where $B'$ is how many entries fit in a block — larger than $B$, because an entry is a key and a pointer rather than a row. Building it costs a sort. Keeping it costs an insertion per row inserted, which is one block written per row by the arithmetic of the previous rung, plus whatever the tree spends splitting nodes.

So the honest comparison for a workload rather than for a query is: the scan costs $\lceil n/B\rceil$ per query and nothing per update, and the index costs its descent plus its fetches per query and about one block per update. There is a break-even in the ratio of queries to updates, and it is a different break-even from the one on the plate. A table read once a day and written continuously should have fewer indexes than its query plans would like, and that trade has no representation in a figure whose x axis is selectivity.

This is the same omission what O notation does not say is about, one level up: the plate prices an operation and the decision is about a workload, and a workload has a shape that no single operation’s cost reveals.

What survives, stated narrowly #

Four things the plates support, and one they do not.

It is worth reading that list against the rest of this field before taking any of it as a conclusion. Nothing above is a duration, nothing above is a prediction, and the ordering of two plans whose counts differ by less than a factor of two is not decided here — which is the standing rule a limit is not a prediction states for every bound on this site and which binds harder in this field than anywhere else.

The scan’s cost is independent of the answer. That is the property that makes it the fallback, and it is exact rather than approximate: $\lceil n/B \rceil$, for one matching row or for every row.

An unclustered index’s cost saturates. It rises as $k$ while the matches are sparse and flattens at the file’s own block count, so its worst case is the scan plus the descent. Nothing on this page finds it costing materially more.

A clustered index’s cost is proportional to the answer, which is the property people mean when they say an index makes a query fast, and only one index per table has it.

A block is the unit, and the unit is what decides. Every difference between the three plans is a difference in how many rows a fetched block delivers: one for the unclustered plan, $B$ for the clustered one and the scan. That is the same observation this field opened with applied to a query plan rather than to a loop, and it is the reason the numbers are as large as they are.

And the crossover is not at $n/B$. The arithmetic that gives that number assumes one transfer per matching row, and that assumption expires exactly where the crossover is supposed to be.

What does not survive is any claim about which plan is faster. These are counts of block transfers between two levels of a hierarchy, they are not durations, and the plans differ by less than the factor by which two transfers can differ. The number a planner uses in place of that missing factor is the most important number in its cost model and it is not measurable here.

Where this ladder goes from here: the estimate the plan rests on #

Every plan on this page was priced against the true number of matching rows, and no query planner has that.

What it has is an estimate, computed from a histogram of the column’s values built at some point in the past by sampling some fraction of the table. The estimate is wrong by a factor that grows with the number of predicates being combined, because the usual combining rule assumes independence between columns and real columns are not independent — a postcode and a city are the same information twice.

That turns the plate above into something more interesting than it looks. The x axis is not an input; it is a guess, and the decision being taken is a decision under an estimate whose error can be an order of magnitude. Two quantities follow immediately and neither has been measured here: how flat the cost is near the crossing, which decides whether an estimate being wrong matters at all, and which way the asymmetry runs, since choosing a scan when an index would have won costs a bounded factor and choosing an index when a scan would have won also costs a bounded factor — and the plate says those two bounds are not equal.

The shape of the answer is already visible in the plates and is not yet a number. Near the crossing the two curves are nearly parallel and nearly equal, so an estimate wrong by a factor of two costs almost nothing there; far from it, on a query matching a handful of rows, choosing a scan costs the full $n/B$ against a handful of transfers, which is the whole file for nothing. So the penalty surface is steeply asymmetric and its steep side is the side a conservative planner falls down. That is a measurement this field can take and has not, and it is the sort of thing the threshold somebody chose found when it swept the constants in real sorting routines: the shipped value is rarely the optimum, and finding out what it is instead is the point.

That asymmetry is computable from the three curves already drawn, it argues for a planner that is deliberately biased rather than merely accurate, and it is the natural next rung: a decision whose input is an estimate should be measured against the estimate’s error, not against the truth.