Answers · Where the data lives

Why does the planner underestimate rows when I filter on two columns that are related?

In shortIt multiplies the two filter shares as if the columns were unrelated, so when one column already implies the other the estimate comes out far too low.

The planner treats the two filters as independent, so it multiplies their shares even when one column already implies the other. That makes the estimate too low by the ratio between the share that passes the second filter after the first has been applied and the share that passes it on its own.

\hat{m}=n\cdot a\cdot b \qquad m=n\cdot a\cdot c

What the multiplication assumes

Here $n$ is the table row count, $a$ is the share passing the first filter, $b$ is the share passing the second filter measured over the whole table, and $c$ is the share passing the second filter among rows that already passed the first. The estimate $\hat{m}$ uses $b$ . The true count $m$ uses $c$ . Multiplying $a$ and $b$ is exactly the rule for independent events: it says the second filter keeps the same fraction whether or not the first has been applied. Nothing in a per-column histogram records any relationship between the columns, so the planner has no other rule available.

Take a table of 9,400,000 addresses. The city filter keeps 3 per cent, so $9{,}400{,}000 \times 0.03 = 282{,}000$ rows. The postcode prefix filter keeps 2 per cent on its own. The planner multiplies the shares: $0.03 \times 0.02 = 0.0006$ , and $9{,}400{,}000 \times 0.0006 = 5{,}640$ rows. In the data, nearly every row with that prefix is in that city, so the second filter removes almost nothing from the 282,000. If it leaves 274,000, the true count is 274,000 and the estimate is low by $274{,}000 \div 5{,}640 \approx 48.6$ , nearly fifty times. Equivalently $c \approx 274{,}000 \div 282{,}000 \approx 0.97$ , not 0.02.

FIG 1The same two filters, estimated and then counted

step	step	what happens	rows	what happened
1	table size from the summary	the starting point	9400000	No error here. The row count is one of the few things the summary knows directly.
2	apply the city filter	3 per cent of 9,400,000	282000	A good estimate, from a measured frequency rather than an assumption.
3	apply the postcode filter as the planner does	multiply by 2 per cent	5640	0.03 times 0.02 is 0.0006, and 9,400,000 times 0.0006 is 5,640.
4	apply the postcode filter as the data does	it removes almost nothing	274000	Nearly every row that passed the city filter passes this one too, because the two columns are saying the same thing.
5	the plan built on 5,640 rows	a nested loop, two further joins above	274000	274,000 divided by 5,640 is about 48.6, so the method chosen above is fed nearly fifty times more rows than it was chosen for.

5 steps

The only wrong step is the multiplication by the unconditional second share. Everything before it is a measurement, and everything after it is a consequence.

Why the natural guess fails

The natural guess is that because each column's frequency was measured, combining them is just arithmetic. It is arithmetic, but the second frequency was measured over the whole table, not over the rows that survived the first filter. The planner needs the conditional share $c$ , and it does not have it. When the columns are related, $c$ is larger than $b$ , often much larger. The error is not in the 3 per cent or the 2 per cent as separate facts; it is in using the unconditional 2 per cent where the conditional share is what the query asks for.

The multiplication is exact when the columns are unrelated, because then $c = b$ . It is nearly exact for weak relationships. It fails badly for a functional dependency, where one column determines another: a postcode determines its city, a product identifier determines its category. Then $c = 1$ , the second filter removes nothing once the first has been applied, and the estimate is low by $1/b$ . With $b = 0.02$ that is a factor of 50; with $b = 0.01$ it is 100. A selective second filter makes the factor large. A second filter keeping 20 per cent on its own can be out by only five in the same extreme case, because $1 \div 0.2 = 5$ .

What changes it

The direct fix is to tell the database that the columns are related, so its statistics job measures their joint distribution and the estimate uses the measured $c$ rather than assuming $b$ . Most systems support this as a declaration over a group of columns. The quick fix is to remove the redundant filter: if the postcode filter removes nothing after the city filter, deleting it costs no correctness and removes the bad multiplication. Where neither is possible, the plan is being chosen on an estimate that cannot be repaired from the query alone, and the remaining options constrain the planner rather than inform it.

Worth keeping

The planner multiplies filter shares because a per-column histogram records no relationship between columns.
When one column determines another, the second filter removes nothing after the first, so the estimate is low by one over the second filter's share.
Joint statistics or deleting the redundant filter fixes the cause; forcing a plan only works around it.

Where this goes next

This question is one step of What the Planner Decides, a course that works through its subject from the beginning. The page that teaches this part of it is Columns That Are Not Independent, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course