Internals · Query Engineplanneraccess pathjoin orderplan treeEXPLAIN

The Planner: Enumerating Ways to Answer

For one bound query there are many correct procedures, differing by orders of magnitude. The planner lists them — access paths per table, join orders, join methods — and needs statistics to tell them apart. The tree it hands over is what EXPLAIN prints.

▶ Interactive Try queries Interview question

Progress

Why this exists

The mechanism as the answer to a problem — read this before the name.

Problem
SELECT * FROM users WHERE email = ? can be answered by reading every page (Seq Scan) or by descending users_email_key (Index Scan). Both are correct. One reads 8 pages, the other 3 — at 900 rows. At 9 million rows one reads 70,000 pages and the other 4.
↓
Naive solution
Always use an index if one exists on the filtered column.
↓
Why it breaks
WHERE country = 'DE' matches 40% of the table. Following the index means 40% of the rows fetched by random page reads — several times slower than reading everything in order. "Always index" is wrong; so is "never".
↓
Better idea
Enumerate the alternatives and estimate what each would cost using what is known about the data: row counts, distinct values, value distributions. Pick the cheapest estimate.
↓
Internal mechanism
For each table: list access paths (seq scan, each index whose leading column is constrained). For each join: consider orders (which side first) and methods (nested loop, hash, merge). Estimate rows out of each node from selectivity statistics; cost each path; keep the cheapest per relation set; build upward. The result is a plan tree.
↓
Trade-offs
The space is exponential in the number of tables. Dynamic programming makes it tractable to about a dozen; beyond that heuristics. And every decision rests on estimates that can be wrong.
↓
Real database
PostgreSQL’s planner() builds RelOptInfos with path lists, runs standard_join_search (DP) up to geqo_threshold = 12 tables and a genetic optimizer beyond. This platform’s engine chooses an access path per table by cost and keeps the join order as written.

Choose your depth

The same mechanism at four altitudes. Start where you are; come back deeper.

Many right answers

A query says what you want. There are always several ways to compute it — read the whole table or use an index, join A to B or B to A, hash or loop — and they can differ by a factor of a thousand. The planner is the component that picks.

It picks by estimate, not by measurement: it never runs anything. That is why it needs statistics about the data, and why wrong statistics produce a confident, wrong plan.

One query, two plans

Take the login query from Reading EXPLAIN ANALYZE: SELECT * FROM users WHERE email = ?. With users_email_key in the catalog the planner has two access paths. Seq Scan: read every page in order, test every row — cost grows linearly with the table, no random reads. Index Scan: descend the B+ tree (height 2–4 random reads), then fetch each matching row from the heap (one random read each). For a unique column the second path costs a handful of reads regardless of size; for a column matching 40% of the table it costs 40% × rows random reads, and the sequential scan wins.

The planner does not know which case it is in until it estimates how many rows match — which is the job of statistics, covered in Cost-Based Optimization. What it does know is the shape of both formulas, and where they cross.

Two candidate plans for the same query, as the planner costs them (900-row users, width 64)

candidate A: Seq Scan on users
  pages   = ceil(900 × 64 / 8192) = 8      × seq_page_cost 1.0   =  8.00
  rows    = 900                            × cpu_tuple_cost 0.01 =  9.00
                                                                   17.00

candidate B: Index Scan using users_email_key    ← chosen
  descent = btree height 2                 × random_page_cost 4.0 =  8.00
  matches = 1 (unique)                     × (0.005 + 4.0×0.6 + 0.01) = 2.42
                                                                   10.42

same query, WHERE country = 'DE' (40% of rows):
  Index Scan = 8.00 + 360 × 2.415 = 877.4      Seq Scan = 17.00   ← chosen

Enumerating candidates

The planner builds the space of plans in three layers. Access paths per table — for each table in FROM, a sequential scan is always possible; each index contributes an index path if the WHERE or JOIN clause constrains its leading column with =, <, >, BETWEEN, IN or a fixed prefix LIKE 'abc%' (a *sargable* predicate — search-argument-able). An index-only path is added when the index covers every column the query touches. Join orders — for a join of A, B and C: (A⋈B)⋈C, (A⋈C)⋈B, (B⋈C)⋈A, and each with either side as the outer input. Join methods — for each join, nested loop (any condition), hash join (equality condition only), merge join (equality, both sides sortable).

Predicates are pushed down as far as they go: a filter on c.name belongs in the scan of categories, not above the join, because filtering early makes every operator above it cheaper. Conjunctions are split (a AND b → two predicates) so each part can travel to its own table. This platform’s engine does exactly this — splitAnd, pushableTo, asSarg in engine.ts — before it chooses an index.

The candidate space for a three-table join, before pruning

access paths        categories:  Seq Scan | (no usable index on name)
                    products:    Seq Scan | Index Scan products_category_id_idx
                    order_items: Seq Scan | Index Scan order_items_order_id_idx (not usable: order_id unconstrained)

join orders         (c ⋈ p) ⋈ oi   (c ⋈ oi) ⋈ p   (p ⋈ oi) ⋈ c   … × 2 for outer/inner swap
join methods        each join: Nested Loop | Hash Join | Merge Join

3 tables → 2 × 2 × 1 paths × 12 orders × 3² methods ≈ 400 plans
10 tables → 10! orders ≈ 3.6 million before methods — hence dynamic programming

Why the planner needs statistics

Every candidate is ranked by an estimate of its cost, and every cost depends on how many rows flow through each node. The planner cannot count — counting would mean running the query — so it uses statistics the database collected earlier: how many rows and pages a table has, how many distinct values each column has, which values are most common and how often, and a histogram of the rest. From these it estimates the selectivity of each predicate (the fraction of rows it keeps) and multiplies bottom-up through the tree.

When the statistics are wrong the plan is wrong in a specific, recognisable way: EXPLAIN ANALYZE shows rows=200 estimated against rows=25000 actual on some node, and every decision above that node was made for a table that does not exist. The challenge Query Optimization: Finding the Actual Bottleneck walks through this; ANALYZE is the fix. What statistics are and how they turn into a number is the next lesson, Cost-Based Optimization.

From plan tree to EXPLAIN output

EXPLAIN is a printer for the plan tree. Each line is one node, indentation is depth, -> marks a child. The parenthesised numbers are the node’s estimates (cost=startup..total rows=n); with ANALYZE, a second group shows what happened (actual time=.. rows=n loops=n). Lines without -> under a node are its predicates: Index Cond is what the index answered, Filter is what was tested afterwards on rows already fetched, Hash Cond and Join Filter are the join’s equality and residual conditions. Rows Removed by Filter is rows fetched and thrown away — the clearest signal of a missing index.

Execution starts at the deepest node and flows upward, which is why a plan is read from the leaves. The bridge to DSA is exact: this is a tree traversed post-order, children before parents, and a CTE referenced from two places turns it into a DAG (Directed Acyclic Graph) with a shared node.

The plan tree and its EXPLAIN rendering, side by side

plan tree                                EXPLAIN ANALYZE output
                                         Limit  (cost=0.00..273.91 rows=30) (actual rows=10)
Limit                                    ->  Sort (quicksort)  (rows=30) (actual rows=30)
 └─ Sort                                       Sort Key: units DESC
     └─ HashAggregate                        ->  HashAggregate  (rows=30) (actual rows=30)
         └─ Hash Join ─┐                           Group Key: p.name
             ├─ Hash Join                        ->  Hash Join  (rows=2) (actual rows=1938)
             │   ├─ Seq Scan categories                Hash Cond: oi.product_id = p.id
             │   └─ Hash → Seq Scan products           ->  Hash Join  (rows=2) (actual rows=30)
             └─ Hash → Seq Scan order_items                  Hash Cond: p.category_id = c.id
                                                             ->  Seq Scan on categories c  (rows=2) (actual rows=1)
                                                                   Filter: c.name = 'Audio'
                                                                   Rows Removed by Filter: 7
                                                             ->  Hash
                                                                   ->  Seq Scan on products p  (rows=240)
                                                       ->  Hash
                                                             ->  Seq Scan on order_items oi  (rows=9580)

Key points

The planner enumerates alternatives — access paths per table, join orders, join methods — and ranks them by estimated cost. It never runs anything.
An index is one candidate among several, not a default. Below a few percent selectivity it wins; above 10–20% the sequential scan does, and the planner is right to ignore the index.
Predicates are pushed down to the scan that owns their columns; only sargable predicates (col op constant) can use an index.
Join-order search is exponential; dynamic programming keeps the best sub-plan per set of tables, and PostgreSQL switches to a genetic search above 12 tables.
Every estimate rests on statistics. A large gap between estimated and actual rows in EXPLAIN ANALYZE means every decision above that node is suspect.
EXPLAIN prints the plan tree: one line per node, indentation for depth, execution starting at the deepest leaf.

Seq scan or index scan?

SELECT * FROM users WHERE email = ? — the planner costs both paths with the constants PostgreSQL uses (seq page 1.0, random page 4.0, cpu tuple 0.01). Move the sliders until the choice flips.

Seq Scan — 7,813 pages × 1 + 1,000,000 rows × 0.0117,813

Index Scan — 3 levels × 4 + 1,000 rows × (0.005 + 4×0.6 + 0.01)2,427

Chosen

Index Scan

Matching rows

1,000

Seq cost

17,813

Index cost

2427.00

Why: 1,000 matching rows means 1,000 random heap reads at 4 each plus a 3-level descent — 2427.00 — which is less than reading all 7,813 pages sequentially (17,813). The index wins until about 0.7% of the table matches.

The cost formulas are this repo's planner (src/db/sql/plan.ts, PostgreSQL's default constants); row width 64 B and a fresh, uncorrelated heap are assumed. Inputs are yours.

table rows1Mselectivity0.1% index on email

Try it in the playground

EXPLAIN ANALYZE
SELECT id, name FROM users WHERE email = 'jonas.olsen7@example.com';

Index path chosen: one matching row. →

EXPLAIN ANALYZE
SELECT id, name FROM users WHERE country = 'DE';

Same table, low-selectivity predicate: no index, and correctly so. →

EXPLAIN ANALYZE
SELECT id FROM users WHERE lower(email) = 'jonas.olsen7@example.com';

Not sargable: the index on email cannot answer a predicate on lower(email). →

When to use — and when not

Use it when

A cost-based planner fits when data sizes and distributions change and queries are ad hoc — which is every general-purpose relational database.
Reading the plan tree fits every slow-query investigation: it is the planner’s reasoning, written down.

Avoid it when

Rule-based planning fits a fixed workload with hand-tuned access paths (embedded engines, some key-value stores) — cheaper to plan, no statistics to maintain.
Query hints fit when the estimate is known to be wrong and cannot be fixed by statistics; PostgreSQL deliberately offers none, MySQL and Oracle do.

Failure modes

A predicate wrapped in a function (lower(email) = ?, date(created_at) = ?) is not sargable; no index path is generated and the scan is sequential.
A composite index whose leading column is not constrained: (user_id, created_at) cannot serve WHERE created_at > ? — the leftmost-prefix rule.
A join order chosen for a row estimate that was 100× off: a nested loop over what turned out to be a million outer rows.
Reading EXPLAIN top-down and blaming the root node; the cost is almost always in a leaf or the join just above it.