查询执行模型

• 火山模型逐行迭代时虚函数调用和数据搬运的开销来源
• 向量化执行批量处理、按列循环、减少虚函数调用与指令开销
• 两者在 OLTP 与 OLAP 场景的适用边界

火山模型用一个统一的 next() 接口把每个算子串成树，每次调用返回一行，下层算子的结果通过内存中的行数据结构逐行向上传递。这个模型功能正交、容易实现，但代价是：(1) 每个算子求值一次只处理一行，产生海量的虚函数调用（造成 CPU 分支预测失败、函数指针间接跳转）；(2) 每一行都要经过内存分配、函数调用栈、数据拷贝，指令级无法向量化，CPU 大部分时间花在循环控制和调度上而非真正的计算。向量化执行直接把算子改为批量处理一批行（通常 1024 行的 Batch），把循环从"行"提升到"列"，并且在最内层循环对同一列连续数据做 SIMD 批处理，从而消除虚函数开销、改善缓存局部性、一次加载多元素并行计算。工程边界上，OLTP 场景行数少、单次查询处理行的混合逻辑复杂、需要随机访问和交互，火山模型简单且足够；OLAP 场景动辄扫描上亿行、列式存储天然按列组织，向量化能成数量级提升吞吐。

关键不是"逐行"本身，而是逐行导致的控制流开销（虚函数调用、分支、缓存失效）无法被 CPU 的指令级并行和 SIMD 利用。向量化把内循环变成对连续列的紧循环，让编译器和硬件都能优化。

• 解释执行在运行时解析表达式树、动态分派、类型检查的开销
• 编译执行把表达式/查询编译成原生机器码，消除解释层开销
• 编译代价（编译时间、代码膨胀、JIT 缓存、冷启动）

解释执行运行时要对每个表达式节点做遍历、动态类型检查、虚函数/算子分派，还要处理通用而低效的数据结构；编译执行（Codegen）在查询首次执行时把整棵表达式树或整个查询编译成原生机器码（LLVM 是常用工具），把解释层的那层间接调用、类型检查全部消除，生成的代码直接对具体列类型操作，内层循环变成紧凑的寄存器级代码，并能为具体查询做内联和常量折叠。Hyper、DuckDB、ClickHouse 等都用编译执行。代价是编译本身需要时间（几毫秒到几十毫秒），代码体积增大、指令缓存（I-Cache）压力变大，小查询的编译开销可能超过收益，因此需要缓存编译产物、按复杂度决定是否编译，还有 JIT 编译器自身的复杂度与调试难度。

5-10x 的加速主要来自消除解释器循环、动态类型检查和通用的 dispatch 开销，而不是算法本身更优；代价是编译时间与实际收益在短查询上的权衡。

• Pull 模型由上层算子主动拉取数据，Push 模型由下层算子主动下推数据
• Push 便于流水线化、控制流下推、减少中间结果
• OLTP 与 OLAP 在数据量、查询形态、并发模型上的差异决定的取舍

Pull（火山）模型是上层算子调用下层 next() 主动拉取数据，数据流动受上层控制，但严格的上拉使得算子间存在隐式屏障，且每层都要处理整个下一层结果，难以做到算子间深度流水线。Push 模型由下层算子主动把数据推给上层，配合物化或向量化，数据块生成后立即被消费（如 colFilter 直接把结果推给 join），减少中间结果物化，并让控制流（limit、filter）尽早生效，避免过多计算。OLAP 引擎数据量大、扫描密集、需要向量化/流水线压榨吞吐，所以逐步转向 Push + 向量化 + 编译执行。OLTP 引擎单条查询处理的行数少、索引点查为主、短事务密集、需要最低的启动开销和简单的并发控制，火山模型实现简单、按需拉取就能满足，为其引入的收益有限，所以保留火山模型。

本质是"谁控制数据流"以及"数据批量粒度"的差异；OLAP 追求吞吐，OLTP 追求低延迟与简单性，两者需求不同导致模型选择不同。

• 列存下先对列做过滤/计算，只保留行号（RowID/位置索引）
• 最后才按需取回需要输出的整行，减少中间物化
• 减少 IO 与缓存占用、保留列间压缩收益

列存是把每列分开存储，延迟物化指查询执行时先只对相关列做谓词过滤、聚合等计算，中间结果只保留候选行的位置（RowID/位图），而不是立即把整行拼接成行式记录；直到真正需要输出完整行时才根据位置去取回整行。这样做的好处是：(1) 中间结果只含行号或位图，体积小，减少物化与内存占用；(2) 过滤时只读需要的列，避免读入会被丢弃的列，减少 IO；(3) 保持列的方向性，压缩和解压只针对命中的列，保留列式压缩的收益；(4) 可供后续算子（如 join、聚合）继续在列上操作。代价是如果最终需要大量行，取回整行的随机访问可能带来开销，需要与"立即物化（Early Materialization）"权衡。

减少中间结果物化与 IO 的核心是"少读、晚读、按需读"——只对需要的列和命中的行做昂贵操作，把整行组装推迟到最后。

• 什么是 pipeline breaker（需要全量中间结果的算子，如排序、hash join 构建、聚合）
• 火山模型每次 next() 只拉一行，中间算子往往要等待完整结果
• 流水线执行把算子分批、阶段化，让可流式部分持续流动

在火山模型中，尽管逐行拉取是流式的，但一旦遇到需要完整中间结果的算子（如 Sort、Hash Join 的构建侧、Hash Aggregation、窗函数），它们就必须先收集完所有输入才能开始输出，形成 pipeline breaker，导致上下游无法并行流动，整条流水线被阻塞。流水线执行是一种把查询拆成若干阶段（pipeline segment）执行的方式：每个阶段内算子之间以批量（batch）为单位顺畅流动，阶段之间通过缓冲区衔接；编译执行（如 DuckDB/Hyper）会把一个阶段内的算子融合成一段连贯代码，让数据在其中持续流动，只在跨阶段边界处才发生物化。这样虽然无法消除排序、hash join 等本质上的全量算子，但能显著减少算子之间"逐行等待 + 反复创建中间对象"的停顿，配合多线程把不同 pipeline 并行调度，从而改善吞吐。

流水线执行并不消除算子本身的算法需求，而是消除"逐行控制流造成的阻塞"和"阶段间不必要的物化"，让数据在能流式处理的部分最大程度地连续流动。

• 运行时统计实际数据分布（实际行数、倾斜）并据此重优化
• 动态调整 Join 策略（如 broadcast vs sort-merge）、shuffle 分区数、合并小分区
• 以 Spark AQE 为例的实现机制（重新规划/优化计划）

自适应查询执行在查询运行过程中，根据已经执行算子的真实输出（而非静态估算）动态调整后续计划。典型实现（以 Spark SQL 的 AQE 为例）在执行阶段收集 shuffle 之后各分区的实际大小与行数，据此重新规划：当 join 一侧实际数据量很小且能广播时，把 sort-merge join 切换为 broadcast join；当某个分区数据量巨大（数据倾斜）时，把倾斜侧拆分并加盐再 join；当 shuffle 分区过小或过大时，动态合并或调整分区数以平衡负载、减少落盘。工程上 AQE 通过一个"可重规划"的执行框架，把已完成的阶段结果缓存，在阶段边界根据反馈重新优化剩余部分，并支持多轮调整。它缓解了基数估计不准带来的计划退化问题，但对执行框架的侵入性较大，需要支持中间结果缓存与计划重写。

AQE 的本质是用"运行时的真实反馈"替代"编译期的静态估计"，把代价估算错误在运行时局部纠正；代价是实现复杂度高、需要额外的阶段间反馈机制。

• 把表达式内循环按列批量执行，脱离逐行求值
• SIMD 指令对同一列的连续元素并行计算
• 列存天然按列组织数据，与向量化求值契合

传统表达式求值对每个输入行逐一调用表达式树求值，循环内伴随判断、分支和间接调用，无法利用 CPU 的 SIMD 单元。向量化表达式求值把表达式改写为对一批元素（Batch）的列式紧循环：每列数据在内存中连续存放，最内层循环对同一列连续元素并行执行同一个运算（如比较、算术、逻辑），由编译器/手写 SIMD 指令一次处理多个元素，从而大幅提升吞吐。列存优势在于数据本已按列连续存储，无需把行转列，可以直接把列指针交给向量化核；同时列存配合压缩（如字典、RLE）还有机会在编码维度上直接加速。向量化求值是向量化执行引擎的基础，也是 SIMD 加速与列存结合的关键点。

向量化的核心是"同样的操作、连续的数、并行地算"，列存恰好提供连续同质数据，SIMD 则把单元素运算变成多元素并行，两者叠加带来吞吐跃升。

• Exchange 算子把数据按分区键 shuffle 到多个下游算子实例
• 并行度选择依据（CPU 核数、数据量、IO 带宽）
• 数据倾斜的动态检测与重分布（加盐、拆分、动态分区）

Exchange（又称 Repartition）是一个"数据转移"算子，它把上游算子的输出按分区键做 hash 或 range 分桶，通过网络或内存缓冲送到下游多个并行实例，从而让下游算子（join、聚合、排序）能并行处理。并行度通常依据 CPU 核数、数据总量、单分区大小和 IO 带宽来设定，目标是让每个分区任务负载均衡、避免过小任务带来的调度开销和过大任务带来的长尾。数据倾斜时，某些分区键行数远超均值，导致个别任务成为瓶颈；动态处理手段包括：倾斜检测（运行时统计分区大小与均值偏离）、对大键分区加盐（salt）拆分后进行二次聚合、对倾斜侧做广播拆分（如 join 时把倾斜键所在分区广播匹配）、以及动态调整分区数（AQE 的分区合并）。这些手段让并行框架在负载不均时也能保持接近线性的扩展。

Exchange 是并行执行的数据分水岭，它决定数据如何分布；并行度与倾斜处理最终都服务于"负载均衡 + 减少长尾"，是并行系统吞吐的关键。

• 谓词下推把过滤条件提前到扫描/join 连接阶段执行
• 投影下推把不需要的列尽量在扫描阶段就裁剪掉
• 减少算子间传递的行数与列数，从而减少计算与 IO

谓词下推是把 WHERE 条件尽可能下推到扫描或更早算子执行，例如把过滤条件推到表扫描（filter 与 scan 合并），或把 join 的等值条件下推让 join 在连接前先过滤；投影下推是把查询用到的列裁剪出来，让扫描阶段只读需要的列，并把不需要的列在算子间去除。这样做的效果是：谓词下推减少了算子之间需要传递的行数（只传满足条件的行），投影下推减少了每一行携带的列数（只传需要的列），从而减少中间结果体积、降低 CPU 与 IO，也减少 join/聚合的输入量。这是优化器（尤其是 RBO）最基础也最有效的优化，在列存下与延迟物化、列裁剪配合收益更大。

下推的核心是"早点过滤、少读少算"，把昂贵的计算和数据移动尽量向下、向更早阶段移动，减少后续算子处理的数据量。

• 查询/会话内存预算（memory budget）的分配与上限
• 算子内存超限时 Spill-to-Disk（落盘）触发的条件与策略
• 避免 OOM 与避免过度落盘的权衡（预算感知、反馈）

执行引擎为每个查询/算子分配内存预算（如 Spark 的执行内存预算、PostgreSQL 的 work_mem、Hash Join 的 memory budget），并要求算子在使用中动态申请内存。当算子（如 Hash Join、Sort、Aggregation）实际需要的内存超过预算时，通过 Spill-to-Disk 把部分数据（如 hash 表分区、排序归并段）写到磁盘，用 IO 换取内存释放，从而避免 OOM。协同的关键在于：预算要能感知全局（多个并行算子共享总预算，避免各自超限导致总和超限）、落盘要渐进式（先 buffer 一部分再落盘）、以及落盘策略要尽量少（选择合适的分区数、在内存合并且需要时才落盘）。过度落盘会因频繁磁盘 IO 拖慢查询，因此需要结合实际内存可用性动态调整，例如在内存宽裕时允许占用更多。

内存管理是"预算约束 + 落盘兜底"的平衡：预算防止 OOM，落盘保证在超限时仍能正确执行，而工程难点是让落盘尽量少、可控、不拖垮性能。

• 火山模型逐行调用虚函数、控制流开销大
• 向量化把内循环改为批量对列做 SIMD
• 两者对吞吐和延迟的影响

火山模型每次调用 next() 只处理一行，operator 之间通过虚函数间接跳转，每行都要经历函数调用、分支判断、数据拷贝，CPU 花在控制流上的开销远大于实际计算，且无法利用 SIMD。向量化执行把内循环提升为对一批（Batch，通常 1024 行）连续列数据的紧循环，最内层对同一列做 SIMD 并行运算，一次指令处理多个元素，同时减少虚函数调用和分支，改善缓存与指令级并行。因此向量化与火山模型在同类算法下吞吐可相差一个数量级，但火山模型实现简单、适用于交互式/短查询；向量化适合大批量扫描与复杂计算。实践中不少引擎在复杂算子（如 join、聚合）内部仍混合使用逐行/逐 Batch 的方式。

差异本质是"控制流开销 vs 数据并行"：火山模型被逐行调度拖累，向量化把工作集中到向量化核上，让计算成为瓶颈而不是调度。

• Exchange 网络数据传输的代价（序列化、网络、反序列化）
• 本地执行算子的比例与数据本地性（data locality）
• 如何通过下推、分区键对齐减少跨节点传输

在 MPP（如 Greenplum、ClickHouse 集群、Impala）中，查询全局执行时，不同节点处理不同分区，当 join、聚合、排序需要跨节点重分布数据时，会通过 Exchange（shuffle）把数据序列化发送到目标节点，产生网络传输开销。网络开销往往远高于本地 CPU/内存计算，通常占全局执行时间的重要比例，因此数据本地性（让数据在本地节点上处理）至关重要。工程上通过：把扫描、过滤、投影、部分聚合下推到各节点本地完成，只在必要时才做跨节点 exchange；利用分区键对齐（join 两侧按相同分区键分布）避免重分布；提前做本地预聚合减少网络数据量。统筹"本地执行占比"与"网络传输"，是 MPP 性能优化的核心。

MPP 性能的关键是"尽量本地算、少跨节点传"，把网络开销控制在必要范围，否则网络会成为瓶颈，分布式反而比单机更慢。

• Exchange 算子的数据重分布职能
• 数据倾斜的动态检测（统计分区大小、均值对比）
• 重分布/加盐/拆分等倾斜处理手段

Exchange 算子是并行执行框架数据流动的分水岭，它把上游输出按分区键 hash/range 送到下游多个并行实例，使 join、聚合、排序得以并行。数据倾斜指某分区键的行数远超均值，导致个别任务长尾、整体吞吐受限。动态检测通常在执行阶段统计各分区实际大小（行数/字节），与均值比较识别异常大分区；检测到后触发重分布，手段包括：对倾斜键加盐拆分（把大键拆成多个子键）后二次聚合、对倾斜 join 侧做动态拆分并广播、动态合并/调整分区数以平衡负载、或者把倾斜数据单独处理。这些手段让并行框架在数据不均时仍能保持较好的负载均衡。

Exchange 负责"分发"，倾斜检测与重分布负责"纠正分发不均"，二者共同决定并行框架能否在真实数据分布下保持高效。

• 逐行 UDF 调用打断向量化流水线、破坏列内循环
• 批量调用（batch UDF）、编译（JIT）与内置函数替代
• 对吞吐的影响

向量化执行依赖内层循环对整列连续数据做 SIMD，而用户自定义 UDF 通常被逐行调用：每行一次函数调用、进入解释型/动态类型代码、破坏数据连续性，导致向量化内循环无法保持，性能骤降。改善方式：提供批量调用接口（batch/vectorized UDF，一次传入整列让 UDF 处理数组）、对 UDF 做编译（JIT/LLVM 把 UDF 编译成原生代码并与查询融合）、或尽量用内置高性能函数替代（内置函数可向量化）。此外要把 UDF 标记为 immutable 类型以便优化器下推。这些手段让 UDF 尽可能融入向量化流水线而非打断它。

UDF 的瓶颈在于"逐行 + 黑盒 + 动态类型"破坏了向量化引擎赖以加速的列内紧循环，所以核心是让 UDF 变成"批量 + 可编译 + 类型明确"。

• 解释执行的运行时解析与分派开销
• 编译执行生成原生机器码的性能优势
• 冷启动与编译成本的权衡

解释执行运行时对每个表达式/算子都要做遍历、动态类型检查、虚函数/算子分派，并维护通用数据结构，开销大；编译执行（Codegen）在首次执行时把表达式或查询编译成原生机器码（常用 LLVM 或手写代码生成），消除分派与类型检查，内层循环紧凑、可内联、可常量折叠，性能普遍比解释执行高数倍（常见 5-10x）。差异代价是编译本身耗时，小查询/短查询的编译成本可能超过收益，因此需要缓存编译产物、按查询复杂度决定是否编译。总体上编译执行适合复杂、重复执行或数据量大的查询，解释执行适合简单、零散的短查询。

性能差异来自"解释层的通用开销 vs 编译后的专用原生代码"，本质是把运行时开销转移到编译期，用编译时间换执行时间。

• Pull 模型主动拉取、算子间可能隐式物化
• Push 模型数据主动下推、利于流水线
• 物化与流水线在中间结果和延迟上的差异

Pull 模型由上层算子调用下层 next() 主动拉取数据，数据流受上层控制，实现简单，但算子间往往每层都要持有/处理完整结果，容易发生中间结果物化（materialization），即把中间结果完整落成行集再交给上层。Push 模型由下层算子主动把数据块推给上层消费，数据生成后立即被下游处理，从而形成流水线（pipelining），中间结果不完整物化、数据持续流动，配合 limit 等算子还能提前终止。差异在于：物化强调"先完整生成再消费"，能支持需要完整输入的算子（如 hash join 构建、排序），但内存/IO 开销大，延迟高；流水线强调"边生成边消费"，减少物化、降低延迟、提升吞吐，但只适用于可流式处理的算子。现代引擎常把两者结合：可流式算子用流水线，全量算子用物化。

物化与流水线是"完整中间结果 vs 持续流动"两种数据流策略，前者通用但昂贵，后者高效但受限，实际引擎按算子类型混合使用。

• Exchange 算子把数据按分区键分发到并行实例
• hash/range 分区的重分布方式
• 与本地执行、数据倾斜的关系

Exchange 算子是并行执行中数据重分布的关键算子，它把上游产生的结果按分区键做 hash 或 range 分桶，通过网络/内存缓冲送到下游多个并行实例，使下游算子能够并行处理不同分区的数据。hash 分区间进行网络 shuffle，是分布式 join、聚合、排序的必经之路；range 分区适合排序去重等需要有序的场景。重分布带来额外开销（序列化、网络、反序列化），因此工程上希望尽量减少不必要的 exchange，通过数据本地性、分区键对齐和本地预聚合来降低重分布成本。Exchange 是并行度的载体，也是网络开销的主要来源。

Exchange 让数据"跨实例流动"以实现并行，但同时带来网络开销；理解和控制 Exchange 是并行执行优化的核心。

• EXPLAIN ANALYZE 提供真实执行的行数、耗时、内存
• 与估算行数对比发现基数估计偏差（计划退化）
• 定位耗时最高的算子与瓶颈

EXPLAIN ANALYZE 真正执行查询并返回每个算子的实际行数、耗时、内存、IO 等运行时信息，与 EXPLAIN（只显示估算）相比能反映真实执行情况。诊断方法：逐算子比较"估算行数 vs 实际行数"，若偏差巨大（如估算 100 行实际 100 万行），说明基数估计不准导致优化器选错 join 顺序/策略，需要更新统计信息或加 hint；再按耗时排序找出最耗时的算子，判断其是扫描、join、聚合还是排序瓶颈，并检查是否有谓词/投影下推、是否发生落盘、是否出现数据倾斜。这些都是执行计划诊断的常用手段。

EXPLAIN ANALYZE 的价值在于"真实数据 vs 估算数据"的对比，行数偏差揭示优化器问题，耗时分布揭示执行瓶颈，两者结合才能定位并修复性能问题。