Every Plan Rests on an Estimate
Last timeThe Queries an Index Cannot Save
The database chooses a plan by predicting how many rows each step will produce. Those predictions come from a small sample, and when one of them is badly wrong the plan is wrong with it.
A plan has numbers in it, and they look authoritative. Each step says how many
rows it expects to produce, and none of them has been counted. They are
projections from a summary built by looking at a small fraction of the data,
possibly some time ago, and the whole plan was chosen on their strength.
What the database actually knows about a column
The stored summary is small and has three parts, and knowing them tells you
immediately which conditions will be estimated well.
There is a list of the most common values with how often each occurs, which makes
a condition on a popular value accurate because its frequency was measured. There
is a set of boundaries dividing everything else into buckets holding roughly
equal numbers of rows, which lets a range be estimated by counting buckets. And
there is a count of distinct values, which is what a condition on an unlisted
value falls back on, assuming the rest are spread evenly.
That last fallback is where single-column estimates go wrong. A value that is
common but did not make the most-common list is assumed to be as rare as
everything else.
- the estimated share of rows satisfying both conditions
- the number of rows the first condition is thought to match
- the number the second is thought to match
- the number of rows in the table
- the first condition's share on its own, which may well be accurate
- the second condition's share, likewise, with the multiplication between them being the entire assumption
Two conditions are worse than one
Consider a table of addresses with a city column and a postal code column. The
city matches a hundredth of the table, the postal code a thousandth, and
multiplying gives one row in a hundred thousand. The true answer is a thousandth,
because the postal code already implies the city. The two conditions carry the
same information twice. An estimate wrong by a factor of a hundred towards too
few rows is the commonest cause of a bad plan, because too few rows is exactly
when an index lookup looks attractive and a scan looks wasteful.
Databases let you declare that two columns are related, so the summary records
their joint behaviour. It helps, it has to be asked for, and almost nobody asks.
The lesson stops here
4 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents