Query optimization and cardinality estimation

Why it matters

The same SQL can run in milliseconds or hours depending on join order and algorithm choice. Optimizers make that choice from estimates, and estimates are wrong in predictable ways. Pointing at the plan node where an estimate went wrong, and explaining why, is a concrete debugging skill and the core problem of a long line of optimizer research.

Core ideas

Architecture. Parse and rewrite the query (push filters down, unnest subqueries, prune columns), enumerate physical plans, estimate the cardinality of every intermediate result, cost each plan and keep the cheapest. Cardinality estimates feed the cost model, so a perfect cost model with bad estimates still picks bad plans.

Selectivity. Systems keep per-column statistics: row count, number of distinct values, most common values with their frequencies, and a histogram for the rest (PostgreSQL uses equal-population buckets). An equality predicate on a common value uses its recorded frequency; otherwise roughly the remaining frequency divided by the remaining distinct values. A range predicate uses the fraction of histogram buckets it covers. Conjunctions multiply selectivities, assuming independence, which underestimates when columns are correlated (city = 'Zürich' AND country = 'CH').

Joins. For an equi-join on columns with d1 and d2 distinct values, a standard estimate is |R|·|S| / max(d1, d2), assuming every value on the side with fewer distinct values finds a match. Each join's error multiplies into the next, so estimates for five-way joins can be off by orders of magnitude, usually downward. Underestimates are the dangerous direction: they make nested-loop joins and small hash tables look cheap.

Search. System R-style dynamic programming builds the best plan for each subset of relations from the best plans of its smaller subsets, keeping extra plans whose sort order is useful later (interesting orders). The search space grows exponentially, so systems restrict tree shapes, avoid cross products, or switch to heuristics beyond a number of tables (PostgreSQL's genetic optimizer, controlled by geqo_threshold). Cascades-style optimizers search top-down with memoization and transformation rules.

Reading plans. In PostgreSQL, compare estimated rows with actual rows (per loop, times the number of loops), working bottom-up. The lowest node where they diverge sharply is usually the cause; nodes above it are victims. Typical fixes: run ANALYZE, raise the statistics target for a skewed column, create extended statistics for correlated columns, rewrite a predicate the estimator cannot see through, or add an index that makes a robust plan available.

Common misconceptions

• "The optimizer finds the optimal plan." It finds the cheapest plan according to its estimates and cost model, within a restricted search space.
• "Faster hardware fixes bad plans." A plan that is wrong by orders of magnitude in rows stays wrong.
• "Start with the most expensive node." Start with the lowest node where estimates and actuals diverge; expensive nodes above it are consequences.
• "Statistics are always current." They are sampled and refreshed periodically; bulk loads and shifting skew leave them stale.
• "Hints are the fix." Hints freeze one plan for today's data; fixing statistics or the query shape usually lasts longer.

How to approach it

Learn the estimation formulas on a small example, then work with real plans. Load data with real correlations (the IMDB data behind the Join Order Benchmark works well) into PostgreSQL, run EXPLAIN ANALYZE on multi-join queries and annotate the error at each node. Add extended statistics and see which estimates change. In interviews, walk through the whole loop: symptom, plan, first misestimate, cause, fix, verification.