06. Query Planning & Cost Modeling¶

The PostgreSQL query optimizer is a cost-based optimizer (CBO). It explores the combinatorial space of join orders and scan methods to construct an execution plan that minimizes estimated disk and CPU work.

1. The Query Processing Pipeline¶

graph LR
    SQL["Raw SQL String"] --> Parser["Parser (Grammar / AST)"]
    Parser --> Analyzer["Analyzer (Catalog Resolution)"]
    Analyzer --> Rewriter["Rewriter (Views / Rules)"]
    Rewriter --> Planner["Cost-Based Planner"]
    Planner --> PlanTree["Execution Plan Tree"]
    PlanTree --> Executor["Volcano Executor"]
    Executor --> Result["Tuple Stream (Client)"]

Parser (parser/): Converts SQL text into a parse tree using Flex/Bison. Checks syntax only; table names and columns are unresolved symbols.
Analyzer (parse_analyze()): Resolves tables, columns, and data types against system catalogs (pg_class, pg_attribute). Produces a semantically validated Query tree.
Rewriter (rewriteHandler.c): Expands database views, handles table inheritance, and applies PostgreSQL RULE macros.
Planner (optimizer/): Converts the logical Query into a physical execution tree (PlannedStmt). Evaluates cost equations across possible access paths.
Executor (executor/): Executes the plan tree using the Volcano Iterator Model.

2. Cost Model Equations¶

Cost in PostgreSQL is an abstract unit where 1.0 cost = one sequential disk page read (seq_page_cost = 1.0).

\[\text{Total Estimated Cost} = \text{I/O Cost} + \text{CPU Cost}\]

Fundamental Cost Variables¶

seq_page_cost = 1.0: Cost to read an 8KB page sequentially from disk.
random_page_cost = 4.0 (HDD default, tune to 1.1 for NVMe SSDs!): Cost to read an 8KB page non-sequentially.
cpu_tuple_cost = 0.01: Cost for CPU to process one tuple header.
cpu_index_tuple_cost = 0.005: Cost for CPU to inspect one index entry.
cpu_operator_cost = 0.0025: Cost to evaluate an operator/function (e.g. WHERE x = 5).

Example: Sequential Scan Cost Calculation¶

For a table with $N_{\text{pages}} = 10,000$ and $N_{\text{tuples}} = 500,000$:

\[\text{Cost} = (10000 \times \text{seq\_page\_cost}) + (500000 \times \text{cpu\_tuple\_cost}) + (500000 \times \text{cpu\_operator\_cost})$$ $$\text{Cost} = 10000 + 5000 + 1250 = \mathbf{16250}\]

3. Statistics Engine (`pg_statistic` & `pg_stats`)¶

The planner calculates cardinality using column statistics gathered by ANALYZE:

n_distinct: Estimated number of distinct values (positive integer = absolute count; negative float = fraction of table, e.g. -1.0 is unique).
Most Common Values (MCV) & Frequencies (MCF): Array of the top values and their exact probability.
Histogram Bounds: Splits non-MCV values into equal-frequency buckets.
Correlation: Physical on-disk clustering order relative to logical value order (close to 1.0 or -1.0 indicates high sequential locality; close to 0.0 indicates random scattering).

Cross-Column Correlation & Extended Statistics¶

When two columns are correlated (e.g. make = 'Audi' and model = 'A4'), standard independent probability assumptions drastically underestimate rows, leading to catastrophic nested loop plans:

\[\text{Independent}: P(A \land B) = P(A) \times P(B) \implies \text{Severe underestimation}\]

-- Create multivariate extended statistics to fix bad row estimates:
CREATE STATISTICS stat_car_make_model (dependencies, mcv) 
ON make, model FROM vehicles;

ANALYZE vehicles;

4. Physical Join Algorithms¶

Algorithm	Best For	Memory Behavior
Nested Loop	Outer table small, inner table indexed	$O(1)$ memory; ideal for low-latency indexed queries
Hash Join	Large un-indexed tables	Builds in-memory hash table of outer relation in `work_mem`. Spills to disk batches if hash table exceeds `work_mem`
Merge Join	Both inputs already sorted on join keys (e.g. via B-Trees)	Streams through both inputs in $O(N + M)$ time; no hash table needed

5. Volcano Iterator Execution & `EXPLAIN (ANALYZE, BUFFERS)`¶

The executor uses the classic Volcano Iterator Model: * Every plan node implements ExecInitNode(), ExecProcNode(), and ExecEndNode(). * Execution is pull-based: the root node calls ExecProcNode() on its children, requesting one tuple at a time. Zero intermediate memory is buffered unless explicitly required (e.g. Sort or Materialize).

Production Diagnostics with `EXPLAIN (ANALYZE, BUFFERS, WAL)`¶

Always run queries with BUFFERS to inspect real cache hits vs disk reads:

EXPLAIN (ANALYZE, BUFFERS, WAL)
SELECT u.name, o.total_cents
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE o.created_at >= NOW() - INTERVAL '7 days';

Hash Join  (cost=125.40..850.10 rows=450 width=48) (actual time=0.820..4.150 rows=420 loops=1)
  Hash Cond: (o.user_id = u.id)
  Buffers: shared hit=452 read=18 dirtied=2
  WAL: records=0 bytes=0
  ->  Seq Scan on orders o  (cost=0.00..680.00 rows=450 width=16) (actual time=0.015..2.100 rows=420 loops=1)
        Filter: (created_at >= (now() - '7 days'::interval))
        Rows Removed by Filter: 19580
        Buffers: shared hit=380 read=18
  ->  Hash  (cost=100.00..100.00 rows=2000 width=40) (actual time=0.780..0.780 rows=2000 loops=1)
        Buckets: 2048  Batches: 1  Memory Usage: 145kB
        Buffers: shared hit=72
        ->  Seq Scan on users u  (cost=0.00..100.00 rows=2000 width=40) ...

shared hit=452: Read directly from shared_buffers in RAM.
read=18: Page missed buffer cache and required OS read.
Batches: 1: Hash table fit entirely within work_mem without spilling to disk.

Algorithm	Best For	Memory Behavior
Nested Loop	Outer table small, inner table indexed	\(O(1)\) memory; ideal for low-latency indexed queries
Hash Join	Large un-indexed tables	Builds in-memory hash table of outer relation in `work_mem`. Spills to disk batches if hash table exceeds `work_mem`
Merge Join	Both inputs already sorted on join keys (e.g. via B-Trees)	Streams through both inputs in \(O(N + M)\) time; no hash table needed