Chapter 15: The Query Planner — How Databases Execute Queries

When you write SQL, you describe WHAT you want. The query planner (also called optimizer) decides HOW to get it — which indexes to use, what order to join tables, which algorithm to use. It's the brain of the database.

Query Processing Pipeline

SQL Query: "SELECT name FROM users WHERE age > 25 ORDER BY name" │ ▼ ┌──────────┐ │ Parser │ → Syntax check, build parse tree └────┬─────┘ ▼ ┌──────────┐ │ Analyzer │ → Resolve table/column names, check types └────┬─────┘ ▼ ┌──────────┐ │ Rewriter │ → Apply rules (views, RLS policies) └────┬─────┘ ▼ ┌──────────────┐ │ Planner/ │ → Generate candidate plans, estimate costs, │ Optimizer │ pick cheapest plan └────┬─────────┘ ▼ ┌──────────┐ │ Executor │ → Run the chosen plan, return results └──────────┘

What the Planner Decides

1. Scan Method (How to Read the Table)

Method	When Used	Cost
Sequential Scan	No useful index, or reading most of table	O(n) — reads every page
Index Scan	Selective WHERE clause with matching index	O(log n + k)
Index Only Scan	All needed columns are IN the index	O(log n + k), no heap access!
Bitmap Index Scan	Multiple conditions, moderate selectivity	Builds bitmap, then reads pages

2. Join Algorithm

Algorithm	When Used	How It Works
Nested Loop	Small tables, indexed inner	For each row in A, look up matching rows in B
Hash Join	Large tables, equality join, no index	Build hash table from smaller table, probe with larger
Merge Join	Both inputs sorted (or can be cheaply sorted)	Walk through both sorted lists simultaneously

3. Join Order

For a query joining 5 tables, there are 5! = 120 possible join orders. The planner estimates the cost of each and picks the cheapest. This is why statistics matter.

Cost Estimation

The planner uses statistics about your data to estimate costs:

Table size — number of rows, number of pages
Column statistics — distinct values, most common values, histogram of value distribution
Correlation — how well physical row order matches column value order

-- PostgreSQL: update statistics (run periodically or after bulk loads)
ANALYZE users;

-- View statistics
SELECT * FROM pg_stats WHERE tablename = 'users' AND attname = 'country';

⚠️ Stale Statistics = Bad Plans

If statistics are outdated (e.g., table grew from 1000 to 1 million rows but ANALYZE wasn't run), the planner makes wrong estimates and picks bad plans. PostgreSQL's autovacuum runs ANALYZE automatically, but after bulk loads you should run it manually.

Why the Planner Sometimes Chooses Sequential Scan

A common surprise: you have an index, but the planner ignores it. This is usually correct:

-- If 80% of users are active, an index scan is SLOWER than seq scan:
SELECT * FROM users WHERE active = true;

-- Index scan: read index pages + random I/O to heap for each row
-- Sequential scan: read heap pages in order (sequential I/O is fast)
-- When returning most of the table, sequential wins.

-- Rule of thumb: index scan wins when selecting < ~10-20% of rows

Helping the Planner

Create appropriate indexes — give it options
Keep statistics fresh — ANALYZE after bulk changes
Write sargable queries — don't wrap indexed columns in functions

-- ✗ NOT sargable (can't use index on created_at):
WHERE YEAR(created_at) = 2024

-- ✓ Sargable (can use index):
WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01'

-- ✗ NOT sargable:
WHERE LOWER(email) = 'alice@example.com'

-- ✓ Use expression index instead:
CREATE INDEX idx_lower_email ON users (LOWER(email));

Key Takeaways

The query planner picks the cheapest execution plan based on cost estimates
It decides: scan method, join algorithm, join order
Cost estimates depend on table statistics (run ANALYZE)
Sequential scan can be faster than index scan for low-selectivity queries
Write sargable queries (don't wrap indexed columns in functions)
The planner is usually right — if it ignores your index, understand why before forcing it

← Previous: B-Tree Internals Next: EXPLAIN ANALYZE →