Query Optimizer Internals Under the Hood: Cost-Based Optimization, Cascades Framework, Join Reordering, and Cardinality Estimation
SQL is a declarative language: a query specifies what data to retrieve, leaving the database engine to determine how to execute it. Behind every high-performance database—such as PostgreSQL, MySQL, CockroachDB, and Microsoft SQL Server—lies a Query Optimizer. The optimizer searches an exponential space of logically equivalent execution plans, estimates physical I/O and CPU costs using statistical histograms, and selects the optimal physical execution tree. In this deep architectural walkthrough, we trace relational algebra rewrites, explore the Volcano/Cascades MEMO framework, analyze System R join reordering algorithms, and inspect cardinality estimation failures.
1. Declarative SQL to Physical Execution: The Query Compilation Pipeline
1.1 From Text to Logical Plan
When an application submits a SQL query text, the database engine processes it through five distinct pipeline stages before reading a single row from disk or buffer pool:
- Predicate Pushdown
- Projection Pruning"] LogicalOpt --> OptimizedLogical["Optimized Logical Plan"] OptimizedLogical --> CBO["4. Cost-Based Physical Optimizer (CBO)
- MEMO Search Space (Cascades)
- Cardinality Estimation (Histograms)
- Join Reordering (DP / System R)"] CBO --> PhysicalPlan["Optimal Physical Execution Plan"] PhysicalPlan --> Executor["5. Execution Engine
(Volcano Iterator / Vectorized Engine)"] style SQL fill:#f1f5f9,stroke:#64748b style LogicalOpt fill:#e0f2fe,stroke:#0284c7 style CBO fill:#dbeafe,stroke:#2563eb,stroke-width:2px style PhysicalPlan fill:#dcfce7,stroke:#16a34a
Diagram 1: Complete Database Query Compilation Pipeline. The Cost-Based Optimizer (CBO) evaluates physical execution alternatives to select the minimal cost execution plan.
1.2 Semantic Analysis and View Expansion
During catalog binding, the analyzer checks whether target relations are actual base tables or user-defined views. If a query references a view, the analyzer expands the view's internal logical tree directly into the parent query tree. This expansion allows the downstream logical optimizer to push predicates down through view boundaries and prune unnecessary joins that the view definition might otherwise introduce.
Developer Pitfall — High Query Compilation Overhead for Dynamic SQL Strings:
If an application generates unique dynamic SQL strings instead of parameterized prepared statements (e.g. WHERE id = 101 instead of WHERE id = $1), the database cannot reuse cached physical query plans in its Prepared Statement Cache. The engine is forced to re-parse, re-analyze, and re-run full CBO search space exploration for every request, creating severe CPU overhead under high transaction volumes. Always use parameterized queries.
2. Relational Algebra Transformations & Logical Rewrites
2.1 Equivalence Rules in Relational Algebra
Logical optimization relies on the mathematical properties of relational algebra ($\sigma$ for Selection, $\pi$ for Projection, $\bowtie$ for Join). Because relational algebra expressions form a mathematical group under set theory, expressions can be transformed into equivalent forms that process dramatically fewer rows.
2.2 Core Rule-Based Rewrites
LEFT OUTER JOIN into an INNER JOIN if a subsequent WHERE clause filter rejects NULL values on the right-hand table. Inner joins allow the optimizer vastly more join reordering flexibility.WHERE EXISTS (SELECT 1 FROM orders WHERE orders.user_id = users.id)) into semi-joins or hash inner joins, eliminating $O(N \times M)$ nested loop evaluation loops.Developer Pitfall — Wrapping Indexed Columns in Scalar Functions Prevents Predicate Pushdown:
If a query contains WHERE UPPER(email) = 'USER@EXAMPLE.COM' or WHERE DATE(created_at) = '2026-08-07', the logical optimizer cannot push down a simple range predicate to a B-Tree index scan on email or created_at. The engine is forced to perform a full sequential table scan, evaluating the function for millions of rows. Rewrite queries to use range bounds (e.g., WHERE created_at >= '2026-08-07 00:00:00' AND created_at < '2026-08-08 00:00:00') or create an explicit functional index.
3. Search Space Exploration: The Volcano and Cascades Frameworks
3.1 The Search Space Explosion Problem
For a query joining $N$ tables, the number of possible join trees grows exponentially. For left-deep trees, there are $N!$ permutations. For bushy trees (where any two subtrees can be joined together), the number of valid join tree topologies is given by the Catalan number sequence:
$$T(N) = \frac{(2N - 2)!}{(N - 1)!} = \frac{1}{N} \binom{2N - 2}{N - 1}$$For a 10-table join, there are over 17.6 million possible physical join trees! Exploring every combination exhaustively would take seconds or minutes of CPU time—far longer than executing the query itself. To explore this vast space efficiently, modern query optimizers use the Volcano / Cascades Framework (developed by Goetz Graefe).
3.2 The MEMO Structure and Equivalence Classes
The core data structure of the Cascades optimizer is the MEMO. The MEMO represents the entire search space of equivalent logical and physical plans compactly using a directed graph of Equivalent Groups (Equivalence Classes).
3.3 Rule Firing and Pattern Matching
Cascades operates via a rule engine containing two types of rules: Transformation Rules (mapping logical expressions to logical expressions, e.g., $A \bowtie B \rightarrow B \bowtie A$) and Implementation Rules (mapping logical operators to physical algorithms, e.g., $A \bowtie B \rightarrow \text{HashJoin}(A, B)$). Rules are fired selectively based on pattern matching against MEMO groups. Once a rule fires, newly created expressions are inserted back into existing or new MEMO groups, seamlessly expanding the search space without duplicating subtree optimization work.
Cascades uses Dynamic Programming and Memoization: once the lowest-cost physical plan for a Group is computed under a specific physical property requirement (e.g. sorted order), that cost is stored in the MEMO. Sub-queries reuse these cached optimal group bounds. Furthermore, Branch-and-Bound Pruning cancels exploration of any subtree as soon as its partial cost exceeds the current best global physical plan cost.
Developer Pitfall — Ignoring Physical Properties (Interesting Orders):
A physical operator choice that is slightly more expensive in isolation (e.g. an Index Scan that is slightly slower than a Sequential Scan) may produce output sorted by an ORDER BY or GROUP BY column. In Cascades terms, this sorted output is an Interesting Order. Passing pre-sorted rows upward eliminates expensive downstream Sort operators or enables fast Merge Joins. Optimizers that discard physical properties prematurely make suboptimal global plan choices.
4. Join Enumeration & Reordering: System R, Dynamic Programming, and Genetic Algorithms
4.1 System R Bottom-Up Dynamic Programming
The classic System R join enumeration algorithm (IBM, Selinger et al., 1979) builds join trees bottom-up using dynamic programming:
System R restricts its search space primarily to Left-Deep Trees (where the right child of every join operator is a base table). Left-deep trees map cleanly to pipelined execution (e.g. building a single hash table and probing it sequentially), but may miss optimal Bushy Trees for complex star/snowflake schema queries.
4.2 Heuristic & Genetic Join Search for Large Joins (GEQO)
When a query joins more than 10 to 12 tables, dynamic programming exceeds time and memory limits. Database engines switch to heuristic or randomized algorithms. PostgreSQL, for instance, switches from DP to GEQO (Genetic Query Optimizer) when `from_collapse_limit` or `join_collapse_limit` (default 8 to 12 tables) is exceeded.
GEQO treats join order permutations as chromosomes in a genetic algorithm, mutating and crossing over candidate join orders over multiple generations to converge on a good physical plan in $O(N)$ time.
Developer Pitfall — Non-Deterministic Plans Triggered by GEQO Thresholds:
If a query joins 14 tables in PostgreSQL, crossing the GEQO threshold (`geqo_threshold = 12`), the optimizer uses randomized genetic search. The engine may generate slightly different physical execution plans for identical queries across runs, leading to unpredictable latency jitter in reporting dashboards. Increase `geqo_threshold` or explicitly rewrite queries into subquery blocks to maintain deterministic DP plan selection.
5. Cardinality Estimation (CardEst) & Database Statistics
5.1 Why Cardinality Estimation Is the Most Critical CBO Component
Cost calculation depends entirely on one metric: Cardinality Estimation (predicting the number of rows that will output from a scan, filter, or join operator). If the optimizer predicts a join will return 10 rows, it will choose a Nested Loop Join. If the join actually returns 10,000,000 rows, the Nested Loop Join will take hours to execute instead of milliseconds!
5.2 Selectivity Formulas for Range and Equality Predicates
Selectivity ($S \in [0, 1]$) is the estimated fraction of table rows satisfying a predicate. For an equality predicate column = 'value' on a column with $D$ distinct values (where the value is not in MCV), selectivity is estimated as:
For range predicates (e.g. val1 <= column <= val2) using an Equal-Depth Histogram bounded by $[\text{Low}, \text{High}]$, selectivity is calculated by interpolating across bucket boundaries:
5.3 Statistics Engine: Equal-Width vs Equal-Depth Histograms
Databases collect statistics by periodically sampling tables (`ANALYZE` command). The statistical profile includes total row count ($N$), null fraction, average width, number of distinct values (n_distinct / $D$), and a Histogram of value distribution.
| Histogram Type | Structure | Strengths & Weaknesses |
|---|---|---|
| Equal-Width Histogram | Divides the value range [min, max] into equal-sized value intervals (buckets). Counts rows per bucket. | Simple, but fails catastrophically on skewed data (skewed values cluster in a single bucket). |
| Equal-Depth (Equi-Height) Histogram | Divides data such that every bucket contains the exact same number of rows ($N / \text{buckets}$). Bucket boundaries vary. | High accuracy across non-uniform distributions. Used by PostgreSQL, Oracle, and SQL Server. |
| Most Common Values (MCV) | Stores the top $K$ most frequent exact values and their exact frequencies separately from the histogram. | Eliminates estimation errors for highly skewed categorical columns (e.g. `status = 'ACTIVE'`). |
5.4 Attribute Value Independence (AVI) and Correlation Failures
Standard selectivity estimation assumes columns are independent (Attribute Value Independence - AVI). The joint selectivity of two predicates is calculated as the product of individual selectivities:
$$\text{Selectivity}(A \text{ AND } B) = \text{Selectivity}(A) \times \text{Selectivity}(B)$$When columns are strongly correlated (e.g., WHERE make = 'Audi' AND model = 'R8'), this independence assumption breaks down completely. If Selectivity(make='Audi') = 0.02 and Selectivity(model='R8') = 0.001, the optimizer estimates joint selectivity as $0.02 \times 0.001 = 0.00002$ (2 rows out of 100,000). But because every R8 is an Audi, the actual matching count is 100 rows! This 50x under-estimation triggers severe plan degradation.
Developer Pitfall — Missing Multi-Column Extended Statistics:
When queries filter on multiple correlated columns, standard single-column histograms produce gross cardinality errors. In PostgreSQL, solve this by creating explicit extended statistics: CREATE STATISTICS s_car_model ON make, model FROM cars; ANALYZE cars;. Extended statistics collect multivariate MCV and dependencies tables, restoring accurate cardinality estimation.
6. Cost Models: Quantifying Physical I/O vs. CPU Weighting
6.1 The Cost Metric Formula
A physical cost model converts estimated page fetches and tuple operations into an abstract cost score (measured in arbitrary disk-page-read cost units). In PostgreSQL, total cost is computed as:
$$\text{Total Cost} = (N_{\text{pages\_seq}} \times \text{seq\_page\_cost}) + (N_{\text{pages\_rand}} \times \text{random\_page\_cost}) + (N_{\text{tuples}} \times \text{cpu\_tuple\_cost}) + (N_{\text{operators}} \times \text{cpu\_operator\_cost})$$By default in older PostgreSQL defaults, seq_page_cost = 1.0 and random_page_cost = 4.0. The 4.0 multiplier reflects traditional spinning hard disk drives (HDDs), where random disk head seeks were 4x slower than sequential reads.
Developer Pitfall — Leaving random_page_cost at 4.0 on Fast NVMe SSD Storage:
If your database runs on high-speed NVMe SSDs or AWS gp3/io2 volumes, leaving random_page_cost = 4.0 artificially penalizes B-Tree Index Scans. The optimizer will incorrectly favor slow Sequential Scans over Index Scans because it overestimates the cost of random SSD block reads. Set random_page_cost = 1.1 on SSD storage environments.
7. Physical Execution Strategies: Nested Loop vs. Hash Join vs. Sort-Merge Join
7.1 Comparative Analysis of Physical Join Operators
The physical optimizer selects among three primary join execution algorithms based on table size, available memory (`work_mem`), and indexing:
| Join Algorithm | Time Complexity | Space Complexity | Optimal Workload Scenario |
|---|---|---|---|
| Nested Loop Join | $O(R \times S)$ without index $O(R \log S)$ with Index Scan |
$O(1)$ Memory | Outer table $R$ is very small (< 100 rows) and inner table $S$ has an indexed lookup key. |
| Hash Join | $O(R + S)$ Average | $O(R)$ (Build side in RAM) | Large unsorted tables with equality join conditions (e.g. `R.id = S.user_id`). Build side fits in `work_mem`. |
| Sort-Merge Join | $O(R \log R + S \log S)$ $O(R + S)$ if pre-sorted |
$O(1)$ to $O(R+S)$ | Both inputs are pre-sorted by B-Tree indexes or join condition includes range operators (`<`, `>`). |
7.2 Mechanics of In-Memory vs. Grace Hash Join
A Hash Join executes in two phases: Build Phase (reads the smaller relation $R$, hashes its join key, and builds an in-memory hash table) and Probe Phase (scans relation $S$, hashes $S$'s join key, and probes the hash table for matches).
If the build table $R$ exceeds `work_mem`, the engine degrades to a Hybrid Grace Hash Join: both $R$ and $S$ are partitioned into matching disk buckets using a second hash function. The engine processes bucket pairs one by one from disk, incurring severe I/O thrashing.
Developer Pitfall — Low work_mem Forcing Grace Hash Join Disk Spills:
If `EXPLAIN (ANALYZE, BUFFERS)` reveals Batches: 32 Memory: 4096kB (written to disk) inside a Hash Join node, the build table exceeded `work_mem` and spilled to disk. Increasing `work_mem` for that session (e.g. `SET work_mem = '256MB';`) keeps the entire hash table in RAM, accelerating execution by 10x to 50x.
8. Adaptive Query Execution (AQE) & Runtime Re-Optimization
8.1 Overcoming Static CBO Mis-Estimates
No matter how sophisticated static CBO estimation becomes, complex predicates and join cascades can still produce estimation errors. Modern cloud analytical and OLTP engines (e.g. Apache Spark, Snowflake, Microsoft SQL Server 2019+, and CockroachDB) employ Adaptive Query Execution (AQE) to fix plan errors dynamically at runtime.
Under AQE, the query execution tree is divided into stages separated by materialization boundaries (such as shuffles or hash builds). When a stage completes execution, AQE collects exact row counts and runtime statistics from the completed stage. If actual row counts differ significantly from the static CBO's estimate, AQE dynamically re-optimizes remaining downstream query stages:
Developer Pitfall — Disabling Adaptive Features in Cloud Analytical Warehouses:
In distributed engines like Spark or Trino, disabling adaptive query execution (`spark.sql.adaptive.enabled = false`) forces the engine to rely exclusively on static estimates. In large ETL pipelines with complex joins, this leads to out-of-memory errors on skewed partitions or massive network shuffle degradation. Keep AQE enabled in cloud warehouse configurations.
9. Step-by-Step Optimization Trace: 4-Table SQL Transformation Walkthrough
9.1 Trace Walkthrough
Let's trace how the CBO transforms a 4-table query from declarative SQL text to a physical execution plan tree:
10. Production Query Diagnosis & EXPLAIN Analysis
10.1 Reading EXPLAIN (ANALYZE, BUFFERS)
Diagnosing query optimizer mistakes requires inspecting real execution metrics with EXPLAIN (ANALYZE, BUFFERS). Look for discrepancy between estimated vs actual rows:
10.2 Understanding Buffer Hit vs. Read Cache Metrics
In BUFFERS output, shared hit indicates pages read directly from PostgreSQL's shared buffer pool in RAM (sub-microsecond latency), while shared read indicates pages that required a system call to the OS Page Cache or physical storage. High shared read numbers under warm cache conditions signal buffer pool exhaustion or un-indexed sequential table scans.
Developer Pitfall — Using Forced Optimizer Hints Instead of Fixing Underlying Statistics:
When a query performs poorly, developers often use query hints (e.g., `pg_hint_plan` or MySQL `FORCE INDEX`) to override the optimizer. While this fixes the immediate issue, query hints bypass CBO dynamic plan adaptation. As data grows or distributions shift, the forced plan will become severely suboptimal. Always fix cardinality estimation errors (run `ANALYZE`, adjust `default_statistics_target`, or create extended statistics) before resorting to hardcoded query hints.
11. Frequently Asked Questions
Q1: What is the primary difference between a Rule-Based Optimizer (RBO) and a Cost-Based Optimizer (CBO)?
A Rule-Based Optimizer (RBO) applies fixed, hardcoded heuristics (e.g., "always use an index if one exists") regardless of table size or data distribution. A Cost-Based Optimizer (CBO) uses statistical data (histograms, page counts, distinct values) to estimate physical I/O and CPU costs for many candidate execution plans, picking the plan with the lowest estimated total cost score.
Q2: Why does `ANALYZE` need to be run periodically in SQL databases?
As applications insert, update, and delete rows, table data distributions change. If statistics become stale, the CBO's cardinality estimates will fail, causing it to select inefficient execution plans (e.g. picking a Nested Loop Join over millions of rows instead of a Hash Join). `ANALYZE` samples table pages to update histograms and distinct value counts in the system catalog.
Q3: How does a Hash Join differ from a Sort-Merge Join?
A Hash Join builds an in-memory hash table on the join key of the smaller input and probes it with rows from the larger input ($O(R+S)$ time). It requires an equality operator (`=`). A Sort-Merge Join sorts both inputs on the join key first ($O(R \log R + S \log S)$) and merges them sequentially. Sort-Merge Joins excel when inputs are already pre-sorted by B-Tree indexes or when join conditions involve inequality operators (`<`, `>`).
Q4: What is the Volcano Iterator Model?
The Volcano Iterator Model (pull-based execution) is the classic execution engine architecture where every physical plan node implements an interface with three methods: `open()`, `next()`, and `close()`. The parent operator repeatedly calls `next()` on child operators to pull tuples one by one up the tree, minimizing memory footprint at the cost of instruction overhead per tuple.
Q5: What are Extended Statistics in PostgreSQL?
By default, database statistics are collected per individual column. If two columns are strongly correlated (e.g., `city` and `zip_code`), standard single-column estimates multiply independent probabilities, severely underestimating row counts. Extended statistics (`CREATE STATISTICS`) track multi-column dependencies and multivariate most-common-value (MCV) lists across column combinations.
Q6: Why are Left-Deep Join Trees preferred over Bushy Join Trees in basic optimizers?
Left-Deep Trees restrict join topology such that the right-hand child of every join operator is always a base relation table. This restricts the search space from Catalan numbers to simple permutations ($N!$) and maps cleanly to pipelined execution where a single hash table is kept in memory while streaming probe rows.
Q7: What causes a Hash Join to spill to disk (Grace Hash Join)?
If the memory required to store the Hash Join's build-side table exceeds the allocated session working memory (`work_mem`), the database engine cannot hold the hash table in RAM. It degrades to a Hybrid Grace Hash Join, partitioning build and probe tuples into matching disk bucket files, causing severe I/O latency.
Q8: How does an Index-Only Scan work?
An Index-Only Scan satisfies a query entirely using the B-Tree index without fetching table pages from physical storage (heap). This occurs when all columns requested in `SELECT`, `WHERE`, and `ORDER BY` clauses are contained within the index structure and the Visibility Map confirms table pages contain no uncommitted transactions.
Q9: What is Subquery Unnesting / Decorrelation?
Subquery decorrelation is a logical optimization transform that converts correlated subqueries (which execute repeatedly for every outer row) into semi-joins, anti-joins, or inner hash joins. This changes query execution complexity from $O(N \times M)$ nested iteration to $O(N + M)$ set-oriented join operations.
Q10: What is the purpose of `random_page_cost` in PostgreSQL?
`random_page_cost` tells the CBO how expensive a random disk page fetch is relative to a sequential page fetch (`seq_page_cost`). On mechanical HDDs, random seeks were 4x slower (`random_page_cost = 4.0`). On modern NVMe SSDs, random reads take nearly identical time to sequential reads, so lowering `random_page_cost` to 1.1 prevents the optimizer from erroneously avoiding B-Tree index scans.