The cost model and the cardinality estimator
Why does the cost model matter far less than the four assumptions behind cardinality estimates?
Two parts that fail differently
People often mix up two components. They fail in different ways.
- The cost model turns a plan plus estimated sizes into a single number.
- The cardinality estimator produces those estimated sizes.
The cost model
The cost model is a weighted sum of resources the plan will use: sequential page reads, random page reads, tuples processed, bytes shuffled. The weights encode a model of the hardware. PostgreSQL ships these defaults:
| Setting | Default | Meaning |
|---|---|---|
seq_page_cost | 1.0 | cost of reading one page in a sequential scan |
random_page_cost | 4.0 | cost of reading one page at random |
cpu_tuple_cost | 0.01 | cost of processing one row |
The 4:1 ratio between random and sequential reads is a calibration for a spinning disk, where a random read needs an arm movement. On NVMe SSDs the real ratio is closer to 1.1 to 1.5. On object storage the model's unit is wrong altogether, because the real cost is a request with a latency floor (tens of milliseconds), not a page.
That these old defaults survive tells you something important: cost models are ordinal, not cardinal. Ordinal means only the ranking matters (plan A is cheaper than plan B). Cardinal means the number itself is meaningful (plan A takes 3.2 seconds). The planner only ever compares plans against each other. It never uses the cost as a prediction. So an absolute error is tolerable as long as the ranking is right. Two corollaries follow:
- "Tune the cost constants" is near the bottom of the diagnostic list. Changing a constant only helps if it flips a specific ranking. The team lead's suggestion was premature.
- Optimizer cost is not an estimate of runtime and cannot be used as one. Every attempt to build admission control (reject expensive queries), cost governors or chargeback (billing by query cost) on raw optimizer cost fails, because the number has no unit and no calibration.
Cloud pricing partly undoes this. With a price per terabyte scanned, the bytes to be read become a truly cardinal, dollar-denominated cost. This is why serverless warehouses show bytes scanned rather than an abstract cost unit: cloud pricing by bytes turns an ordinal quantity back into a cardinal one.
The cardinality estimator and its four assumptions
The estimator is the part that matters. It rests on four named assumptions. Every estimation failure you will ever diagnose is one of them breaking.
- Uniformity: values are spread evenly inside a histogram bucket.
- Independence: conditions on different columns are uncorrelated, so their selectivities multiply.
- Containment: the distinct join values of the smaller side are a subset of the distinct join values of the larger side.
- Inclusion / uniform join: every distinct value takes part in the join equally.
From (3) and (4) the standard join formula follows directly. Let V(A,a) be the number of distinct values of column a in table A. If every distinct value of the join key on side A finds matches in B, and B's rows are spread evenly over its V(B,b) distinct values, then each A row matches |B| / V(B,b) rows. This gives:
- the number of distinct values of column a in table A
The max in the denominator is the containment assumption written as arithmetic. When containment fails, the formula is not approximately wrong; it is wrong by the ratio of the true overlap to the assumed one. This happens in a join between two tables that were filtered on different criteria, which is every star query. Example: after filtering, side A holds the customers who bought in 2024 (50,000 distinct ids), and side B holds customers who signed up in 2020 (60,000 distinct ids). The formula assumes all 50,000 A values appear in B. If only 5,000 do, the result is about 10× smaller than predicted. In other cases it is larger.
When there are no statistics at all
When statistics are missing, systems fall back on constants inherited from IBM's System R: about 1/10 for an equality condition, 1/3 for an inequality, 1/4 for a range. These are not estimates. They are placeholders. A plan built on them is arbitrary. The practical point is: a table without statistics does not produce a slightly worse plan, it produces an unrelated one.
Counting distinct values from a sample is provably hard
One estimation problem is a permanent constraint, not an engineering gap: NDV cannot be estimated well from a sample. Charikar and co-authors proved that any estimator that looks at a sample of size k has worst-case error of order √(n/k), where n is the table size. To get a bounded-error distinct count, you essentially have to look at everything. This is why modern engines compute NDV with HyperLogLog (a sketch that counts distinct values in small memory over a full pass) rather than from the sample they use for histograms. The sketch exists because sampling provably cannot do this job. It is also why COUNT(DISTINCT) cardinality, which decides the size of group-by operations, is the estimate most likely to be badly wrong.
In one sentence: the cost model is an uncalibrated ordinal ranking function encoding obsolete hardware, and it matters far less than the four assumptions (uniformity, independence, containment, inclusion), whose failures are ratios that compound.