Paper · Query Processing

Volcano — An Extensible and Parallel Query Evaluation System

G. Graefe · IEEE Transactions on Knowledge and Data Engineering · 1994

The iterator model that most query engines still use today.

Summary

Query engines need a way to combine operators such as scans, joins, sorts and aggregations into plans, and to run those plans in parallel, without rewriting each operator for every context. Volcano provides a uniform structure that is both extensible and parallel.

Every operator implements the same iterator interface: open, next and close. Plans become trees of iterators that pull one tuple at a time from their children. Parallelism is added by a separate exchange operator, which handles partitioning and communication between processes, so the other operators stay unaware that they run in parallel.

The iterator model is still the default execution design in many systems, including PostgreSQL. Its per-tuple overhead also motivated later work on vectorised and compiled execution, which is why understanding it is a prerequisite for those papers.

Key ideas

  • A uniform open, next and close iterator interface for every operator.
  • Pull-based, tuple-at-a-time execution through a tree of operators.
  • The exchange operator encapsulates parallelism and data partitioning.
  • Operators are composable and extensible without knowing about each other.

More Query Processing papers