Cost Estimation for Query Plans

A query execution plan is a tree of physical operators — table scans, index scans, joins, sorts — each with an implementation and an estimated cost, conventionally measured in disk block transfers (I/Os), sometimes augmented with CPU cost and communication cost in distributed settings. Because a single SQL query can be executed by exponentially many equivalent plans (different join orders, different access paths, different algorithms), the optimizer needs a cheap, purely analytical way to predict each plan's cost without executing it. That predictive machinery is cost estimation. Two quantities sit underneath every cost formula. Cardinality is the estimated number of tuples produced by an operator or sub-plan. Selectivity of a predicate P on a relation r is the estimated fraction of tuples in r satisfying P, so that the estimated cardinality of `σ_P(r)` is `selectivity(P) × |r|`. Selectivities compose: selection cost formulas convert them into output sizes, and join cardinality formulas extend them to two-relation and multi-relation predicates. All of this rests on catalog statistics — summary information about each relation and column that the database system maintains persistently and refreshes periodically (e.g., via `ANALYZE` or automatic statistics collection). The estimation problem is fundamentally about approximating an unknown joint distribution of data values using cheap-to-store summaries. Exact cardinality would require actually evaluating the query, which defeats the purpose; instead, systems use closed-form statistical models — uniform distribution within a domain, independence between predicates, containment of value sets across joining columns — that are wrong in detail but usually close enough in aggregate. Understanding exactly which assumptions are made, and where they break, is the core skill this article develops.

Step 1 — Catalog statistics

For each relation `r`, the system catalog typically stores:

• `n_r` — number of tuples in `r`.
• `b_r` — number of blocks containing tuples of `r`.
• `f_r` — blocking factor, tuples per block (`n_r ≈ b_r · f_r`).
• `V(A, r)` — the number of distinct values of attribute `A` in `r`.
• `min(A, r)`, `max(A, r)` — smallest/largest value of `A`.
• optionally, an equi-width or equi-depth histogram of `A`'s value distribution, and multi-column statistics for correlated attributes.

For each index, the catalog additionally stores the number of levels (height) of the index, the number of leaf blocks, and — for clustering indexes — enough information to estimate range-scan costs directly.

Step 2 — Selectivity of a single-table selection

Given predicate P on relation r, the standard formulas (assuming uniform distribution over `[min, max]`, and no histogram) are:

• Equality, `A = v`: selectivity ≈ `1 / V(A, r)`.
• Range, `A > v`: selectivity ≈ `(max(A,r) − v) / (max(A,r) − min(A,r))`, clipped to `[0, 1]`.
• Range, `A < v`: symmetric.
• Conjunction, `P1 ∧ P2`: selectivity ≈ `sel(P1) · sel(P2)` (independence assumption).
• Disjunction, `P1 ∨ P2`: selectivity ≈ `sel(P1) + sel(P2) − sel(P1)·sel(P2)` (inclusion–exclusion under independence).
• Negation, `¬P`: selectivity ≈ `1 − sel(P)`.

If a histogram is available for `A`, the estimator instead sums the fractions of buckets overlapped by the predicate's range, which is far more accurate when the distribution is skewed.

Step 3 — Join cardinality estimation

For a join `r ⋈ s` on attribute `A` (present in both relations), the classical formula uses the containment assumption: every value of `A` in the smaller-distinct-value relation appears in the larger one. Then: ``` |r ⋈ s| ≈ n_r · n_s / max(V(A, r), V(A, s)) ``` Reasoning: for each tuple in `r`, the expected number of matching tuples in `s` is `n_s / V(A, s)` (spreading `s`'s tuples uniformly over its distinct key values, assuming every value in `r` also occurs in `s`). Summing over all `n_r` tuples of `r` gives `n_r · n_s / V(A, s)`. Symmetric reasoning from `s`'s side gives `n_r · n_s / V(A, r)`; taking the max of the two `V` values in the denominator gives the more conservative (typically more accurate) estimate, since it corresponds to using the larger distinct-value count, which best approximates the "one matching group per join key" model when domains are not perfectly contained. For joins on multiple attributes or with additional local predicates, selectivities multiply under the independence assumption, exactly as with single-table conjunctions.

Step 4 — I/O cost of physical operators

Cost is normally reported in block transfers, `t_T` for average seek+transfer time. Representative formulas (`b_r` = blocks of `r`, `M` = memory buffer blocks available):

These formulas are developed in depth for join algorithms elsewhere; the essential point here is that every one of them takes an estimated cardinality or block count as input, so the accuracy of the whole cost model is bounded by the accuracy of the underlying cardinality estimates.

Step 5 — Combining costs bottom-up over a plan tree

``` function EstimateCost(node): if node is a LeafScan(relation r, access-path): node.cardinality = EstimateCardinality(r) # from catalog stats node.cost = ScanCost(access-path, r) # table/index scan formula return node.cost else if node is a Selection(P, child): childCost = EstimateCost(child) node.cardinality = child.cardinality * Selectivity(P) node.cost = childCost # selections are usually "free" if pipelined return node.cost else if node is a Join(algorithm, left, right): leftCost = EstimateCost(left) rightCost = EstimateCost(right) node.cardinality = JoinCardinality(left, right) # containment-assumption formula node.cost = leftCost + rightCost + JoinAlgoCost(algorithm, left, right) return node.cost else if node is a Sort(child) or Aggregate(child): childCost = EstimateCost(child) node.cardinality = child.cardinality # (or group count for aggregate) node.cost = childCost + SortCost(child.cardinality, child.tupleSize) return node.cost ``` The algorithm is a straightforward post-order tree traversal: each node's cost depends only on its children's already-computed costs and cardinalities, so a single bottom-up pass suffices, and the estimated cardinality of every intermediate result is threaded upward as input to the next operator's formula. ```pseudocode // Full pipeline: statistics -> selectivity -> cardinality -> plan cost procedure OptimizeCostOfPlan(planTree): for each node in PostOrder(planTree): // children before parents stats = LookupCatalogStats(node) // n_r, b_r, V(A,r), histograms sel = EstimateSelectivity(node.predicates, stats) node.card = ComputeCardinality(node, sel) node.cost = ComputeIOCost(node, stats) return planTree.root.cost, planTree.root.card ```

Time complexity of the estimation procedure itself. Given a fixed plan tree with `k` operators, computing all cardinalities and costs is a single post-order traversal, so it runs in `O(k)` time, assuming catalog lookups (`V(A,r)`, histogram bucket lookup) are `O(1)` or `O(log(#buckets))` via binary search. This is essentially free compared to executing the query — which is exactly the point: estimation must be cheap enough to run for every candidate plan the optimizer considers. The harder complexity issue is in the search that surrounds estimation (covered in Query Optimization Fundamentals): the number of join orders for `n` relations is `Ω(n!)` for left-deep trees and worse for bushy trees, so cost estimation must be called on the order of `O(2^n)` or more sub-plans if the optimizer enumerates all subsets (as in dynamic-programming join-order enumeration). Because a single estimation call is `O(k)`, the total optimization time is bounded by (number of sub-plans considered) × `O(k)`, which is why practical optimizers prune the search space (dynamic programming over subsets, or greedy/heuristic join ordering) rather than enumerating exhaustively.

Space. Catalog statistics use `O(1)` space per column for basic summaries (`n_r, V(A,r), min, max`) and `O(h)` space for a histogram with `h` buckets, independent of `n_r`. This is the essential tradeoff: statistics are a lossy compression of the true data distribution, sized so that maintaining and querying them costs far less than storing or scanning the actual table.

Correctness / accuracy argument. "Correctness" for a cost estimator is not a Boolean property but a statistical guarantee under stated assumptions: 1. Selection selectivity is exact if the underlying distribution really is uniform over `[min, max]`, and each value's frequency is close to `n_r / V(A,r)`. With an equi-depth histogram of `h` buckets, the error introduced by within-bucket uniformity is bounded by the maximum intra-bucket skew, which shrinks as `h` grows (at the cost of `O(h)` storage per column). 2. Join cardinality is exact only under the containment assumption — that the set of distinct values of the smaller-`V` relation is a subset of the other relation's values — and under the assumption that values are uniformly spread across matching groups. When both hold, the derivation in Step 3 is an exact expectation calculation, not a heuristic; the error comes entirely from violations of these assumptions (e.g., a foreign key that is genuinely a subset of the primary key satisfies containment exactly, which is why the formula is especially reliable for primary-key/foreign-key joins). 3. Independence of predicates is the weakest link: if two predicates are correlated (e.g., `city = 'NYC' AND zip = '10001'`), multiplying their selectivities drastically underestimates the true selectivity (the true selectivity of the conjunction can be as large as `min(sel(P1), sel(P2))`, not their product). This is the single largest source of real-world cardinality misestimation, and it motivates multi-column statistics and query-driven correlation statistics in modern systems. The honest tradeoff: exact cardinality requires executing the query; the formulas above trade exactness for tractability, and their error grows precisely in proportion to how much real data violates uniformity, containment, and independence.

Consider `Employees(emp_id, dept_id, salary)` and `Departments(dept_id, name)`, with the query: ```sql SELECT e.emp_id, d.name FROM Employees e, Departments d WHERE e.dept_id = d.dept_id AND d.name = 'Sales'; ``` Catalog statistics:

Step 1 — selectivity of `d.name = 'Sales'`: ``` sel = 1 / V(name, Departments) = 1/50 = 0.02 ```

Step 2 — cardinality after selection on Departments: ``` |σ_{name='Sales'}(Departments)| = 0.02 × 50 = 1 ``` (This makes sense: department names are presumably unique, so exactly one row matches.)

Step 3 — join cardinality, `Employees ⋈ σ(Departments)` on `dept_id`: Applying the join formula with `r = Employees`, `s = σ(Departments)` (now `n_s = 1`, but `V(dept_id, s)` is still bounded by 1 since only one department value survives): ``` |r ⋈ s| ≈ n_r · n_s / max(V(dept_id, r), V(dept_id, s)) = 100000 · 1 / max(50, 1) = 100000 / 50 = 2000 ``` This says: about 2,000 employees are expected to belong to the Sales department — exactly `n_r / V(dept_id, r)`, which is the correct expected group size if departments are roughly evenly sized. Note that plugging in the post-selection `V(dept_id, s) = 1` into the max would be wrong if used naively (it would suggest every employee matches); real optimizers track the selectivity-adjusted distinct-value count for `s`, effectively `V(dept_id, s) ≈ V(dept_id, Departments) × sel(name='Sales')`, rounded to at least 1, giving the same `max(50, 1) = 50` behavior. This subtlety — updating `V(A,·)` estimates for filtered sub-plans, not just raw base tables — is exactly the kind of detail that separates a naive optimizer from a careful one.

Step 4 — costs of two candidate plans: Plan A — Nested-loop join, Departments (filtered) as outer: ``` cost = b_Departments + |σ(Departments)| · b_Employees = 2 + 1 · 2000 = 2002 block transfers (plus the 2-block scan+filter of Departments) ``` Plan B — Nested-loop join, Employees as outer (no index, no filter pushed): ``` cost = b_Employees + n_Employees · b_Departments = 2000 + 100000 · 2 = 202,000 block transfers ``` The optimizer, using nothing more than the catalog statistics and the formulas above, correctly predicts that filtering `Departments` first and using it as the outer relation of a nested-loop join (Plan A) is roughly 100× cheaper than the naive ordering (Plan B) — precisely the kind of decision cost-based Join Algorithms: Nested-Loop optimization is built to make, and precisely why cardinality estimates must be computed for every intermediate result, not just base tables.

The formulas and system architecture described here trace back to the earliest cost-based relational optimizers, which first demonstrated that a small set of catalog statistics could drive automatic, correctness-preserving plan selection at scale.

Every general-purpose relational database — PostgreSQL, MySQL/InnoDB, Oracle, Microsoft SQL Server, IBM Db2 — runs a cost-based optimizer whose join-order and access-path decisions are driven directly by the selectivity and cardinality formulas described here. Data warehouse and analytics engines (Snowflake, BigQuery, Spark SQL, Presto/Trino) apply the same principles at larger scale, often adding sampling-based cardinality estimation and adaptive query execution to correct for estimation errors mid-query when actual row counts diverge sharply from predictions. Statistics collection commands (`ANALYZE` in PostgreSQL, `UPDATE STATISTICS` in SQL Server, automatic optimizer statistics gathering in Oracle) exist specifically to keep these catalog inputs fresh. Understanding this pipeline is the prerequisite for reasoning about Join Algorithms: Nested-Loop and other physical join implementations, and for the broader plan-search machinery covered under Query Optimization Fundamentals and The Query Optimizer, where these cost numbers are compared across thousands of candidate plans to choose the one actually executed.

Ask the tutor: How do dynamic-programming join-order enumeration algorithms use these cost estimates to search the plan space efficiently?