Query Planner & Cost Estimation

When you write SELECT * FROM users WHERE id = 42, you don't tell the database HOW to execute it. The query planner transforms the SQL into a tree of physical operators (scans, filters, joins) and picks the cheapest one. This is the most consequential piece of database engineering: a bad plan turns milliseconds into hours.

Logical Plan vs Physical Plan

After parsing, the optimizer has a logical plan — a tree of relational operators (scan, filter, project, join). It then transforms it into a physical plan by choosing implementations for each operator:

• Scan(users) could be SeqScan or IndexScan(idx_id)
• Filter(id = 42) could be pushed into the scan
• Join(a, b) could be NestedLoop, HashJoin, or MergeJoin

Each physical operator has a cost model. Cost is usually estimated as page reads + CPU per row + some I/O constants.

A Simple Cost Model

For our planner we'll use a deliberately simplified model:

For 1,000,000 rows: SeqScan costs 1,000,000 but IndexScan costs only 3 + 20 = 23. That's a 43,000× speedup just from picking the right plan.

Selectivity & Statistics

Real optimizers maintain statistics per column:

• n_distinct — number of distinct values
• histogram — value distribution (e.g., 100 equi-height buckets)
• most_common_values — top-N values and their frequencies
• correlation — physical row order vs sorted order

Selectivity for col = c is estimated as 1 / n_distinct for uniform data, or looked up in the MCV list for skewed data. Multiplying selectivities gives the estimated output rowcount for compound predicates (a notoriously imperfect assumption — Postgres uses correlated statistics to handle column dependencies).

Picking the Access Path

When WHERE a = 1 AND b = 2 has indexes on both a and b, the planner:

1. Estimates selectivity of each predicate.
2. Picks the most selective as the leading access path (the index probe).
3. Applies the others as residual filters on the fetched rows.

For very high selectivity (single matching row), the savings dwarf the residual cost. Postgres' EXPLAIN exposes this choice — read it on every slow query.

Stale Statistics: The DBA Boogeyman

If statistics lag reality (you bulk-loaded a million rows since the last ANALYZE), the planner thinks the table is small and picks a NestedLoop where a HashJoin would win — turning seconds into minutes. pg_stat_user_tables.last_analyze is the first column to check when a query suddenly regresses.