Query Planner & Cost Estimation

Query Planner & Cost Estimation

So far your planner has used fixed rules: "if there's an index, use it." Real query planners go further — they assign a numeric cost to every candidate plan and pick the cheapest one. This lesson has you build that cost model directly, turning planning from a rule lookup into an optimization problem.

Why cost, not just "has an index"

An index isn't automatically the right choice. If a table has only 10 rows, a sequential scan touching all 10 can be cheaper than the overhead of a B-tree seek. Cost-based planning captures this by expressing every access path in comparable units:

SeqScan(t)               cost = rowcount(t)
IndexScan(t, idx_col)    cost = 3 + ceil(log2(rowcount(t)))

SeqScan cost scales linearly with table size — bigger table, proportionally more work. IndexScan cost grows only logarithmically (the depth of a B-tree), plus a small constant (root-to-leaf traversal overhead, e.g. fixed I/O cost). For a large table, 3 + log2(n) is dramatically smaller than n; for a tiny table they can be close or even inverted, which is exactly the nuance a rule-based planner ("always use the index if one exists") misses.

Combining access cost with residual filtering

When a query has two predicates and only one is indexed, the other predicate still needs to be checked on every row the index scan returns — that's not free:

Residual filter   adds rowcount * 0.001 per filtered predicate

So a plan like IndexScan(t, idx_name) Filter(age>20) has total cost = index-scan cost + (rowcount × 0.001) — a small but non-zero penalty representing the CPU cost of evaluating the residual condition on every candidate row. This is the same access/residual split from the previous lesson, just now with a number attached to each side so plans become comparable.

Choosing between candidate plans

With two predicates where both columns are indexed, you now have a real decision to make instead of an arbitrary tie-break: compute the IndexScan cost for each candidate column, and pick whichever is cheaper as the leading access path, applying the other predicate as a residual filter:

Since both candidate IndexScan costs depend only on rowcount(t) (not on which column), they'll actually tie here — but this is the general shape cost-based selection takes once you introduce per-column selectivity estimates (a natural next step beyond this lesson: not all columns narrow the result set equally, e.g. an index on country filters much less than one on email).

Formatting costs

The spec asks you to print an integer when the cost is a whole number, and two decimal places otherwise:

This matters because IndexScan costs are always integers (from ceil), but adding a residual-filter penalty (rowcount * 0.001) almost always produces a non-integer total.

Edge cases to watch

• rowcount = 0 or 1 — log2(0) is undefined, so guard with max(rowcount, 1) before taking the log.
• A predicate on a column with no matching STATS/INDEX declaration at all should be treated as unindexed, not crash.
• Two predicates, neither indexed — total cost is just the seq scan cost; don't add residual-filter penalties on top of a plan that's already a full scan of both predicates (the residual formula applies specifically to extra filtering layered on top of an index access, per the spec).
• Keep the plan string format (spacing, COST= placement) exactly as specified — each plan line is compared against the expected text, so a stray space inside a line fails the test. (Whitespace at the very end of your output is the one thing the comparator forgives.)

This is a compact but faithful model of what Postgres's planner does at a much larger scale: enumerate candidate physical plans, cost each one using table/column statistics, and pick the minimum-cost plan — the foundation of every real SQL optimizer.