Handbooks / DBMS / Chapter 6

Query Processing and Optimization

7 pages · ~5 min✓ Reviewed

Builds on Indexing and Storage. Next up: Transactions and ACID.

DBMSPage 1

Query Pipeline and Optimizer Mental Model

1. Pipeline and Declarative SQL

Parsesyntax, parse tree
Bindtables, types, permissions
Rewriteviews, subqueries, constants
Planpick cheapest
Executereturn rows

SQL is declarative: you say what, the optimizer picks how
Same query, different plan as data changes

2. Rewrite vs Plan

	Rewrite	Planner
Basis	Fixed rules, no costing	Cost estimates
Does	Expand views, flatten IN/EXISTS, fold constants, push predicates down	Picks access paths, join order, join methods
Result	Same query, simpler	Cheapest estimate, not guaranteed fastest

3. Cached Plans

Selectivity = fraction of rows a value matches
Plan cached for a rare value stays slow for a common one
SQL Server: sniffing; PostgreSQL: generic plan
PostgreSQL: 5 custom plans first, then generic if not costlier

sql

PREPARE q(text) AS SELECT * FROM orders WHERE status = $1;
SET plan_cache_mode = force_generic_plan;
EXECUTE q('rare');
EXECUTE q('common'); -- same plan

forces one reused plan

Remember

Optimizer picks the cheapest estimated plan; bad estimates mean bad plans

DBMSPage 2

Cost-Based Optimization, Statistics and Selectivity

1. Cost and Statistics

Cost = I/O + CPU estimate in abstract units, not ms
PostgreSQL: seq_page_cost=1.0, random_page_cost=4.0
ANALYZE / UPDATE STATISTICS stores row and page count
Per column: distinct count, null fraction
Most common values + frequencies, histogram buckets

2. Selectivity

Selectivity = fraction of rows kept (0 to 1)
Estimated rows = table rows × selectivity
Equality ≈ 1 / distinct values, unless in the most-common list
AND multiplies: sel(A) × sel(B)

Case	Calc	Rows
50 distinct, 100,000 rows	1/50 × 100,000	2,000
A 0.1 AND B 0.1	0.1 × 0.1	1% of table

3. When Estimates Break

Correlated columns (city, zip): underestimates by orders of magnitude

DBMSPage 3

Index Scans vs Sequential Scans

1. Choosing a Scan

Scan	Reads	Wins when
Seq	every page, in order	most of the table
Index	B-tree, then heap rows (random I/O)	few rows
Index-only	index alone, if pages all-visible	covering index
Bitmap	page bitmap, heap in physical order	medium; AND/OR of indexes

Index wins under 5-10% of rows
Above that a seq scan is cheaper: the planner is right
Index-only needs the visibility map (vacuumed table)

2. Why the Index Is Skipped

Function or cast on the column: lower(email)=...
Leading wildcard: LIKE '%x'
Type mismatch, or a tiny table
Wrong column order in a composite index

sql

CREATE INDEX ON users (lower(email));
CREATE INDEX ON orders (cust_id) INCLUDE (total);

expression index; covering index

DBMSPage 4

Join Algorithms: Nested Loop vs Hash vs Merge

1. The three algorithms

	Nested loop	Hash	Merge
How	Probe inner per outer row	Build hash on smaller, probe with larger	Sort both, merge in one pass
Joins	Any, incl. non-equality	Equality only	Equality, range-ordered
Needs	Index on inner key	Memory (`work_mem`)	Sorted inputs
Best	Small outer	Large, unsorted	Large, pre-sorted

Nested loop cost ≈ outer rows × inner lookup cost
Only method for non-equality joins without extra support
Hash build side over work_mem spills to disk in batches, slows sharply

2. Choosing

DBMSPage 5

Reading an Execution Plan

1. EXPLAIN Modes

EXPLAIN: estimated plan, query not run
EXPLAIN ANALYZE: runs it, adds real time and row counts
Data-changing statement? Wrap in a transaction, then ROLLBACK
BUFFERS: adds page hits and reads

sql

BEGIN;
EXPLAIN (ANALYZE, BUFFERS)
  DELETE FROM orders WHERE status = 'old';
ROLLBACK;

2. Reading the Tree

Read from the innermost node outward: scans feed joins, joins feed sort/aggregate
cost=startup..total, rows= estimate, width= bytes per row
Estimate vs actual rows gap of 10x or more = where the optimizer went wrong; look first

output

Nested Loop (rows=10) (actual rows=50000 loops=1)
  -> Seq Scan on orders (rows=10) (actual rows=50000)
       Rows Removed by Filter: 4950000

3. Red Flags and Fix Flow

Flag	Sign
Seq Scan	big table, selective filter
Filter	Rows Removed in the millions
Spill	`external merge`, `Batches > 1`

DBMSPage 6

Optimizer Cheat Sheet

1. Pipeline and Selectivity

Parse
Bind
Rewrite
Plan
Execute

Optimizer picks the cheapest estimated plan, not the guaranteed fastest
Selectivity = matching rows ÷ total rows
AND multiplies; OR adds minus overlap
Run ANALYZE after bulk loads

2. Scan and Join Choice

Situation	Pick
Few rows (high selectivity)	Index scan
Medium selectivity	Bitmap scan
Most of the table	Seq scan
Covering index + vacuumed table	Index-only scan
Small outer + indexed inner	Nested loop
Big equality join	Hash join (watch spill)
Pre-sorted inputs	Merge join

3. Plan Debugging

DBMSPage 7

Check yourself

A plan shows a Nested Loop with rows=10, but actual rows=1000000. What went wrong, and what is the right fix?

The estimate was 10x or more off, so the planner picked a join suited to a small outer side
Fix the estimate: ANALYZE or extended stats, not a join hint

An index exists on status, and WHERE status='active' matches 60% of the rows. EXPLAIN shows a Seq Scan. Is that a bug?

No, the planner is right
An index scan makes random heap fetches for most of the table, which costs more than one sequential pass

On 1M rows, city='Paris' has selectivity 0.01 and zip='75001' has 0.01. What rows does the planner estimate for both together, and why can that be wrong?

1M × 0.01 × 0.01 = 100 rows
City and zip are correlated, so the real count may be thousands: a big underestimate