Under the Hood: The Cost-Based Optimizer (CBO)
SQL is a declarative language: you specify what data you want, not how to retrieve it. The database engine's Cost-Based Optimizer (CBO) evaluates hundreds of possible physical execution trees and selects the plan with the lowest estimated I/O and CPU cost.
The Query Optimization Lifecycle
Under the Hood: Join Algorithms Compared
| Join Algorithm | Mechanism & Complexity | Ideal Workload |
|---|---|---|
| Nested Loop Join | For each row in outer table, scan inner table (O(N × log M) with index). | Small outer table joining against an indexed inner table. |
| Hash Join | Builds an in-memory hash table on the smaller table, then streams the larger table (O(N + M)). | Large unindexed equi-joins that fit into memory (work_mem). |
| Merge Join | Sorts both tables on join keys (or uses B-Tree order) and walks pointers together (O(N log N + M log M)). | Large equi-joins on sorted inputs, or when indexes already supply sorted order. (PostgreSQL merge joins support only merge-joinable equality operators; range joins usually become nested loops.) |
The Stale Statistics Trap: If table rows jump from 1,000 to 10,000,000 without running ANALYZE, the planner assumes the table is tiny and chooses a Nested Loop Join over sequential scans, causing massive latency regressions.
Worked example: reading a plan that went wrong
Query: SELECT o.* FROM orders o JOIN customers c ON c.id = o.customer_id WHERE c.country = 'NZ' AND o.created_at > now() - interval '1 day';
Suppose orders has 200M rows, 2M of them from the last day, and customers has 10M rows, 50k of them in NZ.
| Plan option | Estimated work | When the planner picks it |
|---|---|---|
| Nested loop: scan NZ customers (50k), probe orders index on (customer_id, created_at) for each | 50k index probes, about 150k page touches | When it believes few customers match |
| Hash join: hash the 50k NZ customers, stream the 2M recent orders through an index on created_at | 2M rows streamed plus a small hash table | When both inputs are moderately large and memory is enough |
| Merge join: sort both inputs on customer_id | Sort 2M plus 50k rows | When inputs are already sorted by the join key |
Now suppose statistics are stale and the planner thinks NZ has 50 customers. It picks the nested loop, estimating 50 probes. The real run does 50,000 probes of random index pages, and EXPLAIN ANALYZE shows rows=50 estimated against rows=50000 actual on the customer scan. The fix is ANALYZE customers;, not a hint.
What to look for in EXPLAIN ANALYZE
- Estimated vs actual rows on each node. The first node with a large mismatch is the root cause.
- loops= on the inner side of a nested loop. Actual time is per loop, so multiply by the loop count.
- Buffers: shared hit/read (with
BUFFERS). Reads are cache misses, hits are RAM. - Sort Method: external merge Disk or hash Batches > 1 means
work_memwas too small and the operation spilled to disk.
How real systems differ
- PostgreSQL: exhaustive dynamic programming up to 12 relations (
geqo_threshold), then a genetic optimizer. No built-in hints. - MySQL: greedy join search, with hash joins only since 8.0.18. Supports optimizer hints.
- SQL Server and Oracle: plan caches with parameter sniffing, where a plan built for one parameter value is reused for very different values, a classic production incident.