When equivalent plans diverge

A bookstore can find one rare order by reading every order page or by following an index. Both routes are semantically equivalent; they are not economically equivalent. PostgreSQL must choose before it sees the actual rows. It estimates how many tuples will flow through each operator, how many pages a path may read, how much CPU expressions require, and whether a sort or hash is likely to fit in memory.

The most important estimate is cardinality: how many rows a relation or intermediate result will contain. If the planner thinks a predicate returns ten rows when it actually returns ten million, it can choose an index nested loop that performs terribly. If it thinks a small table is large, it can avoid a simple route and pay setup costs it did not need. Cardinality drives almost every later decision, so a bad estimate leads to a confident but wrong choice.

The map called statistics

Statistics supply those estimates. The database samples tables and records facts such as row counts, page counts, most common values, null fractions, value ranges, and histograms. For a predicate like `status = 'paid'`, the planner can estimate selectivity from the common-value list. For `created_at > some_date`, it can consult a histogram. For joins, it estimates how many rows will match using distinct counts and the equality conditions. These are approximations, and the planner treats them as such.

Trace one plan choice

Suppose the orders table has one million rows and statistics say only one hundred have status `review`. The planner estimates the predicate's selectivity, generates a sequential-scan path and an index-scan path, then prices both. The sequential scan has predictable page work. The index path visits a smaller ordered structure and then candidate heap locations. At one hundred estimated matches, avoiding most heap pages can outweigh those extra lookups.

Now suppose the true count is four hundred thousand because statistics are stale. The chosen index path is still correct, but repeated heap visits may make it far slower than the rejected scan. Costing promises a defensible choice from available evidence, not foreknowledge. The plan-selection invariant is semantic validity; performance is an estimate. Execution measurements and refreshed statistics are how the system and operator learn when the estimate failed.

How the access methods compare

A sequential scan and an index scan suit opposite situations. If a predicate matches nearly every row, walking an index can be worse than reading the table in order, because the index adds random lookups and extra page visits without filtering much. If the predicate matches a tiny fraction of rows, the index can skip most table pages. The right choice depends on data distribution, table size, caching, and whether the query needs only columns the index already holds.

Join choices follow the same logic. A nested loop works well when the outer side is small and the inner side has an index. A hash join works well when both sides are large and the equality conditions allow a hash table. A merge join works well when the inputs are already ordered or need ordering anyway. Each one wins in different conditions, so the planner tries to match the algorithm to the estimated data shape.

The cost model turns these estimates into a comparable score. It usually combines page reads, CPU per tuple, CPU per operator, memory effects, and sometimes parallelism. The numbers are not wall-clock time. They are relative values that let the planner rank paths against each other. This is why tuning cost parameters changes plan choices: it changes the planner's assumptions about the price of disk, CPU, and random access.

Planning under uncertainty

A clean design would have perfect statistics and a perfect cost model. Real systems have neither. Data can be skewed. Columns can be correlated: a city column and a postal code column are not independent, but a simple estimator multiplies their selectivities as if they were. Recently changed tables can have stale statistics. Parameterized queries can hide the actual values until execution. The planner always chooses under uncertainty.

One response is to keep planning cheap and accept the occasional bad choice. Another is to spend more time searching and estimating. The right tradeoff depends on query complexity and workload. A primary-key lookup should not explore exotic plans; a report joining twelve tables can justify a larger search. PostgreSQL uses dynamic programming and heuristics, with a genetic search option for very large join sets.

Prepared statements force a choice between generic and custom plans. A custom plan can use the actual parameter values supplied for this execution, which helps when selectivity varies widely between values. A generic plan can be reused, saving planning time, but it can be mediocre for particular values. The database has to decide when reuse is worth giving up that specificity.

Indexes influence costing beyond plain lookups. An index can supply order, enforce uniqueness, enable an index-only scan, or make a join path parameterized by values from another relation. Indexes also carry costs: they consume storage, slow writes, and can still require heap rechecks. The planner sees them as candidate paths to be priced like any other.