postgres://internals

Query Planner

// the problem

SQL is declarative: you say what rows you want, never how to get them. Something has to invent the how — which index (if any) to use, which order to join tables, which algorithm for each step. That something is the planner, and it works like an economist: it estimates the cost of many possible plans and picks the cheapest. Change the data and the same query can get a completely different plan.

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=…:

sql · live postgresrun me first

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;

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;

⌘/ctrl + enter

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.

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.

fig.01 · cost vs selectivity100,000 rows · 1000 pages

selectivity

0.30%

rows matched

299

seq cost

2000

index cost

1201

drag selectivity — how much of the table matches

planner picks: Index Scan — index cost 1201 beats 2000

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:

sql · live postgresselective vs not — read each plan

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

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

⌘/ctrl + enter

// note · the bitmap scan is the middle ground

Between “a few rows” and “most of the table” sits the Bitmap Heap Scan: use the index to collect all matching row locations, sort them, then read the heap pages in physical order — fewer random I/Os than a plain index scan, less waste than a full seq scan.

Where the row estimates come from

Every cost rests on an estimate of how many rows a step produces, and those come from statistics gathered by ANALYZE (stored in pg_statistic): per-column most-common-values, histograms, and distinct-value counts. The planner uses them to guess selectivity. Compare its estimate to reality with EXPLAIN ANALYZE — rows= (estimated) next to actual … rows=:

sql · live postgreseditable — run it

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

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

⌘/ctrl + enter

// gotcha · stale statistics are the #1 cause of bad plans

If the estimate and the actual row counts diverge wildly, the planner is flying blind — usually because statistics are stale after a big data change. The fix is almost always ANALYZE (autovacuum normally does it for you). A planner with good stats picks good plans; a planner with bad stats can't.

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 one side, look up matches on the other (ideally via an index). Great when one side is tiny or the join is very selective.
Hash Join — build a hash table of the smaller table, then probe it with the larger. Great for joining two big unsorted sets on equality.
Merge Join — sort both sides (or use ordered indexes) and zip them together. Great when inputs are already sorted or huge.

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

sql · live postgresa hash join…

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

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

⌘/ctrl + enter

sql · live postgres…and what it falls back to without one

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

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

⌘/ctrl + enter

// why it matters · enable_* flags are for learning, not production

Toggling enable_hashjoin, enable_seqscan, etc. is a great way to see the alternative the planner rejected and compare costs. But they're blunt instruments — don't leave them off in production. If the planner chooses badly, fix the cause (statistics, indexes, cost constants), not the symptom.

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: actual time, real rows, loops (how many times a node ran — multiply for the total), and Buffers (shared hit = cache, read = disk). The gap between estimated rows and actual rows is the first thing to check when a query is slow.

Your turn

Uses orders and customers from the first cell.

// challengewrite it yourself

The join below uses a Hash Join by default. Force the planner to use a Nested Loop instead, and prove it with EXPLAIN.

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;

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;

⌘/ctrl + enter

// challengewrite it yourself

Return the 3 customers with the most orders: their name and order count, highest first.

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;

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;

⌘/ctrl + enter

// what you now understand

01The planner turns declarative SQL into an execution plan by estimating each candidate plan's cost and picking the cheapest.
02Cost is in abstract units anchored on seq_page_cost=1, random_page_cost=4, and small per-tuple CPU costs — never measured time.
03Seq scan cost is flat; index scan cost rises with the number of matched rows, so an index only wins for a small fraction of the table (bitmap scan covers the middle).
04Row estimates come from ANALYZE statistics; stale stats are the top cause of bad plans.
05Joins use nested loop (tiny/selective), hash (big unsorted equality), or merge (sorted/huge) — chosen by cost.
06Join order is searched exhaustively for few tables and via GEQO for many.
07Read plans with EXPLAIN (estimate) and EXPLAIN ANALYZE (actual rows, loops, buffers); a big estimate-vs-actual gap is the red flag.

// self-test

A query matches 90% of a large indexed table. What will the planner most likely choose, and why?

// self-test

EXPLAIN ANALYZE shows a node with estimated rows=5 but actual rows=500,000. What's the most likely problem?

// go deeper

Using EXPLAIN (official docs) — reading plans, costs, ANALYZE/BUFFERS
Planner Cost Constants — seq_page_cost, random_page_cost, and friends
How the Planner Uses Statistics — pg_statistic, selectivity estimation
Genetic Query Optimizer — searching large join-order spaces

nextMVCC & Transactions