Query Planner

You already watched this happen live in the B-tree lesson — a query flipping from a Seq Scan to an Index Scan. Now let's see why the planner flips, and how it decides everything else.

Cost is an estimate, in abstract units

The planner doesn't time anything. It assigns each plan a cost in arbitrary units, anchored on a few constants (Postgres defaults): reading a page sequentially costs 1.0 (seq_page_cost), a random page read costs 4.0 (random_page_cost), and touching a tuple in the CPU costs ~0.01. Every EXPLAIN line shows cost=startup..total rows=… width=…:

DROP TABLE IF EXISTS orders; DROP TABLE IF EXISTS customers;
CREATE TABLE customers (id int primary key, name text);
CREATE TABLE orders (id int primary key, customer_id int, amount int);
INSERT INTO customers SELECT g, 'customer_' || g FROM generate_series(1, 2000) g;
INSERT INTO orders SELECT g, (g % 2000) + 1, (g % 500) FROM generate_series(1, 20000) g;
ANALYZE customers; ANALYZE orders;
EXPLAIN SELECT * FROM orders WHERE id = 42;

startup is the cost before the first row appears; total is for all rows; rows is the planner's estimate of how many rows come out; width is their average byte size. The planner sums costs like these across a whole plan tree and compares totals.

Those units aren't a black box — you can recompute the number yourself. A full sequential scan's cost is simply pages read × seq_page_cost + rows processed × cpu_tuple_cost. Postgres records every table's page and row counts in pg_class, so the arithmetic is right there:

SELECT relpages,                                     -- 8 KB pages in the table
     reltuples,                                    -- estimated row count
     relpages * 1.0 + reltuples * 0.01 AS derived   -- pages×1.0 + rows×0.01
FROM pg_class WHERE relname = 'orders';

EXPLAIN SELECT * FROM orders;   -- Seq Scan … cost=0.00..<the same number>

derived equals the total cost in the EXPLAIN line exactly — that's literally the formula the planner ran. Every plan node has a formula like this; the planner just adds them up the tree and keeps the cheapest grand total.

Why the plan flips: the cost crossover

Here is the core decision, distilled. A Seq Scan reads every page no matter what, so its cost is flat. An Index Scan pays per matching row (a random heap fetch each), so its cost rises with the number of matched rows. Drag the slider and watch which line is lower — the planner always picks the lower one.

The lines cross at a low selectivity (around half a percent here): an index only pays off when a query matches a small fraction of the table. Ask for much more and reading everything in order is cheaper. Postgres agrees, live — a tiny match uses the index, a big one falls back to a sequential (or bitmap) scan:

CREATE INDEX IF NOT EXISTS orders_amount ON orders (amount);
ANALYZE orders;
EXPLAIN SELECT * FROM orders WHERE id = 42;         -- 1 row  → Index Scan
EXPLAIN SELECT * FROM orders WHERE amount < 20;      -- ~4%    → Bitmap Heap Scan
EXPLAIN SELECT * FROM orders WHERE amount < 400;     -- ~80%   → Seq Scan

Where the row estimates come from

Every cost rests on an estimate of how many rows a step produces — and a wrong row estimate poisons every cost above it in the tree. Those estimates come from statistics gathered by ANALYZE and stored in pg_statistic (readable through the pg_stats view). For each column Postgres keeps: how many distinct values there are, the most common values with their frequencies, and a histogram dividing the rest into equal-population buckets. Look at the exact stats it holds for orders.amount:

SELECT n_distinct,                                    -- ~500 distinct amounts
     (most_common_vals::text::text[])[1:5]  AS top_5_values,
     (histogram_bounds::text::text[])[1:6]  AS histogram_start
FROM pg_stats WHERE tablename = 'orders' AND attname = 'amount';

To estimate WHERE amount < 50, the planner walks that histogram, works out what fraction of values fall below 50, and multiplies by the row count. Compare its guess to reality with EXPLAIN ANALYZE — estimated rows= right next to actual … rows=:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM orders WHERE amount < 50;

Watch statistics go stale

Here's the failure mode that wrecks real production queries. Load a table, analyze it, then pour in 50,000 new rows without re-analyzing — and watch the planner keep believing there's just one matching row when there are now fifty thousand:

DROP TABLE IF EXISTS evt;
CREATE TABLE evt (id int, kind text);
INSERT INTO evt SELECT g, 'a' FROM generate_series(1, 1000) g;
ANALYZE evt;                          -- stats now say: no 'b' rows exist

INSERT INTO evt SELECT g, 'b' FROM generate_series(1, 50000) g;   -- no ANALYZE!
EXPLAIN ANALYZE SELECT * FROM evt WHERE kind = 'b';  -- rows=1  vs  actual rows=50000

A 50,000× miss. In a real query that estimate would steer the planner into a catastrophic plan — say a nested loop it expects to run once, actually run fifty thousand times. Refresh the statistics and watch the estimate snap back:

ANALYZE evt;
EXPLAIN ANALYZE SELECT * FROM evt WHERE kind = 'b';  -- estimate now ≈ 50,000

Joining tables: three algorithms

When a query joins tables, the planner also chooses how to match rows. There are three strategies, each best in a different regime:

• Nested Loop — for each row on the outer side, look up matches on the inner side. Naively that's O(N × M), but with an index on the inner side it drops to O(N × log M) — so it's cheap only when the outer side is small (or the join is very selective). It's also the only option for non-equality joins (<, >, range).
• Hash Join — scan the smaller side once to build a hash table, then scan the larger side once and probe it: O(N + M), equality only. The catch: the hash table must fit in work_mem, or it spills to disk in batches (slower).
• Merge Join — walk both sides in sorted order and zip them together: O(N + M) to merge, plus O(N log N) first for any side that isn't already sorted. A bargain when an ordered index provides the sort for free, and it streams arbitrarily large inputs without a big hash table.

Postgres picks by cost. Here it chooses a hash join; disable it and watch the planner fall back to its next-cheapest option:

EXPLAIN SELECT count(*)
FROM orders o JOIN customers c ON c.id = o.customer_id;

SET enable_hashjoin = off;
EXPLAIN SELECT count(*)
FROM orders o JOIN customers c ON c.id = o.customer_id;
RESET enable_hashjoin;

Join order is a search problem

A join of N tables can be arranged in a huge number of orders, and each order has different costs. The planner searches this space for the cheapest arrangement — exhaustively for a handful of tables, and via a genetic algorithm (GEQO) once there are too many to enumerate. This is why adding one more joined table can occasionally change a plan dramatically.

Reading a plan

EXPLAIN shows the estimated plan; EXPLAIN (ANALYZE, BUFFERS) actually runs it and adds the truth. Read a plan inside-out — the deepest, most-indented node runs first and feeds its parent. Four things to watch:

• actual rows vs estimated rows — a big gap means bad statistics, and it's the first thing to check on a slow query (you just saw why).
• loops — how many times a node ran. Under ANALYZE, actual time and rows are reported per loop, so a node showing rows=1 loops=50000 really produced 50,000 rows across 50,000 executions — multiply to get the true total. A surprisingly large loops is the fingerprint of a nested loop gone wrong.
• Buffers — shared hit = served from cache, read = fetched from disk; the ratio tells you how cache-friendly the plan is.
• Rows Removed by Filter — rows the node examined and threw away; a large count often means the right index is missing.

Your turn

Uses orders and customers from the first cell.

SET enable_hashjoin = off;
SET enable_mergejoin = off;
EXPLAIN SELECT count(*)
FROM orders o JOIN customers c ON c.id = o.customer_id;
RESET ALL;

SELECT c.name, count(*) AS orders
FROM orders o JOIN customers c ON c.id = o.customer_id
GROUP BY c.name
ORDER BY orders DESC
LIMIT 3;