Cost-Based Optimization

How the optimizer estimates a plan's cost from statistics collected ahead of time, why an estimation error at one step compounds through every step built on top of it, and what stale statistics actually do to a plan.

AdvancedJune 15, 2026

Join Algorithms described three ways to join two tables without explaining how the optimizer decides which one, in which order, for a given query. The answer is the subject of this article: every candidate plan gets an estimated cost, and the cheapest estimate wins.

Statistics: what the estimate is built from#

The optimizer does not know the real data — it knows statistics collected ahead of time by a command like ANALYZE: row counts, the number of distinct values in a column, and often a histogram approximating that column's value distribution. PostgreSQL's own documentation on planner statistics describes exactly this: cost estimates are only ever as good as the statistics behind them, and those statistics are themselves an approximation, refreshed periodically rather than continuously.

Cardinality estimation, and why its errors compound#

Cardinality estimation is predicting how many rows a step of the plan will produce — a filter, a join. This matters more than it might sound, because a plan is a tree: the estimated row count out of one step becomes the estimated row count into the next:

Text

Estimate: filter on status='shipped' -> 10,000 rows (actual: 200,000)                    ↓ (this wrong estimate feeds the next step)Estimate: join against customers using a plan sized for 10,000 rows                    ↓Result: a join algorithm chosen for 10,000 rows, actually processing        200,000 — often a dramatically worse choice than if the        original estimate had been closer to reality

A cardinality misestimate at one step does not stay contained to that step — it propagates through every later step whose own estimate depends on it, which is exactly why comparing estimated to actual row counts at every node, not just the slowest-looking one, matters: the actual root cause is often several nodes upstream of where the time is actually spent.

Why stale statistics produce bad plans#

Statistics reflect the data at the moment they were last collected. A table that has grown one hundred times larger since the last ANALYZE still reports its old, much smaller row count to the planner — every cost estimate involving that table is built on a number that is no longer true, and the plan chosen from those estimates can be badly wrong even though nothing about the query itself changed.

A large bulk load is exactly when statistics go stale fastest

A table that grows gradually keeps its statistics roughly accurate between routine, scheduled ANALYZE runs. A table that receives one enormous bulk load — an initial backfill, a large batch import — can have statistics that are wrong by orders of magnitude immediately afterward, until statistics are refreshed explicitly. Running ANALYZE after a large load, rather than waiting for the next scheduled one, avoids querying against a plan built on badly outdated numbers.

The join-order search space grows combinatorially#

For a query joining N tables, the number of possible join orders grows roughly with N! — factorial, not linear. Exhaustively costing every possible order is feasible for a handful of tables and becomes impractical well before N reaches double digits; real optimizers switch to heuristic or dynamic-programming search strategies past some threshold, trading a guarantee of finding the truly optimal order for a plan that is good enough to compute in reasonable time. A query joining a dozen or more tables is often the point real-world query performance work needs to consider restructuring the query itself, not just tuning around whatever plan the optimizer settles for.

Common mistakes#

Never refreshing statistics after significant data changes#

Statistics do not update themselves continuously — they update when a statistics-collection command runs. A pipeline that bulk-loads a table and immediately queries it can be querying against badly stale statistics without any error or warning that this happened.

Treating the optimizer's chosen plan as automatically correct#

The optimizer picks the cheapest estimated plan, not the actually cheapest one — when the estimate is wrong, so is the choice built on it. Comparing estimated to actual row counts, as Reading Query Execution Plans covers, is how to catch this rather than trust the plan blindly.

Reaching for manual join-order hints before checking statistics#

A join order that looks wrong is more often a symptom of stale or insufficient statistics than a genuine optimizer limitation. Refreshing statistics and re-checking is usually a faster, more durable fix than hand-tuning a join order that will need to be re-tuned again the next time the data shape changes.