当前位置：首页 > news >正文

cmu15445 2025fall lec13 Query Execution Pt.1

news 2026/4/21 10:53:10

lec13 Query Execution Pt1

目前已经基本实现了基础模块(排序，aggregation,join)，接下来就是如何把这些东西整合到一起来执行查询

intro

从query plan 里细化了
1 pipeline:一系列算子的序列，元组在他们之间连续流动，不需要中间存储
2 pipeline breaker: 指那些在获取其子算子的所有元组之前无法完成工作的算子(比如joins, subqueries, order by)

Agenda

processiong models, access methods, modification queries, expression evaluation

Processiong models

基础知识

定义：处理模型定义了 DBMS 如何执行查询计划，以及数据如何在算子（Operator）之间流动。

执行路径的两大组成部分
每个处理模型都包含两种基本路径：

控制流 (Control Flow)：DBMS如何调用一个算子。即决定“什么时候该谁干活”的逻辑（比如自顶向下的拉取或自底向上的推送）。
数据流 (Data Flow)：算子完成工作后如何发送其结果。即数据是以什么形式传递给下一个环节的。

Approach #1: Iterator Model

most common(OLTP)
它也被形象地称为Volcano（火山）模型或流水线模型 (Pipeline Model)。以下是它的核心机制：

核心方法：Next()
这是该模型运行的灵魂。查询计划中的每个算子都必须实现一个Next()函数：

自顶向下调用：查询计划的最顶层算子（根节点）调用Next()，然后这个调用会像链条一样向下传递。
一次返回一条：每次调用Next()，算子要么返回一个元组（一行数据），要么返回一个EOF（文件结束标志）表示数据已取完。
递归逻辑：当一个算子被调用Next()时，它会在内部循环调用其子算子的Next()，获取数据处理后再返回给上一层。

生命周期管理：Open()和Close()
除了取数据，算子还需要管理自己的状态：

Open()：初始化算子。类似于构造函数，用于分配内存、打开文件或准备内部状态。
Close()：清理算子。类似于析构函数，用于释放资源。

为什么它很重要？

流式处理：由于它一次只处理一条数据，不需要在算子之间存储巨大的中间结果，因此非常节省内存。
易于实现：每个算子的逻辑都是独立的，耦合度低。
几乎所有 SQL 数据库都在用：如 MySQL、PostgreSQL 和早期的 SQL Server 都是基于这个模型构建的。

Approach #2: Materialization Model

rare
与之前的迭代模型（一次处理一条）不同，它的核心逻辑是“全量处理”。以下是详细解释：

核心运作方式：一次性完成

全入全出：每个算子会一次性处理掉所有的输入数据，然后一次性输出所有的结果。
“物化”输出：算子会将处理完的所有结果作为一个完整的集合“物化”（存放在内存或磁盘中），然后传给下一个算子。

优化与灵活性

下推暗示 (Hints)：为了防止数据量过大导致崩溃，DBMS 会下推类似LIMIT的指令，告诉底层算子“只需要处理前 N 条”，从而避免扫描全表。
数据格式：它可以输出整行（NSM，适合 OLTP），也可以输出单列或列的子集（DSM，适合 OLAP）。

特点与适用场景

优点：
- 减少调用开销：不像迭代模型那样需要数百万次的Next()函数调用，它只调用一次，减少了指令执行的负担。
- 适合小型查询：对于 OLTP（短小精悍的查询），这种方式非常快。
缺点：
- 内存压力大：如果中间结果集非常大，会消耗海量内存甚至需要溢写到磁盘。
- 延迟高：上层算子必须等到下层算子全部做完才能开始工作。
- 不适合用于LIMIT这种需要数据子集的算子/命令
历史渊源：这种模式在 90 年代由MonetDB开发，旨在一次处理整列数据而非单行，是列式存储处理的先驱。

Approach #3: Vectorized / Batch Model

common
这张图解释了向量化模型 (Vectorization Model)，它是现代高性能数据库（尤其是 OLAP 场景）的主流选择。
它是对迭代模型和物化模型的“折中”与进化，核心逻辑如下：

它是如何运作的？

结构相似：它沿用了迭代模型的结构，每个算子依然实现Next()函数。
批量发送 (Batch)：不同之处在于，每次调用Next()不再只返回一条数据，而是返回一组元组（a batch of tuples）。
内部循环：算子的内部循环会一次性处理这一批数据。

关键特性

灵活的 Batch 大小：Batch 的大小可以根据硬件（如 CPU 缓存大小）或查询的具体属性进行调整。
数据组织：每个 Batch 通常包含一列或多列数据，并且每列都有自己的Null 位图 (Null Bitmaps)，用于标记哪些位置是空值。

为什么它更强大？

减少函数调用：相比迭代模型，它极大地减少了Next()的调用次数，降低了开销。
利用 SIMD 指令：因为它处理的是数组（Batch），CPU 可以使用SIMD（单指令多数据）指令集来并行处理数据，性能飞跃。
缓存友好：Batch 的大小通常设计为能刚好放入 CPU 的L1 缓存中，减少了从内存读取数据的延迟。

总结：如果迭代模型是“接一杯水”，物化模型是“装一桶水”，那么向量化模型就是“传一箱瓶装水”。它既保留了流水线的灵活性，又获得了极高的批量处理性能。

Access methods

定义：它是数据库管理系统（DBMS）从表中检索存储数据的具体方式。
三种基本途径
全表扫描 (Sequenial Scan)：
- 逻辑：遍历表中的每一个页面（Page），读取每一条记录。
- 适用：查询没有索引的列，或者需要处理表中大部分数据时。
- 有很多优化方法(data skipping有损和无损)
索引扫描 (Index Scan)：
- 逻辑：通过辅助的数据结构（如 B+ 树、哈希索引）快速定位数据。
- 变体：包括唯一扫描、范围扫描等。
多索引扫描 (Multi-Index Scan)：
- 逻辑：如果一个查询涉及多个带索引的列，DBMS 可能会同时扫描多个索引，将结果（通常是 Record ID）进行交集 (And)或并集 (Or)操作后再取回数据。

modification queries

INSERT 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 context

current tuple | query parameters | table schema

Evolving....

传统方式：树遍历（解释执行）

做法：如右上方所示，将s.val = 1转化为一棵树。对于每一行数据，CPU 都要递归地遍历这棵树。
弊端：对 CPU 极不友好。每次访问节点都要判断操作类型（是等于还是加法？）、处理分支预测、进行函数调用。如果数据有上亿行，这种开销会造成巨大的性能浪费。

进阶方式：直接评估（JIT 编译）

做法：不再遍历树，而是利用LLVM或gcc/Clang等工具，在查询运行时动态地将表达式编译成一段简短的机器码（Machine Code）。
效果：如右侧红色箭头所示，原本复杂的树变成了一个简单的 C 函数return (val == 1)。CPU 执行这段代码的速度比遍历树快几个数量级，因为它消除了所有不必要的跳转和判断。