System Design · Data
Database Query Optimization
Two SQL statements that “return the same rows” can differ by 1,000× in latency. The is guessing join order, access paths, and algorithms from . When the guess of is wrong, you get a nested loop over a million rows instead of a hash join.
This lesson is about the planner, not about inventing indexes from scratch. You will read a plan, name join methods, make predicates , and know when to fix stats, rewrite SQL, or change the physical design.
Slow report journey
Shape the SQL
Filters and joins the application actually needs; avoid hiding columns in functions.
ANALYZE after bulk load so histograms match reality.
Estimated vs actual rows; join type; sort/hash spills.
Fix the mismatch
Rewrite, stats, join hint last, or a supporting access path.
What actually happens
Parse builds a tree. Bind resolves names and types. Rewrite inlines views, sometimes flattens subqueries, and may pull predicates through. Then the searches a space of logical join trees and physical operators. Cost-based planners (almost every production OLTP engine) score candidates with a fed by . Rule-based remnants still exist as rewrites (“this subquery is an EXISTS, try a semi-join”).
The executor then runs the chosen tree: scans, filters, joins, aggregates, sorts. Optimization failed if estimated rows at a node diverge badly from actual rows (EXPLAIN ANALYZE). Indexes are only one access path the search considers; a sequential scan is a valid, cheaper choice when is poor.
Read the diagram definition
flowchart TD
SQL["SQL text"] --> Parse["Parse + bind"]
Parse --> Rewrite["Rewrite: views, CTEs,\nsubquery pull-up"]
Rewrite --> Enum["Enumerate plans:\njoin order, access paths"]
Enum --> Cost["Cost with stats"]
Cost --> Pick["Pick cheapest plan"]
Pick --> Exec["Executor: scans, joins,\naggregates, sorts"]
Exec --> Out["Result / spill / timeout"]Cost, cardinality, and why estimates break
cost ≈ pages_read * page_cost + tuples_cpu * cpu_cost + sort/hash spill
page_cost: sequential << random on HDD; closer on SSD
cache: a page already in shared buffers is not a physical read
(planners still often assume a cold-ish cache)
Cardinality pipeline:
table n_live_tup
× predicate selectivities (histogram / MCV / n-distinct)
× join selectivities (often 1/max(ndistinct) style guesses)
Independence assumption:
WHERE city = 'Bengaluru' AND zip = '560001'
correlated → product of selectivities is far too small or too largeExtended statistics (multivariate ndistinct, functional dependencies) exist specifically because errors compound through joins. After three joins, a 3× error per step is 27×. Nested loop vs hash is chosen on that number.
| Symptom in EXPLAIN ANALYZE | Likely cause | First fix |
|---|---|---|
| est 10, actual 8,000,000 | Stale or missing stats; hidden function on column | ANALYZE; make predicate sargable |
| Nested loop, inner index, huge loops | Outer cardinality underestimated | Fix stats; rewrite; discourage NL |
| HashAggregate / Sort spill | work_mem too small vs actual groups | Raise memory; pre-aggregate; partition |
| Seq scan on selective filter | Planner thinks filter is not selective, or no index | Stats + sargable form; then consider index |
Join algorithms and join order
Read the diagram definition
flowchart TD
J["Equality join"] --> Outer{"Outer cardinality\nactually small?"}
Outer -->|Yes + inner index| NL["Nested loop + index probe"]
Outer -->|No, both unsorted| HJ["Hash join\nbuild smaller side"]
Outer -->|Both already ordered| MJ["Merge join"]
HJ --> Mem{"Build fits work_mem?"}
Mem -->|No| Spill["Hash spill to disk"]
Mem -->|Yes| Fast["In-memory hash"]A is a for-each. It shines as nested-loop-index: outer 50 orders, inner primary-key probe for each customer. A shines on large equality joins with no useful order. A shines when both sides arrive sorted on the join key.
Join order: left-deep trees are the usual search shape. Filter early. Join the most selective pair first when it reduces the intermediate. Cartesian products in the middle of a plan are almost always an estimate disaster, not a clever algorithm. Bushy trees appear when two independent subtrees are cheaper to build separately then join.
-- Dangerous shape: function hides join key / filter
SELECT *
FROM orders o
JOIN users u ON o.user_id = u.id
WHERE DATE(o.created_at) = DATE '2026-10-09'; -- not sargable on created_at
-- Optimizer-friendly
WHERE o.created_at >= TIMESTAMP '2026-10-09'
AND o.created_at < TIMESTAMP '2026-10-10';
-- EXISTS vs IN vs JOIN
-- Anti-join / semi-join rewrite: optimizer often turns
-- WHERE id IN (SELECT ...) into a hash or merge semi-join
-- Correlated subquery in SELECT list may execute per row unless flattenedAccess paths and sargable predicates
Sequential scan, index scan, index-only scan, bitmap heap scan, and (in warehouses) column-pruned scans are competing access paths. tries to attach filters to those scans. A predicate is when the comparison is on the column (or a matching expression index), not on a derived value the B-tree never stored.
Usually sargable
col = $1, col > $1, col BETWEEN a AND b, col IN (...small list), col LIKE 'foo%'
Usually not
YEAR(col), col::text = $1 on an int, LIKE '%foo', ABS(col) = 1, mismatched collation casts
OR of two indexed predicates may become a bitmap OR of two index scans — still better than a seq scan, worse than a single composite if one shape dominates. OFFSET pagination that walks 10,000 rows to skip them is an optimizer-visible cost: keyset pagination (WHERE (created_at, id) < ($t, $id)) is a different access path, not a prettier LIMIT.
Rewrites the planner already tries
Predicate placement and view merging
Filters on a view often merge into the view body so you do not materialize the whole view first. Some constructs (volatile functions, LIMIT inside the view, DISTINCT) block merging. If EXPLAIN shows a Materialize or CTE Scan of a huge set, the rewrite failed and you may need to inline by hand.
CTEs: optimization fence vs inline
Older PostgreSQL treated WITH as an optimization fence (always materialize). Newer versions may inline. If a CTE is used once, inlining lets predicates push down. If it is used many times, materialize can win. Check the actual plan; do not assume the WITH keyword means “cache this.”
Aggregation and grouping
HashAggregate vs GroupAggregate (needs sort or ordered input). Partial aggregation in parallel query combines per-worker groups. DISTINCT and GROUP BY on high-cardinality keys need memory grants; spills dominate p99.
Parallel query and prepared plans
Parallel seq scans help large analytics; they can hurt tiny OLTP if worker startup exceeds the query. Prepared statements may reuse a generic plan that was costed for unknown parameters — parameter sniffing (SQL Server) or generic-plan lock-in (Postgres) is why the same query is fast for one bind and slow for another.
A practical tuning loop
1. Capture the statement as the database sees it (log / pg_stat_statements).
2. EXPLAIN (ANALYZE, BUFFERS, VERBOSE) on a snapshot of prod-like data.
Never ANALYZE a write on prod without wrapping or using a replica.
3. Circle every node where actual/est > 10× or < 0.1×.
4. For those nodes:
- stale stats? ANALYZE / create extended stats on correlated columns
- non-sargable predicate? rewrite
- join type insane given actual rows? fix estimates first
5. Only then: covering index, partial index, partitioning prune, denormalize.
6. Hints / pg_hint_plan / optimizer_switch: last resort, document why.
7. Re-measure p95 under concurrency; a plan that wins alone can lock or spill in a storm.Application-level “optimization” that issues N+1 queries bypasses the join optimizer entirely. One join in SQL is often cheaper than 200 primary-key round trips — unless each lookup is a 0.2 ms cached get and the join would sort 20 million rows. Name the row counts.
Warehouse-specific levers
Column stores add zone maps, bloom filters on row groups, partition pruning, and broadcast vs shuffle vs colocated joins. The cost model prices network shuffle, not just pages. into Parquet is the difference between reading 2 GB and 200 GB from object storage. Clustering keys (BigQuery, Snowflake micro-partitions, Redshift SORTKEY) are physical layouts the optimizer can prune with; they are not B-tree seeks, but the same idea: reduce bytes before CPU.
Materialized views and cube tables are optimizer-adjacent: some engines rewrite a query to hit the MV automatically; others require you to query it. Either way, freshness vs scan cost is the trade-off, not a magic skip of statistics.
Trade-offs to state clearly
Search time vs plan quality. The optimizer will not exhaustively try every bushy tree on a 12-way join. You may need to reduce join count (views, staging tables) rather than demand a perfect search.
Generic prepared plans vs custom plans. Parse/plan CPU vs a plan that matches this parameter’s selectivity. High-variance parameters (empty vs huge tenant) are the danger case.
Memory vs spill. Larger work_mem / grants make hash and sort fast until many concurrent queries OOM the host. Cost the fleet, not one session.
Hints vs maintainability. A hint that saved Friday’s incident becomes wrong after data grows. Prefer stats and rewrites; expire hints.
SQL join vs application join. The database has statistics and algorithms; the app has caches and fan-out limits. Pick using actual cardinalities, not ideology.
Choosing and explaining query optimization
A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.
Explain the core idea
The optimizer enumerates physical plans and scores them with a cost model fed by statistics; SQL does not dictate join order.
Cardinality errors explain most disastrous nested loops. Read estimated versus actual rows first.
Sargable predicates, fresh stats, and the right join algorithm beat premature indexes and hints.
When it belongs
A report or OLTP endpoint is slow despite “having indexes.”
You design a multi-join read model and need to argue nested loop vs hash vs merge.
You compare warehouse scans (pushdown, shuffle) with OLTP point plans.
How it fails
Stale histograms after bulk load; independence assumption on correlated columns.
Non-sargable filters forcing sequential scans.
Generic prepared plans or parameter sniffing that freeze a bad shape.
Trade-offs to weigh
Nested loop for tiny outer + indexed inner versus hash for large unsorted equality joins.
CTE materialize versus inline predicate pushdown.
Planner search limits versus hand-staged intermediate tables.
Common misunderstandings
Treating EXPLAIN (no ANALYZE) estimated cost as wall-clock time.
Assuming a sequential scan is always a bug.
Adding an index as the first response to a bad join order.
Wrap-up
Optimization is estimate, search, then execute. Make predicates visible, keep statistics honest, choose join methods from real cardinalities, and only then change physical structures.
Primary sources
Key takeaway
A slow query is usually a wrong cardinality story. Fix what the planner believes, then the SQL shape, then the access path. Nested loop, hash, and merge are tools priced for different sizes — name the sizes.