数据库执行引擎基础：火山模型、迭代模型、物化模型的定义与对比

数据库执行引擎是查询处理器的核心，它负责将优化器生成的逻辑计划转换为物理操作符树，并驱动这些操作符实际计算数据。理解执行引擎的底层模型，是后续进行向量化改造和火山模型优化的前提。本章将深入剖析三种最基础的执行模型——火山模型（Volcano Model）、迭代模型（Iterator Model）与物化模型（Materialization Model），从定义、数据流机制、内存占用、适用场景等维度进行系统对比，并给出工程实践中的选型判断方法。

三种执行模型核心机制对比 火山模型（迭代模型） HashJoin 节点 TableScan 节点 next() 返回单行 逐行调用，流水线式 内存占用 O(1) 函数调用开销大 物化模型 Scan → 物化全部行 中间结果集（临时表） 下一算子读取完整输入 一次物化，多次复用 内存占用 O(N) 适合小数据量/OLAP 向量化模型（批处理） Scan → 批量读取 1024 行 批量处理（SIMD 友好） nextBatch() 返回向量 兼顾流水线与批量处理 内存占用 O(BatchSize) 现代 OLAP 主流方案

2.1 火山模型：经典迭代器的运作机制

核心原理

火山模型（Volcano Model）由 Goetz Graefe 在 1994 年系统化提出，是关系型数据库中最经典的执行模型。其核心思想是将查询计划中的每个物理操作符封装为一个迭代器（Iterator），每个迭代器对外暴露统一的 next() 接口。执行引擎从树顶的根节点开始，反复调用 next() 获取一行结果，直到返回 EOF（End of File）标记。每个操作符的 next() 内部会递归调用其子节点的 next()，从而形成一种“拉取”（Pull-based）的数据流。

这种模型的本质是控制流与数据流的解耦：上层算子不需要关心下层算子如何产生数据，只需要通过统一的接口逐行获取。例如，一个 HashJoin 节点的 next() 会先从左子节点拉取一行，去哈希表中探测，若命中则拼接后返回；若未命中则继续从右子节点拉取。整个过程是同步、阻塞式的，每一行数据在算子间“逐级上抛”。

判断方法与操作流程

在实际数据库源码中，判断一个执行引擎是否采用火山模型，可以观察以下特征：

  • 接口签名：算子基类是否定义了 next() 或 getNext() 方法，返回类型为“单行”或“单行引用”。
  • 调用链：执行循环是否形如 while ((row = child.next()) != EOF) { ... }。
  • 状态存储：算子内部是否维护了游标（cursor）或位置指针，用于记录当前扫描进度。

操作流程通常遵循以下步骤：

  1. 构建物理操作符树，根节点为最上层算子（如 Projection 或 Aggregate）。
  2. 执行器调用根节点的 next()。
  3. 根节点递归调用子节点，直至叶子节点（TableScan）读取一行数据。
  4. 数据沿调用栈逐层返回，每层进行相应处理（过滤、投影、连接等）。
  5. 当叶子节点无更多数据时，返回 EOF，执行结束。

案例拆解：PostgreSQL 的经典实现

PostgreSQL 是火山模型的典型代表。其执行节点（如 SeqScan、NestLoop）都实现了 ExecProcNode 函数，通过 ExecScan、ExecNestLoop 等封装对外提供 next 语义。以一次简单的 SELECT * FROM users WHERE age > 30 为例：

// 伪代码示意
TupleTableSlot *slot;
do {
    slot = ExecProcNode(seqScanState);  // 从 SeqScan 拉取一行
    if (TupIsNull(slot)) break;          // EOF
    // 在 Filter 节点进行条件判断
    if (age > 30) return slot;           // 满足条件则上抛
} while (true);

这种实现的优势是内存占用极低，因为任意时刻只有一行数据在算子间流动。但代价是函数调用开销巨大：每处理一行数据，都要经历多次虚函数调用、上下文切换和分支预测。在 TPC-H 等复杂查询中，CPU 时间大量消耗在调用栈的压栈/弹栈上，而非真正的数据计算。

风险提示：火山模型在 OLTP 场景（小事务、点查）中表现良好，但在 OLAP 场景（大表扫描、聚合）中，逐行调用导致的 CPU 指令缓存（I-Cache）失效和分支预测失败会显著拖慢性能。实测中，火山模型的 CPU 利用率往往只有向量化模型的 1/3 到 1/2。

2.2 物化模型：以空间换时间的朴素策略

核心原理

物化模型（Materialization Model）与火山模型相反，它采用“推”（Push-based）或“一次性计算”的方式：每个操作符一次性处理完所有输入数据，将完整的结果集写入内存或临时文件，然后交给下一个操作符。这种模型下，算子之间传递的不是“一行”或“一批”，而是完整的中间结果集。

物化模型有两种变体：全量物化（一次生成全部结果）和分批物化（按块生成，但块与块之间不流水）。全量物化最简单，但内存压力极大；分批物化是折中方案，但本质上仍是“先算完、再消费”的模式。

判断方法与适用场景

判断一个引擎是否采用物化模型，可以看算子间传递的数据结构：如果传递的是 vector<Row> 或 DataTable 等完整集合，且上层算子必须等待下层算子完全结束后才能启动，则属于物化模型。

物化模型在以下场景中具有优势：

  • 数据量小：如系统表查询、元数据读取，全量物化开销可忽略。
  • 需要随机访问：如排序操作，必须先拿到全部数据才能进行排序。
  • 多次复用：如 CTE（Common Table Expression）被多次引用时，物化一次可避免重复计算。

案例拆解：SQLite 的排序实现

SQLite 在执行 ORDER BY 时，会使用物化模型。其 sorter 模块首先从子节点读取所有行，写入内存中的临时数组（若超过阈值则溢写到磁盘临时文件），然后进行排序，最后再逐行输出。这种设计使得排序操作无法与上游扫描流水线化，但换来了排序算法的简单性和稳定性。

// SQLite sorter 伪代码
void *sorter = sqlite3SorterOpen(...);
while ((row = sqlite3Step(child)) != SQLITE_DONE) {
    sqlite3SorterWrite(sorter, row);   // 全部写入
}
sqlite3SorterSort(sorter);              // 统一排序
while ((row = sqlite3SorterRead(sorter)) != NULL) {
    output(row);                        // 逐行输出
}

这种方式的缺点是：当数据量达到数千万行时，排序阶段的内存占用会急剧膨胀，触发磁盘溢写后 I/O 开销巨大。相比之下，现代数据库（如 ClickHouse）使用外排+归并的流式处理，避免了全量物化。

经验总结：物化模型并非“过时”的技术。在查询优化器中，对于“物化代价低于重新计算代价”的公共子表达式，优化器会主动选择物化。例如，PostgreSQL 的 Materialize 节点就是物化模型的典型应用，用于嵌套循环连接中缓存内表数据，避免重复扫描。

2.3 向量化模型：批处理与流水线的融合

核心原理

向量化模型（Vectorized Model）是火山模型的改进版，其核心思想是将“逐行迭代”改为“逐批迭代”。每个算子对外暴露 nextBatch() 接口，每次返回一个固定大小的行集合（通常为 1024 行或 4096 行），这个集合在内存中连续存储，便于 CPU 进行 SIMD（单指令多数据）向量化计算。

向量化模型保留了火山模型的流水线特性（上层算子不必等待下层算子全部完成），同时通过批量处理摊薄了函数调用开销。更重要的是，批量数据可以按列存储（Columnar Layout），使得聚合、过滤、表达式计算等操作能够利用 CPU 的 SIMD 指令集（如 AVX-512）并行处理多个数据元素。

判断方法与操作流程

判断一个引擎是否向量化，可以观察：

  • 接口返回类型：是否为 Batch 或 ColumnVector，而非单行。
  • 循环结构：执行循环是否形如 while ((batch = child.nextBatch()) != EOF) { process(batch); }。
  • 内存布局：数据是否按列连续存储，而非按行存储。

操作流程如下：

  1. 叶子节点（TableScan）按列读取一批数据到内存中的列向量。
  2. 上层算子（如 Filter）对列向量进行批量谓词判断，生成选择向量（Selection Vector）或压缩后的列。
  3. 聚合算子利用 SIMD 指令对列向量进行累加、计数等操作。
  4. 最终结果按批返回给客户端或写入结果集。

案例拆解：DuckDB 的向量化执行

DuckDB 是一个嵌入式 OLAP 数据库，其执行引擎完全基于向量化模型。以 SELECT sum(l_extendedprice) FROM lineitem WHERE l_shipdate > '1995-01-01' 为例：

// DuckDB 伪代码示意
DataChunk chunk;
while (true) {
    chunk.Reset();
    scanState->Scan(chunk);   // 读取一批（默认 2048 行）
    if (chunk.size() == 0) break;
    // Filter 操作：生成选择向量
    Vector& dateVec = chunk.data[0];
    SelectionVector sel;
    idx_t count = VectorOperations::GreaterThan(dateVec, dateConst, sel);
    // 聚合操作：对选中的行进行累加
    aggregateState->Add(chunk, sel, count);
}

在这个例子中，GreaterThan 操作会遍历 2048 个日期值，使用 SIMD 指令一次性比较 8 个或 16 个元素，生成一个位图掩码，然后通过压缩操作只保留满足条件的行。整个过程没有逐行函数调用，CPU 利用率极高。

实践建议：向量化模型的批次大小（Batch Size）需要调优。批次过小（如 128 行）会导致 SIMD 利用率不足；批次过大（如 65536 行）会增加内存占用和缓存未命中率。经验值在 1024~4096 行之间，具体需根据 CPU 缓存行大小和数据宽度测试确定。

2.4 三种模型的系统化对比与选型

对比维度 火山模型（迭代模型） 物化模型 向量化模型
数据传递粒度 单行 完整结果集 批量（1024~4096 行）
内存占用 O(1) O(N) O(BatchSize)
函数调用开销 极高（每行多次调用） 低（每算子一次） 低（每批一次）
CPU 缓存友好性 差（数据分散） 中（取决于布局） 优（列式连续存储）
SIMD 利用能力 几乎无法利用 有限（需额外转换） 天然适配
流水线能力 完全流水线 无（阻塞式） 完全流水线
典型代表 PostgreSQL、MySQL SQLite（排序）、Spark（Shuffle） DuckDB、ClickHouse、Vectorized MySQL
适用场景 OLTP 点查、小事务 小数据量、需要随机访问 OLAP 分析、大表聚合

选型判断方法

在实际数据库产品设计中，选型并非“非此即彼”，而是混合使用。以下给出判断路径：

  1. 如果查询是点查或小范围扫描（OLTP）：优先选择火山模型，因为其内存开销最小，且单行处理在索引命中时效率很高。
  2. 如果查询涉及大表全扫描或复杂聚合（OLAP）：必须采用向量化模型，否则 CPU 会成为瓶颈。
  3. 如果某个算子需要全量数据才能工作（如排序、哈希连接构建阶段）：即使整体是向量化模型，该算子内部也需要物化（如构建哈希表）。
  4. 如果数据量极小（如系统目录查询）：物化模型最简单，避免引入复杂的迭代器框架。

常见误区与复盘

误区一：认为火山模型“过时”。实际上，PostgreSQL 16 仍然使用火山模型，但通过 JIT（Just-In-Time）编译和表达式扁平化来缓解函数调用开销。火山模型在 OLTP 场景下依然是最佳选择。
误区二：将“向量化”等同于“列存”。列存是存储层的数据布局，向量化是执行层的处理方式。行存数据库也可以实现向量化执行（如将行数据批量转换为列向量），但会引入额外的转换开销。
误区三：忽视物化模型的“溢出”风险。当物化结果超过内存阈值时，必须溢写到磁盘。如果溢写策略不当（如频繁随机写），性能会断崖式下降。建议为物化算子设置明确的内存预算，并采用流式外部排序或分区哈希来避免全量物化。

总结复盘

三种模型本质上是“时间-空间-计算效率”的三角权衡。火山模型用时间换空间（低内存、高调用开销），物化模型用空间换时间（高内存、低调用开销），向量化模型则通过批量处理同时优化了时间和空间，但要求数据布局和算子实现必须面向批处理设计。在实际工程中，现代数据库（如 TiDB、OceanBase）往往采用火山模型框架 + 向量化算子的混合架构：保留迭代器的树形调度逻辑，但将底层算子（扫描、过滤、聚合）替换为批量处理实现。这种架构既兼容了复杂查询计划的灵活性，又获得了向量化的性能收益。

← 上一章 📖 返回目录 下一章 →