3、火山模型的工作原理：Next()调用、算子树、数据流与控制流

火山模型（Volcano Model）是关系型数据库执行引擎中最经典、影响最广泛的迭代式计算模型。自Goetz Graefe在1994年系统化提出以来，它几乎成为所有现代数据库（PostgreSQL、MySQL、SQL Server、Oracle、Hive早期版本等）执行引擎的默认选择。理解火山模型，是理解向量化执行、算子融合、编译执行等后续优化技术的基石。本节将深入剖析火山模型的三大核心要素：Next()调用协议、算子树（Operator Tree）的构建与执行，以及数据流与控制流的解耦与协同，并通过一个完整的SQL执行案例，展示其从解析到物化的全过程。

火山模型执行引擎：算子树与Next()调用协议 Project (投影) Next() → 返回一行 Hash Join Next() → 匹配一行 Table Scan: orders Next() → 返回一行 Table Scan: users Next() → 返回一行 堆表/行存 (Tuple) page 0,1,2... 堆表/行存 (Tuple) page 0,1,2... Next() Next() Next() Tuple Tuple Tuple 图例 控制流：Next() 自上而下驱动（拉取模式） 数据流：Tuple 自下而上返回 存储读取 关键特征：每个算子只关心自己的Next()逻辑，通过火山式递归调用完成整棵树的执行。

上图展示了火山模型执行引擎的核心架构。在火山模型中，控制流（绿色虚线）从树的根节点（Project）出发，逐层向下调用子节点的Next()方法，形成一种“拉取”（Pull）模式；而数据流（蓝色实线）则从叶子节点（Table Scan）向上返回一个又一个的元组（Tuple）。这种“上层驱动、下层生产”的机制，是理解整个执行引擎的关键。

3.1 核心原理：Next()调用协议与迭代器抽象

火山模型的核心思想是将执行计划中的每一个物理操作符（如全表扫描、索引扫描、嵌套循环连接、哈希连接、聚合、排序等）都封装为一个迭代器（Iterator）。每个迭代器对外只暴露三个基本接口：

  • Open()：初始化算子状态，分配内存，打开子节点（如果存在）。例如，Hash Join算子的Open()会读取左子树的所有数据构建哈希表。
  • Next()：核心方法。每次调用返回一个元组（Tuple）或一个“无更多数据”的标记（通常返回NULL或false）。这是火山模型“一次一行”处理模式的直接体现。
  • Close()：释放资源，清理临时状态。

这种抽象的最大优势在于组合性。任何算子只要实现了这三个接口，就可以作为子节点挂接到任意父节点下。执行引擎的调度器（或根节点）只需要简单地循环调用根算子的Next()，直到返回空，即可完成整个查询。这种递归调用的方式，使得查询执行逻辑变得极其简洁和模块化。

关键点：火山模型的“一次一行”并非指物理上只能处理一行，而是指接口粒度。每次Next()调用返回一个逻辑元组，但底层可能涉及批量读取（如从磁盘页中读取多条记录后逐条返回）。这种设计简化了算子间的交互协议，但也是后续向量化优化要解决的主要性能瓶颈——虚函数调用开销过大。

3.2 算子树：从逻辑计划到物理执行

算子树是火山模型执行时的物理载体。它由查询优化器（Optimizer）根据逻辑计划（Logical Plan）生成，并经过一系列物理优化（如选择访问路径、确定连接算法、决定数据分发方式）后得到。算子树具有以下特征：

  1. 树形结构：根节点代表最终输出，叶子节点代表数据源（表、索引、视图），中间节点代表各种运算。
  2. 自底向上构建：优化器从叶子节点开始，逐步向上添加算子，直到生成完整的执行计划。
  3. 物理属性绑定：每个算子节点都绑定了具体的物理实现，例如“Hash Join”而非逻辑上的“Join”，“Index Scan”而非“Table Scan”。

以一条简单的SQL为例：SELECT u.name, o.total FROM users u JOIN orders o ON u.id = o.user_id WHERE o.status = 'PAID'。其逻辑计划是先做过滤（WHERE），再做连接（JOIN），最后投影（SELECT）。而物理计划（算子树）可能如下：

Project (u.name, o.total)
  └── Hash Join (u.id = o.user_id)
        ├── Table Scan (users) AS u
        └── Filter (o.status = 'PAID')
              └── Table Scan (orders) AS o

在这个树中，Filter算子被下推到了Hash Join的右子树中，以减少参与连接的数据量。这是优化器最常见的优化手段之一——谓词下推。

3.3 数据流与控制流：拉取模式与流水线

火山模型最鲜明的特征是其控制流与数据流方向相反。控制流（Next()调用）是自上而下的“拉取”，而数据流（元组返回）是自下而上的“推送”。这种模式也被称为拉取模型（Pull Model）或迭代模型。

这种设计带来了一个重要的执行特性：流水线（Pipeline）。只要父算子需要数据，子算子就立即计算并返回一行。这意味着，在理想情况下，整个执行树可以同时处于工作状态，不同算子在不同数据行上并行处理。例如，当Hash Join在读取右表的一行时，左表的Table Scan可能正在读取下一行，而顶层的Project可能正在处理上一行连接结果。

特性 控制流（Control Flow） 数据流（Data Flow）
方向 自上而下（根→叶） 自下而上（叶→根）
触发方式 父算子主动调用子算子的Next() 子算子返回元组给父算子
核心动作 函数调用、状态判断、循环控制 元组传递、表达式计算、投影
性能瓶颈 虚函数调用开销、递归深度 元组拷贝开销、缓存不友好
优化方向 减少调用次数（如批量Next）、内联化 列存、向量化、批量传递

然而，这种流水线并非总是完美的。存在两类“破坏流水线”的算子：

  • 阻塞算子（Blocking Operator）：如排序（Sort）、哈希聚合（Hash Aggregation）、哈希连接（Hash Join）的构建阶段。这些算子必须读取完所有子节点的数据才能产生第一行输出。例如，Hash Join必须先构建完整的哈希表，才能开始探测。
  • 物化点（Materialization Point）：当需要将中间结果写入磁盘（如临时表）或需要随机访问时，流水线会被打断。
注意：阻塞算子的存在是火山模型性能下降的主要原因之一。在分析型查询（OLAP）中，大量排序和聚合操作会导致执行引擎频繁地“暂停”和“重启”流水线，使得CPU利用率下降。这也是后续向量化执行和列式存储要解决的核心问题。

3.4 案例拆解：一个完整SQL的执行旅程

为了更直观地理解火山模型，我们通过一个具体的案例来拆解其执行过程。假设数据库中有两张表：customers（客户表，100万行）和orders（订单表，1000万行）。执行以下查询：

SELECT c.c_name, o.o_orderdate, o.o_total
FROM customers c
JOIN orders o ON c.c_custkey = o.o_custkey
WHERE c.c_nation = 'CHINA'
  AND o.o_orderdate >= '2024-01-01'
ORDER BY o.o_total DESC
LIMIT 10;

初始现象与目标：该查询需要找出中国客户在2024年后的订单，并按金额降序取前10条。优化器生成的物理计划如下：

Limit (10)
  └── Sort (o_total DESC)
        └── Hash Join (c_custkey = o_custkey)
              ├── Filter (c_nation = 'CHINA')
              │     └── Table Scan (customers)
              └── Filter (o_orderdate >= '2024-01-01')
                    └── Table Scan (orders)

执行过程分析：

  1. 启动阶段：执行器调用根节点Limit的Open()，依次向下递归调用Sort、Hash Join、Filter和Table Scan的Open()。
  2. Hash Join构建：Hash Join的Open()会先读取左子树（Filter(c_nation='CHINA')）的所有数据，对c_custkey计算哈希值，构建一个哈希表。这一步是阻塞的，必须完成。
  3. 流水线探测：构建完成后，Hash Join开始调用右子树（Filter(o_orderdate>=...)）的Next()。右子树从Table Scan中逐行读取，过滤后返回给Hash Join。每收到一行，Hash Join就在哈希表中查找匹配的c_custkey，找到则拼接成一行结果，返回给上层Sort。
  4. 排序与截断：Sort算子接收到所有连接结果后，进行全量排序。排序完成后，Limit算子开始调用Sort的Next()，取出前10行返回给客户端。

关键指标与瓶颈：

  • Hash Join构建阶段耗时约1.2秒（扫描100万行并建哈希表）。
  • 探测阶段耗时约3.5秒（扫描1000万行，但只匹配到约5万行）。
  • Sort排序耗时约0.8秒（对5万行排序）。
  • 总执行时间约5.5秒。其中，Hash Join的构建和探测是主要瓶颈。

优化复盘：如果使用向量化执行引擎，可以将探测阶段的Next()调用次数从1000万次减少到约10万次（每次处理100行），从而显著降低虚函数调用和表达式计算的开销。此外，如果orders表按o_orderdate进行分区，还可以进一步减少扫描数据量。

经验总结：在火山模型下，减少Next()调用次数是提升性能的关键。这可以通过两种途径实现：一是优化器层面（如谓词下推、分区裁剪），二是执行器层面（如批量获取接口，即向量化的雏形）。

3.5 常见误区与总结复盘

在学习和使用火山模型时，开发者常陷入以下误区：

  • 误区一：认为“一次一行”就是低效的代名词。实际上，火山模型的“一次一行”是逻辑抽象，物理上可以通过预取、批量读页等方式隐藏延迟。其真正的开销在于每行都进行虚函数调用，导致CPU分支预测失败和指令缓存失效。
  • 误区二：忽略阻塞算子的影响。很多性能问题并非源于Next()本身，而是因为阻塞算子打断了流水线，导致CPU空闲等待I/O或内存。
  • 误区三：混淆逻辑计划与物理计划。逻辑计划是关系代数层面的描述，不涉及具体算法；物理计划才是火山模型执行的算子树。优化器的工作就是将一个逻辑计划转换为高效的物理计划。
← 上一章 📖 返回目录 下一章 →