The Query Planner: Choosing by Cost

The previous lessons chose plans with fixed rules: "if the column has an index, use it". That works until it doesn't. On a table with one row, walking an index is more work than simply reading the row. With three predicates and two indexes, which index is better? A cost-based planner stops guessing: it estimates what each possible plan would cost, and runs the cheapest.

Statistics and cost

An estimate needs numbers about the data. A database keeps statistics per table (here just the row count n, set with STATS) and compares plans in some unit of work. This lesson uses a small model:

The 3 + ceil(log2 n) is the descent through a balanced index: about log2 n comparisons to find the entry plus a few steps to fetch the row. The 0.001 * n term is a small charge for re-checking each leftover predicate. A SeqScan evaluates the predicates while it reads, so its cost is just n.

Costs are fractional, so to keep the arithmetic exact the program counts in thousandths: a SeqScan costs n * 1000, an IndexScan (3 + ceil_log2(n)) * 1000 + n for each leftover predicate. ceil_log2(n) is the smallest k with 2^k >= n (0 for n of 0 or 1). A cost is printed as a plain integer when it is whole, otherwise with two decimals, rounded half up: 14024 thousandths prints 14.02, 11256 prints 11.26, 13000 prints 13.

Choosing

A query is SELECT * FROM t followed by an optional WHERE col = value AND col = value .... Candidates:

1. the SeqScan (always possible);
2. one IndexScan for every predicate whose column has an index (INDEX t col), driving by that predicate and filtering with the others.

Pick the cheapest. A tie goes to the SeqScan (the simpler plan), and among IndexScans to the leftmost predicate. Worked examples:

STATS t 1024, index on uid:   uid = 7 AND status = 'paid'
  SeqScan   1024
  IndexScan 3 + 10 + 0.001 * 1024 = 14.024   -> IndexScan(t, idx_uid) Filter(status='paid')  COST=14.02

STATS small 1, index on id:   id = 0
  SeqScan   1
  IndexScan 3 + 0 = 3                        -> SeqScan(small) Filter(id=0)  COST=1

The second plan is the interesting one. An index is not magic; below a handful of rows reading everything is cheaper, and a rule-based planner that always takes the index gets it wrong. At n = 6 both plans cost 6 and the tie goes to the SeqScan; at n = 7 the index wins.

The plan text is SeqScan(t) or IndexScan(t, idx_<column>), then Filter(...) with the predicates the plan does not use, in query order and joined by AND, then two spaces and COST=<cost>.

A simplification to be aware of

Real planners also estimate how many rows each predicate matches (its selectivity) and cost the scan of those rows. This model charges only the leftover predicates a flat amount and ignores selectivity, so it cannot tell a column with 2 distinct values from a unique one. Statistics about value distributions are the next step in a real system; the structure (generate candidates, cost them, pick the minimum) stays the same.

The commands

STATS <table> <rowcount> (up to 9 digits) and INDEX <table> <column> print OK. QUERY <sql> prints the plan line. SQL words are case-insensitive; table and column names are not. Values are integers (optionally negative) or 'quoted text' (no quote inside), printed back as written. Anything else is ERR unsupported query, and a table without statistics is ERR no statistics for table: <name>.

What you build

The starter parses the commands and prints plans. You write:

• ceil_log2,
• choose_plan: cost the candidates and pick one,
• format_cost.

Common mistakes

• Floating point. Costs like 14.024 rounded through floats differ between languages and runs; thousandths in integers are exact.
• Taking the index whenever one exists, instead of comparing its cost with the SeqScan.
• Letting an equal cost pick the index, or the rightmost of two equal indexes.
• Rounding down (or to even) in format_cost.

Your exercise

You implement ceil_log2, choose_plan and format_cost. The mistake to avoid: preferring the index even when the table is so small that scanning is cheaper.