火山模型与算子

数据库中的火山模型是一种经典的查询执行模型，由 Goetz Graefe 于 1994 年在《Volcano - An Extensible and Parallel Query Evaluation System》中提出，因此也被称为 迭代器模型。它的核心思想是将查询执行计划中的每一个物理操作抽象成一个独立的算子，并通过统一的接口让数据在算子之间自底向上“拉取”传递。下面我会从模型原理、算子实现、优缺点与现代演进几个层面，为你做一个全面细致的解析。

一、火山模型的运行机制

1. 统一迭代器接口

每个算子都被封装成一个迭代器，对外只暴露三个方法：

Open()：初始化算子，分配资源（如内存、文件句柄），并递归调用子算子的 Open()。

Next()：向上层返回一行（tuple）数据。若没有更多数据，则返回 `EOF`（End of File 标记）。这是模型的核心。

Close()：清理资源，递归关闭子算子。

2. “拉取”式数据流

火山模型是 pull-based的执行方式：

执行引擎从查询计划树的根节点开始，调用根算子的 `Next()`。

根算子为了产出一行，会调用它的子算子的 `Next()`，如此层层向下调用，直到叶子节点（如全表扫描算子）从磁盘或内存中读取一行原始数据。

数据再沿调用栈逐层向上返回，每经过一个算子就会被加工一次（过滤、投影、连接等），最终到达根节点输出给客户端。

这种一拉到底，再逐级传回的方式，很像火山喷发时岩浆从地底逐层上升，故称火山模型。

3. 一次一行的处理粒度

经典火山模型的 `Next()` 每次只返回一个元组，算子也每次只处理一个元组。这使得内存占用极低，逻辑清晰，但函数调用次数非常多（百万行数据就有百万次虚函数调用），这也是它后来被向量化模型替代的主要原因。

二、火山模型的优缺点

优点

简洁与可组合：

所有算子接口相同，任意复杂查询都可通过搭建一棵算子树实现，扩展新算子只需实现三个接口。

流式处理，内存节约：

非阻塞算子可以边读边处理，不需要缓存大批数据，适合处理海量数据集。

易于实现流水线并行：

只要解决上下文切换问题，多线程可自然形成生产者-消费者流水线。

中断/取消天然支持：

只要在 `Next()` 中检查中断标志并返回 `EOF` 即可优雅停止查询。

缺点

虚函数开销巨大：

每处理一行都要经历从根到叶的多次虚函数调用，CPU 分支预测频繁失败。

Cache 与 SIMD 不友好：

一次一行的模式使得代码和数据局部性很差，难以利用 CPU 的向量化指令（SIMD）批量处理。

阻塞算子内存压力：

排序、哈希连接等需要先吃掉全部子节点数据才能开始产出行，遇到大数据集可能 OOM。

难以发挥现代硬件特性：

无法充分利用多核、预取、批量 I/O 等优化。

三、算子详解

在火山模型中，算子是构成查询执行树的基本单元，一个算子对应关系代数中的一种操作，并负责维护自己的执行状态。

算子的分类

无状态算子（Stateless）：

每次 `Next()` 仅依赖于一次或几次子算子的返回值，不跨行保存额外信息。如过滤、投影。

有状态算子（Stateful）：

需要累积多行（甚至全部输入）才能产出一行结果，必须在内部维护哈希表、排序缓冲区等状态。这类算子通常是阻塞算子。

阻塞与非阻塞：

非阻塞算子：

`Next()` 不会长时间等待，可形成流水线。

阻塞算子：

在 `Open()` 阶段就会通过循环调用子算子的 `Next()` 将所有输入全部耗尽，构建内部数据结构。之后自己的 `Next()` 才从内部结构中取数输出。

四、常见算子实现剖析

下面以伪代码和逻辑描述的形式，说明各典型算子在火山模型下的内部行为。

1. 扫描算子（Table Scan / Seq Scan）

叶子节点，从存储引擎获取数据。

Open(): 打开表文件，定位到第一条记录。

Next(): 从文件读取下一条记录，组装成元组；无数据则返回 EOF。

Close(): 关闭文件。

索引扫描（Index Scan）与之类似，只是通过索引获取满足条件的元组物理位置再回表，但接口不变。

2. 过滤算子（Filter / Selection）

非阻塞，无状态。

Open(): child.Open()

Next():

while (tuple = child.Next()) != EOF:

if 谓词(tuple) 为真:

return tuple

return EOF

Close(): child.Close()

它不停地从子节点拉取，直到找到满足条件的行才向上返回，对上层透明。

3. 投影算子（Projection）

非阻塞，无状态。

Next():

tuple = child.Next()

if tuple == EOF: return EOF

计算表达式列表，生成新元组（可能只保留部分列）

return 新元组

4. 排序算子（Sort / Order By）

阻塞算子，有状态。

Open():

child.Open()

初始化一个空列表 buffer

while (t = child.Next()) != EOF:

buffer.append(t)

按排序键对 buffer 排序

buffer 上设置迭代指针 cursor = 0

child.Close() // 可选：因为数据已全部取出

Next():

if cursor < buffer.size():

return buffer[cursor++]

else:

return EOF

Close(): 释放 buffer

如果是基于外存的排序（外部归并排序），内部会分多轮进行，但对外仍是阻塞、一次一行输出。

5. 限制算子（Limit）

非阻塞，但带计数器。

Open(): child.Open(); count = 0

Next():

if count >= limit: return EOF

tuple = child.Next()

if tuple == EOF: return EOF

count++

return tuple

6. 聚合算子（Aggregation）

通常为阻塞算子（如果无分组则内部只保留累加器，亦可流式）。

哈希聚合（Hash Aggregation）：

Open():

child.Open()

初始化哈希表 (key -> 累加状态)

while (t = child.Next()) != EOF:

计算 group key

在哈希表中更新聚合状态（count, sum, min, max...）

child.Close()

将哈希表条目转为迭代器，比如存成列表

Next():

从列表中顺序取下一组聚合结果（key + 聚合值），返回一行

```

排序聚合：

先由 Sort 算子按分组键排序，再顺序扫描合并，可利用排序流特性省去哈希表，但仍需排序算子阻塞。

7. 连接算子（Join）

(1) 嵌套循环连接（Nested Loop Join）

传统上左表为外层，右表为内层。有两种实现方式：

基于迭代器的嵌套循环（右表可能需要重复扫描）：

Open(): left.Open(); right.Open(); left_tuple = left.Next()

Next():

loop:

if left_tuple == EOF: return EOF

right_tuple = right.Next()

if right_tuple != EOF:

if 连接条件(left_tuple, right_tuple):

组合并返回

else:

// 右表扫完一轮，重置右表，取下一行左表

right.Close()

right.Open()

left_tuple = left.Next()

```

可见右表如果是基础扫描，会被反复打开关闭，代价极高。实际系统会结合索引或缓存优化。

(2) 哈希连接（Hash Join）

典型阻塞算子，分为构建（Build）和探测（Probe）两阶段。

Open():

// 构建阶段：选择较小的子节点作为 Build 端

build_child.Open()

哈希表 = {}

while (t = build_child.Next()) != EOF:

计算连接键 hash，存入哈希表（键->多行列表）

build_child.Close()

// 探测端准备

probe_child.Open()

current_probe_tuple = null

matches_iterator = 空 // 用于遍历匹配的多行

Next():

loop:

// 如果当前探测键还有未返回的匹配行

if matches_iterator 有下一项:

return 组合(current_probe_tuple, matches_iterator.next())

// 否则取下一行探测元组

t = probe_child.Next()

if t == EOF: return EOF

current_probe_tuple = t

查找哈希表，得到匹配行列表 matches_list

if matches_list 非空:

matches_iterator = matches_list.iterator()

return 组合(t, matches_iterator.next())

// 若无匹配，且是 inner join，则继续外层循环；若是 outer join，则需返回 null 补齐

哈希连接在 `Open()` 中耗尽 Build 端，因此属于阻塞型。

(3) 归并连接（Sort-Merge Join）

前提是两个输入都已按连接键排序。同样是**阻塞算子**或依赖已排序的输入。

Open():

left.Open(); right.Open()

预取第一行 left_tuple = left.Next(); right_tuple = right.Next()

Next():

while left_tuple != EOF && right_tuple != EOF:

if left_tuple.key < right_tuple.key:

left_tuple = left.Next()

else if left_tuple.key > right_tuple.key:

right_tuple = right.Next()

else: // 匹配

保存当前 join key

// 需处理重复键，通常需读取两边所有同键行做笛卡尔积

...

组合并返回，维护指针状态

return EOF

```

由于需要两边有序，它往往和 Sort 算子配合使用。

五、火山模型的现代演进

虽然原始一次一行的火山模型在 OLTP 或简单查询中足够，但在分析型负载（OLAP）下性能瓶颈明显。因此现代数据库系统出现了若干改进：

1. 向量化执行模型：

将 `Next()` 改为返回**一批行**（如 1000 行），每次循环内对批量数据应用紧凑循环或 SIMD 指令处理，大幅减少虚函数调用并提高 cache 利用率。代表系统：Vectorwise、ClickHouse、Presto、DuckDB 等。它有时被称为“向量化火山模型”。

2.代码生成与编译执行：

如 Hyper、Impala 采用的“推模型”，将查询计划直接编译成机器码或中间代码，把算子逻辑内联在一起，消除迭代器开销，使数据以紧凑循环在寄存器间“推送”。

3. 混合模型：

一些系统在优化器阶段决定哪些部分用拉模型（易于实现复杂控制流），哪些用推模型或向量化批量处理。

六、总结

火山模型是数据库查询执行的基石，它用三个简单的接口将不同算子统一成可任意组合的“乐高积木”，使得优化器能够灵活地生成执行计划。每个算子内部封装了具体的算法逻辑，阻塞与非阻塞的特性决定了查询的流水线程度和内存占用。理解火山模型和算子的内部工作机制，是深入掌握数据库内核、SQL 调优以及新型执行引擎原理的必经之路。虽然其一次一行的设计在现代大数据量下面临挑战，但其清晰抽象思想仍深深影响着向量化执行等后继模型。