Selectivity, Cost and Choosing a Scan

Why this stage exists

Every plan so far was chosen by rule: if an index can serve the WHERE, use it. Here is a table where that rule is a disaster. A thousand rows, a column v with two values, 'a' and 'b', and an index on v:

select count(pad) from w where v = 'a';

The index finds 500 entries, and each one costs a descent of the table: hundreds of page reads, many of the same pages again and again. A full scan reads each of the table's pages once. The rule picked the slow plan, and it will keep picking it.

A cost-based optimizer asks two questions instead: how many rows will each plan touch, and what will that cost. The statistics of the previous stage answer the first; a few integer formulas answer the second.

How many rows: selectivity

The selectivity of a predicate is the fraction of rows it keeps. With statistics it is a guess, but a good one:

Multiplying assumes the two predicates are independent: that knowing a person's city tells you nothing about their age. Real data breaks that all the time (city and postcode, make and model), and real optimizers misestimate because of it. It is still what almost every optimizer does by default, because anything better needs statistics on column pairs.

What it costs: page reads

Di and Dt are the depths of the index and the table, P and R the table's pages and rows, E the estimated rows. With them the two-value table is no contest:

Change the query to select count(v) and the index covers it. Now the index-only cost is about 2 + 5, far below 110, and the index wins again. Covering is not a detail: it moves the tipping point by a factor of a hundred.

On a tiny table the opposite surprise happens. Four rows in one leaf: a full scan costs 1, any index costs at least 2. So where name = 'bob' is a SeqScan even with an index on name, and that is right.

Stale statistics are believed

ANALYZE runs only when asked, so the planner may be working from an old picture. Take 1000 distinct values, ANALYZE, then update t set v = 'x'. The statistics still say one row in a thousand has any given value, so where v = 'x' is estimated at 1 row and planned as an IndexScan. It finds 1000, with 1000 table descents. Nothing is wrong with the planner; its information is. ANALYZE again and the same query becomes a full scan. The next stage, EXPLAIN ANALYZE, puts the estimate and the truth side by side so you can see this happen.

No statistics, no change

A table that has never been analysed is planned exactly as before, by the rules, and explain prints no estimates. That keeps every earlier stage's plans as they were, and makes the cost model something you turn on, table by table, by running ANALYZE.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, section 60.

There is no new syntax and no new code.

What you should see when done

$droid --db cost.db
Welcome to droid!
>create table s (id int, name varchar(10), n int);
Create table statement executed successfully
>create index sn on s (name);
Create index statement executed successfully
>insert into s (id, name, n) values (1, 'ada', 1);
Insert statement executed successfully (1 rows)
>insert into s (id, name, n) values (2, 'bob', 2);
Insert statement executed successfully (1 rows)
>explain select * from s where name = 'bob';
[PLAN] select * from s where name = 'bob'
[PLAN]   └── IndexScan (table=s, index=sn, key='bob')
>analyze s;
Analyze statement executed successfully
>explain select * from s where name = 'bob';
[PLAN] select * from s where name = 'bob'
[PLAN]   └── Filter (name = 'bob') (rows=1 cost=1)
[PLAN]       └── SeqScan (table=s) (rows=2 cost=1)
>.exit
exiting.. good bye!

Before ANALYZE the rule uses the index; after it, the planner knows the table is one page and reads it whole.

Common bugs in this stage

• Rounding each factor. 5/100 × 1/10 × 1000 is 5; rounding 5/100 × 1000 to 50 first and then 50 × 1/10 happens to agree, but other inputs do not. Multiply exact fractions and round down once.
• Floating point. Two languages can print different estimates from the same doubles. Use integers or exact fractions.
• Forgetting the table descent per row. Without E × Dt an index always looks cheaper than a scan, and the stage teaches nothing.
• Choosing by cost on a table without statistics. The earlier stages' plans must not change.
• Clamping too late. age < 500 over ages 0–99 is a selectivity of 1, not 5.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C: keep a fraction as two uint64_t (numerator and denominator); a few conjuncts over a thousand rows stay far from overflow.
• C++: the same pair, or std::ratio-like helpers; avoid double.
• Rust: a small struct Frac { num: u128, den: u128 } with Mul keeps the code readable.
• Zig: u128 numerators and denominators, multiplied with std.math.mul to catch overflow in debug builds.