Query Planning & Optimization
How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?
Who this mechanism is for: a developer who writes SQL, uses dashboards or ORMs, and has seen the words "execution plan" or EXPLAIN but has never studied how a database chooses a plan. You do not need to know how a join is implemented inside the engine. Every technical term is explained the first time it appears, and again in the glossary at the end.
The story we will follow
Ananya is a data engineer at Kiranamart, an online grocery company with about 400 stores and a web shop. Dev is the analytics lead. He owns the dashboards, which are built with a BI tool (a business-intelligence tool that writes SQL automatically from drag-and-drop choices). Dev asks the awkward questions: "Why is this slow today when it was fast yesterday?"
Kiranamart keeps its data in a Postgres-style SQL warehouse. The main table is orders, with about 1 billion rows, one partition per day, loaded every night and growing about 1% per load. Next to it sit order_items and the small dimension tables customers, products, stores, dates, promotions and couriers. The dashboards also sit on a stack of SQL views, for example v_sales_enriched. Later, the same data is also exported as Parquet files in object storage for a second query engine.
Each article below opens with a problem that looks like a bug: a report that was fast and is now slow, a query that gives the same answer as another but takes a thousand times longer. At the end of the article we go back to Ananya and Dev and solve it. The theme repeats in every article, and it is the main idea of this mechanism:
How this mechanism is organized
- 1
Limited by what it can know
Why is planning a different kind of problem from everything below it, and why do estimation errors grow so fast?
Case12 rows expected, 9 million arrived
- 2
From SQL text to a plan
What steps turn SQL into a plan, and which of them are always correct?
CaseSix joins, and only two of them used
- 3
Estimating cost
How does the optimizer guess how much a plan costs, and where do the guesses come from?
CaseThe planner expects 1 row
- 4
Join order search
How can an optimizer search a space with billions of plans, and what happens when it cannot?
CaseThe database is rolling dice
- 5
Rewrites
Why do queries that mean the same thing run at very different speeds?
CaseNOT IN takes 40 minutes, NOT EXISTS 2 seconds
- 6
Data reduction
How do systems remove work (not just rearrange it) using pushdown, pruning and skipping?
Case40 rows returned, 4.2 TB scanned
- 7
Execution decisions
What can be decided late, decided once, or not decided at all?
CaseOne store takes 9 minutes, the others 0.2 seconds
- 8
Diagnosing a bad plan
In what order should you look for the cause, and what can planning never do?
CaseThe post-mortem: what to check first
After that: a summary, hands-on labs, interview questions and a glossary.
What do I do, and what does each option cost?
Diagnose a bad plan
A query got a bad execution plan: check estimated against actual rows first, then statistics, correlation, subqueries, the number of joined tables and pushdown, and only then the cost settings.
DiagnoseFind why a query reads so much
A query reads far more data than its result needs: check that the filter reaches the scan on a clustered column, that it is not negative, that runtime filters, projection and Top-N apply, before making execution faster.
DiagnoseSpeed up a reasonable plan
A query has a sensible plan and reads only what it needs, but is still too slow or too frequent: reuse the answer, reuse the plan, adapt at runtime, compile, or cache a shared subplan, in order of payoff.
Diagnose
Can I see it myself?
Estimate versus actual on a correlated filter
A PostgreSQL table where postcode implies city: the row estimate against the actual count, with per-column statistics, dependencies and an MCV list.
Real systemDocker, PythonJoin elimination with and without an enforced constraint
PostgreSQL removes a LEFT JOIN to a unique key it does not need; an inner join stays. Then an unenforced key and an orphan row change the answer.
Real systemDocker, PythonFind the index-versus-scan crossover on your machine
Force index and sequential scans across selectivities from 0.01% to 50%, on clustered and shuffled data, and compare with what the planner picks.
Real systemDocker, PythonA partition with no statistics
Load a new day into a partitioned PostgreSQL table and compare the plan before and after ANALYZE on that partition alone.
Real systemDocker, PythonCross the dynamic-programming cliff
Plan joins of 8 to 16 tables in a chain and a star with PostgreSQL's exhaustive search and with GEQO; count distinct plans.
Real systemDocker, PythonFour pairs of equal queries
NOT IN against NOT EXISTS with a NULL, a function on a partition key against a range, and a CTE materialized or not, in PostgreSQL.
Real systemDocker, PythonMin/max skipping on sorted versus unsorted data
10 million store_ids in Parquet, random and sorted: how many of 100 row groups a filter must read, and what one outlier does.
MeasurePython with PyArrowPushdown and projection: count the bytes
DuckDB on Parquet: a filter on sorted and random files, all columns against one, and a filter wrapped in an expression.
MeasurePython with DuckDBTop-N heap against full sort
The top 100 of 20 million numbers with a sort and with a heap; then a PostgreSQL LIMIT that makes the plan worse.
Real systemDocker, PythonBloom filter size and false-positive rate
Bloom filters for a million keys at 5, 10 and 15 bits per key: false-positive rate and size.
MeasurePython with NumPyLate materialization crossover
Filter a 100-million-element array with a boolean mask and with a position list, across selectivities, and find where gathering loses.
MeasurePython with NumPyParameter sniffing in PostgreSQL
A prepared statement on a 95%/0.002% skewed column: custom plans, generic plans, and when PostgreSQL switches between them.
Real systemDocker, Python
Can I reason about it under questioning?
Interview questions
Short questions on query planning, such as cardinality estimation, statistics, join order, rewrites, data skipping and run-time decisions, each with an answer you could give aloud and a link to the full explanation.
Scenarios
Longer problems on query planning, of the kind asked in senior interviews: each one estimated with numbers, diagnosed, and answered with its trade-offs.
The tensions this mechanism takes a position on. Each recurs across mechanisms.
Early binding vs. late binding
When structure is committed; determines where the failure surfaces, at write time or read time.
Precompute vs. compute-on-read
For example: materialized views, ELT vs. ETL, schema-on-read.
Exactness vs. approximation
For example: sketches, sampling, ANN.
Simplicity vs. adaptivity
For example: static plans vs. adaptive execution.
Mutability vs. immutability
In-place update vs. append-only + GC; buys reproducibility and cheap concurrency, pays in space and janitorial work.
Ideas this mechanism meets that keep coming back, mechanism after mechanism.
Variance costs more than volume
Variance costs more than volume.
Independence is assumed
Independence is assumed everywhere and is true almost nowhere.
Fixed cost per operation
Fixed cost per operation implies a natural batch size.
Costs are conserved
Costs are conserved, never removed.
Granularity mismatch
Granularity mismatch creates amplification.
Show all 12 principlesShow fewer
The algebra decides
What can be skipped, pushed down, parallelized, merged or precomputed is determined by the algebra of the function, not the layout of the data.
Which way the error points
Opacity forfeits optimization
Opacity forfeits optimization.
Immutable storage grows indirection
An immutable substrate grows an indirection layer plus a collector.
Masking moves failure
Masking a failure moves it from a channel with a schema to a channel without one.
Sound approximations
When exactness is too expensive, use a sound approximation.
Bound the answer, bound the state