Volcano — 把'算子可组合'与'并行可分离'拼成执行器范式

是什么

Volcano 不是一个单独的算法，是一套把 SQL 执行器拆成两个正交问题的思想框架。日常类比：像乐高积木 + 一种特殊的传送带——每块积木（算子）只管自己干活，传送带（Exchange）单独负责’让多份积木同时干、再把结果汇起来’。两件事互不知道彼此存在。

它的两条主轴：

算子可组合：任何算子都实现 Open / Next / Close 三函数。Filter 不知道下面是 Scan 还是 Join，Join 也不知道上面是 Sort 还是 Project——所有算子像同型号的乐高接口。
并行可分离：把’多线程 / 数据切分 / 进程间通信’全部塞进一个叫 Exchange 的特殊算子。其他算子完全不知道自己在并行执行；并行性是 Exchange 单独承担的关心。

正因为这两件事被掰开了，Volcano 之后 36 年里，PostgreSQL / Oracle / Spark / DuckDB 加新算子或换并行策略时，几乎不用改其他算子——这是范式级别的回报。

为什么重要

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

为什么 PostgreSQL 加并行查询（v9.6）只新增了 Gather 一个算子，几百个其他算子完全没动
为什么 Spark 的 shuffle 写在 RDD 边界、不写在 map / filter 算子里——这是 Exchange 思想的 RDD 翻译
为什么数据库教材都把’优化器’和’执行器’分开讲——Volcano 第一次把这条边画清楚
为什么 DuckDB 这种’反 Volcano’引擎的论文，每篇都从 Volcano 讲起——它是讨论起点

核心要点

Volcano 框架可以拆成 三块支柱：

三函数迭代器协议：Open() 准备资源，Next() 吐一行（或返回 EOF），Close() 收尾。算子之间只能假设对方实现了这三个函数，不能假设对方是哪种算子。
Exchange 算子封装并行：Exchange 自己 fork N 个 worker 跑下游子树、收 tuple 进队列、按需吐给上游。上下游算子都被’欺骗’——上游以为下游是单线程在产数据，下游以为自己单线程在跑。
机制 vs 策略分离：执行器内核只负责’怎么跑’（机制），优化器负责’跑哪条 plan’（策略）。同一个执行器内核可以驱动关系代数、对象代数、流式代数——只要把算子库换一套。

三块加起来的关键性质：正交。改一块不动其他块。

实践案例

案例 1：PostgreSQL 加并行只动一个算子

PostgreSQL 9.6（2016）首次支持并行查询。设计选型记录在 postgres/postgres@e2b3573/src/backend/executor/nodeGather.c：新增 Gather 算子（= Volcano Exchange 的 N→1 模式），HashJoin / NestLoop / Sort 全部一行没改。

// 简化伪代码：Gather 算子的 Next()
TupleTableSlot *ExecGather(GatherState *node) {
    if (!node->initialized) {
        LaunchParallelWorkers(...);   // 第一次调 Next 时才 fork
        node->initialized = true;
    }
    return gather_getnext(node);     // 从 worker 队列拉一条
}

Volcano 教训直接落地：并行性是 Exchange/Gather 单独承担的关心。

案例 2：写一个 30 行 Python 见证’并行透明’

from queue import Queue
import threading

class Exchange:
    """Volcano Exchange : N 个 worker 跑同一棵子树, 主线程拉队列."""
    def __init__(self, child_factory, n=2):
        self.child_factory, self.n = child_factory, n
        self.q, self.done = Queue(maxsize=64), 0
        self.lock = threading.Lock()
    def _worker(self):
        op = self.child_factory(); op.open()
        while (t := op.get_next()) is not None: self.q.put(t)
        op.close()
        with self.lock:
            self.done += 1
            if self.done == self.n: self.q.put(None)
    def open(self):
        self.threads = [threading.Thread(target=self._worker) for _ in range(self.n)]
        for th in self.threads: th.start()
    def get_next(self): return self.q.get()
    def close(self):
        for th in self.threads: th.join()

把任何已写好的单线程算子塞进 child_factory，外层调 Exchange.get_next() 的代码看不出任何变化——这就是 Volcano 不变式的力量。

案例 3：流处理框架其实是分布式 Volcano

Apache Flink 的 source / transform / sink 算子链 = Volcano 的算子树；Flink 的 network shuffle = Exchange 的 TCP 版；Flink 的 watermark / checkpoint = Volcano 没解决但工程上必须补的’容错维度’。

读完 Volcano 再读 Flink 文档，会发现 80% 概念能直接对上号——剩下 20% 是 Volcano 当年没考虑分布式留下的坑。

踩过的坑

以为 Exchange 在分布式自动适用：Volcano 假设单机共享内存队列。把它套到跨机器场景，TCP 延迟从 ns 跳到 ms、worker 崩溃要全 plan 重跑——Spark RDD 重新发明 DAG scheduler 的根本原因，就是 Exchange 模型在分布式下水土不服。
以为’三函数迭代器’是协议要求：很多人把’一次返回一行’当成 Volcano 的硬规定，于是 OLAP 跑得慢就怪范式。其实’一次一行’只是 1990 年硬件下的合理选择，接口可以不变、粒度换成 chunk 就能拿到向量化收益（DuckDB 走的路）。
在算子里偷偷写并行控制：违反 Exchange 不变式的最大诱惑——‘我这个 HashJoin 自己开两个线程不就行了’。代价是新加的并行算子要重写、调度逻辑散落各处、debug 噩梦。Volcano 的核心教训就是抗拒这个诱惑。
拿 Volcano cost model 评估向量化引擎：粒度差了 2048 倍，cost 公式不可比。这是迁移引擎时常见的’看起来变慢了’误判。

适用 vs 不适用场景

适用：

任何’算子链 + 数据流’结构的系统：SQL 执行器 / 流处理 / ETL / dataflow 工具
单机或共享内存并行：算子树 + Exchange 直接落地，工程量极小
需要算子库可扩展：加新算子 = 写一个 struct + 三函数，不动其他算子
教学场景：50 行 Python 就能复现核心思想，门槛极低

不适用：

跨机器分布式 + 高可用：Volcano 没回答容错问题，需要补 DAG scheduler / lineage 重算
极致 OLAP 性能：1 tuple 粒度浪费 SIMD，要切到向量化或编译执行
点查 / OLTP-like 工作负载下硬上 push-based：source 一推就是 chunk，撤不回来——拉式 Volcano 反而更优
流处理的 watermark / 状态管理：Volcano 不假设 input 有时间维度

历史小故事（可跳过）

1989：Goetz Graefe 在科罗拉多大学博尔德分校博士在读，研究方向是’查询执行器的可扩展性’。
1990：Graefe 完成博士论文《Volcano: An Extensible and Parallel Dataflow Query Processing System》，第一次把’算子可组合 + 并行可分离’两件事拼到一起。
1994：论文 IEEE TKDE 期刊版发表，30 页双栏。引用数 36 年后超过 2700 次，是数据库执行器领域最高引论文之一。
1995：Graefe 在微软研究院发表 Cascades 论文，把 Volcano 优化器部分进一步形式化。微软 SQL Server / Calcite / Greenplum ORCA 用的都是 Cascades + Volcano 执行器。
2005：Boncz 等人发表 MonetDB X100，第一次系统挑战 Volcano 的 1-tuple 粒度——但保留接口、只换粒度。

学到什么

‘掰开两个正交问题’是范式级杠杆：Volcano 的全部价值不是某个具体算法，是把’算子组合’与’并行调度’分开这一刀。设计任何复杂系统时都该先问’有没有两件事正在被搅在一起’。
接口稳定 36 年的代价是粒度过时：1 tuple 在 1990 是合理选择，2005 后变成显著开销。接口对 ≠ 粒度对——这是面对长寿设计要警惕的细分维度。
正交分离让生态可演化：Volcano 之后所有改进都只动一块（Cascades 改优化器 / X100 改粒度 / HyPer 改控制流），不动其他块就能落地——这是范式被验证’抗腐烂’的标志。
可读性 = 长期影响力的乘数：Volcano 论文 30 页、Python 50 行可复现核心思想——读得懂的论文才会被持续引用、被持续改进。

关联

volcano-1994 —— 1994 TKDE 期刊版的细读：三函数迭代器协议本身
selinger-1979 —— System R 优化器，Volcano Section 6 的直接前作
cascades-1995 —— Graefe 自己的优化器后续：top-down memo + branch-and-bound
bigtable —— 大规模分布式存储，与 Volcano 的’算子正交’思想一脉相承
bernstein-1981-cc —— 并发控制经典，与 Volcano 的执行模型形成数据库内核两条主线
aries-1992 —— 恢复算法经典，Volcano 没解的容错维度的工业答卷

反向链接

aries-1992 —— ARIES 1992 — 数据库崩溃后怎么把账目对回来
bernstein-1981-cc —— Bernstein 1981 并发控制综述 — 把分布式数据库的 20+ 算法整成两条主线
cascades-1995 —— Cascades 1995 — 用规则 + Memo 拼装一个可扩展查询优化器
f1-2013 —— F1 2013 — 把 Spanner 包成 SQL，扛起 AdWords 全部账单
leis-2015-optimizers —— Leis 2015 — 用真实数据打脸所有数据库的查询优化器
paxos —— Paxos — 分布式共识算法
polars —— Polars — Rust 写的列存 DataFrame
selinger-1979 —— Selinger 1979 — 基于代价的查询优化
spanner —— Spanner — 全球分布式 SQL 数据库
volcano-1994 —— Volcano 1994 — 把 SQL 执行写成 next() 拉式数据流