How a Query Executes

Here are two runs of the same query, against the same rows, on the same machine. One finishes in 0.074 milliseconds. The other takes 204 milliseconds — nearly three thousand times longer. Nothing about the data changed. The only difference is how the database decided to execute it.

That decision belongs to the planner, and it is the one part of a database that gets to have an opinion. You hand SQL to the engine and say what you want; you never say how. Somewhere between your text and your rows, something has to invent a strategy — which index to use, or whether to use one at all; which table to read first; and, when two tables meet, which of three very different join algorithms to run. Get that right and a query is instant. Get it wrong and the same query melts.

We've been circling this the whole section. Inside a Database: The Journey of a Write named the rooms — parser, rewriter, planner, executor — and promised we'd come back to watch the planner earn its salary. Indexes Deep-Dive ended on the question it couldn't answer: how does the planner actually choose which index, which join, which scan? This is that answer, and it's the finale of Database Internals.

The punchline, up front: the planner is not reading your data. It is reading a summary of your data — a few hundred numbers collected the last time someone ran ANALYZE. Every choice it makes is arithmetic on that summary. When the summary is good, the plans are brilliant. When the summary lies, the plan is confidently, catastrophically wrong. By the end of this lesson you'll be able to compute the planner's cost numbers on paper, name the three join algorithms and predict which one it will pick, and read an EXPLAIN well enough to catch it in a lie.

In this lesson: the pipeline and the one step that has a choice; why cost is not milliseconds (and the formula that produces it, verified to the decimal); where the planner's row estimates come from; the three join algorithms and the tipping point between them; how to read EXPLAIN ANALYZE; and the blind spot that makes the planner guess wrong by 2,000×.

Scope: which indexes to create — composite, covering, partial — is Indexes Deep-Dive, and we assume it here. How rows are versioned and made visible is MVCC: Readers Don't Block Writers. Running a query across many machines is a different animal entirely; that waits for sharding in Data Systems at Scale. Here: one database, one query, one plan.

A query goes through four rooms, and we named them all in Inside a Database: The Journey of a Write:

1. Parser — turns your text into a tree. Catches typos. No opinions.
2. Rewriter — expands views and rules into the tree. Mechanical. Still no opinions.
3. Planner (the optimizer) — takes the tree and asks the only interesting question in the whole pipeline: of all the ways I could execute this, which is cheapest?
4. Executor — takes the winning plan and actually runs it, pulling rows through the tree.

Three of those four rooms have no discretion at all. The planner is where the intelligence — and all of the risk — lives. It builds candidate plans, prices each one, and keeps the cheapest. That word cheapest is doing enormous work, so let's find out what it actually means.

Run EXPLAIN and the first thing you see is a cost:

Seq Scan on orders  (cost=0.00..34706.00 rows=2000000 width=27)

Almost everyone reads 34706.00 as some unit of time. It isn't. Cost is dimensionless. The whole scale is anchored to one thing: reading a single page from disk sequentially costs 1.0. Everything else in the database is priced relative to that one act. So a cost of 34,706 means "about as much work as 34,706 sequential page reads" — not 34 seconds, not 34 milliseconds, not anything you can put a stopwatch to.

There are five knobs, and these are the real defaults:

Look at random_page_cost = 4.0 for a second. The planner believes a random read is four times more expensive than a sequential one. On a spinning disk, where an arm physically moves, that was about right. On an SSD it is nonsense — and it's the single most commonly retuned knob in Postgres (most people running on SSDs drop it to somewhere between 1.1 and 2.0). If your database keeps refusing to use an index you're certain it should use, this number is the first suspect: an inflated random_page_cost makes every index scan look more expensive than it really is.

Now the part that turns the cost model from a black box into arithmetic.

Our orders table holds 2,000,000 rows across 14,706 pages. A sequential scan has to read every page and process every row, so:

cost = seq_page_cost × pages + cpu_tuple_cost × rows
cost = 1.0 × 14,706 + 0.01 × 2,000,000 = 34,706

And here is what a real Postgres actually prints:

To the decimal. That's worth sitting with, because it changes how you should feel about the planner: it is not an oracle and it is not a mystery. It is a small pile of arithmetic over a few constants — and you can do that arithmetic yourself.

One more detail you'll need later. Every node reports two numbers, cost=startup..total. The startup cost is the work required before the node can emit its first row. A sequential scan can emit row one immediately, so its startup is 0.00. But a Sort has to consume its entire input before it knows what comes first, and a hash join must finish building its hash table before it can return anything — those have big startup costs. This is exactly why adding LIMIT 10 can change which plan wins: when you only want ten rows, a plan that starts producing immediately beats a plan with a lower total but a slow start.

Look again at that first plan line. Next to the cost sits rows=2000000. Where did that come from? The planner didn't count them — counting them would mean running the query, which is the thing it's trying to plan.

It came from statistics: a compact summary of each column that ANALYZE collects by sampling the table and stores in the catalog. You can read it yourself in pg_stats. Three pieces do most of the work:

• most_common_vals / most_common_freqs — a list of the most frequent values and how often each appears. For a skewed column this is a direct lookup: if 'shipped' is recorded as 90% of the status column, then WHERE status = 'shipped' has a selectivity of 0.9. Done.
• histogram_bounds — for everything that isn't a common value, roughly 100 buckets, each holding about the same number of rows. To estimate WHERE data <= 240 the planner finds the bucket that 240 lands in and interpolates inside it.
• n_distinct — how many distinct values the column has. For equality against a value that isn't in the common list, selectivity is roughly 1 / n_distinct.

Multiply the selectivity by the table's row count and you have the estimated rows. That single number is the most important number in the database, because everything downstream depends on it: whether to use an index, which table to lead with, and — as we're about to see — which join algorithm to run.

And it is an estimate. The planner is looking at a hundred-bucket sketch of a table with two million rows in it, drawn the last time somebody ran ANALYZE. Hold on to that thought; we'll come back and break it on purpose.

Everything so far has been about reading one table. The moment a query mentions two, the planner faces its biggest decision — and this is the piece we haven't taught anywhere yet.

There are exactly three ways to match rows in table A with rows in table B. Not three implementations of one idea — three genuinely different strategies, with different shapes, different costs, and different failure modes.

Nested Loop. Take each row from the outer table, and for every one of them go look up the matching rows in the inner table. That's it — it's the double for loop you'd write yourself. Naively that's O(N × M) and disastrous. But if the inner table has an index on the join key, each lookup is a cheap index seek, and the whole thing becomes roughly O(N × log M). That makes the nested loop brilliant in one specific situation: the outer side is small and the inner side is indexed. Five outer rows means five index seeks — you'll be done before the alternatives have finished setting up. Its weakness is written on its face: the cost scales linearly with the outer row count, so if that count turns out to be much larger than expected, it degrades smoothly and relentlessly into disaster.

Hash Join. Pick the smaller side, read it once, and build a hash table on the join key in memory. Then stream the bigger side past it, probing the hash for each row. Two scans, no index needed, no sorting. This is the workhorse for big joins — it doesn't care that either table is huge, because the work is basically "read both sides once." It has two conditions attached. First, it only works on equality (a.id = b.id); you can't hash your way through a.x < b.y. Second, the hash table has to fit in work_mem (4 MB by default) — if it doesn't, Postgres splits the work into batches and spills to disk, and the join gets substantially slower. It also has a real startup cost: nothing comes out until the entire build side has been read.

Merge Join. Sort both sides by the join key, then walk the two sorted lists in lockstep — like merging two piles of alphabetised paper. If both inputs already arrive sorted, this is superb and nearly free, and it's the one algorithm that streams gracefully to disk when the data is enormous. It's also the only one of the three that can handle range conditions rather than just equality. The catch is in the first word: if the inputs aren't already sorted, somebody has to sort them, and that sort is expensive enough to usually hand the win to a hash join.

So which one does the planner pick? It prices all three and takes the cheapest. Which sounds anticlimactic — until you watch the prices move.

Here's the experiment that makes the whole cost model click. One query shape, one dataset (2,000,000 orders, 200,000 customers, an index on orders(customer_id)). The only thing I changed was how many customers the filter lets through — the size of the outer side:

Somewhere between forty and eighty thousand outer rows, the planner changed its mind. It wasn't a mood — look at the cost arithmetic and you can see the two lines cross:

• Nested loop = scan the customers (3,735) + N × 0.83 for each index probe. That's a straight line with a slope: every extra outer row adds cost.
• Hash join = read all 2,000,000 orders once (34,706) + build the hash. That's an enormous flat fee that barely moves as the outer grows.

Draw those two lines and they intersect around forty-five thousand rows. To the left, the nested loop is cheaper and the planner picks it. To the right, the hash join's flat fee wins and the planner switches. The planner isn't choosing an algorithm; it's just picking whichever line is lower at your N. That's the entire decision.

Now, why should you care? Because N is an estimate — and if the estimate is wrong, you land on the wrong line. Watch what that costs:

• With a 5-row outer, I forced a hash join instead of the nested loop: 204.6 ms instead of 0.074 ms. Nearly 2,750× slower — the hash join dutifully scanned all two million orders to answer a question about five customers.
• Going the other way, with a big outer I forced a nested loop instead of the hash: 373 ms instead of 29.8 ms. 12.5× slower.

Same query. Same rows. Same machine. The only variable is which algorithm ran — and that was decided by a number the planner guessed.

Time to play the planner. Below you set the shape of the problem — how big each table is, how selective the filter is, whether an index exists on the join key — then predict the plan before you're shown it. The widget runs the real cost formulas from this lesson (the same constants: 1.0, 4.0, 0.01, 0.005, 0.0025), prices every candidate, and reveals the winner with the arithmetic laid out beside it.

Try this first: start with a tiny filter (a handful of outer rows) and guess nested loop — you'll be right. Then drag the selectivity up and keep guessing nested loop, and watch the moment the cost lines cross and it becomes wrong. Then flip on stale statistics and watch the planner make a confident, well-reasoned, catastrophic decision using a number that isn't true anymore.

EXPLAIN shows you the plan the planner chose and what it expects to happen. EXPLAIN ANALYZE actually runs the query and shows you what did happen, side by side. That pairing — expected next to actual — is the most valuable diagnostic in the whole database, and reading it well is a skill you can learn in about five minutes.

Two mechanical rules first.

Read it inside-out, not top-down. A plan is a tree, printed with indentation. The most-indented nodes are the leaves — they run first and hand their rows upward to their parent. The top line is the last thing that happens, not the first. Find the deepest nodes and start there.

EXPLAIN ANALYZE really executes. On a SELECT that's harmless. On an UPDATE or DELETE it will genuinely modify your rows — so wrap it in BEGIN; ... ROLLBACK; when you're profiling a write.

Now the fields that matter:

• rows= versus actual rows= — the estimate against the truth. This is the line you read first. If the planner said rows=1 and reality was actual rows=2000, then every decision it made downstream of that node was built on a lie, and you have found your bug. A divergence beyond roughly 10× is a genuine smell; beyond 100× it's the answer.
• loops=N — how many times that node ran; the fingerprint of a nested loop's inner side. This carries the single most common misreading of a query plan, so read it twice: the actual time and actual rows printed on a looped node are per-loop averages, not totals. A node showing actual rows=10 loops=40000 produced 400,000 rows, not ten. An inner scan that looks like a harmless 0.05 ms is five entire seconds of your query if it ran a hundred thousand times. Multiply by loops before you believe any number on that line.
• Rows Removed by Filter — how much work was wasted. A scan that reads 200,000 rows and throws away 198,000 of them is telling you an index is missing (or that the planner declined the one you have).
• Buckets / Batches / Memory Usage on a hash node — if Batches is greater than 1, the hash table did not fit in work_mem and spilled to disk. That's a silent, significant slowdown with an obvious fix.
• Heap Fetches: 0 on an index-only scan — the covering index from Indexes Deep-Dive is working; the query never touched the table.
• Buffers: shared hit=… read=… (you get this with EXPLAIN (ANALYZE, BUFFERS)) — and look what just walked in. hit means the page was already in the buffer pool; read means it had to come off disk. That is precisely the buffer pool from Inside a Database: The Journey of a Write, now visible node by node. Two queries with identical plans and wildly different runtimes usually differ right here.
• Planning Time versus Execution Time — usually planning is a rounding error. If planning time is large, you're probably joining a lot of tables (see below).

The mindset, in one sentence: don't read a plan looking for something slow — read it looking for a place where the planner was surprised. The slow part is almost always downstream of the surprise.

(When a plan gets big, you don't have to do this by eye. Dump it with EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON) and paste it into a plan visualizer — explain.depesz.com and pgMustard are the usual two; they do the loops multiplication for you and colour the surprises.)

The planner's estimates come from per-column statistics. One column at a time. So what happens when a query filters on several columns at once? It multiplies the selectivities together — as if the columns had never met each other:

selectivity(a AND b) = selectivity(a) × selectivity(b)

That's the independence assumption, and it is the planner's great blind spot. Real columns are not independent. City and country aren't. Postcode and region aren't. Tenant and plan-tier aren't. Whenever two columns secretly encode the same fact, multiplying their selectivities under-counts, badly.

I built the purest version of this to measure it: three columns on the customers table with a hundred distinct values each — and identical contents, so knowing one tells you both others.

Two thousand times off — and then, after one CREATE STATISTICS, essentially perfect. Extended statistics are the planner's cure for correlated columns, and almost nobody reaches for them. If you have a query with a multi-column filter and an EXPLAIN line where estimated and actual are wildly apart, this is very often the reason.

Now an honest correction, because the folklore around this topic is worse than the truth. The story everyone tells is "bulk-load a table, query it before autovacuum analyzes it, and the planner will pick a catastrophic plan." I tried hard to reproduce that and couldn't. I analyzed a table while it was empty, loaded 500 rows into it, and re-planned — and Postgres re-derived an estimate from the table's physical size at planning time, guessed 765 rows against an actual 500, and picked exactly the right join anyway. Modern planners are more robust than the war stories suggest, and it's worth knowing that rather than repeating a scare.

The truthful version is more subtle, and more useful: a bad estimate doesn't always produce a bad plan — it leaves you one cost-tweak away from one. When the two cost lines are close together, a wrong N puts you on the wrong side of the crossing and you eat the 12×, or the 2,750×. The estimate is the foundation; sometimes a building stands on a bad foundation for years.

How bad is this in general? Bad enough to have its own famous paper. In How Good Are Query Optimizers, Really? (VLDB, 2015), Viktor Leis and colleagues built a benchmark out of real, messy, correlated movie data and pointed it at the industrial optimizers. Their findings are blunt: every serious cardinality estimator produces large errors routinely, errors of a factor of 1,000 or more are common, and — the part that matters most — the errors compound as you add joins, because a misestimate at the leaves gets multiplied all the way up the tree. On PostgreSQL 9.4, roughly 10% of their queries never finished in reasonable time, purely because of bad row estimates.

Their headline conclusion is the one to carry with you: cardinality estimation errors are the dominant cause of bad plans, while the cost model and the plan-search strategy matter comparatively little. Which means that if a query is badly planned, fiddling with random_page_cost is fiddling at the margins. The estimates are the game. (There's a 2025 follow-up paper — Still Asking: How Good Are Query Optimizers, Really? — which tells you how solved this problem is a decade on.)

Three more places the planner runs out of road:

Too many tables. Join order is its own combinatorial monster — the number of possible orderings explodes roughly factorially with the table count. Postgres searches exhaustively with dynamic programming up to geqo_threshold (12 tables by default), and past that it gives up on exhaustive search and switches to GEQO, a genetic algorithm that samples the space. So a 20-table join doesn't get the best plan; it gets a good-enough plan found by guided random search — and you may not get the same one twice.

Your query gets slow on its sixth run. This one is a genuine ghost story, and the explanation is delightful. Anything that goes through a prepared statement — which, quietly, is most things your ORM or driver sends — gets planned as a custom plan for its first five executions: re-planned each time with your actual parameter values, so it can exploit the common-value list. Then Postgres builds one generic plan, which by definition cannot know your parameter and has to assume an average selectivity, and compares its cost to the average of those five. If the generic plan isn't much worse on paper, every execution from the sixth onward uses it. On a heavily skewed column, that's the sound of a query that was fast five times and is now permanently slow — the generic plan averaged away exactly the skew the custom plans were exploiting. If you've ever chased that, the escape hatch is plan_cache_mode = force_custom_plan.

The knobs are lies about your hardware. We saw random_page_cost = 4.0 assumes a spinning disk. If you're on NVMe and the planner keeps stubbornly refusing your index, it isn't being stupid — it's costing your SSD as if it were a 2005 hard drive.

A closing word on enable_nestloop = off and friends. I used them in this lesson to force plans so we could measure the alternatives, and that is exactly what they're for: diagnosis, not treatment. They're sledgehammers that apply to every query in the session. If a plan is bad, the professional move is to fix the input the planner reasoned from — run ANALYZE, add extended statistics, raise the statistics target on a skewed column, correct random_page_cost, build the missing index — not to overrule its conclusion.

Ten minutes with a real database will do more than another page of prose. Every number below came from an actual run — predict each one before you look.

1. Do the planner's arithmetic before it does. Make a table, find its size, and compute the sequential-scan cost yourself:

2. Catch the planner guessing. Look at the summary it's actually using:

3. Break it on purpose. This is the one to actually run, because it's the lesson in miniature:

If you only do one of these, do the third. Watching rows=1 sit next to actual rows=2000 in your own terminal is the moment the planner stops being magic and starts being a colleague who is working from an out-of-date spreadsheet.

• "Cost is milliseconds." No. It's dimensionless, anchored so that one sequential page read = 1.0. A cost of 34,706 is a relative price, not a duration. Two plans with the same cost can have very different runtimes.
• "An index always beats a sequential scan." No — and the planner knows better than you here. For a query returning a big slice of the table, a sequential scan beats an index plus a storm of random heap fetches, and the planner correctly ignores your index (Indexes Deep-Dive measured it: 118 ms seq scan vs 0.23 ms index scan on the same table — different selectivity, different winner).
• "The planner knows my data." It knows a ~100-bucket histogram, a list of common values, and a distinct-count — sampled the last time ANALYZE ran. It is reasoning about a sketch.
• "EXPLAIN runs my query." Plain EXPLAIN only plans it. EXPLAIN ANALYZE really executes it — including the UPDATE. Wrap writes in a transaction and roll back.
• "Read the plan top to bottom." Read it inside-out. The most-indented node runs first; the top line runs last.
• "actual rows=10 means it produced ten rows." Only if loops=1. Looped nodes report per-loop averages — rows=10 loops=40000 is four hundred thousand rows.
• "A nested loop is the slow, naive join." It's the fastest join when the outer side is small and the inner side is indexed — 0.074 ms against a hash join's 204 ms in our run. It's only a disaster when the outer side turns out to be big.
• "Tuning the cost constants is how you fix bad plans." Mostly no. Leis and colleagues found the cost model matters far less than the cardinality estimates. If a plan is bad, suspect the estimate before you touch a knob.

• The planner is the only part of the pipeline with a choice. Parser and rewriter are mechanical; the executor just obeys. All the intelligence, and all the risk, is in the middle.
• Cost is arithmetic, not magic. Dimensionless units anchored to one sequential page read; five constants; a formula you can compute on paper — and it matched the printed number to the decimal (34,706.00 and 39,706.00).
• startup..total matters. Sorts and hash builds have to finish before emitting a row, which is why LIMIT can change the winner.
• Three joins, three shapes. Nested loop: small outer + indexed inner, cost grows linearly with the outer. Hash: big equijoins, flat cost, needs work_mem (watch for Batches > 1). Merge: inputs already sorted, handles ranges and huge data gracefully.
• The tipping point is just two lines crossing. Nested loop rises with N; hash is flat. The planner picks the lower line — and landing on the wrong one cost us 2,750× in one direction and 12.5× in the other.
• N is an estimate, and the estimate is the weak link. The planner reads a summary of your data, not your data. Its independence assumption made it guess rows=1 where the truth was 2000 — a 2,000× miss, fixed with one CREATE STATISTICS.
• Read EXPLAIN for surprise, not for slowness. Estimated vs actual rows is the first line you check; the slow part is almost always downstream of where the planner was wrong.
• Fix the input, not the conclusion. enable_nestloop=off is a diagnostic, not a cure. ANALYZE, extended statistics, an honest random_page_cost, the missing index — those are the cures.

This is the last lesson of Database Internals, and it's worth noticing that a single EXPLAIN output now contains every room we've visited.

That Seq Scan is reading the heap pages through the buffer pool from Inside a Database: The Journey of a Write. The Index Scan beside it is descending the three-level B-tree from B-Trees & B+ Trees — and if you'd chosen a write-optimized engine instead, it would be merging sorted runs from LSM Trees & SSTables. The Heap Fetches: 0 on an index-only scan is the covering index from Indexes Deep-Dive paying off. The rows the scan quietly steps over are the dead tuples from MVCC: Readers Don't Block Writers, waiting for a vacuum. And the whole thing is durable the instant it commits because of the log from WAL & Durability: Why Committed Data Survives.

Six lessons ago, a database was a box you sent SQL to. Now it's a machine you can reason about: pages and a buffer pool, a tree that stays three levels deep, a log that makes a promise, versions instead of locks, and an optimizer doing arithmetic over a summary of your data. When a query is slow, you no longer guess — you ask it what it did, and you know how to read the answer.

Next up is the checkpoint for this section, where you'll make the calls yourself.