SQL Query Executor: Volcano Iterator Model
Understand the pull-based Volcano iterator execution model in SQL engines. Walk through open(), next(), and close() interfaces, see pipeline breakers like Hash Join
Continue with the guided workspace
Use the paired workspace to connect this guide's mental model with live component state, visible signals, and the outcome each step or scenario is meant to prove.
In relational database management systems (RDBMS), the Volcano Iterator Model (also known as the Pipeline or Iterator Model) is the classic framework for query execution. Designed in the 1990s when memory was highly constrained, it structures physical database operators as a tree of iterators that process data by pulling tuples up the plan tree.
Mental Model
Think of the Volcano model like an assembly line with a demand-driven pull system. The worker at the end of the line (the root node, e.g., the Project operator) asks the worker before them for a single item (next()). That worker asks the next, and so on, propagating requests all the way down to the warehouse (table scan). If an operator needs to sort or join items (a pipeline breaker like Hash Join), it must consume enough input to build its state before it can pass the first result forward; cancellation must then close that state to release buffers.
Components and Why They Exist
Project Operator
The Project operator sits at the root of the query plan, initiating execution by calling next() on its child node and shaping the final column list returned to the client. It pulls tuples one at a time, computes column projections, and yields each formatted output row upward.
Hash Join Operator
The Hash Join operator joins tuples from two child streams by matching join keys in memory. Acting as a pipeline breaker during its build phase, it must first pull and accumulate all tuples from the build-side child into an in-memory hash table before probing begins against the second child stream.
Filter Operator
The Filter operator discards rows that do not satisfy query predicate conditions early in the execution pipeline. By repeatedly invoking next() on its child scan node and evaluating the predicate against each tuple, it drops non-matching rows immediately instead of forwarding them to the join.
Seq Scan (Sequential Scan)
The Seq Scan operator serves as a leaf data source that reads table pages directly from storage when no index is used. Each next() call from its parent Filter node advances the cursor across sequential table blocks to return the next raw tuple.
Index Scan
The Index Scan operator provides targeted data access by traversing an index structure (such as a B+ tree) instead of scanning the entire table. It walks the index entries on demand to locate matching record pointers and supplies probe tuples directly to the Hash Join operator.
Edge Cases and Misconceptions
- Volcano is Pull-Based, not Push-Based: Unlike push-based stream processing systems, Volcano is entirely demand-driven. Rows are only computed when a parent operator requests them via a
next()call. - Pipelining is not Instantaneous: While streaming operators (
Filter,Project) process and forward rows instantly, blocking operators (Sort,Hash Join,Aggregation) must accumulate all input rows before producing their first output row, breaking the pipeline and creating memory and latency spikes. - High CPU Overhead on Large Datasets: Because Volcano makes a virtual function call (
next()) for every single row, processing millions of rows incurs severe CPU branch mispredictions and instruction cache misses, making it less efficient for analytical workloads (OLAP) than columnar vectorization or JIT compilation.
Common Questions
What is the Volcano Iterator model in database systems?
It is a demand-driven query execution model where physical operators are structured as a tree and communicate via three standard methods: open(), next(), and close(). Data flows upward one tuple at a time.
Why is Hash Join considered a 'pipeline breaker' in this model?
A pipeline breaker is an operator that cannot return any output tuples until it has fully processed its input. Hash Join must completely consume and build its hash table from the build input before it can begin probing and returning matched results.
How does the Volcano model achieve low memory overhead?
Because it processes tuples one at a time (streaming) through the tree, it avoids storing full intermediate query results in memory. Only state-accumulating operators (like Hash Joins or Sorts) allocate significant buffers.
What are the modern alternatives to the Volcano Iterator model?
Modern high-performance engines use Vectorization (processing batches of tuples to reduce function-call overhead and enable SIMD) or Just-In-Time (JIT) compilation (compiling query plans into raw machine code to eliminate call dispatching entirely).
Why must a Hash Join read all build-side rows before reading the probe-side rows?
A hash join matches keys by looking them up in a hash table. If the hash table is incomplete, the join cannot know whether a probe row matches. Therefore, it must completely consume the build input to construct the hash table before it can process a single probe row.
How does the Volcano model handle query cancellation?
Query cancellation is typically handled by having operators check a cancellation flag or thread interrupt status inside their next() loop. When an interrupt is detected, the current operator aborts and propagates an error up the tree, causing the engine to call close() on all active operators to free allocated resources.
What is the difference between open(), next(), and close()?
open() propagates initialization down the tree, allocating memory buffers and preparing file scans or index cursors. next() requests the next single row from a child operator, returning either a tuple or an End-Of-File (EOF) marker. close() cleans up operator state, deallocating memory, hash tables, and file handles, moving from the root down.