Gowtham Potureddi

Posted on Sep 5

How Query Optimizers Work: Statistics, Cardinality & Join Order

#python #sql #interview #dataengineering

The query optimizer is the piece of your database that turns a declarative SELECT into a concrete, executable plan — and it is the single component that decides whether a query returns in three milliseconds or three minutes against the exact same data. You wrote what rows you want; the optimizer decides how to fetch them: which index to use, which table to scan first, which join order to walk, and which physical join algorithm (nested loop, hash, or merge) to run at each step. Every one of those decisions is driven by two numbers the planner has to guess before a single row is read — the estimated number of rows a step will produce (its cardinality estimation) and the estimated cost of producing them — and when those guesses are wrong, the plan is wrong, no matter how clean your SQL looks.

This guide is the walkthrough you wished existed the first time an interviewer slid an EXPLAIN ANALYZE output across the table and asked "why is this slow, and how would you fix it?" It opens the black box in layers: the table statistics the planner collects with ANALYZE (histograms, most-common-values, distinct-value counts), the selectivity math that converts those statistics into a row estimate, the cost-based optimizer's search through the factorial space of join orders, and finally how to read the execution plan a real EXPLAIN ANALYZE prints so you can tell a good plan from a bad one at a glance. Each section pairs a teaching block with a Solution-Tail interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works. All examples are PostgreSQL, but the mental model carries over to MySQL, SQL Server, Oracle, and every other cost-based engine.

When you want hands-on reps immediately after reading, drill the query optimization practice library →, sharpen your estimation intuition on the cardinality practice library →, and rehearse the fundamentals on the SQL practice library →.

On this page

Why the optimizer is the most important black box in your database
Statistics — histograms, MCVs, n_distinct
Cardinality estimation — the make-or-break guess
Join order and join algorithms
Cost models and reading EXPLAIN ANALYZE
Cheat sheet — query optimizer recipes
Frequently asked questions
Practice on PipeCode

1. Why the optimizer is the most important black box in your database

Declarative SQL states the goal; the query optimizer chooses the physical plan that reaches it cheapest

The one-sentence invariant: a query optimizer takes a parsed, rewritten SQL statement and searches a space of semantically-equivalent physical execution plans — different scan methods, join algorithms, and join orders — estimating the cost of each from table statistics and cardinality estimates, and returns the single cheapest plan it can find in a bounded amount of planning time. SQL is declarative: you describe the result set you want, never the procedure to compute it. That gap between "what" and "how" is exactly the space the optimizer lives in, and everything else in this article — statistics, cardinality, join order, cost — is machinery in service of picking one plan out of that space.

The four-stage pipeline every query walks.

Parse. The raw SQL text is tokenized and turned into a parse tree. Syntax errors die here. The parser knows grammar, not tables — it does not yet know whether orders exists.
Analyze / rewrite. The parse tree is resolved against the catalog (tables, columns, types) and rewritten: views are inlined, rules applied, subqueries sometimes pulled up into joins, constant expressions folded. The output is a query tree — still logical, still declarative.
Plan / optimize. The planner (the optimizer) enumerates physical plans for the query tree, costs each, and picks the cheapest. This is where scan methods, join algorithms, and join order are decided. The output is a plan tree of executable nodes.
Execute. The executor walks the plan tree, pulling rows through it node by node (the classic Volcano / iterator model), and streams the result to the client. The plan is fixed at this point; the executor does not re-plan mid-flight.

Cost-based vs rule-based — why modern engines are cost-based.

Rule-based optimization (RBO). The legacy approach: a fixed priority list of heuristics ("if an index exists on the predicate column, use it; prefer index access over full scan"). Deterministic and simple, but blind to data distribution — it will happily use an index to fetch 90% of a table, which is far slower than a sequential scan.
Cost-based optimization (CBO). The modern approach used by PostgreSQL, MySQL 8+, SQL Server, and Oracle: assign every candidate plan a numeric cost estimate derived from statistics, then pick the minimum. CBO can decide that a sequential scan beats an index scan for this predicate on this data because it costed both.
Why data distribution decides. The same query, same schema, same indexes can want two completely different plans depending on how many rows the predicate actually matches. A predicate matching 5 rows wants an index; the same predicate matching 5 million rows wants a sequential scan. Only a cost-based optimizer, fed good statistics, gets this right.

The two numbers that decide everything: rows and cost.

Estimated rows (cardinality). For every node in the plan tree, the planner estimates how many rows the node will emit. This drives every downstream decision — the row estimate of a scan feeds the cost of the join above it, whose row estimate feeds the join above that. Errors compound multiplicatively up the tree.
Estimated cost. An abstract, unitless number (roughly "number of sequential page fetches") built from the row estimate plus per-page and per-tuple cost constants. Lower is better. The planner never measures real time during planning — it only compares these estimates.
The failure mode. Because the plan is chosen from estimates, a bad estimate produces a bad plan even when the SQL and indexes are perfect. Ninety percent of "why is this query slow" incidents trace back to a cardinality misestimate, not a missing index.

What interviewers listen for.

Do you say "the optimizer picks a plan from estimates, not measurements" — the framing that explains every bad plan? — senior signal.
Do you distinguish cost-based from rule-based and name data distribution as why CBO wins? — required answer.
Do you name the four stages (parse → rewrite → plan → execute) without prompting? — senior signal.
Do you reach for EXPLAIN ANALYZE and compare estimated vs actual rows as your first diagnostic move? — required answer.
Do you describe the plan as "a tree of physical operators the executor pulls rows through" rather than as "the query"? — senior signal.

Worked example — the same query, two plans, driven by selectivity

Detailed explanation. The clearest way to feel why the optimizer matters is to hold the query constant and change only how many rows the predicate matches. The planner will flip between an index scan and a sequential scan purely on the estimated row count — proving the plan is a function of data distribution, not of the SQL text.

Table. orders(id, customer_id, status, total_cents, created_at) on Postgres 16, 10 million rows.
Index. idx_orders_status ON orders(status).
Two predicates. status = 'cancelled' (rare — 5,000 rows) versus status = 'delivered' (common — 8,000,000 rows).

Question. For each predicate, which access method does the optimizer pick and why?

Input.

Predicate	Matching rows	Fraction of table	Intuitive best access
`status = 'cancelled'`	5,000	0.05%	index scan (few rows)
`status = 'delivered'`	8,000,000	80%	sequential scan (most rows)

Code.

-- Rare value: the planner expects few rows, uses the index
EXPLAIN
SELECT * FROM orders WHERE status = 'cancelled';

-- Common value: the planner expects most of the table, scans sequentially
EXPLAIN
SELECT * FROM orders WHERE status = 'delivered';

-- Plan for status = 'cancelled'
Index Scan using idx_orders_status on orders  (cost=0.43..412.55 rows=5000 width=48)
  Index Cond: (status = 'cancelled'::text)

-- Plan for status = 'delivered'
Seq Scan on orders  (cost=0.00..204622.00 rows=8000000 width=48)
  Filter: (status = 'delivered'::text)

Step-by-step explanation.

Both queries are syntactically identical except for the compared constant. The optimizer costs each independently using the statistics for the status column.
For 'cancelled', the planner estimates 5,000 rows out of 10 million. Fetching 5,000 rows via the index means ~5,000 random-ish page lookups — cheap relative to reading the whole table. Index scan wins.
For 'delivered', the planner estimates 8,000,000 rows — 80% of the table. Using the index here would mean 8 million random page fetches, each far more expensive than a sequential read. A Seq Scan that reads every page once, in physical order, is dramatically cheaper. The index is ignored on purpose.
Notice the rows= value in each plan: it is the cardinality estimate, and it is what tipped the decision. Change that estimate (via stale statistics) and the planner flips to the wrong method.
This is the whole thesis of cost-based optimization in one example: there is no universally "right" access method — only the cheapest one for the estimated row count on this data.

Output.

Predicate	Estimated rows	Chosen plan	Reason
`status = 'cancelled'`	5,000	Index Scan	few matches → random lookups cheap
`status = 'delivered'`	8,000,000	Seq Scan	most of table → sequential read cheaper

Rule of thumb. "Should I use the index?" has no answer without the row estimate. The optimizer already asks that question for you every time — your job is to make sure the statistics feeding it are honest.

Worked example — what the planner does with a three-table join

Detailed explanation. With one table the optimizer only picks a scan method. The combinatorics explode the moment you join. For a three-table join, the planner must choose a join order, a join algorithm per join, and a scan method per table — dozens of candidate plans for a query that looks trivial. Walk the space it searches.

Query. orders ⋈ customers ⋈ line_items, filtered to one region and one date range.
Decisions per plan. join order (which pair to join first), join algorithm at each of the two joins, and access method for each of the three tables.
The point. Even here the search space is large; the planner prunes it with dynamic programming rather than brute force (section 4).

Question. Enumerate the kinds of decisions the optimizer makes for this three-table join and why the join order is the highest-leverage one.

Input.

Decision	Options
Join order	`(o⋈c)⋈l`, `(o⋈l)⋈c`, `(c⋈l)⋈o`, …
Join algorithm (×2)	nested loop, hash join, merge join
Scan method (×3)	seq scan, index scan, bitmap heap scan

Code.

EXPLAIN
SELECT c.name, o.id, li.sku
FROM   orders      o
JOIN   customers   c  ON c.id = o.customer_id
JOIN   line_items  li ON li.order_id = o.id
WHERE  c.region = 'EU'
  AND  o.created_at >= DATE '2026-01-01';

Hash Join  (cost=1120.00..48210.30 rows=42000 width=64)
  Hash Cond: (li.order_id = o.id)
  ->  Hash Join  (cost=430.00..9800.10 rows=21000 width=40)
        Hash Cond: (o.customer_id = c.id)
        ->  Index Scan using idx_orders_created_at on orders o  (cost=0.43..7200.00 rows=60000 width=24)
              Index Cond: (created_at >= '2026-01-01'::date)
        ->  Hash  (cost=300.00..300.00 rows=7000 width=24)
              ->  Seq Scan on customers c  (cost=0.00..300.00 rows=7000 width=24)
                    Filter: (region = 'EU'::text)
  ->  Seq Scan on line_items li  (cost=0.00..30000.00 rows=2000000 width=32)

Step-by-step explanation.

The planner chose to join orders and customers first (the inner Hash Join), then join the result to line_items. That ordering is a choice among several — it was picked because joining the two smaller, filtered inputs first keeps the intermediate result (21,000 rows) small.
Each join is a Hash Join: the smaller side is built into an in-memory hash table, the larger side is probed against it. The planner picked hash over nested loop because both inputs are large after filtering — nested loop would re-scan the inner side per outer row.
Access methods differ per table: orders uses an index scan on created_at (the date predicate is selective), customers uses a sequential scan with a filter (the region predicate is not selective enough to beat a scan on a small table), and line_items is scanned sequentially because the whole table participates.
The rows= on the top node (42,000) is the final cardinality estimate; the rows= on each child feeds the cost of the parent. A misestimate low in the tree — say customers was actually 700,000 EU rows, not 7,000 — would poison every cost above it.
Join order is the highest-leverage decision because it controls the size of the intermediate results, and intermediate size dominates the cost of everything downstream. Get the order wrong and you materialize millions of rows only to throw most of them away.

Output.

Node	Estimated rows	Role
Seq Scan customers (EU)	7,000	build side of inner join
Index Scan orders (date)	60,000	probe side of inner join
Inner Hash Join	21,000	intermediate result
Seq Scan line_items	2,000,000	probe side of outer join
Outer Hash Join	42,000	final result

Rule of thumb. In a multi-table join, the plan you get is dominated by (a) the join order and (b) the cardinality estimate of each input. Read those two things first when a join plan looks slow; the scan methods are secondary.

SQL Interview Question on how the optimizer chooses a plan

A senior interviewer often opens with: "You run the same query on staging and production. Staging returns instantly; production takes 40 seconds even though production has more hardware. Same schema, same indexes, same query. Walk me through how the query optimizer could produce two different plans, what you'd inspect first, and how you'd confirm the root cause."

Solution Using EXPLAIN ANALYZE to compare estimated vs actual rows

-- Step 1 — get the plan AND the reality on the slow environment
EXPLAIN (ANALYZE, BUFFERS, VERBOSE)
SELECT o.id, o.total_cents
FROM   orders o
JOIN   customers c ON c.id = o.customer_id
WHERE  c.region = 'EU'
  AND  o.status = 'pending';

-- Production plan (slow): estimate says 50 rows, reality is 480,000
Nested Loop  (cost=0.86..812.40 rows=50 width=16)
             (actual time=0.13..39584.10 rows=480000 loops=1)
  ->  Index Scan using idx_customers_region on customers c
        (cost=0.43..210.00 rows=50 width=8)
        (actual time=0.05..44.2 rows=95000 loops=1)
        Index Cond: (region = 'EU'::text)
  ->  Index Scan using idx_orders_customer_id on orders o
        (cost=0.43..12.00 rows=1 width=16)
        (actual time=0.30..0.41 rows=5 loops=95000)
        Index Cond: (customer_id = c.id)
        Filter: (status = 'pending'::text)
Planning Time: 0.4 ms
Execution Time: 39712.6 ms

-- Step 2 — the fix: refresh statistics so the estimate matches reality
ANALYZE customers;
ANALYZE orders;

-- Step 3 — re-plan; a correct estimate flips the join to a hash join
EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, o.total_cents
FROM   orders o
JOIN   customers c ON c.id = o.customer_id
WHERE  c.region = 'EU'
  AND  o.status = 'pending';

Step-by-step trace.

Input — the production plan above, where every node prints rows= (estimate) next to actual … rows= (reality):

The outer Index Scan on customers estimated rows=50 but produced rows=95000 — a 1,900× underestimate. Production statistics on customers.region are stale; the planner thinks 'EU' is rare when it is common.
Because the planner believed only 50 customers matched, it chose a Nested Loop: "for each of ~50 customers, look up their orders." Nested loop is only cheap when the outer side is tiny.
Reality: 95,000 customers matched, so the inner Index Scan on orders ran 95,000 times (loops=95000), each loop doing an index descent. That is 95,000 × ~5 rows = 480,000 inner rows, executed as hundreds of thousands of random lookups.
The actual time on the root balloons to 39,584 ms — the loops are the smoking gun. The plan is not "wrong SQL"; it is a correct plan for the wrong estimate.
ANALYZE recollects statistics; now the planner estimates ~95,000 matching customers, costs the nested loop as catastrophically expensive, and switches to a Hash Join that builds customers once and probes orders once. Final result — execution drops from ~40 s to well under a second.

Output:

Metric	Before ANALYZE	After ANALYZE
Estimated rows (customers)	50	~95,000
Actual rows (customers)	95,000	95,000
Join algorithm chosen	Nested Loop	Hash Join
Inner-side loops	95,000	1
Execution time	~39,700 ms	< 1,000 ms

Why this works — concept by concept:

Estimate versus actual — EXPLAIN ANALYZE prints both the planner's rows= guess and the executor's real actual … rows=. Any large gap is the root cause of a bad plan; you read the tree looking for the first node where the two diverge.
Loops on the inner side — a Nested Loop re-executes its inner node once per outer row. loops=95000 means the "cheap" inner index scan actually ran 95,000 times. High loop counts on a nested loop are the classic signature of an underestimated outer input.
Stale statistics — the planner is only as good as the last ANALYZE. A bulk load or a shifting data distribution silently invalidates the estimates; the same query then plans differently on two databases that "look identical."
Join-algorithm flip — correcting the estimate changes the cost ranking, and the planner switches from nested loop to hash join on its own. You did not rewrite the query; you fixed the input to the optimizer.
Cost — the fix (ANALYZE) is O(sample) — Postgres reads a bounded random sample, not the whole table. The bad plan was O(outer × inner-lookup); the good plan is O(build + probe). Same query, two orders of magnitude apart, decided entirely by one estimate.

SQL
Topic — optimization
Query optimization and plan-reading problems

Practice →

SQL Topic — sql SQL problems on planner behaviour

Practice →

2. Statistics — histograms, MCVs, n_distinct

`ANALYZE` samples your data into histograms, most-common-values, and distinct counts — the raw material every estimate is built from

The mental model in one line: table statistics are a compact, sampled summary of each column's data distribution — a distinct-value count, a null fraction, a list of the most common values with their frequencies, and an equi-depth histogram of the rest — that ANALYZE collects into the pg_statistic catalog, and the planner reads these summaries (never the table itself) to estimate how many rows any predicate will match. Every cardinality estimate in every plan traces back to these numbers; if they are missing or stale, the optimizer is guessing blind, and no index or query rewrite will save you.

$Iconographic statistics diagram — an ANALYZE sampler reading a table and building a histogram plus a most-common-values list, with n_distinct and null_frac chips, feeding the planner.$

What ANALYZE collects per column.

null_frac. The fraction of the column that is NULL. Used to discount row estimates for IS NOT NULL predicates and to reason about outer joins.
n_distinct. The number of distinct values. A positive integer means an absolute count; a negative value between -1 and 0 means "distinct values scale with table size" (e.g. -1 = every value unique, like a primary key). This drives equality selectivity for values not in the MCV list.
most_common_vals (MCVs) and most_common_freqs. Two parallel arrays: the most frequently occurring values and their observed frequencies. For any value in this list, the planner knows its selectivity exactly (as sampled), not by approximation.
histogram_bounds. An equi-depth histogram of the non-MCV values: a sorted list of boundaries dividing the remaining data into buckets that each hold roughly the same number of rows. Drives range predicate (<, >, BETWEEN) selectivity.
correlation. How closely the physical row order on disk matches the sorted order of the column (−1 to +1). Near ±1 means an index range scan reads nearly-sequential pages (cheap); near 0 means random I/O (expensive). This is why random_page_cost and correlation together decide index viability.

Where statistics live and how you inspect them.

pg_statistic. The raw catalog — cryptic, internal, keyed by stakind slots. You rarely read it directly.
pg_stats. A human-readable view over pg_statistic: one row per column with null_frac, n_distinct, most_common_vals, most_common_freqs, histogram_bounds, and correlation as readable columns. This is your window into what the planner sees.
The default sample. ANALYZE reads a random sample of 300 × default_statistics_target rows (default target = 100, so ~30,000 rows) — not the whole table. Statistics are an estimate of an estimate; larger statistics_target = bigger sample = more histogram buckets and MCV slots = better accuracy at the cost of longer ANALYZE and slower planning.

How statistics go stale — the silent plan-killer.

Bulk loads and backfills. Insert 50 million rows and the planner still believes the pre-load distribution until ANALYZE runs. Every plan on that table is now built on fiction.
Distribution drift. A status column that was 5% 'shipped' at launch becomes 60% 'shipped' a year later. Old MCV frequencies mislead every selectivity estimate for that value.
Autovacuum's analyze pass. Postgres runs ANALYZE automatically when the number of changed rows exceeds autovacuum_analyze_scale_factor × table_rows + autovacuum_analyze_threshold (default 10% + 50 rows). For large tables 10% can be millions of rows — meaning stats can lag reality badly between auto-analyzes. Lower the scale factor on volatile large tables.
After a restore or major version upgrade. pg_upgrade does not carry statistics forward; you must ANALYZE the whole cluster or the first post-upgrade plans are catastrophic.

Common interview probes on statistics.

"What does ANALYZE actually store?" — required answer: null_frac, n_distinct, MCVs + freqs, histogram_bounds, correlation.
"Why did a good plan suddenly go bad after a data load?" — stale statistics; the estimate no longer matches the data.
"What is the difference between MCVs and the histogram?" — MCVs handle skewed/common discrete values exactly; the histogram handles the long tail and ranges.
"How would you make estimates more accurate on a wide, skewed column?" — raise statistics_target for that column, or add extended statistics for correlated columns.

Worked example — reading `pg_stats` for a skewed column

Detailed explanation. Before you can reason about a bad estimate you have to see what the planner sees. pg_stats exposes exactly that. Walk through reading it for a skewed status column and translate each field into what the optimizer will do with it.

Column. orders.status — heavily skewed: most orders are 'delivered', a few are 'cancelled'.
Goal. Read the MCV list and histogram and predict the selectivity the planner will assign to two predicates.

Question. Given the pg_stats row for orders.status, what selectivity will the planner compute for status = 'delivered' and for status = 'refunded' (a value not in the MCV list)?

Input.

pg_stats field	Value
`null_frac`	0.0
`n_distinct`	6
`most_common_vals`	`{delivered, pending, shipped, cancelled}`
`most_common_freqs`	`{0.80, 0.10, 0.06, 0.02}`
(remaining mass)	0.02 spread over 2 non-MCV values

Code.

-- Inspect exactly what the planner will use
SELECT null_frac, n_distinct, most_common_vals, most_common_freqs
FROM   pg_stats
WHERE  tablename = 'orders' AND attname = 'status';

-- Predicate A: a value that IS in the MCV list
EXPLAIN SELECT * FROM orders WHERE status = 'delivered';

-- Predicate B: a value that is NOT in the MCV list
EXPLAIN SELECT * FROM orders WHERE status = 'refunded';

-- Predicate A (delivered): selectivity read straight from MCV freq = 0.80
Seq Scan on orders  (cost=0.00..204622.00 rows=8000000 width=48)
  Filter: (status = 'delivered'::text)

-- Predicate B (refunded): not in MCVs, estimated from leftover mass
Index Scan using idx_orders_status on orders  (cost=0.43..8300.0 rows=100000 width=48)
  Index Cond: (status = 'refunded'::text)

Step-by-step explanation.

For status = 'delivered', the value appears in most_common_vals at position 1, with frequency 0.80. The planner reads that frequency directly: selectivity = 0.80, estimated rows = 0.80 × 10,000,000 = 8,000,000. No approximation — this is the sampled truth.
For status = 'refunded', the value is not in the MCV list. The planner cannot read a frequency, so it falls back to the distribution of non-MCV values: leftover mass (1 − sum of MCV freqs = 0.02) divided across the non-MCV distinct values (n_distinct minus MCV count = 6 − 4 = 2). Selectivity ≈ 0.02 / 2 = 0.01, estimated rows = 100,000.
This split — exact for common values, averaged for rare ones — is why MCVs exist. Without them, the planner would assume uniform distribution (each of 6 values = 1/6 of the table), massively overestimating 'cancelled' and underestimating 'delivered'.
The estimate directly picks the access method: 8,000,000 rows → seq scan; 100,000 rows → index scan. The statistics, not the query, chose the plan.
If 'refunded' later becomes common (say a product recall spikes refunds to 30% of orders) but ANALYZE has not re-run, the planner still thinks it is 1% — and every refund query gets the wrong plan until statistics refresh.

Output.

Predicate	Source of estimate	Selectivity	Estimated rows
`status = 'delivered'`	MCV frequency (0.80)	0.80	8,000,000
`status = 'refunded'`	leftover mass / non-MCV distinct	0.01	100,000

Rule of thumb. When an estimate looks wrong, SELECT * FROM pg_stats for the column first. If the value is skewed and missing from most_common_vals, raise that column's statistics_target so more values land in the MCV list.

Worked example — range selectivity from the histogram

Detailed explanation. MCVs handle equality on discrete values; ranges are handled by the equi-depth histogram. Each histogram bucket holds roughly the same fraction of rows, so a range predicate's selectivity is "how many buckets does the range span." Walk through a date-range estimate.

Column. orders.created_at, one year of data, histogram with 100 equi-depth buckets (each ≈ 1% of rows).
Predicate. created_at >= '2026-10-01' on a table where that date sits near the 75th bucket boundary.

Question. How does the planner estimate the selectivity of created_at >= '2026-10-01' from the histogram?

Input.

Histogram fact	Value
Bucket count	100 (each ≈ 1% of rows)
Total rows	10,000,000
`'2026-10-01'` falls at	≈ 75th boundary
Fraction of data ≥ that point	≈ 0.25

Code.

-- The histogram bounds the planner uses for ranges
SELECT histogram_bounds
FROM   pg_stats
WHERE  tablename = 'orders' AND attname = 'created_at';

EXPLAIN
SELECT * FROM orders WHERE created_at >= DATE '2026-10-01';

Bitmap Heap Scan on orders  (cost=... rows=2500000 width=48)
  Recheck Cond: (created_at >= '2026-10-01'::date)
  ->  Bitmap Index Scan on idx_orders_created_at  (cost=... rows=2500000)
        Index Cond: (created_at >= '2026-10-01'::date)

Step-by-step explanation.

The histogram divides created_at into 100 buckets, each holding ~1% of rows by construction (equi-depth, not equi-width — busy periods get narrower buckets, quiet periods wider ones).
The planner locates '2026-10-01' within the sorted bucket boundaries. It sits at roughly the 75th boundary, so ~75% of rows are below it and ~25% are at or above it.
Selectivity for >= '2026-10-01' is therefore ≈ 0.25, giving an estimate of 0.25 × 10,000,000 = 2,500,000 rows. For a value landing inside a bucket, the planner interpolates linearly across that bucket's width for extra precision.
Because 25% of the table is a lot, the planner chose a Bitmap Heap Scan — a hybrid that uses the index to build a bitmap of matching pages, then reads those heap pages in physical order. It is the middle ground between a plain index scan (good for few rows) and a seq scan (good for most rows).
Equi-depth histograms are robust to skew in ranges: even if orders cluster around holidays, each bucket still holds ~1% of rows, so range estimates stay honest. This is why the histogram is a separate mechanism from MCVs.

Output.

Query fragment	Mechanism	Selectivity	Estimated rows
`created_at >= '2026-10-01'`	histogram bucket position	≈ 0.25	2,500,000
chosen access method	(from estimate)	—	Bitmap Heap Scan

Rule of thumb. Range predicates lean on the histogram; equality on skewed values leans on MCVs. If range estimates are off, more histogram buckets (higher statistics_target) is the lever; if equality estimates on rare values are off, more MCV slots is the lever — and both are the same knob.

Worked example — extended statistics for correlated columns

Detailed explanation. The planner assumes columns are independent by default: the selectivity of A = x AND B = y is estimated as sel(A=x) × sel(B=y). When columns are correlated, that multiplication is wildly wrong. Extended statistics (CREATE STATISTICS) teach the planner about the correlation. Walk through the classic city/postal_code case.

Columns. addresses(city, postal_code) — perfectly correlated: a postal code implies its city.
Bad estimate. WHERE city = 'Berlin' AND postal_code = '10115' — the planner multiplies two small selectivities and estimates almost no rows, when in reality the postal code alone already implies Berlin.

Question. Fix the underestimate on WHERE city = 'Berlin' AND postal_code = '10115' using extended statistics.

Input.

Fact	Value
`sel(city = 'Berlin')`	0.02
`sel(postal_code = '10115')`	0.0005
Independent estimate (product)	0.00001 → ~10 rows
Actual matching rows	~5,000

Code.

-- Before: planner multiplies selectivities under the independence assumption
EXPLAIN
SELECT * FROM addresses WHERE city = 'Berlin' AND postal_code = '10115';
-- rows=10  (catastrophic underestimate; picks a nested loop upstream)

-- Teach the planner the columns are correlated
CREATE STATISTICS stx_addr_city_zip (dependencies, ndistinct)
  ON city, postal_code FROM addresses;

ANALYZE addresses;

-- After: functional-dependency stats correct the estimate
EXPLAIN
SELECT * FROM addresses WHERE city = 'Berlin' AND postal_code = '10115';
-- rows=5000  (matches reality)

-- Before
Index Scan ... rows=10   (planner thinks the pair is ultra-rare)
-- After CREATE STATISTICS + ANALYZE
Bitmap Heap Scan ... rows=5000   (dependency: postal_code -> city)

Step-by-step explanation.

By default the planner has no idea postal_code determines city. It computes sel(city='Berlin' AND postal='10115') = sel(city) × sel(postal) = 0.02 × 0.0005 = 0.00001, estimating ~10 rows.
Reality: postal code '10115' is always in Berlin, so adding city = 'Berlin' filters out nothing — the true selectivity equals sel(postal_code='10115') alone ≈ 5,000 rows. The independence assumption overcounted the "extra" filtering by 500×.
CREATE STATISTICS ... (dependencies) records functional dependencies between the columns. After ANALYZE, the planner knows postal_code → city and stops multiplying in the redundant city selectivity.
The ndistinct kind additionally records the number of distinct combinations of the columns, which fixes GROUP BY city, postal_code cardinality estimates (otherwise estimated as n_distinct(city) × n_distinct(postal_code), another independence error).
With the corrected estimate the upstream plan changes — a downstream join that was going to nested-loop over "10 rows" now correctly plans for 5,000, avoiding the same loops-blowup we saw in section 1.

Output.

Stage	Estimate mechanism	Estimated rows	Actual rows
Before	independence (product of selectivities)	10	5,000
After `CREATE STATISTICS`	functional dependency	5,000	5,000

Rule of thumb. Whenever two predicated columns are correlated (city/zip, country/currency, brand/category), the independence assumption underestimates the AND. Reach for CREATE STATISTICS (dependencies, ndistinct) — it is the single most effective fix for correlated-column misestimates.

SQL Interview Question on table statistics

A senior interviewer might ask: "A dashboard query was fast for months, then after a large monthly data import it started timing out — no code changed, no index dropped. Walk me through why statistics are the most likely culprit, how you'd confirm it from pg_stats, and how you'd stop it recurring after every import."

Solution Using ANALYZE, statistics_target tuning, and autovacuum settings

-- Step 1 — confirm the stats are stale: compare last analyze vs the import time
SELECT relname,
       last_analyze,
       last_autoanalyze,
       n_live_tup,
       n_mod_since_analyze          -- rows changed since the last analyze
FROM   pg_stat_user_tables
WHERE  relname = 'orders';

-- Step 2 — see what the planner currently believes about the skewed column
SELECT attname, n_distinct, most_common_vals, most_common_freqs
FROM   pg_stats
WHERE  tablename = 'orders' AND attname = 'status';

-- Step 3 — refresh statistics immediately
ANALYZE orders;

-- Step 4 — raise resolution on the skewed / filtered columns
ALTER TABLE orders ALTER COLUMN status        SET STATISTICS 500;
ALTER TABLE orders ALTER COLUMN created_at     SET STATISTICS 500;
ANALYZE orders;

-- Step 5 — make autovacuum analyze this large table far more often
ALTER TABLE orders SET (
  autovacuum_analyze_scale_factor = 0.02,   -- analyze after 2% churn, not 10%
  autovacuum_analyze_threshold    = 5000
);

-- Step 6 — belt-and-braces: ANALYZE at the end of the import job itself
-- (run inside the ETL DAG immediately after the COPY / INSERT completes)
ANALYZE orders;

Step-by-step trace.

Input — pg_stat_user_tables and pg_stats snapshots taken right after the failing import:

n_mod_since_analyze reads 42,000,000 while last_autoanalyze is dated before the import — proof the planner is running on pre-import statistics.
pg_stats shows most_common_freqs for status still reflect the old distribution (e.g. 'delivered' at 0.80) even though the import shifted the mix. Every selectivity for status is now wrong.
ANALYZE orders (step 3) recollects the sample; most_common_vals/freqs and histogram_bounds update to the post-import reality. The next plan is costed correctly.
Raising SET STATISTICS 500 (step 4) grows the MCV list and histogram from ~100 to ~500 slots, so more skewed values are tracked exactly and range estimates get finer — worthwhile on the columns that actually appear in WHERE clauses.
Lowering autovacuum_analyze_scale_factor to 0.02 (step 5) means autovacuum re-analyzes after 2% churn instead of 10%; on a 400M-row table that is the difference between analyzing after 8M vs 40M changed rows. Step 6 removes the race entirely by analyzing inside the import job. Final result — the dashboard query returns to sub-second and stays there across future imports.

Output:

Signal	Before fix	After fix
`last_analyze` vs import	stale (pre-import)	fresh (post-import)
MCV / histogram slots	~100	~500
Autoanalyze trigger	10% churn (~40M rows)	2% churn (~8M rows)
Estimate vs actual on `status`	~10× off	within noise
Dashboard latency	timeout	sub-second

Why this works — concept by concept:

Change tracking (n_mod_since_analyze) — Postgres counts modified rows since the last analyze; comparing it to the import size proves the stats are stale without guessing.
ANALYZE resample — one ANALYZE re-reads the bounded random sample and rewrites pg_statistic, instantly realigning every estimate with the current distribution. It is cheap relative to the query it fixes.
Statistics target — SET STATISTICS 500 trades a slightly slower ANALYZE and planning step for many more MCV slots and histogram buckets, which is the correct lever for skewed, frequently-filtered columns.
Autovacuum scale factor — the default 10% threshold is far too lax for large tables; lowering the scale factor keeps stats fresh automatically between manual runs.
Cost — ANALYZE is O(sample size), independent of table size; the recurring win is eliminating an O(rows) timeout every month. Freshening statistics is the highest return-on-effort fix in the entire optimizer toolkit.

SQL
Topic — database
Database internals and statistics problems

Practice →

SQL Topic — sql SQL problems on selectivity and filtering

Practice →

3. Cardinality estimation — the make-or-break guess

Selectivity turns statistics into a row estimate, and that estimate — right or wrong — decides every plan above it

The mental model in one line: cardinality estimation is the process of converting a predicate plus the column statistics into an estimated number of output rows, via a selectivity (the fraction of rows a predicate keeps) that the planner multiplies against the input row count — and because the estimate at each node becomes the input to the cost model of the node above it, a single misestimate low in a join tree compounds into a wildly wrong plan for the whole query. Cardinality estimation is the beating heart of the optimizer; statistics are its fuel and cost is its output, but this is where the accuracy is won or lost.

Selectivity — the fraction that survives a predicate.

Definition. Selectivity is a number in [0, 1]: the fraction of input rows a predicate is expected to keep. Estimated output rows = selectivity × input rows. A selectivity of 0.01 on a million-row input estimates 10,000 output rows.
Equality (col = const). If the constant is an MCV, selectivity = its stored frequency. Otherwise, selectivity ≈ (1 − sum(mcv_freqs)) / (n_distinct − num_mcvs) — the leftover mass averaged over the non-MCV distinct values.
Range (col < / > / BETWEEN). Selectivity comes from the histogram — the fraction of buckets (with linear interpolation inside the boundary bucket) that the range spans.
Inequality and IS NULL. col <> const = 1 − sel(col = const); col IS NULL = null_frac; col IS NOT NULL = 1 − null_frac.

Combining predicates — where the independence assumption bites.

Conjunction (A AND B). The planner assumes independence: sel(A AND B) = sel(A) × sel(B). Correct only when A and B are statistically independent; for correlated columns it underestimates (the AND keeps more rows than the product suggests).
Disjunction (A OR B). sel(A OR B) = sel(A) + sel(B) − sel(A) × sel(B) (inclusion–exclusion), again under independence.
Join selectivity. For an equi-join t1.x = t2.y, the planner estimates output rows ≈ rows(t1) × rows(t2) / max(n_distinct(x), n_distinct(y)). This assumes uniform distribution of join keys — skewed keys (a few customers with millions of orders) break it.
The fix. CREATE STATISTICS for correlated single-table columns; for join skew, sometimes a rewrite or a manually chosen join order is the only lever.

Why estimates go wrong — the five classic causes.

Correlated columns. The independence assumption multiplies selectivities that should not be multiplied (section 2's city/zip). Underestimates conjunctions.
Skewed join keys. Uniform-distribution join math underestimates when a handful of keys dominate (celebrity users, a mega-merchant).
Functions and expressions on columns. WHERE lower(email) = 'x' or WHERE created_at::date = '...' — the planner has no statistics on the expression, so it falls back to a default guess (often 0.5% for equality). Fix with an expression index (which gets its own statistics) or extended/expression statistics.
Stale or missing statistics. Covered in section 2 — the estimate is honest but based on obsolete data.
Multi-join error compounding. Each join's output estimate feeds the next; a 10× error at the bottom becomes 10× → 100× → 1000× as it propagates up a deep join tree. This is why deep joins are where estimation pain concentrates.

Common interview probes on cardinality estimation.

"What is selectivity?" — required answer: the fraction of rows a predicate keeps; estimate = selectivity × input rows.
"Why does the planner underestimate A = x AND B = y for correlated columns?" — the independence assumption multiplies selectivities.
"Why does WHERE lower(email) = … get a bad estimate?" — no statistics on the expression; default guess. Fix with an expression index.
"Why are deep joins where estimates hurt most?" — errors compound multiplicatively up the tree.

Worked example — equality selectivity from n_distinct

Detailed explanation. The most common estimate in any workload is equality on a column value not in the MCV list. Walk through the exact arithmetic the planner does so you can predict — and sanity-check — any equality estimate.

Column. orders.customer_id, 10,000,000 rows, n_distinct = 200000 (200k distinct customers), no meaningful MCVs (roughly uniform).
Predicate. customer_id = 91744 — a value not tracked in MCVs.

Question. What does the planner estimate for WHERE customer_id = 91744, and what happens if one customer is actually a 2-million-row outlier?

Input.

Fact	Value
Table rows	10,000,000
`n_distinct(customer_id)`	200,000
MCV coverage	~0 (assumed uniform)
Predicate	`customer_id = 91744`

Code.

EXPLAIN
SELECT * FROM orders WHERE customer_id = 91744;

-- Uniform assumption: 10,000,000 / 200,000 = 50 rows per customer
Index Scan using idx_orders_customer_id on orders  (cost=0.43..190.10 rows=50 width=48)
  Index Cond: (customer_id = 91744)

Step-by-step explanation.

With no MCV entry for 91744, the planner assumes each distinct customer_id is equally likely: selectivity = 1 / n_distinct = 1 / 200,000 = 0.000005.
Estimated rows = selectivity × table rows = 0.000005 × 10,000,000 = 50 rows. This is the "average customer has 50 orders" assumption baked into the uniform-distribution math.
For a typical customer this is fine, and the 50-row estimate correctly picks an index scan.
But suppose customer 91744 is a wholesale account with 2,000,000 orders — 20% of the table. The planner still estimates 50 (it has no MCV telling it otherwise). Upstream, a join keyed on this customer plans for 50 rows and picks a nested loop — which then loops 2,000,000 times. The classic skewed-key blowup.
The fix: raise statistics_target on customer_id so mega-customers land in the MCV list (then their true frequency is used), or restructure so the outlier is handled separately. Uniform math is only safe when the data is actually uniform.

Output.

Scenario	Estimate	Actual	Consequence
Typical customer	50	~50	correct index scan
Whale customer (in MCVs)	true freq	~2,000,000	seq/bitmap scan, hash join
Whale customer (not in MCVs)	50	~2,000,000	nested-loop blowup

Rule of thumb. Equality on a non-MCV value estimates table_rows / n_distinct. That is only trustworthy when the column is roughly uniform; on skewed keys, get the outliers into the MCV list with a higher statistics_target.

Worked example — conjunction under the independence assumption

Detailed explanation. The independence assumption is the single most common source of misestimates in real workloads. Walk through a two-predicate conjunction on correlated columns and quantify how far off the product goes.

Columns. products(brand, category) — correlated: 'Apple' products are almost all in 'Electronics'.
Predicate. brand = 'Apple' AND category = 'Electronics'.

Question. Compute the independent estimate for the conjunction and compare it to reality; then state the fix.

Input.

Fact	Value
Table rows	1,000,000
`sel(brand = 'Apple')`	0.03 → 30,000 rows
`sel(category = 'Electronics')`	0.20 → 200,000 rows
Independent product	0.03 × 0.20 = 0.006 → 6,000 rows
Actual (Apple ⊂ Electronics)	~29,500 rows

Code.

-- Independence: sel(A AND B) = sel(A) * sel(B)
EXPLAIN
SELECT * FROM products
WHERE brand = 'Apple' AND category = 'Electronics';
-- rows=6000   (underestimate: nearly all Apple products ARE electronics)

-- Fix: functional-dependency statistics
CREATE STATISTICS stx_prod_brand_cat (dependencies)
  ON brand, category FROM products;
ANALYZE products;

EXPLAIN
SELECT * FROM products
WHERE brand = 'Apple' AND category = 'Electronics';
-- rows=29500  (dependency brand -> category recognised)

-- Before: rows=6000   |   After: rows=29500 (matches actual)

Step-by-step explanation.

Individually the selectivities are reasonable: 3% of products are Apple, 20% are electronics. The planner multiplies them: 0.03 × 0.20 = 0.006, estimating 6,000 rows.
Reality: essentially every Apple product is already an electronic, so adding category = 'Electronics' removes almost nothing. The true count is ~29,500 — close to the brand = 'Apple' count alone.
The independence assumption therefore underestimates by ~5×. Underestimates are especially dangerous because they push the planner toward nested loops and under-sized hash tables.
CREATE STATISTICS (dependencies) records that brand functionally implies category; after ANALYZE, the planner stops discounting for the redundant category predicate and estimates ~29,500.
Note the direction of the error: correlated ANDs underestimate; the independence assumption never overestimates a conjunction of positively-correlated predicates. Knowing the direction helps you predict which way a plan will go wrong.

Output.

Estimate method	Rows	Error vs actual
Independence (product)	6,000	~5× under
Functional-dependency stats	29,500	within noise

Rule of thumb. A conjunction of correlated columns always underestimates under independence. If you see a small rows= on an AND of two columns you know are related, suspect the independence assumption before anything else and add extended statistics.

Worked example — expression predicates defeat statistics

Detailed explanation. Statistics are collected per column, not per expression. The moment you wrap a column in a function, the planner loses its statistics and falls back to a hard-coded default guess. Walk through the failure and the two fixes.

Predicate. WHERE lower(email) = 'ceo@acme.com' on a 5,000,000-row users table.
Problem. No statistics exist for lower(email), so the planner uses a default equality selectivity (~0.5%), estimating ~25,000 rows for what is actually 1 row.

Question. Why does WHERE lower(email) = 'ceo@acme.com' get a terrible estimate, and how do you fix it two different ways?

Input.

Fact	Value
Table rows	5,000,000
Statistics on `email`	yes (per column)
Statistics on `lower(email)`	none
Default equality selectivity	~0.005 → ~25,000 rows
Actual matching rows	1

Code.

-- Bad: statistics are on `email`, not on `lower(email)`
EXPLAIN
SELECT * FROM users WHERE lower(email) = 'ceo@acme.com';
-- Seq Scan ... rows=25000   (default guess; may even skip the index)

-- Fix A: expression index — it gets its own statistics
CREATE INDEX idx_users_lower_email ON users (lower(email));
ANALYZE users;

EXPLAIN
SELECT * FROM users WHERE lower(email) = 'ceo@acme.com';
-- Index Scan using idx_users_lower_email ... rows=1

-- Fix B: extended/expression statistics without an index (PG 14+)
CREATE STATISTICS stx_users_lower_email ON lower(email) FROM users;
ANALYZE users;

-- Before: rows=25000 (Seq Scan)   |   After expression index: rows=1 (Index Scan)

Step-by-step explanation.

The planner has rich statistics on the raw email column, but the predicate compares lower(email). That expression is opaque to the column statistics — there is no MCV or histogram for "email lowercased."
Lacking any distribution, the planner applies a built-in default selectivity for equality (~0.5%), estimating ~25,000 rows on 5,000,000 — off by four orders of magnitude for a unique email.
The overestimate can push the planner to a sequential scan (thinking 25,000 rows scattered everywhere) and, upstream, to a hash join sized for 25,000 rows.
Fix A — an expression index on lower(email). Postgres collects statistics on the indexed expression automatically, so after ANALYZE the planner knows lower(email) is effectively unique and estimates 1 row. Bonus: the query can now use the index.
Fix B — if you cannot afford the index but still want a good estimate, CREATE STATISTICS ON lower(email) (expression statistics, PG 14+) gives the planner the distribution without the index's write cost. Choose based on whether you need the access path or just the estimate.

Output.

Approach	Estimate	Access method	Write cost
No stats on expression	25,000	Seq Scan	none
Expression index	1	Index Scan	index maintenance
Expression statistics	1	Seq Scan (better costed)	analyze only

Rule of thumb. Any function wrapping a column in a WHERE clause blinds the planner. If the expression is a real access pattern, build an expression index; if you only need the estimate, add expression statistics. Better still, avoid wrapping the column at all when a sargable rewrite exists.

SQL Interview Question on cardinality estimation

A senior interviewer might ask: "This query joins four tables and runs for minutes; the EXPLAIN ANALYZE shows a bottom-level scan estimated at 20 rows but actually producing 900,000, and every join above it uses a nested loop. Walk me through why one bad estimate at the bottom wrecks the whole plan, how you'd find which estimate is the root, and how you'd fix it."

Solution Using EXPLAIN ANALYZE row-skew diagnosis and extended statistics

-- Step 1 — get estimate vs actual on every node; find the FIRST big divergence
EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, SUM(oi.qty * oi.unit_price) AS spend
FROM   customers   c
JOIN   orders      o  ON o.customer_id = c.id
JOIN   order_items oi ON oi.order_id   = o.id
JOIN   products     p ON p.id          = oi.product_id
WHERE  c.country = 'DE' AND c.tier = 'gold'   -- correlated columns
  AND  p.category = 'Electronics'
GROUP  BY c.name;

Nested Loop  (cost=... rows=20 width=...) (actual ... rows=900000 loops=1)
  ->  Nested Loop (cost=... rows=20) (actual ... rows=90000 loops=1)
        ->  Index Scan on customers c
              (cost=... rows=20 width=8)          -- ESTIMATE
              (actual ... rows=45000 loops=1)      -- ACTUAL  <-- root divergence
              Filter: (country='DE' AND tier='gold')
        ->  Index Scan on orders o (rows=1) (actual rows=2 loops=45000)
  ->  Index Scan on order_items oi (rows=1) (actual rows=10 loops=90000)
Execution Time: 214300 ms

-- Step 2 — root divergence is at customers: country & tier are correlated
CREATE STATISTICS stx_cust_country_tier (dependencies, ndistinct)
  ON country, tier FROM customers;
ANALYZE customers;

-- Step 3 — re-plan: correct estimate flips nested loops to hash joins
EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, SUM(oi.qty * oi.unit_price) AS spend
FROM   customers c
JOIN   orders o       ON o.customer_id = c.id
JOIN   order_items oi ON oi.order_id   = o.id
JOIN   products p     ON p.id          = oi.product_id
WHERE  c.country = 'DE' AND c.tier = 'gold'
  AND  p.category = 'Electronics'
GROUP  BY c.name;

Step-by-step trace.

Input — the annotated plan above, scanning nodes bottom-up for the first big estimate-vs-actual gap:

Read the plan from the leaves up, comparing rows= (estimate) to actual … rows=. The orders and order_items scans are roughly right (1 vs 2, 1 vs 10). The first large divergence is the customers scan: estimate 20, actual 45,000 — a 2,250× miss. That is the root.
country = 'DE' AND tier = 'gold' are correlated (German customers skew heavily gold in this data). Under independence the planner multiplied sel(country) × sel(tier) and got ~20 rows.
Believing 20 customers matched, the planner chose nested loops all the way up. The orders scan runs 45,000 times (loops=45000), order_items runs 90,000 times — the 20-row plan is executed against 900,000 real rows.
CREATE STATISTICS (dependencies, ndistinct) on (country, tier) teaches the planner the correlation; ANALYZE refreshes. The customers estimate jumps to ~45,000.
With honest cardinality, nested loops are now costed as ruinously expensive, so the planner switches to hash joins that build each table once. Final result — execution drops from ~214 s to a few seconds; the plan reads as hash joins with correct rows= at every level.

Output:

Node	Est (before)	Actual	Est (after fix)
customers (DE, gold)	20	45,000	~45,000
⋈ orders	20	90,000	~90,000
⋈ order_items	20	900,000	~900,000
Join algorithm	Nested Loop ×3	—	Hash Join ×3
Execution time	~214,000 ms	—	few seconds

Why this works — concept by concept:

Bottom-up plan reading — cardinality errors originate at the leaves and compound upward, so the first node (scanning up) where estimate and actual diverge sharply is the root cause; nodes above it are just amplifying it.
Independence-assumption underestimate — correlated country/tier predicates were multiplied, collapsing a 45,000-row estimate to 20. Underestimates specifically drive the planner toward nested loops.
Loop count as evidence (loops=45000) — a nested loop's inner node runs once per outer row; a huge loop count confirms the outer estimate was far too small.
Extended statistics — (dependencies, ndistinct) records the functional dependency and the distinct-combination count, fixing both the AND selectivity and any group-by cardinality on the pair.
Cost — the fix is one CREATE STATISTICS + ANALYZE (O(sample)); it converts an O(outer × inner) nested-loop cascade into O(build + probe) hash joins. One corrected estimate at the bottom fixes the entire tree above it.

SQL
Topic — cardinality
Cardinality and selectivity estimation problems

Practice →

SQL Topic — sql SQL problems on predicates and filtering

Practice →

4. Join order and join algorithms

The planner picks both how to join each pair (nested loop, hash, merge) and in what order — and the order controls the size of every intermediate result

The mental model in one line: join planning has two coupled dimensions — the physical algorithm for each pairwise join (nested loop, hash join, or merge join, each with a different cost curve) and the order in which the tables are joined (which determines how big each intermediate result is) — and because the number of possible join orders grows factorially with table count, the optimizer uses dynamic programming (and a heuristic search above a threshold) to find a near-optimal ordering without enumerating them all. Join order is the single highest-leverage decision the optimizer makes, because intermediate result size dominates the cost of everything downstream.

The three physical join algorithms.

Nested loop join. For each row of the outer input, probe the inner input for matches. Cost ≈ rows(outer) × cost(inner probe). Wins when the outer side is tiny and the inner side has an index on the join key (each probe is an index lookup). Catastrophic when the outer side is large — it re-scans the inner side per outer row.
Hash join. Build an in-memory hash table on the smaller ("build") input keyed on the join column, then scan the larger ("probe") input and look up each row. Cost ≈ rows(build) + rows(probe). Wins for large, unsorted inputs with an equi-join. Needs work_mem to hold the build side; spills to disk (batched) if it does not fit.
Merge join. Sort both inputs on the join key (or read them pre-sorted from an index), then walk them in lockstep like a zipper. Cost ≈ sort(both) + linear merge. Wins when both inputs are already sorted on the join key (e.g. index order) or when the result must be sorted anyway.

Choosing the algorithm — the cost curves cross.

Small outer + indexed inner → nested loop. 10 outer rows × cheap index probe beats building a hash table.
Two large inputs → hash join. Building once and probing once beats sorting both or looping.
Pre-sorted inputs or ordered output needed → merge join. No sort cost if the order is free; merge also handles inputs too large for a hash table gracefully.
The build-side rule. For a hash join the planner always tries to make the smaller input the build side — the hash table must fit in work_mem, and a smaller build side means fewer batches and less memory.

Join order — why it dominates cost.

Intermediate result size. Joining the two most-selective inputs first keeps the first intermediate result small, so every subsequent join processes fewer rows. Join the wrong pair first and you materialize millions of rows you will only filter away later.
Left-deep vs bushy trees. A left-deep tree joins one base table at a time onto a growing intermediate (((A⋈B)⋈C)⋈D) — pipelines well, small memory footprint, the classic shape. A bushy tree joins intermediate results to each other ((A⋈B)⋈(C⋈D)) — can be cheaper for some shapes but explodes the search space.
The combinatorial explosion. The number of join orders grows factorially: n tables have up to n! left-deep orderings (and far more counting bushy trees and algorithm choices). Ten tables is millions of candidate plans — you cannot enumerate them all within a sane planning budget.

How the optimizer searches the space.

Dynamic programming (System R algorithm). Build the cheapest plan for every subset of tables bottom-up: cheapest way to access each single table, then cheapest 2-table join for each pair, then 3-table, and so on, reusing sub-results. This finds the optimal join order while examining far fewer than n! plans.
The join_collapse_limit / from_collapse_limit knobs. Control how many tables the planner will flatten into one join-order search. Below the limit, full DP; explicit JOIN syntax beyond the limit fixes the order as written.
GEQO (genetic query optimizer). Above geqo_threshold (default 12 tables) Postgres switches from exhaustive DP to a genetic algorithm — a randomized heuristic that finds a good-enough order in polynomial time, because full DP on 15+ tables is itself too slow.

Common interview probes on joins.

"When does the planner pick a nested loop over a hash join?" — small outer input with an indexed inner side.
"Which side does a hash join build?" — the smaller input, so the hash table fits in work_mem.
"Why does join order matter?" — it controls intermediate result size, which dominates downstream cost.
"How does the planner avoid enumerating all n! orders?" — dynamic programming (System R), and GEQO above the threshold.

Worked example — nested loop vs hash join, and where they cross

Detailed explanation. The choice between nested loop and hash join is a cost crossover driven entirely by the outer row count. Walk through both costs for the same join at two different outer cardinalities and find the crossover.

Join. orders o ⋈ customers c ON c.id = o.customer_id, with a PK index on customers.id.
Variable. The number of orders rows feeding the join (the outer side), controlled by an upstream filter.

Question. For 100 outer rows vs 5,000,000 outer rows, which join algorithm wins and why?

Input.

Outer rows (orders)	Nested loop cost model	Hash join cost model
100	100 × index probe	build 2M customers + probe 100
5,000,000	5,000,000 × index probe	build 2M customers + probe 5M

Code.

-- Few outer rows: nested loop with index probe wins
EXPLAIN
SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.id = 42;                       -- outer side = 1 row

-- Many outer rows: hash join wins
EXPLAIN
SELECT * FROM orders o JOIN customers c ON c.id = o.customer_id
WHERE o.created_at >= DATE '2020-01-01';  -- outer side = ~5M rows

-- Outer = 1 row  → Nested Loop
Nested Loop  (cost=0.86..16.90 rows=1 width=64)
  ->  Index Scan on orders o (rows=1)
  ->  Index Scan using customers_pkey on customers c (rows=1)
        Index Cond: (id = o.customer_id)

-- Outer = 5M rows → Hash Join (build the smaller customers side)
Hash Join  (cost=68000.00..410000.00 rows=5000000 width=64)
  Hash Cond: (o.customer_id = c.id)
  ->  Seq Scan on orders o (rows=5000000)
  ->  Hash (rows=2000000)
        ->  Seq Scan on customers c (rows=2000000)

Step-by-step explanation.

With one outer row (o.id = 42), the nested loop does exactly one index probe into customers — cost ≈ a single index descent. Building a 2-million-row hash table just to probe it once would be absurd. Nested loop wins decisively.
With 5,000,000 outer rows, a nested loop would do 5,000,000 index probes into customers — millions of random lookups. The hash join instead builds customers (the smaller side, 2M rows) into a hash table once, then streams 5M orders through it — two sequential scans plus in-memory probes.
The crossover is where outer_rows × index_probe_cost exceeds build_cost + probe_cost. Roughly, once the outer side is more than a small multiple of the inner-table size divided by the probe cost, hash join wins. The planner computes both and compares.
Note the build-side choice: the planner hashes customers (2M) not orders (5M), because the smaller build side needs less work_mem and fewer batches.
This crossover is exactly why a cardinality misestimate on the outer side is so destructive: estimate 50 outer rows when there are 5,000,000 and the planner picks nested loop — then executes 5,000,000 probes instead of a hash join. Section 1's incident in one sentence.

Output.

Outer rows	Chosen algorithm	Why
1	Nested Loop	single indexed probe, no build cost
5,000,000	Hash Join	build small side once, probe once

Rule of thumb. Nested loop is a bet that the outer side is tiny; hash join is the safe choice for two large inputs. The planner's bet is only as good as the outer-side row estimate — which is why sections 2 and 3 come first.

Worked example — join order changes intermediate result size

Detailed explanation. Two join orders produce the identical result set but can differ by orders of magnitude in cost, purely because of how big the intermediate result is. Walk through a three-table join under two orderings.

Tables. customers (7,000 EU rows after filter), orders (60,000 after date filter), line_items (2,000,000 total).
Two orders. (a) (customers ⋈ orders) ⋈ line_items vs (b) (orders ⋈ line_items) ⋈ customers.

Question. Which join order keeps intermediate results smaller, and how much does it matter?

Input.

Order	First join	Intermediate size	Second join input
(a) filtered-first	customers ⋈ orders	~21,000	⋈ 2,000,000 line_items
(b) big-first	orders ⋈ line_items	~2,000,000	⋈ 7,000 customers

Code.

-- Let the planner choose (it will pick the filtered-first order)
EXPLAIN
SELECT c.name, li.sku
FROM   customers  c
JOIN   orders     o  ON o.customer_id = c.id
JOIN   line_items li ON li.order_id   = o.id
WHERE  c.region = 'EU'
  AND  o.created_at >= DATE '2026-01-01';

-- Good order: join the two filtered/small inputs first (intermediate = 21k)
Hash Join  (cost=... rows=42000)                       -- ⋈ line_items last
  ->  Hash Join  (cost=... rows=21000)                 -- customers ⋈ orders FIRST
        ->  Seq Scan on customers (rows=7000, EU)
        ->  Index Scan on orders (rows=60000, date)
  ->  Seq Scan on line_items (rows=2000000)

Step-by-step explanation.

Order (a) joins the two filtered inputs — customers (7,000) and orders (60,000) — first. Because both are already reduced by their predicates, the intermediate result is only ~21,000 rows. That small intermediate is then joined to line_items.
Order (b) joins orders (60,000) to line_items (2,000,000) first, producing a ~2,000,000-row intermediate, and only then filters down by joining to the 7,000 EU customers. It builds a huge intermediate just to discard most of it.
The result set is identical either way — join is associative and commutative for inner joins — but the work is not. Order (a) processes ~21,000 intermediate rows; order (b) processes ~2,000,000. A ~100× difference in the middle of the plan.
The planner's dynamic-programming search evaluates both (and more) and picks (a) because its costed intermediate is far smaller. This is the single biggest reason join order is the highest-leverage decision.
When the planner picks the wrong order it is almost always because a cardinality estimate made a filtered input look bigger, or an unfiltered input look smaller, than it really is — again pointing back to statistics and estimation.

Output.

Join order	Peak intermediate rows	Relative cost
filtered-first (chosen)	~21,000	1×
big-first	~2,000,000	~100×

Rule of thumb. Good join order = join the most-selective (smallest-after-filter) inputs first to keep intermediates tiny. When a multi-join is slow, check whether the planner built a giant intermediate early — that is a join-order (usually estimate-driven) problem.

Worked example — the search space and GEQO threshold

Detailed explanation. You cannot brute-force join order for many tables. Walk through why the space is factorial, how dynamic programming tames it, and when Postgres gives up on DP and switches to the genetic optimizer.

Fact. n tables have up to n! left-deep join orders (more with bushy trees and per-join algorithm choices).
DP. System R dynamic programming reuses sub-plans to explore the space in ~O(2^n × n) instead of n!.
GEQO. Above geqo_threshold (default 12) Postgres uses a genetic heuristic because even DP is too slow.

Question. How many join orders exist for 5 vs 12 tables, and what does Postgres do differently at 12+?

Input.

Tables (n)	Left-deep orders (`n!`)	Planner strategy
3	6	full DP
5	120	full DP
10	3,628,800	full DP (still feasible via reuse)
12+	~479,001,600+	GEQO (genetic heuristic)

Code.

-- Inspect the knobs that govern the join-order search
SHOW join_collapse_limit;   -- default 8: flatten up to 8 tables for reordering
SHOW from_collapse_limit;   -- default 8: same for FROM-list subqueries
SHOW geqo;                  -- on
SHOW geqo_threshold;        -- 12: switch to genetic search at/above 12 rels

-- Raise the collapse limit so the planner reorders a 10-table join fully
SET join_collapse_limit = 12;
SET geqo_threshold      = 14;   -- prefer exhaustive DP a bit longer

-- With join_collapse_limit high enough, an implicit-join 10-table query
-- is fully reordered by DP. With explicit JOINs beyond the limit, the
-- written order is largely preserved (planning stays fast, order fixed).

Step-by-step explanation.

Join order count is factorial: 3 tables → 6 orders, 5 → 120, 10 → 3.6 million, 12 → ~479 million (left-deep only; bushy trees multiply this further). Naive enumeration is hopeless past a handful of tables.
Dynamic programming avoids re-deriving sub-plans: it computes the cheapest access for each single relation, then the cheapest join for each pair, reusing those to build triples, and so on. This is exponential in n but with a small base — feasible up to ~10–12 tables.
join_collapse_limit (default 8) caps how many tables the planner flattens into one reorderable join problem. Below it, full DP reorders freely; explicit JOIN clauses beyond it are largely executed as written, trading optimality for bounded planning time.
At geqo_threshold tables (default 12), Postgres switches to GEQO — a genetic algorithm that evolves a population of candidate orders, keeping the fittest (cheapest) — because DP itself would take too long. GEQO finds a good order, not necessarily the optimal one.
The practical lever: for a critical 10–12 table query you can raise join_collapse_limit and geqo_threshold so the planner does full DP (better plan, slower planning). For ad-hoc many-table queries the defaults protect planning time. It is a planning-time-vs-plan-quality trade.

Output.

Tables	Strategy	Planning cost	Plan quality
≤ 8 (default limit)	full DP	low	optimal within cost model
9–11	DP if limits raised	moderate	near-optimal
≥ 12	GEQO (genetic)	bounded	good, not guaranteed optimal

Rule of thumb. Trust the planner to order small joins optimally. For a hot 10+ table query, consider raising join_collapse_limit/geqo_threshold (better plan) or writing the join order explicitly and lowering the limit (fixed order, fast planning) — measure both.

SQL Interview Question on join order and algorithms

A senior interviewer might ask: "A three-table analytics join was fast, then someone added a fourth dimension table and it went from two seconds to four minutes. The plan now shows a nested loop with millions of loops. Walk me through how you'd diagnose whether it's a join-order problem or a join-algorithm problem, and how you'd get the planner back to a good plan without hard-coding hints."

Solution Using estimate correction plus join_collapse_limit tuning

-- Step 1 — read the plan: is the pain a bad order or a bad algorithm?
EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, d.region_name, SUM(f.amount) AS total
FROM   fact_sales   f
JOIN   dim_customer c ON c.id = f.customer_id
JOIN   dim_date     d ON d.id = f.date_id
JOIN   dim_region   r ON r.id = c.region_id     -- the newly added table
WHERE  d.year = 2026 AND r.region_name = 'EMEA'
GROUP  BY c.name, d.region_name;

Nested Loop  (cost=... rows=30) (actual ... rows=3200000 loops=1)
  ->  Nested Loop (rows=30) (actual rows=800000 loops=1)
        ->  Index Scan dim_region r (rows=1) (actual rows=1)
        ->  Seq Scan dim_customer c (rows=30) (actual rows=800000 loops=1)
              Filter: (region_id = r.id)            -- 800k, not 30!
  ->  Index Scan fact_sales f (rows=1) (actual rows=4 loops=800000)
Execution Time: 238000 ms

-- Step 2 — the estimate on dim_customer is 30 vs actual 800k. Refresh stats;
-- the join key region_id is skewed, so also raise its resolution.
ALTER TABLE dim_customer ALTER COLUMN region_id SET STATISTICS 500;
ANALYZE dim_customer;

-- Step 3 — ensure the planner is allowed to reorder all four tables
SET join_collapse_limit = 12;   -- (default 8 is fine here, but be explicit)

-- Step 4 — re-plan
EXPLAIN (ANALYZE, BUFFERS)
SELECT c.name, d.region_name, SUM(f.amount) AS total
FROM   fact_sales f
JOIN   dim_customer c ON c.id = f.customer_id
JOIN   dim_date d     ON d.id = f.date_id
JOIN   dim_region r   ON r.id = c.region_id
WHERE  d.year = 2026 AND r.region_name = 'EMEA'
GROUP  BY c.name, d.region_name;

Step-by-step trace.

Input — the four-table plan above, diagnosed for order vs algorithm:

Read bottom-up. dim_region is correct (1 row). The dim_customer scan estimates 30 rows but actually returns 800,000 — the new dim_region join made the planner mis-estimate how many customers are in EMEA (skewed region_id, and stale stats after adding the table).
Because the planner believed only 30 customers matched, it chose nested loops and put the tiny-looking dim_customer result on the outer side of the join to fact_sales. The fact_sales index scan then runs 800,000 times (loops=800000).
This is both symptoms at once: the wrong estimate caused the wrong algorithm (nested loop instead of hash) and a poor effective order (looping a huge input). But the root is one thing — the cardinality estimate.
Refreshing statistics and raising region_id's target (step 2) corrects the dim_customer estimate to ~800,000. Now the planner costs the nested loop as enormous and switches to hash joins, and the DP search reorders to join the small filtered dimensions first.
join_collapse_limit = 12 (step 3) guarantees all four tables are in one reorderable search (they already are under the default 8, but making it explicit documents intent). Final result — hash joins, correct row counts, execution back to a couple of seconds.

Output:

Aspect	Before	After
dim_customer estimate	30	~800,000
Root join algorithm	Nested Loop	Hash Join
Inner-side loops	800,000	1
Effective join order	big input looped	small dims joined first
Execution time	~238,000 ms	~2,000 ms

Why this works — concept by concept:

Diagnose order vs algorithm together — a nested loop with millions of loops is almost always a symptom of an underestimated outer input, not an independent "wrong algorithm" choice. Fix the estimate and both the algorithm and the effective order correct themselves.
Skewed join key resolution — raising SET STATISTICS on the skewed region_id gets the heavy regions into the MCV list so their true frequency drives the estimate instead of uniform math.
DP reordering — with honest cardinalities the System R dynamic-programming search naturally orders the small filtered dimensions first, shrinking every intermediate result.
join_collapse_limit — controls how many tables the planner may freely reorder; keeping it at or above the table count lets DP do its job rather than honoring the written order.
Cost — the fix is statistics + one GUC, no query rewrite and no hints. It turns O(outer × inner) nested loops into O(build + probe) hash joins with a small filtered build side — the recurring theme of the whole optimizer.

SQL
Topic — joins
Join order and join-algorithm problems

Practice →

SQL Topic — indexing Indexing problems for join performance

Practice →

5. Cost models and reading EXPLAIN ANALYZE

Cost is an abstract page-and-tuple estimate; `EXPLAIN ANALYZE` shows you the guess and the reality side by side so you can tell a good plan from a bad one

The mental model in one line: the cost model assigns every plan node a unitless number built from the estimated rows times per-page and per-tuple cost constants (seq_page_cost, random_page_cost, cpu_tuple_cost, …), the planner sums these up the tree and picks the minimum-total-cost plan — and EXPLAIN shows you that estimate while EXPLAIN ANALYZE additionally runs the query and shows the actual rows, time, and loops, so the gap between estimate and actual is your primary diagnostic for a bad plan. Reading a plan tree fluently — cost, rows estimated vs actual, loops, buffers — is the skill that turns "the query is slow" into "this node is the problem, here is why."

The cost constants — what the numbers are made of.

seq_page_cost (default 1.0). Cost of reading one page sequentially. The unit everything else is measured against.
random_page_cost (default 4.0). Cost of reading one page at a random offset — 4× a sequential page on spinning disks. On SSDs the real ratio is closer to 1.1–1.5; lowering random_page_cost is the single most common cost-model tune because the default over-penalizes index scans on modern storage.
cpu_tuple_cost (0.01), cpu_index_tuple_cost (0.005), cpu_operator_cost (0.0025). Per-row CPU costs for processing a heap tuple, an index tuple, and evaluating an operator/function. Small individually, but they dominate on CPU-bound in-memory work.
The formula, roughly. A sequential scan costs ≈ pages × seq_page_cost + rows × cpu_tuple_cost. An index scan costs ≈ index_pages × random_page_cost + heap_fetches × random_page_cost × correlation_factor + cpu costs. The planner plugs the estimated rows into these and sums up the tree.

EXPLAIN vs EXPLAIN ANALYZE — guess vs truth.

EXPLAIN (no ANALYZE). Shows the plan and the estimates only: cost=startup..total rows=N width=B. Does not run the query — safe on expensive statements. Use it to see what the planner intends.
EXPLAIN ANALYZE. Actually executes the query and adds actual time=startup..total rows=N loops=L to each node. The rows here is the real row count; comparing it to the estimated rows is the whole game. Note: it runs the query (including writes — wrap DML in a transaction and ROLLBACK).
startup vs total cost/time. startup is the cost/time before the first row is returned (e.g. a sort must finish before emitting anything); total is for all rows. A LIMIT cares about startup; a full aggregation cares about total.
loops. How many times the node executed. On a nested loop's inner side, loops = outer row count, and the printed actual time/rows are per loop — multiply by loops for the true total. High loops is the nested-loop-blowup signature.

Reading the plan tree — the method.

It is a tree; read leaves-up for cardinality, root-down for cost. Execution flows bottom-up (scans feed joins feed aggregates); the top node's total cost/time is the query's. For root-cause, scan from the leaves for the first big estimate-vs-actual divergence (section 3's method).
Indentation = tree depth. Each -> is a child node feeding its parent. Sibling nodes at the same indentation are the inputs to the join/append above them.
BUFFERS tells you I/O. EXPLAIN (ANALYZE, BUFFERS) adds shared hit= (pages found in cache) and read= (pages read from disk). A node with huge read= is doing real I/O; huge hit= with slow time is CPU-bound. Essential for distinguishing an I/O problem from a CPU problem.
Node types to know. Seq Scan, Index Scan, Index Only Scan, Bitmap Heap/Index Scan, Nested Loop, Hash Join, Merge Join, Hash, Sort, Aggregate, HashAggregate, GroupAggregate, Gather (parallel workers), Memoize (cached inner results).

Common interview probes on cost and EXPLAIN.

"What is the unit of cost?" — abstract; anchored to one sequential page read (seq_page_cost = 1.0), not milliseconds.
"Difference between EXPLAIN and EXPLAIN ANALYZE?" — estimates only vs actually runs and shows real rows/time/loops.
"The inner node says rows=5 but the query is slow — why?" — check loops; 5 rows × 200,000 loops is 1,000,000 rows of work.
"How do you tell an I/O problem from a CPU problem in a plan?" — BUFFERS: high read= is I/O, high hit= with slow time is CPU.

Worked example — anatomy of a single plan node

Detailed explanation. Every plan node prints the same skeleton; once you can read one node you can read any plan. Dissect a single Index Scan node field by field.

Node. Index Scan using idx_orders_created_at on orders.
Goal. Translate every number in the node line into what it means and what it would tell you if it were off.

Question. Given the node below, explain each field and identify whether this node is healthy.

Input.

Field	Value shown
cost	`0.43..7200.00`
rows (estimate)	`60000`
actual time	`0.05..58.3`
actual rows	`61240`
loops	`1`

Code.

Index Scan using idx_orders_created_at on orders
  (cost=0.43..7200.00 rows=60000 width=24)
  (actual time=0.05..58.30 rows=61240 loops=1)
  Index Cond: (created_at >= '2026-01-01'::date)
  Buffers: shared hit=1200 read=6100

Step-by-step explanation.

cost=0.43..7200.00 — startup cost 0.43 (cheap to return the first row from an index), total cost 7200.00 (to return all rows). These are abstract units, not milliseconds.
rows=60000 width=24 — the planner estimates 60,000 output rows, each ~24 bytes wide. width feeds memory sizing for sorts and hashes upstream.
actual time=0.05..58.30 — measured wall-clock milliseconds: 0.05 ms to first row, 58.30 ms to last. Because loops=1, these are the true totals for this node.
actual rows=61240 loops=1 — the node really produced 61,240 rows in a single execution. Estimate 60,000 vs actual 61,240 is a ~2% miss — excellent. This node is healthy; its estimate matches reality, so any plan built on it is well-founded.
Buffers: shared hit=1200 read=6100 — 1,200 pages came from cache, 6,100 were read from disk. This node is doing real I/O; if it were the bottleneck you would look at caching or a covering index. Here the timing (58 ms) is reasonable for 6,100 page reads.

Output.

Field	Meaning	Verdict here
cost `0.43..7200`	abstract startup..total	fine
rows `60000` vs actual `61240`	estimate vs reality	~2% off — excellent
actual time `..58.3`	ms, total (loops=1)	reasonable
Buffers `read=6100`	disk pages read	some I/O, expected

Rule of thumb. Read every node as four questions: what did it estimate, what did it actually produce, how many times did it run (loops), and how much I/O did it do (Buffers). A node where estimate ≈ actual and time is proportional to work is healthy; skip it and move on.

Worked example — spotting the estimate-vs-actual blowup

Detailed explanation. The fastest way to find the problem node in a big plan is to scan for the largest rows estimate-to-actual ratio. Walk through a plan with one poisoned node and show how the ratio pinpoints it.

Plan. A three-node plan where one scan is off by 1000×.
Goal. Find the culprit purely from the ratios, without knowing the data.

Question. In the plan below, which node is the root cause and what does its ratio tell you?

Input.

Node	Estimate	Actual	Ratio
Seq Scan events	100	100,000	1000× under
Nested Loop	100	100,000	inherited
Hash (dim)	500	500	1× (fine)

Code.

Nested Loop  (cost=... rows=100) (actual ... rows=100000 loops=1)
  ->  Seq Scan on events e
        (cost=... rows=100 width=..)            -- estimate 100
        (actual ... rows=100000 loops=1)         -- actual 100,000  <-- 1000x
        Filter: (event_type = 'click' AND is_bot = false)
  ->  Index Scan on dim_page p
        (cost=... rows=1) (actual rows=1 loops=100000)   -- ran 100k times!
        Index Cond: (id = e.page_id)

Step-by-step explanation.

Scan the nodes for the biggest estimate-to-actual ratio. The Seq Scan on events estimates 100 rows but produced 100,000 — a 1000× underestimate. That is the poisoned node.
The predicate event_type = 'click' AND is_bot = false is the likely cause: correlated columns (most non-bot traffic is clicks) multiplied under the independence assumption, or a stale/missing MCV for 'click'. Either way the selectivity was far too small.
The underestimate cascaded: the Nested Loop inherited the 100-row belief and chose to loop the dim_page index scan once per event — but loops=100000 shows it actually ran 100,000 times.
The dim_page node itself is healthy (1 estimated, 1 actual per loop) — it is a victim, not the cause. This is why you must find the first divergence, not just any slow-looking node.
The fix follows directly from the diagnosis: add extended statistics on (event_type, is_bot) or raise their target so the events estimate becomes ~100,000, at which point the planner abandons the nested loop for a hash join.

Output.

Node	Ratio	Role	Action
Seq Scan events	1000× under	root cause	fix stats on the predicate columns
Nested Loop	inherited	amplifier	corrects itself after fix
Index Scan dim_page	1×	victim	none

Rule of thumb. To find the problem in any plan, sort the nodes by estimate-to-actual ratio and start at the worst one nearest the leaves. The fix is almost always statistics or a rewrite at that node, not the slow-looking node at the top.

Worked example — full EXPLAIN ANALYZE diagnosis with BUFFERS

Detailed explanation. Put it all together: a real slow query, the full EXPLAIN (ANALYZE, BUFFERS), and the reasoning from symptom to fix. This is exactly the artifact an interviewer hands you.

Query. Aggregation over a filtered fact table joined to a dimension.
Symptom. Slow; the plan shows a large sort spilling to disk and an estimate-vs-actual gap.

Question. Diagnose the plan below end to end and propose the fix.

Input.

Symptom in plan	Reading
`Sort Method: external merge Disk: 512000kB`	sort spilled to disk (work_mem too small)
`rows=1000` vs `actual rows=1200000`	estimate 1200× low
`Buffers: ... read=210000`	heavy disk I/O

Code.

GroupAggregate  (cost=... rows=1000) (actual ... rows=1200000 loops=1)
  ->  Sort  (cost=... rows=1000) (actual ... rows=1200000 loops=1)
        Sort Key: f.customer_id
        Sort Method: external merge  Disk: 512000kB
        ->  Hash Join  (cost=... rows=1000) (actual ... rows=1200000 loops=1)
              Hash Cond: (f.customer_id = c.id)
              ->  Seq Scan on fact_sales f (rows=1000) (actual rows=1200000)
                    Filter: (region = 'EMEA')
              ->  Hash (rows=50000) (actual rows=50000)
                    ->  Seq Scan on dim_customer c (rows=50000)
  Buffers: shared hit=8000 read=210000, temp read=64000 written=64000
Execution Time: 41200 ms

Step-by-step explanation.

Start at the worst estimate-vs-actual gap: Seq Scan on fact_sales estimates 1,000 rows for region = 'EMEA' but produces 1,200,000 — a 1200× underestimate. Root cause: stale or low-resolution statistics on fact_sales.region (EMEA is common, not rare).
That bad estimate propagated to the Sort and GroupAggregate, which were sized for 1,000 rows. When 1,200,000 rows actually arrived, the sort could not fit in work_mem and spilled: Sort Method: external merge Disk: 512000kB — 512 MB written to and read from temp files (temp read=64000 written=64000 pages).
Buffers: read=210000 confirms heavy heap I/O on the fact scan, and the temp buffers confirm the disk sort. Together they explain the 41-second runtime: it is I/O-bound on both the scan and the spilled sort.
Two independent fixes: (a) ANALYZE fact_sales (and raise region's statistics target) so the estimate becomes ~1,200,000 — this alone lets the planner size the sort correctly and may switch to a HashAggregate; (b) raise work_mem for this query so a 1.2M-row sort stays in memory instead of spilling.
After both, the fact estimate is honest, the aggregate is sized correctly, the sort stays in RAM (no Disk: line), and the query drops from ~41 s to a few seconds. The diagnosis chain — worst ratio → propagation → spill → I/O — is the repeatable method.

Output.

Fix	Effect
`ANALYZE` + higher `region` target	estimate 1,000 → ~1,200,000; correct sizing
Raise `work_mem`	sort stays in memory (no external merge)
Combined	41,200 ms → few seconds; no temp I/O

Rule of thumb. Sort Method: external merge Disk: and temp read/written in BUFFERS mean a spill — either the estimate was too low (fix stats) or work_mem is too small (raise it). Always diagnose the estimate first; a correct estimate often removes the spill for free.

SQL Interview Question on reading execution plans

A senior interviewer might ask: "Here is an EXPLAIN ANALYZE for a report that runs in 30 seconds. Walk me through, node by node, how you'd decide whether the problem is a missing index, a bad cardinality estimate, an under-sized work_mem, or the wrong join algorithm — and what single change you'd try first."

Solution Using a systematic EXPLAIN ANALYZE reading method

-- Always capture estimates, actuals, AND I/O in one shot
EXPLAIN (ANALYZE, BUFFERS, VERBOSE, SETTINGS)
SELECT p.category, COUNT(*) AS n, SUM(oi.qty * oi.unit_price) AS revenue
FROM   order_items oi
JOIN   orders   o ON o.id = oi.order_id
JOIN   products p ON p.id = oi.product_id
WHERE  o.created_at >= DATE '2026-01-01'
  AND  p.category IN ('Electronics','Home')
GROUP  BY p.category;

HashAggregate  (cost=... rows=2) (actual ... rows=2 loops=1)
  Group Key: p.category
  ->  Hash Join  (cost=... rows=800) (actual ... rows=1500000 loops=1)   <-- 1875x
        Hash Cond: (oi.product_id = p.id)
        ->  Hash Join (rows=800) (actual rows=1500000 loops=1)
              Hash Cond: (oi.order_id = o.id)
              ->  Seq Scan on order_items oi (rows=6000000) (actual rows=6000000)
              ->  Hash (rows=800) (actual rows=300000)                    <-- 375x
                    ->  Index Scan on orders o (rows=800) (actual rows=300000)
                          Index Cond: (created_at >= '2026-01-01')
        ->  Hash (rows=2000) (actual rows=2000)
              ->  Seq Scan on products p (rows=2000)
  Buffers: shared hit=12000 read=180000
Execution Time: 30100 ms

Step-by-step trace.

Input — the annotated plan above, read with a fixed checklist:

Find the worst estimate/actual ratio nearest the leaves. The Index Scan on orders estimates 800 rows but returns 300,000 (375×). That is the first big divergence — the created_at >= '2026-01-01' predicate is far less selective than the stats believe (stale histogram after recent data growth).
Trace the propagation. The 800-row belief flowed up: both hash joins were sized for ~800 rows but processed 1,500,000. The hash tables were under-sized, forcing extra batches (and possible spills).
Rule out a missing index. order_items is scanned sequentially producing all 6,000,000 rows — but it is the large fact table being fully consumed by the join, so a seq scan is correct here; an index would not help. Not an index problem.
Rule out work_mem as the root. The under-sized hashes are a consequence of the 375× estimate, not an independent cause. BUFFERS shows heavy read=180000 on the scans, consistent with processing 6M + 1.5M rows.
Pick the single first change: fix the estimate. ANALYZE orders (and raise created_at's target) makes the estimate ~300,000; the planner then sizes both hash joins correctly and the query drops sharply. Final result — one ANALYZE addresses the root; only if a spill remains do you also raise work_mem.

Output:

Diagnostic question	Evidence in plan	Verdict
Missing index?	order_items fully consumed by join	no — seq scan correct
Bad cardinality?	orders 800 est vs 300,000 actual	yes — root cause
work_mem too small?	under-sized hashes (consequence)	secondary
Wrong join algorithm?	hash join is right for the real sizes	no
First change	`ANALYZE orders` + raise target	fixes the root

Why this works — concept by concept:

Worst-ratio-first reading — scanning for the largest estimate-to-actual ratio nearest the leaves finds the root cause immediately, instead of being distracted by the slowest-looking (often victim) node higher up.
Propagation awareness — one leaf misestimate under-sizes every hash and sort above it; recognizing consequences vs causes stops you from "fixing" work_mem when the real problem is statistics.
BUFFERS to classify I/O vs CPU — shared read= vs hit= and temp counters distinguish disk-bound scans, cache-bound CPU work, and sort spills, so you change the right knob.
Rule out before you rewrite — a full seq scan on the fact table is correct, not a missing index; the method eliminates false fixes before proposing one.
Cost — the single highest-leverage change is almost always correcting the estimate (O(sample) ANALYZE), which re-sizes joins and sorts for free; index or work_mem changes come second and only if the corrected plan still shows a specific bottleneck.

SQL
Topic — optimization
EXPLAIN ANALYZE and query-tuning problems

Practice →

SQL
Topic — indexing
Indexing and access-path problems

Practice →

Cheat sheet — query optimizer recipes

Fix statistics before anything else. 90% of bad plans are a stale or missing estimate, not a missing index. Run ANALYZE tbl; first; check pg_stat_user_tables.last_analyze and n_mod_since_analyze to confirm freshness after any bulk load, restore, or pg_upgrade (which drops stats entirely).
Read EXPLAIN for intent, EXPLAIN ANALYZE for truth. EXPLAIN prints cost=startup..total rows=N width=B (estimates, does not run). EXPLAIN (ANALYZE, BUFFERS) runs the query and adds actual time=.. rows=.. loops=.. plus shared hit/read and temp read/written. Wrap DML in a transaction and ROLLBACK when using ANALYZE.
Diagnose by estimate-vs-actual ratio, leaves first. Scan nodes bottom-up; the first node where rows= (estimate) diverges sharply from actual rows= is the root cause. Nodes above it merely amplify the error. Watch loops= — on a nested loop, per-loop actuals multiply by the loop count.
Correlated columns → CREATE STATISTICS. The planner assumes independence, so A = x AND B = y on correlated columns (city/zip, country/tier, brand/category) underestimates. Fix with CREATE STATISTICS s (dependencies, ndistinct) ON a, b FROM tbl; ANALYZE tbl; — the highest-return fix for AND-predicate misestimates.
Skewed columns → raise statistics_target. ALTER TABLE t ALTER COLUMN c SET STATISTICS 500; ANALYZE t; grows the MCV list and histogram so skewed/whale values are tracked exactly instead of averaged. Apply to columns that actually appear in WHERE/JOIN.
Expression predicates blind the planner. WHERE lower(email) = … has no column statistics; the planner uses a ~0.5% default guess. Add an expression index (CREATE INDEX ON t (lower(email))) for both estimate and access path, or expression statistics (CREATE STATISTICS ON lower(email) FROM t, PG 14+) for the estimate alone.
Join-algorithm cheat. Nested loop = tiny outer + indexed inner (each probe is one lookup). Hash join = two large unsorted inputs on an equi-join (build the smaller side into work_mem, probe with the larger). Merge join = both inputs already sorted on the key, or the output must be sorted anyway.
Join order is the highest-leverage decision. Join the most-selective (smallest-after-filter) inputs first to keep intermediate results tiny. A giant early intermediate is a join-order problem, almost always caused by a cardinality misestimate on a filtered input.
Control the join search with GUCs. join_collapse_limit/from_collapse_limit (default 8) cap how many tables the planner reorders; geqo_threshold (default 12) switches from exhaustive DP to the genetic optimizer. For a hot 10–12 table query, raise both for a better plan; lower them (or write explicit JOIN order) for faster planning on ad-hoc many-table queries.
Tune cost constants for your storage. random_page_cost defaults to 4.0 (spinning disk); on SSD/NVMe set it to ~1.1–1.5 so the planner stops over-penalizing index scans. Set effective_cache_size to ~50–75% of RAM so the planner knows how much data is likely cached. Raise work_mem to keep sorts and hashes in memory (watch total = work_mem × concurrent operations).
Add an index vs rewrite vs tune — in that decision order. First make the estimate honest (stats). Then, if a selective predicate still does a seq scan, add/adjust an index (including expression or partial indexes). Then rewrite (de-sargable-ize predicates, avoid functions on columns, split OR into UNION). Only then reach for planner GUCs or pg_hint_plan.
Kill a bad plan without a rewrite. In order of preference: ANALYZE → raise statistics_target / add extended statistics → adjust work_mem/random_page_cost for the session → as a last resort disable a node type for the session (SET enable_nestloop = off;) to confirm the alternative is cheaper, then fix the estimate that made the planner avoid it. Never ship enable_*=off in production — it is a diagnostic, not a fix.

Frequently asked questions

What is a query optimizer in one sentence?

A query optimizer is the database component that takes your declarative SQL — which says what result you want, not how to compute it — and searches a space of equivalent physical execution plans (different scan methods, join algorithms, and join orders), estimating the cost of each from table statistics and cardinality estimates, then hands the executor the cheapest plan it found within its planning-time budget. It is the reason the same query can run in milliseconds or minutes on identical data: the plan, not the SQL, determines performance. Every senior database interview probes the optimizer because reading and fixing its decisions is the core of query tuning.

What is the difference between a cost-based and a rule-based optimizer?

A rule-based optimizer (RBO) applies a fixed priority list of heuristics ("if an index exists on the filtered column, use it") regardless of the actual data — deterministic but blind, so it will happily use an index to fetch 90% of a table. A cost-based optimizer (CBO) — used by PostgreSQL, MySQL 8+, SQL Server, and modern Oracle — assigns every candidate plan a numeric cost derived from statistics about the data distribution, then picks the minimum. The decisive advantage is that CBO adapts to how many rows a predicate actually matches: it can correctly choose a sequential scan over an index when the predicate is unselective, something an RBO cannot reason about.

What is cardinality estimation and why does it matter so much?

Cardinality estimation is the planner's prediction of how many rows each plan node will produce, computed by multiplying a selectivity (the fraction of rows a predicate keeps, derived from histograms and most-common-value lists) against the input row count. It matters more than almost anything else because each node's estimate becomes the input to the cost model of the node above it — so a single misestimate low in a join tree compounds multiplicatively upward and produces a wrong plan for the entire query. The classic failure is an underestimate that makes the planner choose a nested loop, which then executes hundreds of thousands of inner lookups; you spot it in EXPLAIN ANALYZE as a huge gap between rows= and actual rows=.

Why does the planner ignore my index and choose a sequential scan?

Because for the estimated number of matching rows, the sequential scan is genuinely cheaper. An index scan fetches matching rows via (often random) page lookups; when a predicate matches a large fraction of the table, doing millions of random lookups is far slower than reading every page once in physical order. The planner costs both and picks the cheaper — so an "ignored" index usually means the predicate is unselective (correctly) or the row estimate is wrong (stale statistics making a rare value look common). Check EXPLAIN ANALYZE: if the estimate matches reality the seq scan is right; if not, run ANALYZE. On SSDs, also lower random_page_cost toward 1.1–1.5 so index scans are not over-penalized.

How do I read an EXPLAIN ANALYZE plan?

Read it as a tree: each -> is a child node feeding its parent, execution flows from the leaves (scans) up to the root (final result), and indentation shows depth. For each node compare rows= (the planner's estimate) to actual … rows= (reality) — the first large divergence scanning up from the leaves is your root cause. Watch loops=: on a nested loop's inner side the printed per-loop actuals multiply by the loop count, so rows=5 loops=200000 is a million rows of work. Add BUFFERS to see shared hit/read (cache vs disk I/O) and temp read/written (sort/hash spills), which tell you whether a slow node is I/O-bound, CPU-bound, or spilling.

How do I fix a bad plan without rewriting the query?

Start with statistics, because most bad plans are misestimates: run ANALYZE, then raise statistics_target on skewed columns and add CREATE STATISTICS for correlated ones. Next, tune cost inputs for your hardware — lower random_page_cost on SSDs, set effective_cache_size realistically, and raise work_mem to stop sorts and hashes spilling to disk. If a critical many-table join is mis-ordered, adjust join_collapse_limit/geqo_threshold. Use SET enable_nestloop = off (or similar) only as a diagnostic to confirm the alternative is cheaper, then fix the underlying estimate rather than shipping the toggle. Reserve query rewrites and index changes for when honest statistics still leave a specific, identifiable bottleneck.

Practice on PipeCode

Drill the query optimization practice library → for the plan-reading, estimate-vs-actual diagnosis, and slow-query tuning problems senior interviewers love.
Sharpen your estimation intuition on the cardinality practice library → for selectivity math, the independence assumption, and correlated-column misestimates.
Rehearse the fundamentals on the SQL practice library → and level up join performance on the joins practice library → and the indexing practice library →.
Stack these against PipeCode's broader 450+ data-engineering catalogue to anchor the statistics → cardinality → join-order → cost mental model against real graded inputs.

Lock in query-optimizer muscle memory

Docs explain what a query optimizer is. PipeCode drills make you read the plan — spot the estimate-vs-actual blowup, name why a nested loop looped a million times, decide whether to fix statistics, add an index, or raise work_mem. Pipecode.ai is Leetcode for Data Engineering — plan-first practice tuned for the production trade-offs senior data engineers actually face.

Practice optimization problems →
Practice SQL problems →

1. Why the optimizer is the most important black box in your database

Declarative SQL states the goal; the query optimizer chooses the physical plan that reaches it cheapest

Worked example — the same query, two plans, driven by selectivity

Worked example — what the planner does with a three-table join

SQL Interview Question on how the optimizer chooses a plan

Solution Using EXPLAIN ANALYZE to compare estimated vs actual rows

2. Statistics — histograms, MCVs, n_distinct

ANALYZE samples your data into histograms, most-common-values, and distinct counts — the raw material every estimate is built from

Worked example — reading pg_stats for a skewed column

Worked example — range selectivity from the histogram

Worked example — extended statistics for correlated columns

SQL Interview Question on table statistics

Solution Using ANALYZE, statistics_target tuning, and autovacuum settings

3. Cardinality estimation — the make-or-break guess

Selectivity turns statistics into a row estimate, and that estimate — right or wrong — decides every plan above it

Worked example — equality selectivity from n_distinct

Worked example — conjunction under the independence assumption

Worked example — expression predicates defeat statistics

SQL Interview Question on cardinality estimation

Solution Using EXPLAIN ANALYZE row-skew diagnosis and extended statistics

4. Join order and join algorithms

The planner picks both how to join each pair (nested loop, hash, merge) and in what order — and the order controls the size of every intermediate result

Worked example — nested loop vs hash join, and where they cross

Worked example — join order changes intermediate result size

Worked example — the search space and GEQO threshold

SQL Interview Question on join order and algorithms

Solution Using estimate correction plus join_collapse_limit tuning

5. Cost models and reading EXPLAIN ANALYZE

Cost is an abstract page-and-tuple estimate; EXPLAIN ANALYZE shows you the guess and the reality side by side so you can tell a good plan from a bad one

Worked example — anatomy of a single plan node

Worked example — spotting the estimate-vs-actual blowup

Worked example — full EXPLAIN ANALYZE diagnosis with BUFFERS

SQL Interview Question on reading execution plans

Solution Using a systematic EXPLAIN ANALYZE reading method

Cheat sheet — query optimizer recipes

Frequently asked questions

What is a query optimizer in one sentence?

What is the difference between a cost-based and a rule-based optimizer?

What is cardinality estimation and why does it matter so much?

Why does the planner ignore my index and choose a sequential scan?

How do I read an EXPLAIN ANALYZE plan?

How do I fix a bad plan without rewriting the query?

Practice on PipeCode

Lock in query-optimizer muscle memory

`ANALYZE` samples your data into histograms, most-common-values, and distinct counts — the raw material every estimate is built from

Worked example — reading `pg_stats` for a skewed column

Cost is an abstract page-and-tuple estimate; `EXPLAIN ANALYZE` shows you the guess and the reality side by side so you can tell a good plan from a bad one