Volcano 1994 — 把 SQL 执行写成 next() 拉式数据流

是什么

Volcano 是一份把数据库执行器写成”算子树 + 三函数迭代器”的设计。日常类比：像一条自助取餐传送带——下游饿了喊一声 next()，上游做出一份就传一份；不喊就不做。

你写 SQL：

SELECT name FROM users WHERE age > 18;

数据库内部会编译成一棵算子树：Project(name) → Filter(age>18) → Scan(users)。每个算子都实现三个函数：Open() 准备资源、Next() 吐一行、Close() 收尾。

执行时根节点（Project）调一次 Next()，向下传给 Filter，Filter 又向下喊 Scan，Scan 从磁盘读一行回来——再一路向上返回到 Project。整个执行就是”沿树自顶向下喊、自底向上抬”，懒得不能再懒。

这套接口让 36 年后的 PostgreSQL / Oracle / SQL Server / Spark / DuckDB 几乎一字不差地复用。Volcano 是现代 SQL 执行器的骨架。

为什么重要

不理解 Volcano，下面这些事都没法解释：

为什么 PostgreSQL 源码里有 ExecInitNode / ExecProcNode / ExecEndNode 这套三函数——那就是 Open/Next/Close 改了名
为什么 Spark 把数据流叫 Iterator[InternalRow]，DuckDB 把它叫 GetChunk()——都是 Volcano 的变体
为什么数据库可以”一份算子代码同时跑串行和并行”——Exchange 算子把并行藏起来了
为什么 2010 年代有人写论文骂”迭代器太慢，得做向量化 / 编译”——是在和 Volcano 对话

核心要点

Volcano 三个最重要的设计可以拆成三层：

算子 = 迭代器（Open / Next / Close）：所有算子都长一样的接口。类比：电池标准化以后，任何遥控器都能装任何牌子的 AA 电池——接口比内核更值钱。
拉式执行（pull-based）：根节点喊 next()，往下一路传，叶子节点（Scan）读一行回来。和”推式”（push-based，叶子主动推）相反。拉式简单、好调试、控制反转明确，懒到极致。
Exchange 算子封装并行：把”跨进程发数据”也包成一个普通迭代器。在算子树里随便插一个 Exchange，上下游就自动变成”两个进程并行跑、Exchange 中间帮你 shuffle”。其它算子完全不知道自己被并行化了。

三层加起来叫 Volcano model 或 iterator model，也是后来 dataflow toolkit 思想的源头。

实践案例

案例 1：PostgreSQL 里的 Volcano 接口

打开 Postgres 源码 src/backend/executor/execProcnode.c，你会看到：

TupleTableSlot *ExecProcNode(PlanState *node)  // 拉一行，对应 Next()
void ExecInitNode(Plan *node, EState *estate)  // 准备资源，对应 Open()
void ExecEndNode(PlanState *node)              // 收尾，对应 Close()

每个算子（SeqScan / HashJoin / Sort / Aggregate）都实现这三个函数。逐部分解释：

ExecProcNode 返回一行（一个 TupleTableSlot），返回 NULL 表示流结束
上层算子拿到一行后做完自己的处理（比如 Filter 判断是否丢掉），再拉下一行
整棵树自顶向下递归调用，和 1994 年论文里画的图一模一样
30 年没换过名字，是接口稳定性的极致案例

案例 2：Exchange 算子怎么把并行藏起来

Aggregate
   ↓ next()
Exchange(hash by user_id)   ← 把并行性藏在这里
   ↓ next()
Scan(events)

加上 Exchange 后，Scan 在 4 个 worker 上并行扫表，Exchange 内部按 user_id 哈希 shuffle 到上游 4 个 Aggregate 实例。Aggregate 完全感知不到自己被并行化，它收到的还是普通的 next() 调用。

这就是论文的杀手锏：并行性是一个可插拔的 wrapper，不污染算子代码。

案例 3：DuckDB 把 Next() 升级成 GetChunk()

DuckDB 源码 src/include/duckdb/execution/physical_operator.hpp：

virtual OperatorResultType Execute(DataChunk &input, DataChunk &chunk, ...);

每次返回 1024 行（一个 DataChunk）而不是 1 行。这就是向量化执行——保留 Volcano 的算子树形状，把”一行一调用”改成”一批一调用”，摊平 virtual call 开销。

对照原版 Volcano，唯一的差别是返回的颗粒度：行 → 批。算子树形状、调用方向、Open/Close 钩子完全一样。Volcano 模型还活着，只是吃了药变快了。

踩过的坑

以为 Volcano = 1990 年那篇短文：1990 是初版，1994 TKDE 才是定稿，含完整 Exchange 算子和 dataflow toolkit 设计；课件常引错。
以为迭代器模型必然慢：慢是 per-tuple virtual call + 缓存不友好的现代 CPU 现象。1994 年瓶颈在磁盘 IO，迭代器的简洁性远胜性能开销；2000s CPU 加速后才暴露问题。
把 Exchange 当成”shuffle 算子”：它是一个能在任意位置插入的并行性 wrapper，可同时实现 producer/consumer 解耦、partition 重分布、pipeline 并行——shuffle 只是它的一种用法。
以为 Volcano 已经死了：Postgres / DuckDB / Spark SQL 物理算子接口几乎一字不差就是 Open/Next/Close；ClickHouse / Snowflake 也是迭代器加上向量化扩展。骨架还活着。

适用 vs 不适用场景

适用：

SQL 数据库执行器骨架（OLTP / OLAP 都行）
需要把”算子组合”和”并行硬件”解耦的批处理系统（Spark / Flink）
教学：第一次理解”查询计划如何变成可执行代码”
需要支持任意算子组合的 dataflow 框架（即使不是 SQL）

不适用：

极致 OLAP 性能（CPU bound）→ 改向量化（DuckDB）或编译（HyPer / Photon）
实时流处理且每行延迟敏感 → push-based 模型（Flink）更自然
嵌入式键值访问（不需要算子组合）→ 直接调存储引擎更简单

历史小故事（可跳过）

1986 年：Goetz Graefe 在 Wisconsin-Madison 读博，做 EXODUS 可扩展数据库的执行器，是 Volcano 的前身
1990 年：发表 Volcano 短文，提出迭代器接口和 Exchange 算子
1994 年：在 IEEE TKDE 6(1) 发表完整版（本笔记主角），把 1990 短文 + 后续工作整合
1995 年：Graefe 发表 Cascades 优化器框架，影响 SQL Server / CockroachDB / Calcite
2005 年：MonetDB/X100 提出向量化执行，对 Volcano 的”per-tuple 调用”开刀，但保留树形
2011 年：Neumann 在 VLDB 用 HyPer 提出 push-based 编译执行，正式向 Volcano 模型发起挑战；2024 年 Volcano-style 仍是工业主流

学到什么

接口的力量：三个函数的简单接口（Open / Next / Close）比再花哨的具体实现更值钱——这是 32 年后还在用的根本原因
抽象隔离硬件：Exchange 算子让”算子代码”和”并行硬件”解耦，是 dataflow 系统的一次设计胜利
简洁 > 性能：1994 年选简洁，是因为瓶颈在 IO；今天有人选编译，是因为瓶颈在 CPU。架构选择跟着瓶颈走
向量化是 Volcano 的子代而非反对者：DuckDB / ClickHouse 保留树形 + 迭代器，只把”行”改成”批”
学一个范式，先学它的接口而不是它的实现：迭代器三函数比具体算子代码更应该背下来

关联

selinger-1979 —— 查询优化器：Volcano 是它的下游，优化器选好计划后由 Volcano 执行
system-r-1976 —— SQL 数据库的祖先，定义了”优化器 → 执行器”的分工模式
aries-1992 —— 同年代的恢复算法：Volcano 管”读”，ARIES 管”写后崩溃恢复”
bernstein-1981-cc —— 并发控制：Volcano 在事务上层跑，并发控制管事务之间互不踩
spanner —— 现代分布式数据库执行器，仍是迭代器 + Exchange 的变体（跨数据中心）
bigtable —— 列式存储 + 迭代器接口，证明 Volcano 模式不限于关系型

反向链接

aries-1992 —— ARIES 1992 — 数据库崩溃后怎么把账目对回来
bernstein-1981-cc —— Bernstein 1981 并发控制综述 — 把分布式数据库的 20+ 算法整成两条主线
cascades-1995 —— Cascades 1995 — 用规则 + Memo 拼装一个可扩展查询优化器
dewitt-gray-1992 —— DeWitt-Gray 1992 — 并行数据库取代专用机的宣言
distserve —— DistServe — 把 prefill 和 decode 拆到不同 GPU 上跑
duckdb-2019 —— DuckDB — 把 OLAP 数据库塞进你的 Python 进程
halide —— Halide — 把”算什么”和”怎么算”分开写
leis-2015-optimizers —— Leis 2015 — 用真实数据打脸所有数据库的查询优化器
monetdb-x100-2005 —— MonetDB/X100 — 让数据库一次处理一向量行而不是一行
neumann-2015-large-joins —— Adaptive Optimization of Very Large Join Queries — 100 张表也敢精确求解
pandas —— pandas — Python 表格数据事实标准
polars —— Polars — Rust 写的列存 DataFrame
rocksdb-lsm —— LSM-tree 与 RocksDB — 把所有写都变成顺序写
selinger-1979 —— Selinger 1979 — 基于代价的查询优化
spanner —— Spanner — 全球分布式 SQL 数据库
system-r-1976 —— System R 1976 — 第一个跑起来的关系数据库
volcano —— Volcano — 把’算子可组合’与’并行可分离’拼成执行器范式