Lec13 查询执行 I — 处理模型、访问方法、表达式求值

本讲解决一个核心问题：当 DBMS 拿到查询计划后，如何实际执行它？ 内容涵盖三种驱动元组在算子间流动的处理模型、从表中读取数据的主要访问方法，以及 DBMS 如何高效地求值表达式。

查询执行概述

在讨论处理模型之前，先明确关键术语。查询计划（query plan）是一个由算子构成的 DAG。在计划中：

  • 流水线（pipeline）是一系列算子的序列，元组在它们之间连续流动，无需中间存储。
  • 流水线阻断器（pipeline breaker）是一种在所有子节点输出全部元组之前无法完成的算子 — 例如 Join（构建侧）、子查询和 Order By。

DBMS 将查询计划按流水线阻断器拆分为若干流水线段，然后逐段执行。

处理模型

DBMS 的处理模型定义了系统如何执行查询计划以及如何在算子之间移动数据。不同模型在 OLTP 和 OLAP 工作负载之间做出不同的权衡。每种模型包含两类执行路径： - 控制流（Control Flow）：DBMS 如何调用算子 - 数据流（Data Flow）：算子如何发送结果

算子的输出可以是完整元组（NSM）或列的子集（DSM）。三种主要模型的区别在于每个算子每次处理的数据粒度。

迭代器模型（Volcano / Pipeline）

使用最广泛的处理模型（最常见）。每个算子实现三个函数：

  • Open()：初始化算子状态并对子节点调用 Open()
  • Next()：返回下一个单元组，或在结束时返回 null/EOF 标记
  • Close()：清理资源并对子节点调用 Close()
1
2
3
4
5
6
7
function Next():
    for each child in children:
        tuple = child.Next()
        if tuple is not null:
            process(tuple)
            emit(tuple)
    return null  // no more tuples

核心特性： - 每次调用 Next() 返回一个元组（或表示流结束的 null 标记） - 顶层算子反复调用子节点的 Next()，子节点递归调用其子节点，一直到叶子（扫描）算子 - 元组在树中向上逐个流动 — 也称流水线模型，因为元组产生后立即被处理 - 几乎所有 DBMS 都使用：PostgreSQL、MySQL、SQLite、MongoDB 等

该模型的优雅之处在于简洁 — 每个算子自包含，只需实现一个接口。但对于处理数十亿元组的分析型工作负载，逐元组的函数调用开销会变得显著。

物化模型

另一个极端（少见）：每个算子一次性处理所有输入并产出所有输出。

1
2
3
4
5
6
7
8
function Output():
    result = []
    for each child in children:
        child_result = child.Output()
        for tuple in child_result:
            process(tuple)
            result.append(tuple)
    return result

核心特性： - 每个算子将其完整结果集作为物化集合返回 - 更适合 OLTP 工作负载，这类查询只涉及少量数据 — 函数调用更少，控制流更简单 - DBMS 可以向下传递 LIMIT 等提示以避免不必要的物化 - 对于中间结果巨大的 OLAP 工作负载表现较差 — 物化数百万元组浪费内存 - 支持算子融合：由于每个算子一次看到所有输入，DBMS 可以将相邻算子（如扫描 + 过滤 + 投影）融合为对数据的单次遍历

向量化 / 批处理模型

一个折中方案（在现代系统中常见），兼具两者优势。每个算子每次调用输出一批元组（通常 1024 个左右）。最初在 MonetDB/X100 系统中提出。

1
2
3
4
5
6
7
8
9
10
function Next():
    batch = []
    for each child in children:
        child_batch = child.Next()
        for tuple in child_batch:
            process(tuple)
            batch.append(tuple)
        if len(batch) >= BATCH_SIZE:
            return batch
    return batch

核心特性： - 将函数调用开销分摊到多个元组上（类似物化模型），同时保持流式特性（类似迭代器模型） - 非常适合 OLAP 工作负载 — 批大小选择为可放入 CPU 缓存，从而通过 SIMD 实现高效的向量化操作 - 每个批内部使用列式布局，算子包含 null 位图来跟踪批中哪些条目有效 - 被现代分析系统采用：DuckDB、Snowflake、Databricks、ClickHouse 等

对比

模型 粒度 最适用场景 函数调用开销
迭代器 单元组 通用 高（逐元组）
物化 整个结果集 OLTP（小结果集） 低（逐算子）
向量化 元组批次 OLAP（大规模扫描） 中（逐批次）

计划处理方向

无论采用哪种处理模型，DBMS 都必须决定数据在计划树中流动的方向。

自顶向下（Pull）

  • 根算子通过调用 Next() 或 Output() 从子节点”拉取”元组
  • 控制流从顶部开始递归向下
  • 数据从叶子向根向上流动
  • 迭代器模型使用的经典方式

自底向上（Push）

  • 叶子算子将元组”推送”给父算子
  • 控制流从叶子开始
  • 允许更紧凑的循环 — 叶子处的算子可以在不返回控制权的情况下将元组推过编译好的流水线
  • 支持算子融合：流水线中的相邻算子可以融合为一个紧凑的循环，消除算子间的虚函数调用开销
  • 被 HyPer 及采用基于推送的查询编译的系统使用

Push 模型可以获得更好的性能，因为它避免了递归函数调用的开销。叶子算子（如表扫描）运行一个紧凑循环，将元组推过一系列编译为单一函数的算子链，而不是每个算子从子节点拉取。

Push 与 Pull 的权衡

方面 Pull（自顶向下） Push（自底向上）
虚函数开销 每个元组/批次一次 Next() 调用 通过算子融合编译消除
LIMIT 处理 简单 — 停止调用 Next() 即可 较难 — 需要将”停止”信号传播回叶子
Sort-Merge Join 自然 — 可以交替从两个已排序的输入拉取 困难 — 两个推送源需要协调
调度 简单的递归控制流 需要调度器管理哪个流水线何时运行
输出控制 消费者控制节奏 生产者控制节奏；需要输出缓冲

访问方法

访问方法是 DBMS 从表中读取数据的方式。查询优化器基于代价估算选择访问方法。

顺序扫描

最简单的方法：逐页读取表中的每一页。

1
2
3
4
for page in table.pages:
    for tuple in page.tuples:
        if evaluate(predicate, tuple):
            emit(tuple)

这通常是最坏情况，但 DBMS 可以应用多种优化：

  • 预取（Prefetching）：在需要之前将接下来的几个页面取入缓冲池
  • 缓冲池绕过（Buffer Pool Bypass）：对于大型顺序扫描，绕过缓冲池以避免用不会被重新读取的页面污染缓存
  • 并行化（Parallelization）：将扫描分配给多个线程或工作者
  • 延迟物化（Late Materialization）：在列式存储中，延迟列的拼接直到绝对必要时 — 只读取查询实际需要的列
  • 堆聚簇（Heap Clustering）：如果表在某个键上物理排序，该键上的范围谓词可以跳过大量堆页面
  • 数据编码/压缩：直接在压缩数据上操作而不解压（如游程编码可以在不展开的情况下回答某些谓词）
  • 扫描共享（Synchronized Scans）：如果多个查询并发扫描同一张表，共享扫描游标使它们可以搭载彼此的 I/O
  • 物化视图/缓存结果：预计算并缓存常见查询结果，从而完全避免扫描
  • 代码特化/编译：在查询编译时为特定模式和谓词生成特化的扫描代码，避免通用解释开销

数据跳过

数据跳过的核心思想是避免检查保证不满足查询谓词的页面或元组。有两类方法：

近似查询（有损）：在数据的采样子集上执行查询以产生近似答案。以精度换取速度 — 适用于不需要精确答案的探索性分析。

Zone Maps（无损）：关于每个页面（或页面范围）中值的预计算元数据，允许 DBMS 确定性地跳过页面：

  • 为连续页面范围中的每个属性存储 MIN、MAX、AVG、SUM、COUNT
  • 扫描页面前先检查 zone map — 如果谓词不可能匹配范围内的任何值，则跳过整个页面
  • 对排序或半排序数据上的范围谓词极其有效
  • Zone maps 随数据的插入/更新自动维护
  • 使用方：Netezza、Oracle、Vertica、SingleStore、Snowflake，以及列式文件格式 Parquet、ORC、Vortex 和 LanceDB 原生支持

例如，如果查询要求 WHERE val > 600，而某页面的 zone map 显示 MAX(val) = 400，则可以跳过该整个页面。

索引扫描

如果表在谓词所用的属性上有索引，DBMS 可以使用索引直接找到匹配的元组，避免全表扫描。

查询优化器必须决定：使用索引还是直接做顺序扫描更便宜？ 这取决于： - 谓词的选择性（有多少元组匹配） - 索引是否聚簇（数据是否按索引键物理排序） - 随机 I/O 与顺序 I/O 的代价

对于低选择性谓词（匹配元组少），索引扫描通常更快。对于高选择性谓词，非聚簇索引的随机 I/O 可能使顺序扫描更便宜。

多索引扫描

当查询在多个属性上有谓词且每个属性上都有索引时，DBMS 可以：

  1. 独立扫描每个索引以获得匹配的记录 ID（RID）集合
  2. 使用集合运算对这些 RID 集合计算交集（AND）或并集（OR）
  3. 使用结果 RID 集合检索实际元组

当多个选择性谓词组合时，这种方法可能比使用单个索引更高效。

修改查询

修改数据库的算子（INSERT、UPDATE、DELETE）需要特殊处理，因为它们既读又写数据。

Halloween 问题

以 1976 年万圣节在 IBM 被发现而得名。问题是：如果扫描和更新操作在同一个索引上进行，UPDATE 查询可以看到自己的修改。

例如： 

1
UPDATE employees SET salary = salary + 100 WHERE salary < 1100;

如果表通过 salary 上的索引扫描，salary = 1000 的元组被更新为 1100。但扫描尚未结束 — 它可能在索引的新位置（现在位于键 1100，如果游标尚未经过该位置则仍在扫描范围内）再次遇到同一个元组。该元组被再次更新为 1200，如此循环 — 造成元组不断在扫描游标前方”逃跑”的无限循环。

解决方案： - 跟踪已修改元组：记录已更新元组的 RID，如果再次遇到则跳过 - 先物化：先扫描所有符合条件的元组，然后再应用更新 — 这会打断流水线但能保证正确性

表达式求值

DBMS 必须对 WHERE 子句、SELECT 列表和其他上下文中的表达式进行求值。

执行上下文

对于每次表达式求值，DBMS 维护一个执行上下文来跟踪：

  • 当前元组：正在处理的元组
  • 查询参数：参数化查询的绑定值
  • 表模式：解释列引用所需的元数据

表达式求值的朴素方法是表达式树，其中每个节点是一个运算符或值。

表达式树求值

1
2
3
4
5
    >
   / \
  +   600
 / \
A   B

求值时递归遍历树。问题在于：对每个元组，DBMS 都要遍历树、在运行时检查节点类型、追踪指针 — 由于以下原因，这很慢： - 指令缓存行为差（指针追踪） - 分支预测失误（每个节点的类型检查） - 函数调用开销

优化

  1. 常量折叠（Constant Folding）：在计划阶段预计算不依赖元组数据的表达式
    • WHERE 1 = 0 → 跳过整个查询
    • WHERE x > 3 + 2 → WHERE x > 5
    • SELECT UPPER('wutang') → SELECT 'WUTANG'（对常量的函数调用也会被折叠）
  2. 公共子表达式消除（CSE）：如果同一子表达式出现多次，只计算一次并复用结果
    • 例如：WHERE STRPOS(name, 'Andy') > 0 AND STRPOS(name, 'Andy') < 5 — STRPOS(name, 'Andy') 调用只计算一次，结果被共享
  3. JIT 编译：在查询时将表达式（或整个查询流水线）编译为原生机器码，消除树解释的开销
    • PostgreSQL 使用 LLVM 进行表达式的 JIT 编译
    • HyPer/Umbra 将整个查询流水线编译为原生代码
    • 消除类型检查、指针追踪和函数调用开销

Lec13 要点回顾

  • 向量化模型是分析型工作负载的最佳选择：它分摊函数调用开销，同时保持数据在缓存中并支持 SIMD
  • Zone Maps 是顺序扫描的简单而强大的优化 — 让 DBMS 在不维护完整索引的情况下跳过无关页面
  • Halloween 问题是当修改和扫描共享同一个索引结构时出现的微妙正确性问题
  • 基于推送的执行可以通过将算子编译为紧凑循环来超越基于拉取的方式，避免递归函数调用
  • JIT 编译表达式和流水线消除了在分析查询中占主导的 CPU 解释开销

Lec14 查询执行 II — 并行化

本讲探讨的核心问题是：DBMS 如何利用并行硬件来加速查询执行？ 涵盖管理工作者的进程模型、三种查询并行类型、通过 SIMD 实现的数据级并行，以及 I/O 并行技术。

并行与分布式

首先做一个重要区分：

方面 并行 DBMS 分布式 DBMS
资源 物理位置相近，通过高速互连通信 节点可能相距很远，通过较慢的网络通信
通信 廉价且假设可靠 代价不可忽略；消息可能丢失
示例 单台多核机器、共享内存集群 CockroachDB、Spanner

本讲聚焦于单台机器或紧耦合集群内的并行执行。分布式查询执行在后续讲座中介绍。

进程模型

DBMS 进程模型定义了系统如何将内部工作者抽象映射到 OS 级的进程或线程。这与 Lec13 讨论的查询处理模型是不同的概念。

每个工作者一个进程

每个工作者是一个独立的 OS 进程： - 依赖 OS 调度器分配 CPU 时间 - 工作者通过共享内存访问全局数据结构（缓冲池、锁表等） - 一个工作者崩溃不一定导致整个系统宕机 - 上下文切换开销高于线程 - 使用方：PostgreSQL、Oracle（早期）、IBM DB2

每个工作者一个线程（最常见）

每个工作者是单个 DBMS 进程中的一个 OS 线程： - 更低的开销 — 线程共享相同的地址空间，无需共享内存段 - DBMS 管理自己的调度（或依赖 OS 线程调度器） - 一个线程崩溃可能导致整个进程宕机 - 过去约 25 年的所有主流 DBMS 都使用原生 OS 线程（而非绿色线程或用户级协程） - 使用方：MySQL、SQL Server、Oracle（现代版本）、大多数现代系统

重要：使用线程-每-工作者模型并不自动意味着 DBMS 支持查询内并行。它只意味着 DBMS 可以在不同线程上并发运行多个查询。利用单个查询内的并行需要额外的基础设施（Exchange 算子、并行感知算子等）。

嵌入式 DBMS

DBMS 运行在应用进程内部（没有独立的服务器）： - 不需要进程间通信 - 应用负责管理并发 - 使用方：SQLite、DuckDB、LevelDB、RocksDB、BerkeleyDB、WiredTiger（MongoDB 的存储引擎）

对比

模型 隔离性 开销 使用方
每工作者一进程 高（进程边界） 高（上下文切换） PostgreSQL
每工作者一线程（最常见） 低（共享地址空间） 低（轻量级） MySQL、SQL Server
嵌入式 无（进程内） 最小 SQLite、DuckDB

调度

对于线程-每-工作者系统，DBMS 必须决定如何将任务分配给工作者线程。两种方式：

  • OS 级调度：让 OS 决定哪个线程运行在哪个核心上。简单但 DBMS 无法控制放置决策。
  • DBMS 级调度：DBMS 维护自己的工作队列并将任务分配给线程。这允许 NUMA 感知放置（将工作调度到距数据最近的核心）并避免过多的上下文切换。

现代高性能系统（如 SQL Server、Oracle）倾向于 DBMS 级调度以保持对资源分配的控制。

查询并行

有两个顶层类别：查询之间的并行和单个查询内部的并行。

查询间并行

在不同的工作者上同时执行多个查询。这很直接 — 每个查询独立运行。主要挑战是并发控制（确保事务之间互不干扰），这是后续讲座的主题。

改善的是吞吐量（每秒查询数）而非单个查询的延迟。

查询内并行

使用多个工作者执行单个查询。这改善的是单个查询的延迟。有三种方式：

算子内并行（水平） — 最常见

将单个算子分解为独立的片段，各自操作不同的数据子集：

1
2
3
     Gather
    /  |  \
Scan₁ Scan₂ Scan₃    ← same operator, different data partitions
  • 一个表扫描被拆分给 3 个工作者，每个读取不同范围的页面
  • 结果在上方的 Exchange 算子处合并
  • 也称水平分区或算子级的数据并行
  • 最常见的查询内并行形式
  • 示例：并行 Grace Hash Join — 使用连接键上的哈希对两个表分区，然后在多个工作者上对每对分区独立运行 hash join 实例

算子间并行（垂直/流水线化） — 较少见

查询计划中的不同算子在不同的工作者上同时运行，以生产者/消费者范式传递元组：

1
Worker 1: Scan → Filter  ──tuples──▶  Worker 2: Join → Project
  • 也称流水线并行 — 算子是流水线中的各阶段
  • 受最慢阶段限制（如果一个算子远慢于其他算子，流水线会停顿）
  • 实践中较少见，因为需要仔细的负载均衡
  • 在流式系统中更常见（如 Apache Kafka、Flink、Spark Streaming、Storm），而非传统 DBMS

Bushy 并行 — 高端系统

两者的组合：计划树的不同分支并行执行，每个分支内的算子也可以并行化：

1
2
3
4
     Join
    /    \
Scan₁   Scan₂    ← two branches in parallel
(W1,W2) (W3,W4)  ← each branch also uses multiple workers
  • 最灵活但调度最复杂
  • 被现代 MPP 系统用于复杂的多路连接

Exchange 算子

Exchange 算子是实现查询内并行的关键机制。它位于查询计划的并行片段之间，管理数据分发。

三种类型：

类型 行为 用例
Gather 将多个工作者的结果合并为一个流 合并并行扫描结果
Distribute 将一个流拆分到多个工作者 为并行连接分区数据
Repartition 将数据从 N 个工作者重新分布到 M 个工作者 在查询执行中途更改分区方案

Exchange 算子将并行抽象化 — 它上下方的算子无需知道自己正在并行运行。这是一种清晰的架构分离。

Google BigQuery 广泛使用 Repartition（shuffle）exchange — 其执行引擎在数千个工作者之间对中间数据进行大规模重分布，以执行分布式连接和聚合。

SIMD 数据并行

SIMD（Single Instruction, Multiple Data，单指令多数据）使用宽 CPU 寄存器同时对多个数据元素施加相同操作。

为什么 SIMD 对数据库很重要

典型的数据库扫描对数百万个值施加简单谓词（如 val > 100）。没有 SIMD 时，需要逐值比较。有了 SIMD，一条指令可以同时比较 4、8 甚至 16 个值（取决于寄存器宽度：SSE=128 位、AVX2=256 位、AVX-512=512 位）。

SIMD 选择扫描

考虑一个选择扫描：SELECT * FROM T WHERE val > 100

不使用 SIMD： 

1
2
for each value v in column:
    if v > 100: output v

使用 SIMD（AVX2，256 位寄存器，32 位整数 = 每寄存器 8 个值）： 

1
2
3
4
5
threshold = broadcast(100)  // [100, 100, 100, 100, 100, 100, 100, 100]
for each group of 8 values:
    data = load(values[i:i+8])
    mask = compare_gt(data, threshold)  // produces bitmask
    output matching values using mask

理论上每个指令周期可处理 8 倍的值。

潜在加速与多核并行叠加。例如，一台拥有 32 个核心、每个核心执行 4 路 SIMD 指令的机器，相比标量单核执行可获得高达 128 倍的吞吐量。

过滤器表示

SIMD 比较产生符合条件元组的位掩码后，DBMS 应如何表示和使用这个过滤器？

选择向量（Selection Vectors）：在数组中存储符合条件元组的位置（索引）。 - 当选择性低（匹配少）时紧凑 - 下游算子遍历位置 - 使用方：DuckDB、Vectorwise

位图（Bitmaps）：一个位向量，其中位 i = 1 表示元组 i 符合条件。 - 无论选择性如何，大小固定 - 对多个谓词的按位 AND/OR 高效 - 使用方：Oracle、许多列式存储

表示方式 空间 最适用场景 集合操作
选择向量 O(matches) 低选择性 需要归并
位图 O(n) 固定 高选择性、多谓词 按位 AND/OR

I/O 并行

当瓶颈是磁盘 I/O 而非 CPU 时，DBMS 可以并行使用多个存储设备。单个磁盘的带宽从根本上受限，因此扩展 I/O 需要将数据分布到多个设备上。

多磁盘并行

将数据库分布在多个磁盘上以增加聚合 I/O 带宽。

RAID 0（条带化）：以轮询方式将每个文件拆分到多个磁盘上。 - 读/写带宽随磁盘数量线性增长 - 无冗余 — 任何单个磁盘故障都会丢失数据 - 对 DBMS 透明

RAID 1（镜像）：在多个磁盘上复制每个文件。 - 读带宽翻倍（可以从任一副本读取） - 写带宽不变（必须写入两个副本） - 容错 — 可承受单个磁盘故障 - 对 DBMS 透明

实践中，生产系统使用 RAID 10（镜像条带）或依赖分布式存储系统在更高层处理冗余。RAID 通常在硬件或 OS 层配置 — 对 DBMS 透明。现代云/分布式系统通常用软件定义的纠删码替代硬件 RAID。

多磁盘配置的基本权衡三角是性能 vs 持久性 vs 容量 — 最多只能同时优化其中两个，第三个必须妥协。

数据库分区

将逻辑数据库拆分为不相交的段，存储在不同的磁盘上（或分布式系统中的不同机器上）。

垂直分区：按列拆分表 — 将不同列存储在不同磁盘上。 - 类似列存储布局 - 当查询只访问部分列时有用

水平分区：按行拆分表 — 不同的范围或哈希桶存放在不同磁盘上。 - 常见分区策略：范围、哈希、轮询 - 支持并行扫描，每个工作者从不同分区读取 - 需要注意点查询的分区裁剪 - PostgreSQL 通过 Tablespaces 支持此功能，允许将不同的表/索引存储在不同的磁盘卷上

并行化的挑战

并行化引入了 DBMS 必须处理的若干实际挑战：

  • 协调开销：同步工作者增加延迟（如 exchange 算子、屏障）
  • 调度：决定为每个查询分配多少工作者，以及如何在它们之间划分工作
  • 并发问题：对共享数据结构（哈希表、缓冲池）的并行访问需要精心的锁设计或无锁设计
  • 资源竞争：多个并行查询争夺 CPU、内存和 I/O 带宽

目标是在保持这些开销可控的同时，最大化吞吐量、最小化延迟。

Lec14 要点回顾

  • 线程-每-工作者是现代 DBMS 中占主导的进程模型 — 但使用线程并不自动意味着 DBMS 支持查询内并行
  • 算子内（水平）并行是最常见的查询内并行形式，通过 Exchange 算子实现清晰的抽象
  • SIMD 为扫描密集的分析工作负载提供显著加速 — 与多核并行结合，可实现 100 倍以上的吞吐量提升
  • I/O 并行通过 RAID 和分区在磁盘带宽成为瓶颈时至关重要，存在性能、持久性和容量之间的基本权衡
  • 并行化引入协调开销、调度复杂性和资源竞争 — DBMS 必须在这些代价与吞吐量收益之间取得平衡

总结

主题 核心思想
处理模型 迭代器（逐元组）、物化（一次性全部）、向量化（逐批次）— 向量化在 OLAP 中胜出
计划方向 Pull（自顶向下）简单；Push（自底向上）支持编译流水线
访问方法 带 zone maps 的顺序扫描、选择性查询的索引扫描、复合谓词的多索引扫描
Halloween 问题 UPDATE 可以通过共享索引看到自己的修改 — 必须跟踪或先物化
表达式求值 表达式树很慢；JIT 编译消除解释开销
并行 vs 分布式 并行 = 资源相近、通信廉价；分布式 = 节点远、网络不可靠
进程模型 每工作者一进程（隔离性） vs 每工作者一线程（性能，最常见） vs 嵌入式（简洁性）
查询内并行 水平（最常见）、垂直/流水线化（较少见）、Bushy（高端系统）
Exchange 算子 Gather / Distribute / Repartition — 将并行从算子中抽象出来
SIMD 一条指令操作多个数据值 — 与多核结合可获得 100 倍以上加速
过滤器表示 选择向量（稀疏，适合低选择性） vs 位图（密集，适合组合谓词）
I/O 并行 RAID 条带化/镜像增加带宽，分区支持并行扫描；权衡：性能 vs 持久性 vs 容量

核心要点：现代查询执行是处理模型、并行策略和硬件利用的协同设计 — 向量化批处理模型、Exchange 算子和 SIMD 共同使分析系统能够每秒处理数十亿元组。

参考文献

  • A. Pavlo, “Query Execution I,” CMU 15-445/645 Lecture #13, Spring 2024.
  • A. Pavlo & J. Patel, “Query Execution II,” CMU 15-445/645 Lecture #14, Spring 2024.
  • G. Graefe, “Volcano — An Extensible and Parallel Query Evaluation System,” IEEE TKDE, 1994.
  • T. Neumann, “Efficiently Compiling Efficient Query Plans for Modern Hardware,” VLDB, 2011.
  • P. Boncz, M. Zukowski, N. Nes, “MonetDB/X100: Hyper-Pipelining Query Execution,” CIDR, 2005.

本文基于 CMU 15-445/645 Database Systems 课程材料，讲师 Andy Pavlo 与 Jignesh Patel（Lecture #13: Query Execution I, Lecture #14: Query Execution II）。