cmu15445 2025fall lec13 Query Execution Pt.1

lec13 Query Execution Pt1目前已经基本实现了基础模块(排序aggregation,join)接下来就是如何把这些东西整合到一起来执行查询intro从query plan 里细化了1 pipeline:一系列算子的序列元组在他们之间连续流动不需要中间存储2 pipeline breaker: 指那些在获取其子算子的所有元组之前无法完成工作的算子(比如joins, subqueries, order by)Agendaprocessiong models, access methods, modification queries, expression evaluationProcessiong models基础知识定义处理模型定义了 DBMS 如何执行查询计划以及数据如何在算子Operator之间流动。执行路径的两大组成部分每个处理模型都包含两种基本路径控制流 (Control Flow)DBMS如何调用一个算子。即决定“什么时候该谁干活”的逻辑比如自顶向下的拉取或自底向上的推送。数据流 (Data Flow)算子完成工作后如何发送其结果。即数据是以什么形式传递给下一个环节的。Approach #1: Iterator Modelmost common(OLTP)它也被形象地称为Volcano火山模型或流水线模型 (Pipeline Model)。以下是它的核心机制核心方法Next()这是该模型运行的灵魂。查询计划中的每个算子都必须实现一个Next()函数自顶向下调用查询计划的最顶层算子根节点调用Next()然后这个调用会像链条一样向下传递。一次返回一条每次调用Next()算子要么返回一个元组一行数据要么返回一个EOF文件结束标志表示数据已取完。递归逻辑当一个算子被调用Next()时它会在内部循环调用其子算子的Next()获取数据处理后再返回给上一层。生命周期管理Open()和Close()除了取数据算子还需要管理自己的状态Open()初始化算子。类似于构造函数用于分配内存、打开文件或准备内部状态。Close()清理算子。类似于析构函数用于释放资源。为什么它很重要流式处理由于它一次只处理一条数据不需要在算子之间存储巨大的中间结果因此非常节省内存。易于实现每个算子的逻辑都是独立的耦合度低。几乎所有 SQL 数据库都在用如 MySQL、PostgreSQL 和早期的 SQL Server 都是基于这个模型构建的。Approach #2: Materialization Modelrare与之前的迭代模型一次处理一条不同它的核心逻辑是“全量处理”。 以下是详细解释核心运作方式一次性完成全入全出每个算子会一次性处理掉所有的输入数据然后一次性输出所有的结果。“物化”输出算子会将处理完的所有结果作为一个完整的集合“物化”存放在内存或磁盘中然后传给下一个算子。优化与灵活性下推暗示 (Hints)为了防止数据量过大导致崩溃DBMS 会下推类似LIMIT的指令告诉底层算子“只需要处理前 N 条”从而避免扫描全表。数据格式它可以输出整行NSM适合 OLTP也可以输出单列或列的子集DSM适合 OLAP。特点与适用场景优点减少调用开销不像迭代模型那样需要数百万次的Next()函数调用它只调用一次减少了指令执行的负担。适合小型查询对于 OLTP短小精悍的查询这种方式非常快。缺点内存压力大如果中间结果集非常大会消耗海量内存甚至需要溢写到磁盘。延迟高上层算子必须等到下层算子全部做完才能开始工作。不适合用于LIMIT这种需要数据子集的算子/命令历史渊源这种模式在 90 年代由MonetDB开发旨在一次处理整列数据而非单行是列式存储处理的先驱。Approach #3: Vectorized / Batch Modelcommon这张图解释了向量化模型 (Vectorization Model)它是现代高性能数据库尤其是 OLAP 场景的主流选择。它是对迭代模型和物化模型的“折中”与进化核心逻辑如下它是如何运作的结构相似它沿用了迭代模型的结构每个算子依然实现Next()函数。批量发送 (Batch)不同之处在于每次调用Next()不再只返回一条数据而是返回一组元组a batch of tuples。内部循环算子的内部循环会一次性处理这一批数据。关键特性灵活的 Batch 大小Batch 的大小可以根据硬件如 CPU 缓存大小或查询的具体属性进行调整。数据组织每个 Batch 通常包含一列或多列数据并且每列都有自己的Null 位图 (Null Bitmaps)用于标记哪些位置是空值。为什么它更强大减少函数调用相比迭代模型它极大地减少了Next()的调用次数降低了开销。利用 SIMD 指令因为它处理的是数组BatchCPU 可以使用SIMD单指令多数据指令集来并行处理数据性能飞跃。缓存友好Batch 的大小通常设计为能刚好放入 CPU 的L1 缓存中减少了从内存读取数据的延迟。总结如果迭代模型是“接一杯水”物化模型是“装一桶水”那么向量化模型就是“传一箱瓶装水”。它既保留了流水线的灵活性又获得了极高的批量处理性能。Access methods定义它是数据库管理系统DBMS从表中检索存储数据的具体方式。三种基本途径全表扫描 (Sequenial Scan)逻辑遍历表中的每一个页面Page读取每一条记录。适用查询没有索引的列或者需要处理表中大部分数据时。有很多优化方法(data skipping有损和无损)索引扫描 (Index Scan)逻辑通过辅助的数据结构如 B 树、哈希索引快速定位数据。变体包括唯一扫描、范围扫描等。多索引扫描 (Multi-Index Scan)逻辑如果一个查询涉及多个带索引的列DBMS 可能会同时扫描多个索引将结果通常是 Record ID进行交集 (And)或并集 (Or)操作后再取回数据。modification queriesINSERT UPDATE DELETE修改算子的职责同步更新这些算子不仅负责修改目标表Heap/Table中的数据还必须同时负责修改所有相关的索引。约束检查 (Constraint Checks)立即检查在算子执行修改时立即验证例如检查主键是否重复、非空约束。延迟检查等到事务提交Commit时才统一验证。输出结果 (Output)与SELECT不同修改算子的输出通常有两种形式Record IDs返回受影响行的内部标识符。元组数据 (RETURNING)有些数据库支持在修改后直接返回被修改的整行内容例如 PostgreSQL 的INSERT ... RETURNING *。UPDATE/DELETE这两个操作的核心是“先找到再处理”传递 Record ID子算子通常是扫描算子负责定位符合条件的行并将这些行的Record ID物理标识符传递给修改算子。追踪已处理记录算子必须记录keep track of已经处理过的元组。原因这是为了避免我前面提到的“万圣节问题 (Halloween Problem)”。如果更新操作改变了数据的物理位置或索引值防止同一个查询计划在后续扫描中再次读到这一行从而导致重复更新。INSERT两种实现策略插入操作的实现取决于数据的来源选择 #1 算子内部物化 (Materialize)场景如INSERT INTO T VALUES (1, abc)。逻辑数据就在 SQL 语句中算子直接在内部构造出完整的元组并写入表。选择 #2 接收子算子传递 (From Child)场景如INSERT INTO T (SELECT * FROM S)。逻辑算子作为一个接收端将子算子对表 S 的查询源源不断传上来的元组直接插入到目标表中。万圣节问题这个概念最早由 IBM 的研究人员在 1976 年的万圣节当天发现。他们发现一个简单的加薪 SQL 导致公司所有人的薪水都变成了上限值。expression evaluation这张图讲解的是数据库如何处理 SQL 中的计算逻辑即表达式计算 (Expression Evaluation)。在之前的图中我们看到了查询计划算子树而每一个具体的WHERE子句或计算公式在数据库内部则是通过表达式树 (Expression Tree)来表示的。execution contextcurrent tuple | query parameters | table schemaEvolving....传统方式树遍历解释执行做法如右上方所示将s.val 1转化为一棵树。对于每一行数据CPU 都要递归地遍历这棵树。弊端对 CPU 极不友好。每次访问节点都要判断操作类型是等于还是加法、处理分支预测、进行函数调用。如果数据有上亿行这种开销会造成巨大的性能浪费。进阶方式直接评估JIT 编译做法不再遍历树而是利用LLVM或gcc/Clang等工具在查询运行时动态地将表达式编译成一段简短的机器码Machine Code。效果如右侧红色箭头所示原本复杂的树变成了一个简单的 C 函数return (val 1)。CPU 执行这段代码的速度比遍历树快几个数量级因为它消除了所有不必要的跳转和判断。终极方式向量化Vectorization做法在编译的基础上一次性处理一批a batch元组。核心利用 CPU 的SIMD单指令多数据指令集。例如一条指令同时比较 8 个或 16 个整数是否等于 1。优势这是目前 OLAP分析型数据库如 ClickHouse、DuckDB能跑得飞快的核心秘密。optimizations常量折叠 (Constant Folding)原理识别查询中多余或不必要的计算。如果一个子表达式的所有输入都是常量那么它的结果也是固定的。优化逻辑DBMS 会在查询编译阶段预先算出这个值然后在执行时用结果替换掉原来的表达式。例子图中UPPER(wutang)会被直接优化为常量WUTANG。好处避免对每一行数据per tuple都重复执行相同的计算函数如UPPER。公共子表达式消除 (Common Sub-Expr. Elimination)原理识别在同一个查询树中重复出现的完全相同的子表达式。优化逻辑DBMS 只会计算一次该子表达式的值然后将结果缓存起来供树中的其他位置重复使用。例子图中STRPOS(x, col1)在OR的左右两侧都出现了。优化后系统只需计算一次位置值然后分别判断它是否 2或 8。好处显著减少昂贵的函数调用次数特别是当子表达式涉及复杂的字符串处理或数学运算时。