How SQL Query Optimizers Think

You write a SQL query. The database does not execute it. It optimizes it — reordering joins, choosing indexes, estimating costs — and then executes the optimized plan. The plan is not what you asked for; it is what the optimizer decided was cheapest given what it knows about your data. When the plan changes overnight, the optimizer is responding to new statistics, not new code. Understanding how it thinks is the difference between writing SQL that works and writing SQL that performs.

The optimizer's job: pick the cheapest plan

A SQL query is declarative — you say what you want, not how to get it. The optimizer converts your declarative statement into a physical execution plan — a sequence of operations (index scans, hash joins, sorts) with specific access paths.

The optimizer's task is to minimize estimated cost, where cost is typically measured in I/O operations (disk reads) because disk is the bottleneck:

SELECT o.id, c.name
FROM orders o
JOIN customers c ON o.customer_id = c.id
WHERE o.total > 100
ORDER BY o.created_at DESC
LIMIT 10;

Possible plans:

Plan A:                          Plan B:
1. Seq scan orders (total>100)   1. Index scan orders (total>100)
2. For each row:                  2. Sort by created_at DESC
   Index lookup customers(id)    3. Limit 10
3. Sort by created_at DESC       4. For each row:
4. Limit 10                         Index lookup customers(id)

Plan A scans the entire orders table (expensive), filters, then sorts. Plan B uses an index on total to find qualifying rows, sorts the smaller set, takes 10, and joins. If 0.1% of orders have total > 100, Plan B is dramatically cheaper.

The optimizer picks Plan B — but only if it knows that 0.1% figure. That knowledge comes from statistics.

Statistics: the optimizer's map of your data

Every major database maintains statistics about each table and column:

These statistics are collected by ANALYZE (or automatically after a threshold of changes). The optimizer uses them to estimate:

• Selectivity — what fraction of rows will a predicate match? WHERE status = 'open' matches 5% of rows? The most_common_vals statistic tells the optimizer exactly this.
• Join cardinality — if table A has 10,000 rows and table B has 1,000, and the join is on a column with 100 distinct values in both, the estimated output is ~10,000 × 1,000 / 100 = 100,000 rows.
• Index usefulness — if an index covers 95% of the table, a sequential scan might be cheaper than an index scan plus heap lookups.

The critical failure mode: stale statistics. If the optimizer thinks a table has 10,000 rows but it actually has 10 million, every cost estimate is wrong by a factor of 1,000. The plan will be catastrophically suboptimal. This is why ANALYZE after bulk loads is not optional.

Join ordering: the combinatorial explosion

The optimizer's hardest problem is join ordering. For a query joining N tables, there are (N-1)! possible left-deep join orders (and more with bushy plans). For 8 tables, that's 40,320 plans. For 12 tables, 39 million.

PostgreSQL uses genetic query optimization (GEQO) for joins with more than 12 tables — it samples the plan space stochastically instead of exhaustively. The JVM's optimizer uses dynamic programming for small join counts and greedy algorithms for large ones.

The join order matters enormously because it determines which tables are filtered early:

-- 10 million orders, 100K customers, 500 products
-- Filter: orders.total > 100 AND products.category = 'electronics'
 
-- Bad plan: orders × products (5 billion rows) × customers
-- Good plan: products(category='electronics') → 200 rows
--            orders(total>100, join products) → 50K rows
--            customers(join orders) → 50K rows

The good plan filters products first (reducing to 200 rows), then joins orders (reducing to 50K), then joins customers. The bad plan starts with the cross product. The difference is 5 billion vs. 50K intermediate rows.

Join algorithms: the physical choices

Once the order is fixed, the optimizer picks a join algorithm for each pair:

Nested loop is the default for small inner tables. For each outer row, it probes the inner table — typically via an index. If the outer table has 10 rows and the inner has an index, this is 10 index lookups.

Hash join builds a hash table on the smaller side, then scans the larger side and probes the hash table for each row. It's O(n + m) — linear in both inputs — but requires memory for the hash table. If the hash table exceeds work_mem, it spills to disk, and the cost increases dramatically.

Merge join requires both inputs to be sorted on the join key. If they're already sorted (an index scan, an ORDER BY), it's a single-pass merge — the cheapest join possible. If they're not sorted, the sort cost dominates.

When the optimizer gets it wrong

The optimizer fails predictably:

1. Correlated columns. The optimizer assumes column values are independent. WHERE city = 'Paris' AND country = 'France' — the optimizer estimates selectivity as city_selectivity × country_selectivity, but in reality, every Paris row is in France. Multi-column statistics and extended statistics (PostgreSQL 10+) address this.

2. Complex predicates. WHERE jsonb_extract_path_text(data, 'status') = 'active' — the optimizer cannot estimate how many rows match without scanning the JSON, so it guesses. Expression statistics help, but the guess is often wrong.

3. Parameter sensitivity. A prepared statement with WHERE id = $1 may be optimal for id = 1 (returns 1 row, index scan) but terrible for id = 999999 (returns 100,000 rows, sequential scan). Plan caching uses the same plan for all parameter values. PostgreSQL 12+ supports plan_cache_mode = force_custom_plan for this.

4. Missing statistics. Temporary tables, CTEs, and subqueries may not have statistics at all. The optimizer guesses, and the guess is often a factor of 10 off.

What this means for your code

1. Run EXPLAIN ANALYZE on every slow query. The plan tells you what the optimizer decided. The actual rows tell you where the estimates were wrong.

2. Keep statistics fresh. ANALYZE after bulk loads, after schema changes, and periodically on hot tables. Stale statistics are the #1 cause of sudden query performance degradation.

3. Use pg_stat_statements or sys_statements. The query execution statistics show which queries are slow, how often they run, and whether the plan changed. This is more valuable than optimizing any single query.

4. Prefer sargable predicates. WHERE date_trunc('day', created_at) = '2026-01-01' is not sargable — it cannot use an index on created_at. WHERE created_at >= '2026-01-01' AND created_at < '2026-01-02' is sargable. The optimizer can use the index.

5. Understand that LIMIT changes the plan. A query with LIMIT 10 may choose an index scan even when the full query would use a sequential scan, because the optimizer only needs 10 rows. This is correct behavior, not a bug.