Part 7: Query Execution Engines: Volcano Iterators & Cost-Based Optimization
Module Overview
When an application submits a declarative SQL query, the database engine must translate the text into an optimal sequence of low-level algorithms. In this seventh installment, we analyze the Query Processing Pipeline: Abstract Syntax Trees, logical query plans, the classic Volcano Iterator Model, physical join implementations (Nested Loop, Sort-Merge, Grace Hash Join), and Cost-Based Optimization (CBO) utilizing catalog statistics and dynamic programming.
1. The Query Processing Pipeline
- Lexical & Syntactic Analysis: Parses raw SQL text into an Abstract Syntax Tree (AST), ensuring grammar conformance.
- Semantic Analysis & Binder: Validates table and column names against the system catalog, binds identifiers, and verifies user access privileges.
- Logical Plan Generation: Converts the bound AST into an initial tree of relational algebra operators (Select, Project, Join).
- Cost-Based Optimization (CBO): Explores alternative algebraically equivalent physical execution trees, evaluates catalog statistics, and selects the lowest-cost plan.
- Code Generation / Execution: Compiles the physical plan into bytecode or invokes the execution engine to stream tuple results.
2. The Volcano Iterator Execution Model
First formulated by Goetz Graefe in 1994, the Volcano Model (also termed the Pipeline or Iterator Model) defines every physical operator in the execution tree through a simple, standardized interface containing three core methods:
open(): Initializes operator state, allocates hash tables or sort buffers, and opens child iterators.next(): Returns either the next single matching tuple or anEOFmarker.close(): Cleans up scratch memory allocations and closes child operator streams.
Pipelined Processing Advantage
Tuples are pulled demand-driven from the root of the tree down to the leaves one record at a time. The engine can begin streaming results to the client before preceding operations finish reading their entire tables, dramatically reducing memory footprint.
3. Physical Join Algorithms Compared
| Join Algorithm | Time Complexity | I/O Cost | Best Applied When |
|---|---|---|---|
| Nested Loop Join (NLJ) | $O(|R| \cdot |S|)$ | $M + (M \cdot N)$ | One table is tiny, or the inner table has an index on the join key (Index NLJ: $O(|R| \cdot \log |S|)$). |
| Sort-Merge Join (SMJ) | $O(R \log R + S \log S)$ | $3(M + N)$ | Both tables are already sorted on join attributes (e.g., clustered index) or query includes ORDER BY. |
| Grace Hash Join | $O(|R| + |S|)$ | $3(M + N)$ | Large unsorted tables with equality join predicates; builds in-memory hash table on smaller relation. |
4. Cost-Based Optimization & Statistical Selectivity
The Cost-Based Optimizer (CBO) estimates the total system cost (a weighted sum of disk block I/Os, CPU instruction cycles, and memory pressure) for thousands of feasible execution plans:
To accurately predict the cardinality (number of output rows) of intermediate joins and filters, the database engine maintains an internal statistical catalog:
- Equi-Width & Equi-Depth Histograms: Partition attribute domain values into buckets to estimate selectivity for range queries (e.g.,
salary BETWEEN 50000 AND 80000). - HyperLogLog (HLL): Probabilistic cardinality estimators that calculate the number of distinct values (NDV) in billion-row datasets using only kilobytes of state.
- Dynamic Programming (Selinger Algorithm): Solves the combinatorial join-ordering search space ($N!$ permutations for $N$-way joins) by finding optimal plans bottom-up for sub-relations.
Next in Curriculum
In Part 8: Transactions: ACID Guarantees, Isolation Levels & MVCC Concurrency, we transition from single-query execution to multi-user concurrency control, locks, and Multi-Version Concurrency Control (MVCC).
Related reading
How to Give Google Antigravity Direct SSH Access to Remote Servers (Proxmox & Linux)
Connect Google Antigravity directly to Proxmox and Linux servers using the Model Context Protocol (MCP), dedicated Ed25519 keys, and automated updates.
By Md. Harun-Or-Roshid
Part 9: Load Balancing: Layer 4 vs Layer 7, Algorithms, Reverse Proxies & High Availability
Master high-availability load balancing, comparing Layer 4 transport vs Layer 7 application routing, consistent hashing rings, and health checks.
By Md. Harun-Or-Roshid
Part 10: Distributed Databases: Partitioning, Sharding, 2PC & CAP Theorem
Master distributed database architecture: horizontal sharding, consistent hashing, two-phase commit (2PC), CAP theorem trade-offs, and NewSQL engines.
By Md. Harun-Or-Roshid
Part 10: Multicore Systems: SMP, NUMA Architecture & Amdahl's Law Scaling
A study of multicore scalability, exploring Symmetric Multiprocessing (SMP), Non-Uniform Memory Access (NUMA), Amdahl's law, and on-chip mesh Networks-on-Chip.
By Md. Harun-Or-Roshid