The Volcano Execution Model & Cost-Based Optimizer: From SQL to EXPLAIN Plans

A developer pushes a report query to production:

SELECT users.name, COUNT(orders.id) AS total_orders
FROM users
JOIN orders ON users.id = orders.user_id
WHERE users.country = 'CA' AND orders.status = 'COMPLETED'
GROUP BY users.id, users.name;

In staging, against 1,000 test rows, this query returned in 3 milliseconds.

In production, against 50,000,000 rows, the query runs for 48 seconds, spiking CPU utilization across all database cores to 100%.

Why did the database execute this query so slowly?

SQL is a declarative programming language. You specify what data you want, but you do not specify how the storage engine should retrieve it.

Behind the scenes, the database compiler must translate your text query string into a physical binary execution tree, choosing between full table scans, index range scans, hash joins, or nested loops.

Understanding The Volcano Execution Model and the Cost-Based Optimizer (CBO) is essential to predicting database behavior under production loads.

The Query Processing Pipeline

When a database connection receives a raw SQL text string over the network socket, it processes the request through four sequential transformation stages:

[ Raw SQL String ]
        |
        v
 +--------------+
 |  1. Parser   |  ---> Generates Abstract Syntax Tree (AST) & validates schema
 +--------------+
        |
        v
 +--------------+
 |  2. Logical  |  ---> Applies relational algebra (Predicate Pushdown, Projection)
 |  Optimizer   |
 +--------------+
        |
        v
 +--------------+
 |  3. Physical |  ---> Calculates execution cost (I/O + CPU) for candidate plans
 |  Optimizer   |       using catalog statistics & selects lowest cost plan
 +--------------+
        |
        v
 +--------------+
 | 4. Execution |  ---> Executes physical iterator tree using Volcano Model
 |    Engine    |
 +--------------+

1. Parsing and AST Generation

The parser verifies SQL syntax and converts the string into an Abstract Syntax Tree (AST).

For example, the predicate WHERE status = 'COMPLETED' AND amount > 100 becomes an operator node tree:

          [ AND ]
         /       \
      [ = ]     [ > ]
     /     \   /     \
  status  'C' amount  100

During semantic analysis, the engine verifies that the orders table exists, the user has read privileges, and column names resolve to valid field data types.

2. Logical Query Optimization (Relational Algebra)

The Logical Optimizer applies rule-based relational algebra rewrites to transform the AST into a normalized logical query plan.

Key Relational Algebra Rewrites

Predicate Pushdown: Moves WHERE filter conditions as close to the physical table scan nodes as possible. Evaluating country = 'CA' before performing an expensive table join eliminates non-matching rows early, drastically reducing join memory overhead.
Projection Pushdown: Eliminates unused columns from memory payloads early so intermediary iterators don’t copy unnecessary byte arrays.
Constant Folding: Pre-evaluates static expressions like WHERE timestamp > NOW() - INTERVAL 7 DAY once during compilation instead of recalculating the timestamp for all 50,000,000 rows.

3. Physical Optimization & Cost-Based Optimizer (CBO)

A single logical plan can be executed physically in hundreds of different ways:

Should it scan users first or orders first?
Should it use an Index Range Scan or a Full Table Scan?
Should it execute a Nested Loop Join or a Hash Join?

The Cost-Based Optimizer (CBO) calculates the estimated cost of candidate execution paths and selects the plan with the lowest total score.

The Cost Formula

$\text{Cost} = (\text{Page Fetches} \times \text{I/O Block Cost}) + (\text{Row Evaluated} \times \text{CPU Operator Cost})$

Default cost parameters in MySQL InnoDB:

memory_block_read_cost: 0.25 (Reading a 16KB page frame from Buffer Pool RAM)
io_block_read_cost: 1.00 (Reading a 16KB page from physical NVMe disk)
row_evaluate_cost: 0.10 (CPU cycles to evaluate a row filter predicate)

Data Statistics and Histograms

To estimate how many rows a query predicate will match (Cardinality Estimation), the CBO reads statistics collected in information_schema:

Total table page counts.
Distinct value counts ( $N_{\text{distinct}}$ ) for indexed columns.
Equi-height Histograms: Range buckets tracking value distribution across skewed datasets.

If statistics are out of date, the optimizer might miscalculate costs—for instance, assuming a predicate matches 10 rows when it actually matches 5,000,000—leading to catastrophic execution plan selection. Running ANALYZE TABLE refreshes these metrics.

4. The Volcano Execution Model (Iterator Pattern)

Once a physical plan is chosen, the engine executes it using the Volcano Execution Model (also known as the Iterator Model or Pipelined Model).

Every physical operator node in the execution plan implements a uniform 3-method interface:

public interface VolcanoIterator {
    void open();         // Initialize resources, open child iterators
    Tuple next();        // Return the next single matching tuple, or NULL if EOF
    void close();        // Release memory, file handles, and locks
}

Tree Execution Flow

Iterators are composed into a parent-child execution tree. Execution flows from top to bottom via recursive next() invocations:

                     [ Aggregate Iterator ]
                               |  next()
                               v
                     [ Filter (status='COMPLETED') ]
                               |  next()
                               v
                     [ Hash Join Iterator ]
                      /                  \
              next() /                    \ next()
                    v                      v
        [ Index Scan: users ]      [ Table Scan: orders ]

Why Volcano Is Efficient

Pipelined Row-by-Row Streaming: Rows are pulled upward through the operator chain one tuple at a time. The engine doesn’t need to materialize 10,000,000 intermediate join rows in RAM before applying downstream filters.
Low Memory Footprint: Memory usage remains minimal regardless of table size.

Pipeline Breakers

Certain operations cannot stream rows tuple-by-tuple:

ORDER BY (Sorting requires examining all dataset tuples before emitting the top row).
GROUP BY Aggregations without an index.
Hash Join build phase.

These operators act as Pipeline Breakers—they must fully pull and materialize all child tuples into memory or temporary disk files before emitting their first output row.

Inspecting Execution Trees with MySQL EXPLAIN

In modern MySQL versions (8.0+), you can inspect the exact physical iterator tree generated by the optimizer using EXPLAIN FORMAT=TREE:

EXPLAIN FORMAT=TREE 
SELECT u.name, o.amount 
FROM users u 
JOIN orders o ON u.id = o.user_id 
WHERE u.country = 'CA';

Example Tree Output

-> Nested loop inner join  (cost=1250.50 rows=500)
    -> Index lookup on u using idx_country (country='CA')  (cost=125.00 rows=500)
    -> Single-row index lookup on o using PRIMARY (id=u.id)  (cost=2.25 rows=1)

Reading EXPLAIN FORMAT=TREE:

Execution starts at the innermost indented leaf nodes (Index lookup on u).
Rows stream upward into the Nested loop inner join parent operator.
The parent operator uses the user key to invoke the Single-row index lookup on o iterator for each matching record.

Summary & Next Steps

SQL query execution bridges declarative code and physical storage hardware:

Parsing converts text strings into Abstract Syntax Trees (ASTs).
Logical Optimization simplifies plans using relational algebra (Predicate Pushdown).
Cost-Based Optimization (CBO) calculates I/O and CPU unit costs using table statistics to choose the cheapest plan.
The Volcano Execution Model streams tuples through recursive next() iterator calls, minimizing memory allocations.

In the next article, we take a deep dive into Join Algorithms Under the Hood: Nested Loop, Hash Join, and Sort-Merge Join Mechanics.

References & Further Reading

Kung, H. T., & Robinson, J. T. (1981). On Optimistic Methods for Concurrency Control. ACM Transactions on Database Systems (TODS), 6(2), 213–226.
PostgreSQL Global Development Group. PostgreSQL 16 Documentation: Chapter 13 Concurrency Control (MVCC). PostgreSQL Docs.
Bernstein, P. A., & Goodman, N. (1983). Multiversion Concurrency Control Theory and Algorithms. ACM TODS, 8(4), 465–483.