Skip to content

Query Optimizer#

Problem statement (interviewer prompt)

A query joins three tables with predicates and an ORDER BY. The database has multiple indexes and join algorithms available. Describe how the optimizer chooses a plan and what statistics it relies on. Why does the same query sometimes run 100x slower after a schema change?

A SQL query is declarative; the optimizer turns it into an execution plan. It enumerates candidate plans, costs each using statistics about row counts and selectivity, and hands the winner to the executor.

flowchart TB
  SQL[SQL text] --> Parse[Parser + binder]
  Parse --> Rewrite[Rewriter / views / CTEs]
  Rewrite --> Plan[Optimizer<br/>plan enumeration<br/>+ cost model]
  Plan --> Exec[Executor]
  Stats[(Statistics<br/>histograms, counts)] -. read .-> Plan

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-query-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class Parse,Rewrite,Plan,Exec service;
    class Stats datastore;

The same query can have wildly different plans depending on statistics, indexes, and predicate selectivity. EXPLAIN shows the chosen plan; EXPLAIN ANALYZE runs it and reports actual vs estimated row counts.

The optimizer is the database component that decides how to run a query. Misunderstand it and your most innocuous query can scan 100M rows; understand it and you can shape your schema and indexes to make the optimizer pick correctly every time.

Stages#

flowchart TB
  SQL[SQL] --> P[Parse: AST]
  P --> B[Bind: resolve table & column refs]
  B --> R[Rewrite: view expansion, CTE inline, predicate push-down]
  R --> O[Optimize: enumerate plans, cost each]
  O --> X[Execute]

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class P,B,R,O,X service;

Access paths#

For each table reference, the optimizer enumerates ways to read it:

Path When
Sequential scan Small table or high selectivity (most rows match)
Index scan Selective predicate matches an index
Index-only scan All columns the query needs live in the index
Bitmap heap scan Many index hits; gather them then visit heap once per page

Join algorithms#

Algorithm Best when
Nested loop One small side, indexed lookup on the other
Hash join Equality on a non-clustered column, one side fits in memory
Sort-merge join Both sides already sorted (or one indexed) on join key

A typical multi-join query has dozens of valid plans; the optimizer prunes by cost.

Cardinality estimation#

The cost model multiplies an estimated row count by a per-operation cost (page read, CPU per row). The crucial input is selectivity: what fraction of rows match each predicate?

  • Histograms of column distributions: how many rows have created_at in [2024-01, 2024-02)?
  • Most-common values (MCVs): exact frequency for the top-N values.
  • Correlations: are (country, currency) independent? If not, naive product over-estimates.

A bad cardinality estimate cascades: if you under-estimate by 100x, the optimizer picks nested-loop when it should hash-join. Result: 100x slow.

EXPLAIN ANALYZE#

EXPLAIN (ANALYZE, BUFFERS) SELECT ... ;

Shows: - Estimated rows vs actual rows (the smoking gun for bad stats). - Cost in arbitrary units; map to seconds with experience. - Buffer hits vs reads (memory vs disk). - Per-node timing.

Hash Join  (cost=1.00..1500.00 rows=1000 width=128) (actual time=2.10..30.5 rows=987 loops=1)
  -> Seq Scan on orders   (rows=10000)  (actual rows=10000)
  -> Hash
       -> Index Scan on customers  (rows=100)  (actual rows=101)

Plan stability#

The same query can switch plans when:

  • Statistics change (run ANALYZE after big loads).
  • Data distribution shifts (e.g. new tenant dominates).
  • Postgres' random_page_cost or seq_page_cost tuned.
  • An index added / dropped.

Tools:

  • Plan hints: pg_hint_plan, MySQL /*+ ... */, MSSQL plan guides. Use sparingly.
  • Stored plans: Oracle SQL Plan Management, MSSQL Query Store.
  • Statistics targets: increase histogram resolution per column.

Common pitfalls#

Symptom Cause
Sudden slowdown after data load Statistics stale; run ANALYZE
Plan flips between fast and slow Histogram boundary case; consider hints
Index ignored Optimizer thinks table scan is cheaper (bad stats or low selectivity)
Predicate not pushed down Functional predicate on indexed column; add functional index
OR-ed predicates slow Optimizer falls back to seq scan; rewrite as UNION

Rules-based vs cost-based#

Old optimizers used fixed rules ("use the index if one exists"). Modern optimizers (Postgres, SQL Server, Oracle, Snowflake) are cost-based with statistics. Rule-based optimizers are simpler but blow up on non-standard data shapes.

Where the optimizer sits#

flowchart TB
  QO((Query<br/>optimizer))
  IDX[Indexing strategies<br/>access paths to choose]
  SE[Storage engines LSM / B-Tree<br/>how scans hit disk]
  MVCC[MVCC isolation<br/>snapshot the executor reads]
  CP[Connection pooling<br/>concurrent plans in flight]
  IDX --> QO
  SE --> QO
  MVCC --> QO
  CP -. concurrency .- QO

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class QO service;
    class IDX,SE,MVCC,CP datastore;

Glossary & fundamentals#

Tag Concept What it is Page
HLD Indexing strategies the access-path catalogue indexing-strategies
HLD Storage engines LSM B-Tree the disk layer the executor reads storage-engines-lsm-btree
HLD MVCC isolation levels snapshot the executor reads against mvcc-isolation-levels
HLD Connection pooling how many concurrent plans run at once connection-pooling

Quick reference#

Stages#

Parse → Bind → Rewrite → Optimize (cost-based) → Execute.

Access paths#

  • Seq scan
  • Index scan
  • Index-only scan (covering)
  • Bitmap heap scan

Join algorithms#

Algo Best for
Nested loop One side small, indexed lookup on other
Hash Equality, one side fits memory
Sort-merge Both sides sorted on join key

Statistics#

  • Histograms (per column)
  • Most-common values (MCV)
  • Multi-column correlations
  • Run ANALYZE after bulk loads

EXPLAIN ANALYZE workflow#

  1. EXPLAIN (ANALYZE, BUFFERS) ...
  2. Compare estimated rows vs actual rows
  3. If diverged: stats stale or correlation missed → ANALYZE / extended statistics
  4. If actual fast on indexed lookup but plan picked seq: tune random_page_cost

Plan-stability tools#

  • pg_hint_plan, MySQL hint comments, MSSQL plan guides
  • Oracle SQL Plan Management
  • MSSQL Query Store

Common bugs#

  • Stats stale → wrong plan after data load
  • Plan flip on histogram boundary
  • Functional predicate skipping index (WHERE lower(col)=? needs functional index)
  • OR-ed predicates → seq scan; rewrite as UNION

Refs#

  • PostgreSQL Performance Tips docs
  • Winand - SQL Performance Explained
  • Petrov - Database Internals

FAQ#

What does the query optimizer do?#

It turns a declarative SQL query into a runnable plan by enumerating join orders and access paths, estimating cost from statistics, and handing the cheapest plan to the executor.

Why does the same query suddenly get 100x slower?#

Stats went stale or a histogram changed, so the planner flipped to a worse plan, usually a nested loop where a hash join was right, or it stopped using a key index.

How do I read EXPLAIN output?#

Read the plan inside-out. Each node shows its operator, estimated rows, and cost. EXPLAIN ANALYZE adds actual rows and time so you can spot bad row estimates.

What is selectivity?#

Selectivity is the fraction of rows a predicate keeps. The planner estimates it from histograms and most-common-value lists, then uses it to pick the smaller input as the build side.

Cost-based vs rule-based optimizer?#

Rule-based optimizers follow heuristics like always use the index. Cost-based ones model row counts and IO. Every modern engine (Postgres, MySQL, Oracle, SQL Server) is cost-based.

Further reading#