Query Optimization & Execution Plans (EXPLAIN ANALYZE)

Relational databases use a Cost-Based Optimizer (CBO) to determine the physical execution plan for every SQL query. Unlike procedural code where you write explicit loops, declarative SQL specifies what data you want, leaving how to retrieve it to the CBO.

The optimizer calculates arbitrary cost units (where 1.0 unit = 1 sequential 8KB page read from disk):

Total Cost = (Disk Page Reads × Page Cost) + (Rows Processed × CPU Tuple Cost) + (Operator Cost)

How Statistics Guide the CBO: The database maintains statistical histograms in its system catalog (e.g., pg_statistic in PostgreSQL, mysql.innodb_table_stats):

• Number of distinct values (n_distinct): Measures column cardinality.
• Most Common Values (MCVs): Tracks frequency distribution of popular values.
• Null Fraction: Percentage of rows containing NULL.

If statistics become stale (e.g., after loading 10M rows without running ANALYZE), the CBO makes catastrophic routing errors (e.g., choosing a Sequential Scan on 10 million rows instead of an Index Scan).