An optimizer estimates 3 rows for a filter on both a `city` column and a `postal_code` column, but the query actually returns about 40,000 rows, and the resulting plan is catastrophically slow. Why does this kind of underestimate happen, and what can be done about it?

seniorshould knowfreq 42%

answer

sel(A AND B) = sel(A) × sel(B) by default
correlated → underestimate, product double-counts
city/postal, model/manufacturer, status/shipped_at
3 est. rows → nested loop executed 40,000 times
fix: extended/multi-column stats, drop redundant predicate

basics

~20 s

The optimizer assumes predicates on different columns are independent and multiplies their selectivities. City and postal code are almost perfectly correlated, so the true combined selectivity is roughly the postal code's alone, not the product. Fix it with multi-column/extended statistics, or by removing the redundant predicate.

solid answer

~60 s

By default a cost model treats predicates on different columns as independent: combined selectivity = selectivity(city) × selectivity(postal_code). With, say, 1/5,000 for the city and 1/40,000 for the postal code, that product is astronomically small, so the estimate floors at a handful of rows.

But those columns are functionally dependent — a postal code essentially determines the city. Knowing the postal code adds nothing once you know the city, so the real selectivity is roughly the more selective predicate alone. The estimate is therefore off by the factor by which the second predicate was double-counted.

The damage is not the estimate itself, it's the plan: 3 estimated rows makes a nested loop look free, and it then executes 40,000 times; or a hash table gets sized for 3 rows and spills.

Fixes, in order: gather multi-column / extended statistics on the correlated pair so the engine knows the functional dependency; drop the redundant predicate if the application can; or restructure so the correlated filters land in one indexed composite lookup. As containment, materializing the filtered set or hinting the join can hold the line.

By default a cost model treats predicates on different columns as **independent**: combined selectivity = selectivity(city) × selectivity(postal_code). With, say, 1/5,000 for the city and 1/40,000 for the postal code, that product is astronomically small, so the estimate floors at a handful of rows. But those columns are functionally dependent — a postal code essentially determines the city. Knowing the postal code adds nothing once you know the city, so the real selectivity is roughly the more selective predicate alone. The estimate is therefore off by the factor by which the second predicate was double-counted. The damage is not the estimate itself, it's the plan: 3 estimated rows makes a nested loop look free, and it then executes 40,000 times; or a hash table gets sized for 3 rows and spills. Fixes, in order: gather **multi-column / extended statistics** on the correlated pair so the engine knows the functional dependency; drop the redundant predicate if the application can; or restructure so the correlated filters land in one indexed composite lookup. As containment, materializing the filtered set or hinting the join can hold the line.

code

text · 8 lines

text

rows = 20,000,000
sel(city='Springfield')      = 1/5,000   = 0.0002
sel(postal_code='62704')     = 1/10,000  = 0.0001

independent:  20,000,000 * 0.0002 * 0.0001 = 0.4  -> clamped to 1
reality:      postal_code determines city    -> 2,000 rows

error factor ~2,000x -> nested loop chosen -> inner side probed 2,000x

go deeper

for a junior

Recognise that the optimizer multiplies the two filters' selectivities and that the columns are related, so the real answer is much larger than the product.

for a middle

Explain the independence assumption explicitly, work through the arithmetic, and name multi-column statistics or dropping the redundant predicate as fixes.

for a senior

Connect the underestimate to the specific plan damage — nested loop, join order, hash spill — and sequence the remedies from extended statistics through query restructuring, with hints only as containment.

for a principal

Discuss where estimation is structurally unreliable in a schema, which correlated column groups warrant standing extended statistics, and how to design critical paths so plan quality does not depend on a fragile joint estimate.

The independence assumption

Estimating the selectivity of a single predicate is a solved problem: statistics describe one column, and a histogram gives a good answer. Estimating the selectivity of several predicates together is much harder, because it requires knowing the joint distribution — how values in one column co-occur with values in another. Storing joint distributions for every pair of columns is combinatorially expensive, so the default model assumes independence:

sel(A AND B) = sel(A) × sel(B)

This is right when the columns really are unrelated, and badly wrong when they are not.

Why correlation makes it fail, and in which direction

Take a 20-million-row addresses table:

city = 'Springfield' — say 1 in 5,000 rows, selectivity 0.0002.
postal_code = '62704' — say 1 in 10,000 rows, selectivity 0.0001.

Independent estimate: 0.0002 × 0.0001 = 2 × 10⁻⁸, times 20,000,000 = 0.4 rows, which engines clamp to 1 or a small floor. Reality: every row with postal code 62704 is in Springfield, so the conjunction returns exactly the postal-code set — 2,000 rows, or in the question's numbers 40,000.

The general rule: positively correlated predicates are underestimated by the independence assumption, because the second predicate is treated as filtering further when it filters nothing new. Negatively correlated or mutually exclusive predicates get overestimated the other way, which is less damaging in practice.

Common correlated pairs in real schemas:

city / state / postal code / country
product model / manufacturer
order status / shipped-date presence
created_at / any monotonically-assigned identifier
department / job title / salary band
any denormalized copy of a column alongside its source

Why a small underestimate becomes a large outage

Row estimates are inputs, and a wrong input propagates:

Join method. A nested loop is optimal when the outer side has very few rows, because it probes the inner side once per outer row. Estimating 3 rows makes that look like 3 probes; 40,000 actual rows makes it 40,000 probes, and if the inner probe is itself not cheap, the query dies.
Join order. The optimizer places the smallest intermediate result first. A phantom 3-row relation gets driven first, reshaping the whole tree around a false premise.
Memory sizing. Hash tables and sort buffers are sized from estimates. Under-sizing causes spills to disk, which turns an in-memory operation into an I/O-bound one.
Access path. A tiny estimate favours index-with-lookup paths; 40,000 lookups may cost more than a scan.

So the visible symptom is a nested loop or a spilling hash, and the invisible root cause is one multiplication that should not have happened.

Remedies

Multi-column / extended statistics. Modern engines can gather statistics describing a set of columns, capturing either functional dependency ("postal_code determines city") or joint distinct counts. Once present, the optimizer stops multiplying and uses the recorded relationship. This is the correct, targeted fix: it corrects the estimate without constraining the plan.
Remove the redundant predicate. If postal code determines city, filtering on both is belt-and-braces. Applications often send both because a UI form collects both. Sending only the more selective one removes the problem at the source — assuming the data really is consistent.
Composite index on the correlated columns. An index on (postal_code, city) lets the engine derive a single combined access path, and index-level statistics on that combination are often better than multiplying two column estimates. This helps access-path selection and, in some engines, estimation too.
Restructure the query. Materializing the filtered subset into a temporary structure gives the optimizer a real row count for subsequent joins instead of a derived one. This is heavier-handed but reliable when estimation cannot be repaired.
Containment via hints or pinned plans. Where supported, forcing a hash join or a join order stops the bleeding. Treat it as temporary: it is a lie told to work around a different lie, and it will age badly as data shifts.

What a strong answer emphasises

That the estimate is the defect, not the plan. Candidates who reach immediately for a hint have skipped the diagnosis; candidates who explain the independence assumption, name the correlated pair, and propose extended statistics before hints demonstrate they understand what the optimizer is doing and why it went wrong. Also worth saying: this class of error is invisible in an estimate-only plan and obvious the moment you compare estimated to actual rows.

## The independence assumption Estimating the selectivity of a single predicate is a solved problem: statistics describe one column, and a histogram gives a good answer. Estimating the selectivity of *several* predicates together is much harder, because it requires knowing the joint distribution — how values in one column co-occur with values in another. Storing joint distributions for every pair of columns is combinatorially expensive, so the default model assumes independence: sel(A AND B) = sel(A) × sel(B) This is right when the columns really are unrelated, and badly wrong when they are not. ## Why correlation makes it fail, and in which direction Take a 20-million-row addresses table: - `city = 'Springfield'` — say 1 in 5,000 rows, selectivity 0.0002. - `postal_code = '62704'` — say 1 in 10,000 rows, selectivity 0.0001. Independent estimate: 0.0002 × 0.0001 = 2 × 10⁻⁸, times 20,000,000 = 0.4 rows, which engines clamp to 1 or a small floor. Reality: every row with postal code 62704 *is* in Springfield, so the conjunction returns exactly the postal-code set — 2,000 rows, or in the question's numbers 40,000. The general rule: **positively correlated predicates are underestimated** by the independence assumption, because the second predicate is treated as filtering further when it filters nothing new. Negatively correlated or mutually exclusive predicates get overestimated the other way, which is less damaging in practice. Common correlated pairs in real schemas: - city / state / postal code / country - product model / manufacturer - order status / shipped-date presence - created_at / any monotonically-assigned identifier - department / job title / salary band - any denormalized copy of a column alongside its source ## Why a small underestimate becomes a large outage Row estimates are inputs, and a wrong input propagates: - **Join method.** A nested loop is optimal when the outer side has very few rows, because it probes the inner side once per outer row. Estimating 3 rows makes that look like 3 probes; 40,000 actual rows makes it 40,000 probes, and if the inner probe is itself not cheap, the query dies. - **Join order.** The optimizer places the smallest intermediate result first. A phantom 3-row relation gets driven first, reshaping the whole tree around a false premise. - **Memory sizing.** Hash tables and sort buffers are sized from estimates. Under-sizing causes spills to disk, which turns an in-memory operation into an I/O-bound one. - **Access path.** A tiny estimate favours index-with-lookup paths; 40,000 lookups may cost more than a scan. So the visible symptom is a nested loop or a spilling hash, and the invisible root cause is one multiplication that should not have happened. ## Remedies 1. **Multi-column / extended statistics.** Modern engines can gather statistics describing a *set* of columns, capturing either functional dependency ("postal_code determines city") or joint distinct counts. Once present, the optimizer stops multiplying and uses the recorded relationship. This is the correct, targeted fix: it corrects the estimate without constraining the plan. 2. **Remove the redundant predicate.** If postal code determines city, filtering on both is belt-and-braces. Applications often send both because a UI form collects both. Sending only the more selective one removes the problem at the source — assuming the data really is consistent. 3. **Composite index on the correlated columns.** An index on `(postal_code, city)` lets the engine derive a single combined access path, and index-level statistics on that combination are often better than multiplying two column estimates. This helps access-path selection and, in some engines, estimation too. 4. **Restructure the query.** Materializing the filtered subset into a temporary structure gives the optimizer a real row count for subsequent joins instead of a derived one. This is heavier-handed but reliable when estimation cannot be repaired. 5. **Containment via hints or pinned plans.** Where supported, forcing a hash join or a join order stops the bleeding. Treat it as temporary: it is a lie told to work around a different lie, and it will age badly as data shifts. ## What a strong answer emphasises That the *estimate* is the defect, not the plan. Candidates who reach immediately for a hint have skipped the diagnosis; candidates who explain the independence assumption, name the correlated pair, and propose extended statistics before hints demonstrate they understand what the optimizer is doing and why it went wrong. Also worth saying: this class of error is invisible in an estimate-only plan and obvious the moment you compare estimated to actual rows.

Does the independence assumption ever cause an over-estimate, and does that matter as much?
Yes — with negatively correlated or mutually exclusive predicates, multiplying selectivities can predict more rows than actually qualify in some formulations, and disjunctions are commonly overestimated. Overestimates are usually less harmful: the optimizer picks a hash join or a scan, which is robust and degrades gracefully, whereas an underestimate picks a nested loop that degrades catastrophically.
How would you spot this problem in a plan without knowing the schema semantics?
Compare estimated to actual rows on the filter node itself. A single-table filter that estimates 1–3 rows and returns tens of thousands, with two or more predicates on different columns of the same table, is the fingerprint. Then check whether the columns are plausibly dependent, or just gather extended statistics on the pair and see whether the estimate corrects.
Why not just create the composite index and call it done?
A composite index can give a better access path and sometimes a better combined estimate, but it does not by itself teach the optimizer the functional dependency for other queries or other predicate shapes, and it adds write cost on every DML. Extended statistics fix the estimate for all plans at essentially no write cost, so they are the cheaper first move.

Guessing how many people are both left-handed and wear glasses by multiplying the two rates is fine. Guessing how many are both born in Paris and live in France by multiplying is absurd — the second fact is already implied by the first.

saying these in an interview costs you the question

Not knowing that multi-predicate selectivity is estimated by multiplying independent selectivities by default.
Believing that a histogram on each column solves correlation between them.
Reaching for a hint or forced join order before diagnosing the row-estimate error.
Claiming that refreshing statistics will fix a correlation problem — fresh per-column statistics are still per-column.
Treating the resulting nested loop as the bug rather than as the consequence of the estimate.

An optimizer estimates 3 rows for a filter on both a `city` column and a `postal_code` column, but the query actually returns about 40,000 rows, and the resulting plan is catastrophically slow. Why does this kind of underestimate happen, and what can be done about it?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The independence assumption

Why correlation makes it fail, and in which direction

Why a small underestimate becomes a large outage

Remedies

What a strong answer emphasises

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

§ context

▾related questions4 questions

▾related topics3 topics

The independence assumption

Why correlation makes it fail, and in which direction

Why a small underestimate becomes a large outage

Remedies

What a strong answer emphasises

answer

go deeper

context