Cost-Based Optimization

Jr Codex DBMS Notes

Level: Advanced Prerequisites: Chapter 2: Join Algorithms Time to complete: ~20 minutes

Table of Contents

1. What the Optimiser Is Doing
2. The Cost Model
3. Statistics
4. Cardinality Estimation
5. Where Estimates Go Wrong
6. Helping the Optimiser
7. Summary & Next Steps

1. What the Optimiser Is Doing

The Search
─────────────────────────────────────────
  1. ENUMERATE plans that are all provably
     equivalent (Module 2, Chapter 3's algebraic
     laws guarantee this)

  2. ESTIMATE the cost of each

  3. PICK the cheapest

  Step 1 is safe — every candidate returns the same
  answer.

  Step 2 is where everything can go wrong, because
  it is a PREDICTION about data the optimiser has
  only summarised.
─────────────────────────────────────────

The Single Most Useful Sentence in This Module
─────────────────────────────────────────
  A bad plan is almost never a bad COST MODEL. It
  is almost always a bad ROW COUNT ESTIMATE.

  Get the estimate right and the right plan follows
  automatically.

  So debugging a slow query means finding the first
  operator where estimated rows and actual rows
  diverge — which is exactly what Chapter 4 teaches.
─────────────────────────────────────────

2. The Cost Model

The Components
─────────────────────────────────────────
  Cost is an abstract number, not milliseconds.
  PostgreSQL's units, relative to one sequential
  page read = 1.0:

    seq_page_cost         1.0    sequential read
    random_page_cost      4.0    random read
    cpu_tuple_cost        0.01   process one row
    cpu_index_tuple_cost  0.005  process index entry
    cpu_operator_cost     0.0025 one operator/function
─────────────────────────────────────────

# A simplified sequential scan cost.
def seq_scan_cost(pages, rows, seq_page_cost=1.0, cpu_tuple_cost=0.01):
    return pages * seq_page_cost + rows * cpu_tuple_cost
 
# A simplified index scan cost — note the RANDOM page cost per matching row.
def index_scan_cost(matching_rows, index_height, random_page_cost=4.0,
                    cpu_index_tuple_cost=0.005):
    index_reads = index_height + matching_rows * cpu_index_tuple_cost
    heap_reads  = matching_rows * random_page_cost        # ← usually dominates
    return index_reads + heap_reads
 
print(seq_scan_cost(pages=12_346, rows=1_000_000))          # ~22,346
print(index_scan_cost(matching_rows=100,    index_height=3))  # ~403   ← index wins
print(index_scan_cost(matching_rows=200_000, index_height=3)) # ~801,003 ← scan wins

The Crossover, Visible
─────────────────────────────────────────
  100 matching rows      ──► index scan, easily
  200,000 matching rows  ──► sequential scan, by a
                             wide margin

  This is Module 5, Chapter 4's selectivity
  argument, expressed as arithmetic. The optimiser
  is not ignoring your index; it computed that
  using it would be 35x slower.

  NOTE: random_page_cost=4.0 assumes spinning
  disks. On SSDs, 1.1-2.0 is more realistic, and
  setting it correctly makes the optimiser
  willing to use indexes more often.
─────────────────────────────────────────

3. Statistics

The optimiser cannot read the data, so it reads a summary of it.

What Is Collected, Per Column
─────────────────────────────────────────
  n_distinct          how many distinct values
  null_frac           fraction that are NULL
  most_common_vals    the top N values...
  most_common_freqs   ...and their frequencies
  histogram_bounds    boundaries dividing the rest
                      into equal-count buckets
  correlation         how well physical order
                      matches logical order
                      (decides whether an index
                       scan is sequential-ish)
─────────────────────────────────────────

ANALYZE students;                 -- refresh statistics
 
SELECT attname, n_distinct, null_frac, most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'students';

Statistics Are a SAMPLE, and They Go Stale
─────────────────────────────────────────
  They are gathered from a sample of rows
  (default_statistics_target, default 100 buckets),
  not a full read.

  And they are only refreshed by ANALYZE — run
  automatically by autovacuum, but on a delay.

  So a table that has just been bulk-loaded, or has
  changed shape rapidly, may be planned using
  statistics describing a table that no longer
  exists.

  This is the most common cause of a query that was
  fast yesterday and slow today with no code
  change.
─────────────────────────────────────────

4. Cardinality Estimation

Estimating how many rows each operator will produce.

The Basic Formulas
─────────────────────────────────────────
  EQUALITY on a column with d distinct values:
      rows ≈ N / d
      (or the exact frequency, if the value is in
       most_common_vals)

  RANGE:
      rows ≈ N × (fraction of the histogram
                  covered by the range)

  AND of two conditions:
      rows ≈ N × sel(a) × sel(b)
      ── assumes INDEPENDENCE

  JOIN on a key:
      rows ≈ (N_a × N_b) / max(d_a, d_b)
─────────────────────────────────────────

def estimate_and(n_rows, sel_a, sel_b):
    """The independence assumption — correct only when the columns are unrelated."""
    return n_rows * sel_a * sel_b
 
# city='Mumbai' is 10% of rows; pincode='400001' is 0.1% of rows.
print(estimate_and(1_000_000, 0.10, 0.001))     # estimates 100 rows
 
# But every '400001' pincode IS in Mumbai. The conditions are perfectly correlated,
# so the ACTUAL answer is 1,000 rows — a 10x under-estimate.

5. Where Estimates Go Wrong

The Five Failure Modes
─────────────────────────────────────────
  1. CORRELATED COLUMNS
     city and pincode, brand and model, country and
     currency. The independence assumption
     multiplies selectivities that should not be
     multiplied ──► severe UNDER-estimates.

  2. STALE STATISTICS
     Planned against a table that no longer looks
     like that.

  3. SKEWED DATA BEYOND most_common_vals
     A value that is 40% of the table but not in
     the top-N list is estimated as average.

  4. EXPRESSIONS AND FUNCTIONS
     WHERE LOWER(city) = 'pune' — there are no
     statistics on LOWER(city), so the optimiser
     falls back to a fixed guess (often 0.5%).

  5. MULTI-LEVEL JOINS
     Each join's estimate feeds the next. A 10x
     error at the first join becomes a 10x error in
     everything above it — errors COMPOUND upward.
─────────────────────────────────────────

Why Under-Estimates Are Worse Than Over
─────────────────────────────────────────
  UNDER-estimating rows leads the optimiser to
  choose plans that are good for small inputs and
  catastrophic for large ones:

    - nested loop instead of hash join
    - an in-memory sort that then spills
    - an index scan doing millions of random reads

  OVER-estimating leads to a sequential scan where
  an index would have been better — slower, but
  linearly so.

  This asymmetry is why correlated columns
  (failure 1) cause such dramatic blow-ups.
─────────────────────────────────────────

6. Helping the Optimiser

-- 1. KEEP STATISTICS FRESH. First thing to try, always.
ANALYZE orders;
 
-- 2. MORE DETAIL on a skewed or important column.
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 1000;   -- default 100
ANALYZE orders;
 
-- 3. EXTENDED STATISTICS for correlated columns — fixes failure mode 1 directly.
CREATE STATISTICS stats_city_pin (dependencies, ndistinct)
    ON city, pincode FROM addresses;
ANALYZE addresses;
 
-- 4. INDEX THE EXPRESSION so statistics exist for it (Module 5, Chapter 3).
CREATE INDEX idx_lower_city ON students (LOWER(city));
ANALYZE students;
 
-- 5. TUNE THE COST MODEL for your hardware.
SET random_page_cost = 1.1;              -- SSDs, not spinning disks
SET work_mem = '64MB';                   -- fewer spills (Chapter 1)

Extended Statistics Deserve Emphasis
─────────────────────────────────────────
  CREATE STATISTICS is under-used and fixes the
  single worst estimation failure.

  It tells the optimiser that city and pincode are
  dependent, so it stops multiplying their
  selectivities as though they were independent.

  If you have a query with a wildly wrong row
  estimate on two related columns, this is the fix
  — not a hint, not a rewrite.
─────────────────────────────────────────

On Query Hints
─────────────────────────────────────────
  Some databases let you force a plan (index hints,
  join hints). PostgreSQL deliberately does not.

  A hint freezes today's decision forever. When the
  data grows tenfold, the forced plan is still
  forced — and now wrong, with nothing to
  re-evaluate it.

  Prefer fixing the ESTIMATE. That way the
  optimiser keeps adapting as the data changes,
  which was the point of a declarative language
  (Module 1).
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

• The optimiser enumerates provably equivalent plans and picks the cheapest estimated one; the plans are always correct, but the estimates may not be.
• A bad plan is almost always a bad row-count estimate rather than a bad cost model, so fixing the estimate fixes the plan.
• The independence assumption multiplies selectivities of correlated columns, producing severe under-estimates — and under-estimates cause catastrophic plan choices rather than merely slow ones.
• Fix estimates with fresh statistics, higher statistics targets, extended statistics on correlated columns, and expression indexes — not with hints, which freeze a decision that should keep adapting.

Concept Check

1. Why does the optimiser sometimes ignore an index, and why is that usually correct?
2. Explain why city = 'Mumbai' AND pincode = '400001' is under-estimated, and name the fix.
3. Why are under-estimates more dangerous than over-estimates?

Next Chapter

→ Chapter 4: Reading and Fixing Query Plans

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index