Cost Model & Cardinality Estimation

## What an optimizer is doing A SQL query says *what* result you want, never *how* to produce it. Between parsing and execution, the optimizer must choose a physical plan: which access path reaches each table (full scan, index scan, index seek plus row lookup), which algorithm implements each join, in what order tables are joined, and how grouping and sorting are performed. For a query joining six tables there are millions of valid plans whose runtimes differ by orders of magnitude. Choosing among them is the optimizer's whole job. ## Rule-based optimization The original approach — Oracle's RBO is the canonical example, and it was still in use into the 1990s — ranks access paths and transformations in a fixed priority list. A simplified version: single-row lookup by ROWID beats a unique index lookup, which beats a non-unique index range scan, which beats a full table scan; join order follows the order tables appear in the query text. Properties: - **Deterministic.** The same SQL always yields the same plan. No statistics, so no surprise regression after a statistics refresh. - **Cheap to compile.** No enumeration, no estimation. - **Blind to data.** This is the fatal defect. "Prefer the index" is right for a predicate matching 5 rows out of 10 million and badly wrong for one matching 8 million, where the index path means millions of random row fetches while a sequential scan reads the table efficiently. A rule-based optimizer cannot tell those apart, because the distinguishing fact — selectivity — lives in the data, not the query text. - **Syntax-sensitive.** Because join order follows the text, rewriting the FROM clause changes performance, which is a terrible property for maintainable SQL. ## Cost-based optimization System R (IBM, 1979) established the design every mainstream engine still uses. Three components: **1. Plan enumeration.** Generate candidate plans by applying algebraic equivalences (predicate pushdown, join commutativity and associativity, subquery flattening) and by choosing physical operators. The space is exponential, so the search is pruned — dynamic programming over join orders, interesting-order tracking, and heuristic or randomized search once the table count is large. **2. Cardinality estimation.** For each intermediate result, estimate how many rows it produces, starting from stored statistics (row counts, distinct-value counts, histograms, null fractions) and applying selectivity formulas per predicate. This is the part that decides plan quality. **3. Cost model.** Turn estimated cardinalities and access patterns into a number: pages read (distinguishing sequential from random), rows and comparisons processed, memory required. The unit is arbitrary and internal — it is a *comparator*, not a prediction of milliseconds. The cheapest plan is executed. ## Why cost-based won Because the right answer is data-dependent, and only a cost model can express that. The same query against a 1,000-row table and a 1-billion-row table deserves different plans. The same predicate deserves an index seek for a rare value and a scan for a common one. A cost-based optimizer also lets the engine add new physical operators — hash join, bitmap access, parallel execution — and have them chosen automatically wherever they win, instead of demanding a new rule and a new priority position. ## What it costs you - **Estimates can be wrong.** The optimizer optimizes its *belief* about the data. A cardinality estimate off by 1000× yields a plan that is optimal for a world that does not exist. Most catastrophic plans trace to estimation error, not to the cost formula. - **Plans change under you.** New statistics, changed data, a different parameter value, or an engine upgrade can flip a plan. When the flip goes the wrong way it looks like a spontaneous outage. This drove the whole ecosystem of hints, plan baselines, plan guides, and forced plans. - **Compilation is not free.** Enumeration costs CPU, which is why engines cache plans and why plan-cache behaviour (and parameter-sensitive plans) becomes its own topic. - **The model is a simplification.** Cost formulas assume things — a fixed sequential-to-random I/O ratio, an assumed cache-hit fraction, independent predicates — that are approximations of a real machine. ## The nuance worth stating "Cost-based" does not mean rule-free. Every real optimizer still applies heuristic rewrites unconditionally when they are always-or-almost-always beneficial — pushing predicates below joins, eliminating provably empty branches, flattening simple subqueries — because costing them out would waste compile time. The accurate description is that modern optimizers are **cost-based with a heuristic rewrite layer**, and the cost model decides only where the answer genuinely depends on data.