Costs, cardinality, and choosing a plan

When equivalent plans diverge

Query planning matters because equivalent plans are not equally fast. Two plans can produce the same rows and still differ by seconds, by minutes, or by an outage. A Postgre-like planner chooses among the alternatives by estimating cost. It asks how many rows will flow through each operator, how many pages must be read, how much CPU will go to evaluating expressions, whether a sort or hash will fit in memory, and whether an index makes a path attractive.

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.

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 trivial primary-key lookup should not spend milliseconds exploring exotic plans. A reporting query joining twelve tables can justify a larger search. Postgre-like systems use dynamic programming and heuristics, and for very large join sets they fall back to genetic or simplified search strategies.

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.