How a Query Cost Model Reduces I/O and CPU to One Number

A planner has to choose between access paths whose real costs depend on buffer pool contents, disk geometry, concurrent load, and the machine’s memory bandwidth. None of that is known when the plan is built, and measuring it would cost more than the query. So every mainstream optimizer replaces the question “how many milliseconds” with a proxy question: “how many abstract units”, where a unit is defined by a small table of constants. The constants are the entire physical model. Everything else in the optimizer is arithmetic over them.

The consequence is that a cost is only meaningful relative to another cost produced by the same constants. A plan reported at 4317.22 units is not four seconds, not four milliseconds, and not anything else until the constants are calibrated against a particular storage device. What the number does guarantee is a consistent ordering: if plan A costs less than plan B under the same constants, the optimizer believes A does less work. The whole design rests on that being usually true.

Costs are weighted units, and only ratios matter

PostgreSQL names five constants and gives them defaults that are meant to be read as a ratio. A sequential page fetch is 1.0 (seq_page_cost), a random page fetch is 4.0 (random_page_cost), a processed heap tuple is 0.01 (cpu_tuple_cost), a processed index entry is 0.005 (cpu_index_tuple_cost), and one evaluated operator or qual is 0.0025 (cpu_operator_cost). One cost unit therefore means roughly “one page read sequentially”, and the remaining constants are fractions of that.

The 4:1 ratio between random and sequential reads is the load-bearing assumption. On a rotating disk it reflects seek plus rotational latency against a streamed read that amortises the seek; on flash it overstates the penalty, because a random 8 KiB read costs far less than a seek. Deployments on solid-state storage routinely lower random_page_cost toward 1.0–2.0, and doing so changes which plans the optimizer prefers, most visibly by making index scans win at higher selectivity. That is not a tuning trick so much as a correction: the default encodes hardware from the era the constant was chosen.

Because only the ratios matter, scaling every constant by the same factor changes no plan choice at all. This is worth internalising before reading a plan’s cost number. Doubling all five constants doubles every cost and leaves the ordering identical; the optimizer’s decisions are invariant under that transformation. What is not invariant is any comparison against a constant the user wrote by hand, or against a cost threshold baked into an extension.

MySQL separates the same idea into two tables. Server-level constants cover the CPU work of evaluating a row and creating a temporary table, and engine-level constants cover the I/O of reading a block from a particular storage engine. The split exists because the cost of a page depends on the engine: a page in a memory-resident engine and a page on a remote block device are not the same object, and a single global constant would misprice one of them. Both tables are adjustable at runtime, which is how a vendor-supplied default is reconciled with actual hardware.

Startup cost, total cost, and the LIMIT rewrite

A plan is not scored with one number but with a pair: the cost before the first row can be returned, and the cost of returning all rows. EXPLAIN prints them as startup cost..total cost. The pair exists because a query with a small LIMIT does not pay the full total, and a plan that produces its first row cheaply can beat a plan with a lower total.

A sort makes the distinction concrete. Sorting an input of n rows has a startup cost close to the cost of consuming all n rows, because nothing can be emitted until the last row arrives. An index scan that returns rows already in the requested order has a startup cost near zero for the same query, since the first row is available after a single descent. With ORDER BY ... LIMIT 10, the planner compares the index scan’s startup plus the cost of ten rows against the sort plan’s near-total startup, and the index scan usually wins by a wide margin even when its total cost is much higher. Remove the LIMIT and the same comparison reverses.

The same asymmetry appears in nested loop joins, which have low startup and poor total cost, against hash joins, which must build their hash table before emitting anything. A query that fetches a few rows from a large join is often best served by the algorithm with the worst throughput, because the metric being minimised is time to the tenth row, not time to the last.

The arithmetic for a scan and an index probe

The formulas are short enough to write out. A sequential scan reads every page of the relation and evaluates the predicate against every tuple. An index scan reads the index, then fetches matching heap tuples, and the heap fetches are priced as random reads unless the planner knows the rows are physically clustered.

SEQ_PAGE, RAND_PAGE = 1.0, 4.0
CPU_TUPLE, CPU_INDEX_TUPLE, CPU_OP = 0.01, 0.005, 0.0025

def seq_scan_cost(pages, tuples, quals=1):
    return (pages * SEQ_PAGE
            + tuples * CPU_TUPLE
            + tuples * quals * CPU_OP)

def index_scan_cost(index_pages, index_tuples, heap_pages, heap_tuples, quals=1):
    # Heap pages are priced as random; a correlated layout would let the
    # planner treat most of them as sequentially read instead.
    return (index_pages * RAND_PAGE
            + index_tuples * CPU_INDEX_TUPLE
            + heap_pages * RAND_PAGE
            + heap_tuples * CPU_TUPLE
            + index_tuples * quals * CPU_OP)

Feed those functions a million-row table of 10,000 pages, a predicate with one qual, and a selectivity of 0.01 percent, which selects 100 rows. The sequential scan costs 10,000 page units plus 10,000 tuple units plus 2,500 operator units, about 22,500. The index scan touches a few index pages, 100 index entries, and roughly 100 heap pages: about 12 units of index I/O, 400 units of heap I/O, and less than two units of CPU, so around 414. The index wins by a factor near fifty.

Raise the selectivity to 10 percent and the picture reverses. A hundred thousand matching rows spread across 10,000 pages touch essentially every page of the table, and at four units each the heap term alone reaches 40,000, before the index entries and CPU work are counted. The index path now costs around 42,000 against the unchanged 22,500 of the sequential scan, so it loses by a factor near two rather than winning by fifty. Solving the two cost expressions for equality puts the crossover at roughly half a percent selectivity for this table, and the exact position depends on how many distinct pages the matching rows actually occupy. That crossover is the subject of the index-versus-sequential-scan boundary, and the shape of the curve explains why a plan can flip after a statistics refresh that changes an estimate by a few percent.

Where the estimate enters the sum

Notice that the formulas take tuples and index_tuples as inputs, not as facts. The planner does not know how many rows a predicate will match; it multiplies the relation’s row count by an estimated selectivity. That estimate is the single largest source of error in the whole calculation, because cost is linear in it. A selectivity that is ten times too high produces a cost ten times too high for that path, and if the competing path is within a factor of ten, the optimizer picks the wrong one.

This is why cardinality estimation, not the cost constants, dominates optimizer quality in practice. The constants can be calibrated once per storage device and left alone; the estimates change with every query and every data distribution. The machinery that produces them is covered in selectivity estimation from histograms and, for multi-table predicates, in join cardinality and the containment assumption.

What the model leaves out on purpose

The most important thing about a cost model is what it does not represent. There is no term for buffer cache residency: a scan of a table that is entirely in memory is priced as if every page came from disk. There is no term for concurrency, so two plans that behave very differently when sixteen sessions run them simultaneously are ranked as if each ran alone. There is no model of prefetch depth, of write-back cost, or of the difference between reading a page from the OS page cache and from a device queue.

These omissions are deliberate, because including them would require knowledge the planner cannot have at planning time. The buffer pool contents depend on what other sessions have read; the load depends on what they are doing. A model that guessed would add variance without adding accuracy, and a plan that is optimal for a warm cache and wrong for a cold one is worse than a plan that is mediocre for both.

Two practical consequences follow. First, cost differences below roughly ten percent are noise: they are smaller than the error in the underlying estimates, so treating a 2 percent cost gap as meaningful is reading precision that is not there. Second, when a plan is clearly wrong, the constants are rarely the culprit. The estimate feeding them usually is, and the first diagnostic step is to compare the planner’s estimated row count against the actual count at each node, which is what EXPLAIN ANALYZE prints side by side.