The query planner: EXPLAIN, statistics, and join strategies

Every query you've written is a lie of omission. SELECT * FROM expenses WHERE group_id = 'x' ORDER BY created_at DESC LIMIT 20 tells Postgres exactly what you want and says nothing about how to get it. Should it use the index on group_id? Scan the whole table and sort? Which of two indexes, if both apply? SQL is declarative — you describe the result, not the procedure — and the gap between "what" and "how" is filled by the query planner (also called the optimizer), the single most consequential component you never call directly.

Understanding it is what separates "I added an index and the query got slower somehow" from knowing why. And it's built on everything so far: the planner is reasoning about pages and the buffer pool, B-tree lookups, and MVCC visibility — it's the part that decides which of those mechanics to actually invoke.

The planner's job: from one query to many possible plans

For any non-trivial query there are many physically different ways to produce the same rows. Two tables joined on a key can be joined with three different algorithms, in either order, with each table reached by a sequential scan or one of its indexes. That's already a dozen candidate plans for a two-table join, and it explodes combinatorially as tables are added.

The planner's job is to enumerate the sensible candidates, estimate the cost of each, and hand the cheapest one to the executor. "Cost" is an abstract number in arbitrary units, roughly "expected page reads + CPU work," calibrated by tunables like random_page_cost (how much more expensive a random I/O is than a sequential one — default 4×, straight out of the pages lesson's random-vs-sequential story). The planner never runs the query to compare; it predicts. And the entire quality of its decision rests on one thing: how accurately it can guess how many rows each step will produce. Get the row counts right and the cost model almost always picks a good plan. Get them wrong and it confidently picks a disaster.

Reading a plan: EXPLAIN

You see all of this with EXPLAIN. There are two forms, and the difference matters:

• EXPLAIN shows the plan the planner chose, with its estimates. It doesn't run the query.
• EXPLAIN ANALYZE actually executes the query and shows estimates next to the real numbers. This is the one you almost always want — because the whole game is spotting where estimate and reality diverge. (Caveat: it really runs, so EXPLAIN ANALYZE on an UPDATE/DELETE will change data unless you wrap it in a transaction you ROLLBACK.)

Here's a plan for our expenses query (numbers illustrative):

EXPLAIN ANALYZE
SELECT * FROM expenses WHERE group_id = 'g_123' ORDER BY created_at DESC LIMIT 20;

Limit  (cost=0.42..8.90 rows=20 width=210) (actual time=0.03..0.11 rows=20 loops=1)
  ->  Index Scan Backward using expenses_group_created_idx on expenses
        (cost=0.42..421.06 rows=1004 width=210) (actual time=0.02..0.09 rows=20 loops=1)
        Index Cond: (group_id = 'g_123')
Planning Time: 0.15 ms
Execution Time: 0.14 ms

Read a plan inside-out and bottom-up: the most indented node runs first and feeds its parent. Here the executor walks the composite index (group_id, created_at) backward (because we asked for created_at DESC), which hands rows out already sorted, so the Limit just takes the first 20 and stops — no separate sort step at all. Each node reports:

• cost=startup..total — estimated cost to produce the first row (startup) and all rows (total). A high startup cost (e.g. a sort must consume its whole input before emitting anything) is why a LIMIT can be cheap on one plan and ruinous on another.
• rows — the planner's estimate of rows this node emits. This is the number that decides everything.
• actual time / actual rows / loops — from ANALYZE: the real elapsed time, real row count, and how many times this node was executed. loops=1004 means this node ran a thousand times — a giant clue.

The skill is scanning for the node where estimated rows and actual rows diverge by orders of magnitude. That divergence is the root cause of essentially every mysteriously slow query.

Where the estimates come from: statistics

How does the planner guess that group_id = 'g_123' matches ~1004 rows without counting? From statistics it collected earlier and stored in the system catalog (pg_statistic, readable via pg_stats). These are gathered by ANALYZE (run automatically by the same autovacuum daemon from the MVCC lesson), which samples the table and records, per column:

• n_distinct — how many distinct values the column has. For group_id = ?, the planner estimates matching rows as roughly total_rows / n_distinct. This is the workhorse for equality on a "normal" column.
• Most Common Values (MCVs) and their frequencies — an explicit list of the handful of values that appear disproportionately often. This is how the planner knows a status = 'active' filter (where 95% of rows are active) is not selective, while status = 'disputed' (0.1% of rows) is. Without MCVs it would assume every value is equally likely and badly misjudge skewed columns.
• A histogram of value ranges — for range predicates (created_at > ?, amount BETWEEN ? AND ?), the planner reads off what fraction of rows fall in the range.
• null_frac and correlation (how physically ordered the column's values are on disk — high correlation makes an index scan cheaper because matching rows cluster into fewer pages, low correlation scatters them).

From these it computes selectivity — the fraction of rows a predicate passes — and thus the row estimate for every node. Everything downstream is built on these numbers, and they are only as fresh as the last ANALYZE.

Scan choices: why Postgres sometimes refuses your index

The most common "the planner is broken" complaint is: I built an index and it's doing a sequential scan anyway. Usually the planner is right, and here's the reasoning. There are several ways to read a table:

• Sequential Scan — read every page in order. Costs a lot of sequential I/O, which is cheap per page (the pages lesson: sequential reads are far faster than random ones).
• Index Scan — walk the B-tree to find matching entries, then fetch each matching row from the heap. Each heap fetch is a potentially random page read (random_page_cost, 4× a sequential one by default).
• Bitmap Heap Scan — a hybrid: walk the index to build a bitmap of which pages contain matches, then read those pages in physical order. This is the planner's answer to "the index matches a moderate fraction of rows" — it gets index precision without index scan's random-I/O penalty.
• Index-Only Scan — answer entirely from the index without touching the heap, possible only when the query's columns are all in the index and the visibility map (from the B-tree lesson) says the page is all-visible.

Now the key insight: an index scan is only cheaper than a sequential scan when the predicate is selective. If WHERE group_id = 'g_123' matches 0.1% of the table, the index scan reads a few pages and wins massively. But if a predicate matches 40% of the table, the index scan would do hundreds of thousands of random heap fetches — and reading 40% of the table via scattered random I/O is slower than just sequentially reading 100% of it. So the planner correctly chooses a sequential scan. It's not ignoring your index out of stubbornness; it computed that using it would be slower, and it's usually right. (When it's wrong, the cause is almost always back in the previous section — a bad selectivity estimate from stale or missing statistics.)

Drag the selectivity and watch the planner switch plans by cost. At a fraction of a percent it takes the index; push past ~5% and it flips to a bitmap heap scan; past ~40% it abandons the index for a sequential scan — because reading that much of the table randomly is slower than scanning all of it in order.

EXPLAIN
Index Scan using expenses_group_idx  (cost=0.42..18 rows=3,000)

Join strategies: three algorithms, three sweet spots

When a query joins tables, the planner picks among three physical join algorithms. Knowing them turns join plans from mysterious to readable:

Nested Loop — for each row on the outer side, look up matching rows on the inner side. If the inner side has an index on the join key, each lookup is a cheap B-tree probe. Wins when the outer side is small (few iterations) and the inner side is indexed (cheap probes). It's O(outer × inner-lookup-cost), so it's catastrophic when the outer side turns out huge — exactly the stale-stats disaster above.

Hash Join — build a hash table on the join key of the smaller input, then scan the larger input and probe the hash table for each row. O(n + m), no index needed, and it's the planner's default for joining two large tables on an equality condition. The cost is memory: the hash table must fit in work_mem or it spills to disk in batches (slower, and a common cause of "why did this join suddenly get slow" — the data grew past work_mem). Only works for equi-joins (a.x = b.y), not range conditions.

Merge Join — if both inputs are sorted on the join key, walk them together like merging two sorted lists, advancing whichever is behind. O(n + m) given sorted inputs. Wins when the inputs are already sorted — because they came off a B-tree in key order, or feed a later ORDER BY/GROUP BY that needs the sort anyway — so the sort is free or reused. If Postgres has to add explicit sorts just to enable it, hash join usually wins instead.

The planner estimates the cost of each algorithm for each join order and picks the cheapest overall plan. With many tables the number of possible join orders explodes, so beyond a threshold (geqo_threshold, default 12) Postgres switches from exhaustive search to a genetic algorithm (GEQO) that finds a good-enough order without evaluating all of them — a rare case where the "optimal" plan is knowingly traded away because finding it would cost more than the query.

Making the planner honest

You don't command the planner (Postgres deliberately has no query hints — the philosophy is "fix the inputs, not the output"). You inform it:

• ANALYZE after big data changes so estimates match reality. This is 90% of real fixes.
• Raise statistics granularity on skewed or misjudged columns (SET STATISTICS, CREATE STATISTICS for correlated columns).
• Build the right index — a composite index matching the query's filter and sort (like (group_id, created_at) above) lets the planner skip a sort entirely.
• Read EXPLAIN ANALYZE, not EXPLAIN — always compare estimated vs actual rows first; the biggest divergence is your bug.