The Query Planner: How SQL Becomes an Execution Plan

SQL is declarative: you state the result you want, not how to compute it. Something has to decide how, and that something is the planner.

For a separate people-operations perspective, this resource covers workforce metrics and trends.

Understanding it changes how you debug slow queries, because most bad plans are not bad algorithms — they are correct algorithms chosen on the basis of wrong estimates. Fixing the query is often the wrong move; fixing what the planner believes is usually the right one.

The stages

Parse. SQL text becomes a syntax tree. Errors here are syntax errors.

Rewrite. The tree is transformed by rules: views are inlined, subqueries may be flattened into joins, constant expressions folded, redundant conditions removed. Semantics preserved, shape changed.

Plan. The optimiser enumerates ways to produce the result and picks one. This is where the cost model lives.

Execute. The chosen plan runs.

Only the third stage involves guessing, and that is where the interesting failures are.

What the planner is choosing between

Access methods — how to get rows from a table:

• Sequential scan. Read every page. Fast per row, and the right choice when a large fraction of the table is needed.
• Index scan. Walk the index, fetch matching rows from the table. Each fetch is a separate lookup, potentially random I/O.
• Index-only scan. Answer entirely from the index, without touching the table. Only possible when the index contains every column referenced.
• Bitmap scan. Collect matching row locations from one or more indexes, sort them, then read the table in physical order. A middle option for medium selectivity.

The counterintuitive part: a sequential scan is often correct. If a query touches 30% of a table, the index path means 30% of the rows fetched individually in random order, which is slower than reading the whole thing sequentially. A planner choosing a sequential scan over your index is frequently right, and "it is not using my index" is not by itself a bug report.

Join algorithms:

• Nested loop. For each row of the outer input, probe the inner. Excellent when the outer is small and the inner has an index on the join key. Catastrophic when the outer is large and the estimate said it would be small.
• Hash join. Build a hash table from one input, probe with the other. Good for large unsorted inputs, equality joins only, and needs memory for the hash table.
• Merge join. Sort both inputs and walk them together. Good when inputs are already sorted, and it supports inequality conditions.

Join order. With many tables the number of possible orderings grows factorially, so planners search heuristically and may give up on exhaustive search past a threshold. This is why very large joins sometimes get poor plans that a smaller version of the same query does not.

The cost model, and where it breaks

The planner assigns a cost to each candidate plan and picks the cheapest. Cost is an abstract number combining estimated page reads and CPU work.

The costs are driven by cardinality estimates — how many rows the planner believes each step will produce. Everything else follows from these, and this is where plans go wrong.

Estimates come from statistics collected by a background process: row counts, most common values and their frequencies, histograms of value distribution, and the number of distinct values per column.

Where estimation fails, predictably:

Stale statistics. A table loaded with a million rows after the last statistics run is still believed to be small. The planner picks a nested loop for what it thinks is 10 rows and gets a million. This is the single most common cause of a query that was fast yesterday.

Correlated columns. The planner assumes independence by default. For WHERE city = 'Paris' AND country = 'France', it multiplies the two selectivities and estimates far fewer rows than exist, because the columns are perfectly correlated. Several engines support extended statistics on column groups specifically for this.

Expressions the planner cannot see through. WHERE lower(email) = $1 cannot use column statistics on email, and the planner falls back to a fixed guess. Expression indexes and expression statistics both help.

Parameter values it does not know. With a prepared statement, the planner may build a generic plan without knowing whether the parameter is a common value or a rare one. Some engines re-plan per execution, some cache; the resulting behaviour differs and is worth knowing for your engine.

Skewed distributions beyond the histogram. A value appearing in 40% of rows but not captured as a most-common-value produces a badly wrong estimate.

Reading a plan

Get the actual plan, not the estimate: EXPLAIN ANALYZE in PostgreSQL, EXPLAIN ANALYZE FORMAT=JSON in MySQL, actual execution plan in SQL Server.

Compare estimated rows to actual rows at every node. This is the whole technique.

A node estimated at 10 rows that produced 500,000 is the problem, and it is usually the lowest such node in the tree — errors propagate upward, so the top of the plan being wrong is a consequence rather than a cause. Find the deepest node where the estimate diverges and start there.

Then check:

Where the time actually went. Node timings are cumulative in most formats — a child's time is included in its parent. Subtract.

Loop counts on nested loops. A node showing 5000 loops that was expected to run 3 times is the classic estimation failure.

Rows removed by filter. A large number means rows were read and thrown away — usually a missing or unusable index.

Sorts and hashes spilling to disk. If a sort or hash exceeds the memory allowance it spills, and the plan will say so. This can be orders of magnitude slower than the in-memory version, and the fix may be a memory setting rather than a query change.

Making the planner right rather than overriding it

In order of preference.

Update statistics. ANALYZE on the table. Free, immediate, and it fixes a surprising share of sudden regressions. If it fixes the plan, the real problem is your statistics maintenance schedule.

Add the index the query needs. Including composite indexes in the right column order — equality columns first, then range columns — and covering indexes that enable index-only scans.

Add extended statistics where columns are correlated.

Rewrite the query so the planner can see more. Removing a function from around an indexed column, replacing a correlated subquery with a join, splitting a query where one part has a wildly different selectivity.

Increase the statistics target on columns with awkward distributions, so the histogram is finer.

Only then consider hints. Hints freeze a decision that was made with today's data and today's engine version. They are occasionally necessary and they are a maintenance liability, because the hint stays after the reason for it stops applying.

Two patterns worth recognising

The plan changed and nothing else did. Almost always statistics crossing a threshold, or the same query being planned with a different parameter value. Capture plans over time if this recurs; a plan that flips between two shapes under load is a known and unpleasant category.

Fast on a small table, catastrophic on a large one. A nested loop that was correct at 1,000 rows is quadratic at 1,000,000. This is why testing against production-scale data matters more than testing against production-shaped data — the plan itself changes with size, so a query that is correct in staging can select a different algorithm in production.

The summary

The planner is a cost model driven by cardinality estimates. Get the estimates right and the plans follow.

Read plans by comparing estimated to actual rows, starting from the deepest node where they diverge.

A sequential scan is often the correct choice, and "it ignores my index" is usually not the diagnosis.

Fix what the planner believes before you fix the query, and fix the query before you reach for a hint.