Cost-based planning — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 3: Turning requests into execution

Prerequisites: Lesson 15 and the preceding foundations.

Learning outcomes

• Derive cardinality estimates and identify errors caused by skew and correlated predicates.
• Explain how estimation, operator costs, parameter values, and plan reuse interact.
• Compare reoptimization and adaptive execution against their overhead and correctness constraints.

A bad estimate selects a good algorithm for the wrong input

A query filters customers by country and currency. The planner knows that 1% are in one country and 1% use one currency. Assuming independence, it predicts 0.01% satisfy both. In reality nearly every customer in that country uses that currency. The intermediate result is a hundred times larger than estimated, and a plan designed around a tiny input performs millions of unexpected lookups.

Cost-based planning chooses among legal physical plans using estimates of cardinality, width, resource demand, and physical properties. It cannot know the future perfectly. Its quality depends on statistics, modeling assumptions, search strategy, and the ability to adapt when estimates are wrong.

Cardinality and selectivity

Cardinality is the number of rows in a relation or intermediate result. Selectivity is the fraction surviving a predicate. A simple estimate multiplies input cardinality by selectivity. Several predicates require a model of their joint distribution, not just their individual frequencies.

For an illustrative one million rows, two independent 1% predicates yield 1000000 × 0.01 × 0.01 = 100 matches. With perfect correlation, their conjunction yields 10,000 instead. The arithmetic is correct in both cases; the assumption differs. A plan that is reasonable for 100 rows may be unsuitable for 10,000.

Join estimates also depend on distinct counts, key constraints, nulls, and frequency distributions. An equality join on a unique key has different multiplicity from joining two heavily duplicated categories. Averages can hide heavy values that dominate one parameter’s result. Histograms and most-common-value statistics help represent such structure.

Statistics are sampled and time-dependent

Statistics summarize data to make planning affordable. Exact statistics on every expression and combination would be expensive to maintain and impossible to cover exhaustively. Engines therefore sample, summarize, and assume.

Sampling introduces uncertainty. Rapidly changing data can make previously accurate statistics stale. Correlation between columns may require extended statistics or a better model. Expressions and user-defined functions can be difficult to estimate. The planner should handle uncertainty rather than treating every estimate as exact truth.

Statistics collection itself consumes resources and may interact with maintenance. A frequently updated hot partition can need more attention than a large static archive. A global summary may poorly describe a tenant-specific query. Choosing when and where to collect statistics is an operational policy as well as a planner implementation detail.

Cost units and physical properties

A cost model combines estimated CPU work, I/O, memory, and sometimes communication. Its units may be abstract weights rather than milliseconds. An explain output’s cost is not necessarily a direct latency prediction. Relative comparisons can still be useful when the model captures the dominant differences.

Physical properties include ordering, partitioning, and available columns. A more expensive local operator can avoid a later sort or network shuffle. A plan search therefore tracks both cost and properties. Discarding every locally expensive alternative can eliminate the globally best plan.

Memory is especially nonlinear. A hash join that fits can be efficient; one just beyond its budget may spill. An estimate error near that threshold can change behavior sharply. Similarly, a working set just beyond cache capacity can incur a large increase in misses. Smooth cost functions may underrepresent these cliffs.

Join-order search

With many relations, enumerating every plan is impractical. Dynamic programming can retain the best alternatives for subsets and relevant properties. Heuristics limit the search for larger queries. The optimizer trades planning time against the chance of finding a better execution plan.

Planning cost matters for short queries. Spending hundreds of milliseconds optimizing a lookup that executes in a millisecond is not useful if it happens on every request. A complex analytical query running for minutes can justify more exploration. The optimizer needs a budget matched to expected execution and reuse.

A constrained search can miss a plan, while an inaccurate model can choose incorrectly among plans it did find. Those are different failure modes. An investigation should identify whether the desired plan was absent, misestimated, or rejected for another property before adding hints or changing configuration.

Parameter sensitivity and plan caching

A prepared query may run for both a small tenant and a huge tenant. One generic plan can avoid repeated optimization but fail for extreme parameter values. A custom plan can use current values while consuming additional planning resources.

For example, an index lookup strategy may be excellent for a tenant with ten rows and poor for a tenant with ten million. A cached plan selected from the first execution can be inappropriate for the second. The engine’s generic/custom policy and invalidation behavior determine the outcome.

Applications can sometimes improve predictability by separating query shapes or avoiding extreme tenant mixing in one physical layout. However, duplicating query text merely to influence cache behavior can create maintenance complexity. The root issue is a distribution with different optimal strategies, and the chosen remedy should make that distinction explicit.

Adaptive execution

An adaptive engine observes actual cardinalities or resource behavior and changes strategy at safe points. It might choose a join algorithm after materializing a small input, repartition skewed data, or alter parallelism. Adaptation can reduce dependence on perfect estimates.

Changing strategy has costs and semantic constraints. Already emitted rows cannot be casually emitted again. State may need conversion. Distributed workers must agree on a new partitioning boundary. Waiting to gather more information can delay first results. The adaptation protocol is part of the executor, not just a better formula in the planner.

A robust design can also choose a less fragile plan whose performance is acceptable across a range of estimates. The cheapest plan under one exact prediction is not always the best operational choice under uncertainty. This is particularly relevant near memory limits or for high-variance tenant distributions.

Reading evidence from a plan

PostgreSQL’s EXPLAIN shows planned nodes and estimates; EXPLAIN ANALYZE executes the query and reports observed behavior. Executing analysis can modify data or consume substantial resources, so operational use must account for the statement and environment. The course discusses interpretation, not permission to run arbitrary analysis on production.

Compare estimated and actual rows at each node, beginning where the first major divergence appears. A large final difference may originate far below the expensive join. Examine loops as well as rows per loop, and connect buffers, spills, and timing to the plan shape. Do not treat one node’s displayed time as an independent quantity that can always be summed with its descendants.

The implementation-specific fact is that explain facilities expose planner and execution evidence. The broader analysis is a disciplined causal sequence: wrong input model, wrong physical choice, unexpected work, then observed latency. Tuning a downstream timeout without addressing that chain only changes how long the application waits.

Derive an equality estimate and expose its assumptions

Suppose a table has one million rows and one thousand distinct customer identifiers. Under a uniform nonnull distribution, equality on one identifier predicts about one thousand rows. This estimate is row_count / distinct_count. It is reasonable only if the selected identifier behaves like the average and if the statistics describe the relevant snapshot well enough. One customer owning half the rows breaks the uniform assumption for that parameter.

Most-common-value statistics can represent the heavy identifier directly. Remaining frequency mass is distributed across less common values under a residual model. A histogram can summarize ranges for inequalities. Neither automatically captures correlation with another column, such as one customer owning most rows from the current month. A query combining customer and time needs conditional information that single-column summaries may not provide.

For a join between R with N rows and S with M rows on equality columns, a simplified uniform model estimates N × M / max(distinct_R, distinct_S). This assumes compatible domains and distributions and ignores several important details. If the domains do not overlap, the answer can be zero. If both have one very heavy matching value, the result can be much larger than a uniform model predicts. The formula is a starting hypothesis, not a law of joins.

A primary-key uniqueness proof supplies a stronger bound: each matching foreign-key row can match at most one parent. Valid constraints can therefore improve cardinality reasoning beyond sampled frequencies. Nulls, missing parent references, and deferred validation affect which stronger statements are available at the planning boundary.

Sampling has predictable blind spots

Assume an ideal uniform independent sample of 30,000 rows, and a category present in one row out of 100,000. The expected number of sampled instances is 0.3. The probability of seeing none is approximately (1 - 0.00001)^30000, close to exp(-0.3), or 74%. A rare category can therefore be absent from a legitimate sample without any implementation bug.

A rare category can still dominate one query if the application specifically asks for it, or if its rows are exceptionally wide or expensive to process. Sampling accuracy should be evaluated against decision importance, not only global frequency. Targeted statistics or a distinct query shape may be useful when rare values have very different optimal plans.

Rapid change creates another blind spot. A time-partitioned table may receive all recent writes in a new range after statistics collection. A histogram describing yesterday’s maximum can underestimate today’s active tail. Automatic refresh policy, partition-level summaries, or planning rules for out-of-range values can mitigate the error. The design needs a clear response to stale information rather than assuming collection runs continuously and free of cost.

PostgreSQL 18 documents approximate planner statistics and extended statistics for selected relationships. The implementation fact is that a planner can maintain more than independent column summaries. The general limitation remains that no practical summary covers every predicate, expression, and correlation. PostgreSQL planner statistics

Cost a scan and an index path without inventing milliseconds

Consider a constructed table of one million rows in 10,000 data pages. A sequential scan reads each page once and evaluates one million predicates. An index path first reads relevant index pages, then visits data pages containing matches. If 100 matching rows are scattered, about 100 data-page fetches may be attractive. If 500,000 matches scatter across nearly all pages, the index path adds traversal and random-access overhead while touching most of the table anyway.

An abstract cost model can assign weights to sequential pages, random pages, and tuple CPU work. Those weights rank alternatives under an assumed environment. They should not be labeled milliseconds unless calibrated and validated as timing predictions. Cache residency changes the actual I/O cost; concurrent queries change queueing; compression changes CPU and bytes. One fixed model only approximates these effects.

Clustering matters. One thousand adjacent matches can occupy far fewer pages than one thousand uniformly scattered matches. A correlation statistic between index order and physical placement can influence the estimated heap access. A covering index changes the plan again by avoiding some base-record fetches, subject to visibility. Comparing just “index” and “scan” misses the properties that determine their work.

The cost comparison should include startup cost and total cost when time to first rows matters. A hash join can require building its table before returning output, while an indexed nested loop may return the first match quickly. A LIMIT can favor low startup cost if the plan can stop early, but only under the semantic conditions established in Lesson 14.

Dynamic programming retains alternatives with different properties

A small join optimizer can enumerate subsets of relations. For each subset, it considers ways to divide that subset into joined inputs, combines their candidate plans, and keeps promising alternatives. If it retains only the cheapest plan per subset without considering order, it can discard a slightly more expensive ordered plan that avoids a large final sort.

A useful state therefore includes required or delivered physical properties. One alternative can be cheapest unordered; another cheapest ordered by customer identifier; another partitioned by tenant for a distributed join. The number of alternatives grows, so practical search needs pruning and budgets. A property is valuable only when a later operator can use it.

For a simple chain of joins, a selective predicate can make starting from one end attractive. For a star schema, joining a filtered dimension early can reduce the large fact input. But correlations and join multiplicity can reverse those expectations. Heuristics reduce planning effort while risking a missed alternative; cost errors can misrank alternatives that were enumerated. Diagnose these separately.

Planning itself consumes memory and CPU. A service processing thousands of new short query shapes per second cannot spend unlimited time on exhaustive exploration. A repeated analytical query running for minutes can justify a larger budget. Plan caching and search policy trade one kind of work against another, and their benefit depends on reuse.

A memory threshold can reverse the preferred plan

Suppose a build input is estimated at one million rows with 40-byte payload, or 40 MB. Hash metadata and allocation increase the actual state to an illustrative 80 MB. With a 128 MB budget, the plan fits. If the real cardinality is three million, the same representation grows toward 240 MB and must spill or fail under a safe reservation policy.

A model that compares only raw row bytes may select a plan on the wrong side of the threshold even when row-count estimation is accurate. Hash buckets, key storage, duplicate chains, alignment, and parallel copies must be represented. A parallel plan can replicate build state per worker or share it with synchronization; those alternatives have different memory and CPU costs.

Spilling introduces temporary writes, rereads, and partitioning work. The cost curve can have a discontinuity near the budget, while a simple smooth model predicts only a small increase. Robust planning can prefer a plan with slightly higher expected cost but less sensitivity to plausible cardinality error. The appropriate margin follows workload uncertainty and the severity of the spill cliff.

Other thresholds behave similarly: a working set exceeding cache capacity, a sort needing another merge pass, or a network shuffle saturating one link. A resource-aware optimizer should recognize these transitions rather than assuming cost scales smoothly with rows everywhere.

Plan caching needs a distribution-aware policy

Assume the same prepared statement filters one tenant. Most tenants have one hundred rows, while a few have ten million. A generic index-driven plan can serve the majority efficiently and perform poorly for the large tenants. A scan-oriented plan suitable for a large tenant can waste work for the small ones. There may be no single best plan for every parameter.

A custom plan uses parameter values and current statistics but pays optimization cost each time. A generic plan amortizes that work. A system can choose between them using a policy informed by expected savings, or maintain several parameter-sensitive alternatives if its architecture supports that safely. The policy must be explained as implementation-specific rather than assumed universal.

An application can expose genuinely different workloads through different query shapes or tenant placement, but artificially multiplying SQL text solely to evade a cache policy can create churn. The goal is predictable execution under known distributions. Explicitly handling a large-tenant class can be clearer than relying on whichever parameter happened to prepare a statement first.

Invalidation remains necessary when schemas, indexes, or relevant function definitions change. Statistics refresh may trigger replanning under an engine’s policy, while running executions still need stable ownership of their chosen plan. Cache eviction and plan replacement must not free structures still in use.

Interpret actual rows together with loops

An execution report might show an inner index scan returning three rows per loop across 100,000 loops. Its total produced rows are roughly 300,000, not three. A parent nested-loop node might therefore do substantial repeated work even when each individual lookup is cheap. Displays often average or round per-loop values, so exact totals require understanding the tool’s conventions.

Estimated and actual rows should be compared at the earliest major divergence. If a filter estimated 100 rows and produced 100,000, a downstream join can be expensive because its input model was wrong. Forcing a different join can relieve the symptom while leaving the original selectivity problem. Inspect data skew, stale statistics, parameter sensitivity, and expression estimates before concluding the join implementation is inefficient.

Node times often include descendant work or overlap among parallel workers. Summing every displayed time can double count. Buffer counts, temporary bytes, worker utilization, and I/O waits provide complementary evidence. End-to-end request latency can also include connection and queue waits absent from the execution report. A query plan explains a particular boundary, not the entire user experience.

EXPLAIN ANALYZE executes the statement in PostgreSQL. That is especially important for mutations and resource-intensive queries: analysis is an execution action with real effects, not merely a formatting option. PostgreSQL EXPLAIN documentation

Adaptation requires a safe handoff

Suppose the executor materializes an input before choosing a join. It can count actual rows and select an in-memory hash path or an external path before emitting results. This is a relatively clear adaptation boundary because no output has escaped and the materialized input has stable ownership. It costs startup time and temporary state to obtain that information.

Switching after output begins is harder. A restarted algorithm must not emit already returned rows again or omit rows consumed by the previous strategy. Distributed workers need an agreed partitioning and progress boundary. Adapting parallelism can require moving or sharing state while requests continue. The correctness protocol is more important than the attractiveness of the new cost estimate.

Runtime feedback can also inform later executions without changing the current one. Actual cardinality observations can update estimates or trigger investigation. But one execution may be atypical, and feedback tied to one parameter can harm another. Learning policies need bounded influence and context; otherwise the optimizer can oscillate among plans as different tenants alternate.

The practical target is an optimizer that makes useful decisions under imperfect information and fails gracefully when predictions are wrong. Better statistics, robust alternatives, bounded resource ownership, and observability work together. None independently removes the uncertainty inherent in planning future execution.

Compare competing plans under estimated and observed inputs

The rows illustrate separate decision effects; the byte figures are an independent constructed build-side example, not a claim that 10,000 filter rows inherently occupy 120 MB. A useful cost comparison states which input feeds each operator and includes representation overhead. Estimated cost units cannot be converted directly into elapsed time from this table.

The table also distinguishes a bad model from a bad algorithm. The indexed plan may be correct and fast for its predicted hundred probes. Once evidence shows ten thousand, the operator choice deserves reconsideration. Improving statistics can repair future choices, while safe spill paths and adaptive boundaries protect current execution when predictions remain wrong. Neither changes the query’s required result or authorizes silently dropping work to meet a latency target.

Design conclusion

An optimizer is a decision system operating under uncertainty. It needs legal alternatives, useful statistics, resource-aware costs, search budgets, and safe responses to error. Lesson 17 examines how the chosen plan is executed and why the control-flow representation itself can change CPU efficiency.

Sources and further reading

• PostgreSQL 18 planner statistics
• PostgreSQL 18 EXPLAIN

Course index · Lesson plan