8.2 Cardinality Estimation, Cost Modeling, and Execution Plan Diagnosis

A query that ran in just a few milliseconds yesterday now times out today, because the query plan changed the order of joins. The first thing to go wrong in the execution plan is the estimated number of rows in intermediate results.

The hardest part of query optimization isn't knowing which algorithms to use; it's accurately estimating how many rows each intermediate relation will have before execution. A 100x error in cardinality can propagate through a join tree, causing a nested loop join that was originally suitable for a small outer table to be used on millions of rows, or causing a hash table to severely underestimate memory requirements.

What the Optimizer Chooses

Physical alternatives include:

• access path: sequential/index/bitmap/partition scan;
• join order and join algorithm;
• predicate placement;
• aggregation and sort implementation;
• parallelism, partition exchange, materialization;
• required versus provided order;
• remote pushdown;
• JIT or compiled execution thresholds.

The optimizer does not necessarily enumerate all possible plans. The search space grows rapidly with the number of joins, so the system employs techniques such as dynamic programming, memoization, cascades, heuristics, join-order restrictions, or genetic/randomized search to prune the space.

Cost Is Not Milliseconds

In a PostgreSQL execution plan:

cost=startup_cost..total_cost
rows=estimated_output_rows
width=estimated_average_row_bytes

Cost is an abstract unit weighted by configuration parameters, used to compare alternative execution strategies, it does not directly represent wall-clock milliseconds. Common components include page I/O, tuple or operator CPU usage, parallel setup and data transfer, sorting, and hashing.

Values like seq_page_cost and random_page_cost default to values that may vary with version or configuration. It's incorrect to state that "SSDs should simply set random_page_cost to 1.1." These parameters also implicitly reflect the relative cost of caching and the overall workload, and must be validated through benchmarking and plan regression testing.

Selection cardinality

The optimizer may use:

• table row or page estimates;
• NULL fraction;
• number of distinct values;
• most-common values and their frequencies;
• histogram bounds;
• physical correlation;
• expression or index statistics;
• constraints or partition bounds.

For equality predicates, the optimizer can use direct frequencies from the most-common values (MCV). Values not present in the MCV are estimated using the remaining distinct value distribution. Range predicates rely on histogram interpolation. All of these are sample or model-based estimates and are not actual values derived from running the query.

Correlated columns

WHERE country = 'CN'
  AND city = 'Shanghai'

If the optimizer assumes independence:

selectivity(country='CN') × selectivity(city='Shanghai')

this underestimates the selectivity of correlated combinations. PostgreSQL extended statistics can capture dependencies, MCV (most common value) combinations, or ndistinct values:

CREATE STATISTICS stats_country_city
    (dependencies, mcv, ndistinct)
ON country, city
FROM addresses;

ANALYZE addresses;

Support and applicable predicates must be checked against the current version. Extended statistics do not magically resolve cross-table correlations or all expressions.

Join cardinality

A simplified equijoin cardinality estimate may rely on row counts, distinct counts, most common values (MCV), and uniqueness from both sides:

|R ⋈ S| ≈ |R| × |S| / max(ndistinct(R.k), ndistinct(S.k))

This is a rough formula assuming uniform distribution or containment. Skew, partial overlap, NULL values, composite key correlations, and filters can all invalidate it. Primary key, foreign key, and UNIQUE constraints provide strong evidence and thus help optimization, rather than data integrity alone.

Why Statistics Can Be Outdated

• Statistics are not updated after bulk load operations;
• Tables that change rapidly or are partitioned;
• Sampling fails to capture rare skew;
• Distribution of parameters in prepared statements differs;
• Expressions or correlations lack associated statistics;
• Temporary tables with short lifecycles;
• Remote sources do not provide accurate estimates.

"The top reason for sudden performance degradation is lack of ANALYZE" is an overgeneralization. I/O, locks, plan cache behavior, data growth, bloat, network latency, and dependency delays can all be underlying causes.

Join-order search

Inner joins can often be reordered; outer, semi, anti, and lateral joins, along with volatile semantics, impose constraints on legal join orders. Even when three tables admit multiple parenthesizations, commutativity can lead to redundant representations, and the optimizer uses equivalence classes or memoization to avoid exhaustive permutations.

PostgreSQL employs exhaustive or dynamic-programming-style search for small join problems, and for cases exceeding geqo_threshold, it can enable GEQO. GEQO is not a new feature introduced in PostgreSQL 12, its specific threshold and default settings are determined by current configuration.

Manually splitting a 15-table query into temporary tables may reduce search space, but it can also result in loss of pushdown and reordering opportunities, increased I/O, and altered transaction semantics. Always evaluate the impact using plan evidence first.

Prepared statements: custom vs. generic plan

The optimal execution plan for the same SQL query can depend on the parameter values:

SELECT * FROM events WHERE tenant_id = $1;

A small tenant might benefit from an index scan, while a large tenant could perform better with a sequential or bitmap scan. The system can generate a custom plan each time based on the parameter, or reuse a generic plan to reduce planning overhead.

The symptoms of parameter sniffing or generic-plan regression include some parameter values performing quickly while others are slow. To diagnose such issues, it's essential to track the distribution of parameter values and how they influence plan selection. Avoid embedding literal values directly into SQL to prevent plan cache pollution and potential injection risks.

Read EXPLAIN ANALYZE

PostgreSQL secure read query example:

EXPLAIN (ANALYZE, BUFFERS, WAL, SETTINGS, TIMING OFF, SUMMARY ON)
SELECT a.adventurer_id, COUNT(*)
FROM adventurers AS a
JOIN quests AS q
  ON q.adventurer_id = a.adventurer_id
WHERE q.status = 'active'
GROUP BY a.adventurer_id;

ANALYZE executes the statement. For INSERT/UPDATE/DELETE, perform the operation either within a transaction or in a replication environment analysis, and consider triggers/external side effects. ROLLBACK

First, compare estimated with actual rows

Find the node with the earliest order-of-magnitude deviation, rather than the root alone. Upstream errors propagate to parent nodes.

loops

PostgreSQL's actual time and rows are typically per-loop averages; total rows/work must be considered in conjunction with loops. Worker details and gathered rows in a parallel plan should also be examined together.

Buffers

• shared hit/read/dirtied/written;
• temp read/written;
• local buffers;
• I/O timing (if collection is configured).

A buffer hit doesn't mean zero cost; a read doesn't necessarily mean a device miss; the OS cache and async I/O are still beneath us.

Rows Removed

A large number of rows removed by a filter indicates that the access path read many rows and then filtered them, but this doesn't automatically mean "add a single-column index." You need to evaluate composite/partial indexes, selectivity, write cost, and query importance.

Sort/Hash

Check sort method, memory, disk; hash buckets, batches, memory. batches > 1 often indicates spill/repartition, but output field names vary by version.

A Diagnostic Sequence

1. Save the SQL, parameters, schema/index, database version, and plan settings;
2. Verify wait times: CPU, I/O, lock, client/network;
3. Obtain a safe execution plan with actual rows and buffers;
4. Identify the first cardinality deviation;
5. Examine predicate semantics, statistics, correlation, and constraints;
6. Review operator resource usage: spills, loops, heap fetches, parallel skew;
7. Form the minimal change: statistics, index, query, schema, configuration;
8. Test with representative parameters and cold/hot cache comparisons;
9. Monitor write cost, impact on other queries, and concurrency guardrails.

The Boundaries of Query Rewrite

• EXISTS can express semijoin operations to avoid duplicate joins;
• NOT EXISTS provides a safer way to represent nullable anti-joins;
• Predicate pushdown must respect the semantics of outer joins and NULL values;
• Wrapping indexed columns in functions or casts may prevent ordinary index conditions, in which case expression indexes or query rewriting may be needed;
• Whether CTEs are inlined or materialized depends on product version and syntax options;
• OR can use bitmap OR, union, or direct scan; manual rewriting of UNION ALL requires careful handling of duplicate semantics.

Any query rewrite must first prove result equivalence before comparing execution plans.

Remote/FDW

Remote source optimization is constrained by the connector's ability to push down filters, joins, and aggregates, availability of remote statistics, network latency, and transaction semantics. The optimizer's estimated local cost may lack consideration of remote queueing, caching, or data skew.

Instead of broadly stating "the advisor can't handle remote tables," examine the execution plan to identify which operations run remotely and how many rows or bytes are sent back.

Acceptance Checklist

• [ ] Don't treat cost as milliseconds;
• [ ] Identify the earliest cardinality deviation, rather than the root cause alone;
• [ ] actual rows/time combined with loops;
• [ ] Statistics can describe column-level or extended correlations, but not real-time values;
• [ ] Test prepared statements alongside representative parameter sets;
• [ ] Side effects of EXPLAIN ANALYZE are under control;
• [ ] After optimization, verify write latency, concurrency, and other execution plans.

Chapter Summary

The executor decides how to proceed, while the optimizer estimates which approach is cheaper based on incomplete statistics. The most important diagnostic signal is typically the intermediate cardinality compared to actual resource usage, rather than whether a node name appears sophisticated. The next chapter covers query compilation: how to reduce interpreter/iterator overhead and transform expressions into code that runs more efficiently on the CPU.

Official Documentation Entry Points

• PostgreSQL Using EXPLAIN
• PostgreSQL Planner Statistics
• PostgreSQL Genetic Query Optimizer
• PostgreSQL Runtime Config: Query Planning