火山模型与算子

数据库中的火山模型是一种经典的查询执行模型由 Goetz Graefe 于 1994 年在《Volcano - An Extensible and Parallel Query Evaluation System》中提出因此也被称为 迭代器模型。它的核心思想是将查询执行计划中的每一个物理操作抽象成一个独立的算子并通过统一的接口让数据在算子之间自底向上“拉取”传递。下面我会从模型原理、算子实现、优缺点与现代演进几个层面为你做一个全面细致的解析。一、火山模型的运行机制1. 统一迭代器接口每个算子都被封装成一个迭代器对外只暴露三个方法Open()初始化算子分配资源如内存、文件句柄并递归调用子算子的 Open()。Next()向上层返回一行tuple数据。若没有更多数据则返回 EOFEnd 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 tuplereturn EOFClose(): child.Close()它不停地从子节点拉取直到找到满足条件的行才向上返回对上层透明。3. 投影算子Projection非阻塞无状态。Next():tuple child.Next()if tuple EOF: return EOF计算表达式列表生成新元组可能只保留部分列return 新元组4. 排序算子Sort / Order By阻塞算子有状态。Open():child.Open()初始化一个空列表 bufferwhile (t child.Next()) ! EOF:buffer.append(t)按排序键对 buffer 排序buffer 上设置迭代指针 cursor 0child.Close() // 可选因为数据已全部取出Next():if cursor buffer.size():return buffer[cursor]else:return EOFClose(): 释放 buffer如果是基于外存的排序外部归并排序内部会分多轮进行但对外仍是阻塞、一次一行输出。5. 限制算子Limit非阻塞但带计数器。Open(): child.Open(); count 0Next():if count limit: return EOFtuple child.Next()if tuple EOF: return EOFcountreturn tuple6. 聚合算子Aggregation通常为阻塞算子如果无分组则内部只保留累加器亦可流式。哈希聚合Hash AggregationOpen():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 EOFright_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 nullmatches_iterator 空 // 用于遍历匹配的多行Next():loop:// 如果当前探测键还有未返回的匹配行if matches_iterator 有下一项:return 组合(current_probe_tuple, matches_iterator.next())// 否则取下一行探测元组t probe_child.Next()if t EOF: return EOFcurrent_probe_tuple t查找哈希表得到匹配行列表 matches_listif 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 调优以及新型执行引擎原理的必经之路。虽然其一次一行的设计在现代大数据量下面临挑战但其清晰抽象思想仍深深影响着向量化执行等后继模型。