Cost-Based Optimization

Three words that the rest of the lesson depends on. Cardinality of a column is its number of distinct values — 2 for a boolean, 900 for a primary key over 900 rows. Selectivity of a predicate is the fraction of rows it keeps — 0.5 for is_staff = true on a 50/50 column, 1/900 for id = 42. Statistics are the stored summaries from which selectivity is estimated without reading the table: row count, page count, per-column n_distinct, null fraction, most-common values with frequencies, and a histogram of the remaining values.

For an equality predicate the estimate is a lookup or a division. If the value is in the MCV list, its stored frequency is the selectivity — exact, up to sampling. If not, the planner spreads the leftover probability mass evenly over the values it has not seen individually: (1 − Σ mcv_freq) / (n_distinct − n_mcv). For a range predicate the histogram gives the answer: price < 250 with bounds [1, 38, 79, 121, 163, 204, 241, 283, …] covers six full buckets plus (250−241)/(283−241) of the seventh, out of ten — about 0.62.

Cost is measured in abstract units, and the constants are the whole model. seq_page_cost = 1.0 is the unit: one page read as part of a sequential sweep. random_page_cost = 4.0: one page fetched out of order — four times worse, the ratio of a disk seek to a streaming read. cpu_tuple_cost = 0.01: handling one row. cpu_index_tuple_cost = 0.005: visiting one index entry. cpu_operator_cost = 0.0025: evaluating one operator or function. This platform’s plan.ts uses exactly these values, which is why its EXPLAIN numbers look like PostgreSQL’s.

A sequential scan costs pages × 1.0 + rows × 0.01. An index scan costs height × 4.0 to descend, plus per matching row 0.005 for the index entry and a random heap page (4.0, discounted for rows that share a page — this engine uses 0.6) and 0.01 to handle the row. Both are linear in their input; the slopes differ by a factor of roughly 240 per row, and that is the whole reason a low-selectivity index loses.

The constants are hardware assumptions. On an SSD, or when the working set is cached, a random page is no slower than a sequential one and DBAs set random_page_cost = 1.1; the effect is that index scans win over a wider range of selectivities. The interactive on the previous lesson models a warm cache exactly this way.

Yes — often, and the arithmetic says exactly when. Take a 1,000,000-row table with 64-byte rows: 7,813 pages. The sequential scan costs 7,813 × 1.0 + 1,000,000 × 0.01 = 17,813. The index scan costs 3 × 4.0 for the descent plus 2.415 per matching row. Set them equal: 12 + 2.415 × m = 17,813 gives m ≈ 7,370 rows — 0.74% of the table. Below that, the index wins; above it, following the index means more random page reads than simply reading every page in order. WHERE status = 'paid' at 62% selectivity would cost 12 + 620,000 × 2.415 ≈ 1.5 million through the index against 17,813 for the scan: the index is 84× worse.

The break-even moves with row width (wider rows → more pages → the scan costs more → the index wins for longer), with random_page_cost (cached data → 1.0 → break-even around 3%), and with correlation — if the matching rows sit next to each other on disk (a timestamp column in insertion order), the heap reads are nearly sequential and the index wins far above 1%. The rule of thumb "an index pays off below 5–20%" is this calculation with typical inputs.

The model is arithmetic on stored numbers, and the numbers age. Suppose the marketplace orders table was analysed when it had 49 merchants; it has since grown to 400 and a million rows, and autovacuum has not caught up. The planner estimates merchant_id = 137 at (1 − 0.027) / (49 − 10) = 2.5% — 25,000 rows — when the truth is 2,500. On a 400-byte row (48,829 pages, break-even 24,355 rows) that ten-fold error crosses the line: the planner chooses a sequential scan of 48,829 pages for a predicate an index would answer in about 6,000 cost units. Nothing errors. The query is simply eight times slower than it needs to be, on every execution, until ANALYZE orders runs.

This is the failure in the challenge Query Optimization: Finding the Actual Bottleneck describes as stale statistics, and it has one signature in EXPLAIN ANALYZE: rows=25000 estimated next to rows=2500 actual. The other classic cause of the same signature is correlated columns — WHERE city = 'Berlin' AND country = 'DE' is estimated as the product of two selectivities as if they were independent, undercounting by however correlated they are; CREATE STATISTICS on the column pair fixes that one.

Cost is not only pages and rows; some operators need memory proportional to their input, and the planner models what happens when they do not get it. work_mem (4 MB by default in PostgreSQL, per operator, per query) bounds the build side of a hash join, the hash table of a HashAggregate, and the buffer of a Sort. A hash join whose build side fits is one pass over each input. One that does not is split into batches: both inputs are partitioned by hash into files on disk, then each batch is joined in memory — the inputs are written once and read once more, and the cost model adds that I/O. A sort that fits is in-memory quicksort; one that does not is an external merge sort, Sort Method: external merge Disk: 84,000kB in the plan.

Because the planner models the spill, raising work_mem can change the plan, not just the speed: a hash join that would have batched becomes cheaper than the merge join it lost to, and the plan flips. It also means the join-order search — dynamic programming over subsets of tables up to geqo_threshold, genetic search beyond — is comparing numbers that depend on a configuration knob. The optimizer is deterministic; its inputs are not.