元数据卡
维度 值 难度 （黑魔法） 前置 第8章 查询执行与优化器、C 语言虚函数概念 关键词 Volcano Model、Code Generation、LLVM JIT、Pipeline Breaking、Push-based Execution 代码语言 C++ / Pseudocode（主）
你的进度
军师给出了路线图，但老陈不满意。'每次都要看地图、一步一步执行——太慢了。'他想了一个办法：把路线图直接编译成机械指令，工人不用看地图，直接动手。这就是解释执行 vs 编译执行的差别。
破局 · 溯源
1. 火山模型：解释执行的经典
大多数数据库（PostgreSQL、MySQL、SQLite 的传统执行器）都基于火山模型（Volcano Model，也叫 Iterator Model）。
你设想一下：堡垒的工人们排成一条流水线，每个工人只干一件事。前面的工人问下一个下一个是什么，下一个工人就继续往下问。每个工人只等上一手的回答，干完就传给下一手。这就是火山模型的核心：每个算子实现一个 next() 接口。
// 算子基类
class ExecutorNode {
public:
virtual ~ExecutorNode() = default;
virtual Tuple* next() = 0; // 每次调用返回一行，nullptr 表示结束
};一个简单的过滤算子实现：
class FilterNode : public ExecutorNode {
ExecutorNode* child_; // 从下层算子拿数据
Predicate pred_;
public:
Tuple* next() override {
while (true) {
Tuple* t = child_->next();
if (!t) return nullptr; // 下层没数据了
if (pred_(t)) return t; // 满足条件就返回
// 否则继续循环，直到找到满足条件的行
}
}
};一个 Join 算子：
class HashJoinNode : public ExecutorNode {
ExecutorNode* build_child_; // 构建侧
ExecutorNode* probe_child_; // 探测侧
HashTable ht_;
bool built_ = false;
Tuple* build_output_; // 等值匹配的行
public:
Tuple* next() override {
// 构建阶段（只做一次）
if (!built_) {
while (auto* t = build_child_->next()) {
ht_.insert(key(t) t);
}
built_ = true;
}
// 探测阶段（逐行匹配）
while (auto* t = probe_child_->next()) {
if (auto match = ht_.lookup(key(t))) {
// 返回拼合的行
return concat(t match);
}
}
return nullptr;
}
};干活时，控制权从最底层一路往上拉：
[输出]
↑ next()
[HashJoin]
↑ next() ↑ next()
[Scan: adventurers] [Scan: quests]每次 next() 把控制权往上推一层——这就是“拉取模型”（Pull Model）。
好处： 接口简单统一，算子可以独立组合任意嵌套，任何时候只有一行在算子间流动，内存可控。
坏处： 每一行每经过一个算子，就是一次虚函数调用。一次 5-15 纳秒，看着不大，但乘以行数 × 算子数，帐就出来了。
2. 虚函数调用的真实代价
算一笔账：
假设查询计划深度为 4 层（Scan → Filter → HashJoin → Projection），扫描 1000 万行：
// 每行要经历：
child_->next() // Scan → Filter 的虚函数
child_->next() // Filter → HashJoin 的虚函数
child_->next() // HashJoin → Projection 的虚函数 (假设 Hash Join 探测侧)
// 加上内部 Filter 判断、HashTable lookup 等普通调用所以：
1000 万行 × 3 次虚函数调用 × 10ns ≈ 300ms300ms 的纯虚函数开销。听起来不多？对于一个原本跑 500ms 的查询，这 300ms 是 60% 的额外代价。对于分析型查询（处理数十亿行），这个开销可以膨胀到秒级。
更要命的是分支预测： 每个虚函数调用是一次间接跳转，CPU 的分支预测器根本不知道下一步跳哪。这意味着：
虚函数调用 = 无法预测的间接跳转 ≈ CPU 流水线冲刷 ≈ 10-20 个周期对于热点循环（一次扫描处理几亿行），这种**解释执行的"每行税"**可以占执行时间的 30%-50%。
PostgreSQL 社区早就看到了这个问题。9.6 之后引入 JIT（LLVM），但没有动火山模型的根——JIT 只编译了表达式求值，算子框架本身还是解释执行的。
3. 从解释到编译：三种路径
绕过虚函数开销的思路很简单：不通过 next() 逐行解释，直接生成一段能处理数据的机器码。
业界走了三条深度不同的路。
路径 1：表达式编译——最浅的改动
最浅的改动。只编译 WHERE 条件中的表达式部分，算子框架还是火山模型。
PostgreSQL 的 JIT 走的就是这条路：
-- 开启 JIT
SET jit = on;
SET jit_above_cost = 100000;
-- 对复杂表达式，LLVM 编译后会快很多
SELECT * FROM quests
WHERE reward * difficulty_multiplier + bonus > 1000;PostgreSQL 把 reward * difficulty_multiplier + bonus > 1000 这个表达式编译成 LLVM IR，再执行：
// 不做 JIT 时：
bool result = eval_expr(tuple expr_tree); // 遍历表达式树，解释执行
// 做 JIT 后（简化）：
auto compiled_fn = jit_compile(expr_ir); // 生成函数指针
bool result = compiled_fn(tuple); // 直接调用编译后的二进制代码效果：表达式复杂的查询能省去解释遍历表达式树的开销。但对算子之间的 next() 调用链——没用。
路径 2：管道编译——推倒算子之间的墙
把整张查询计划编译成一段首尾相连的代码。算子之间的墙消失了——没有 A 调 B 调 C 了，而是生成一个函数，扫描 → 过滤 → JOIN → 输出全挤在同一个循环里。
HyPer（后来的 Umbra）和 DuckDB 走的就是这条路。
// 对 SELECT a.name FROM adventurers a JOIN quests q ON ...;
// 生成这样的伪机器码（概念）：
void compiled_query(Table* adventurers Table* quests Output* out) {
// 全部在一个函数里，没有算子间的 next() 调用
for each page in adventurers {
for each tuple in page {
if (tuple.level > 30) { // Filter 不单独建对象
// Hash 构建：直接把 adventurer_id 插入哈希表
ht.insert(tuple.adventurer_id tuple.name);
}
}
}
// 探测阶段
for each page in quests {
for each tuple in page {
if (auto match = ht.lookup(tuple.adventurer_id)) {
out->emit(tuple.reward match->name);
}
}
}
}看到了吗？没有 child_->next()。所有循环都在一段连贯的代码里。CPU 看到的是连续的内存访问和能猜对的分支。
Pipeline Breaking：
不是所有操作都能"不打断"地串在一起。典型的打断者：
// 可以串（非打断）
Scan → Filter → Projection // 全部可以挤在一个循环里
// 必须打断（Pipeline Breaker）
Hash Join 的构建阶段需要先 // 需要先从头到尾读一遍构建侧
// 建好哈希表之后才能开始探测
// 另一个打断者：Sort
Sort // 必须全量数据到达后才能输出第一行DuckDB 的编译引擎做得精细：遇到 pipeline breaker 时自动切开生成独立代码块，两个代码块之间通过物化（写入中间结果集）连接。
路径 3：全编译——最彻底的革命
Hyper 从诞生起就押注全编译——直到 Umbra 时代，他们把整个 SQL 查询编译成高效的原生代码，而且还引入自适应索引（adaptive indexing）。
关键洞察：编译执行不只是绕过虚函数。它让编译器能做普通的标量优化（常量折叠、死代码消除、循环展开），还能做数据驱动的优化——比如根据列的实际类型、空值率、重复度生成不同的代码路径。
// 编译时根据列是否可空生成不同代码路径
if (column.has_null_bitmap) {
// 带有 null 检查的版本
} else {
// 没有 null 检查的版本（更快）
}Umbra 的论文报告，全编译执行比 PostgreSQL 的解释执行在 TPC-H 基准测试中快 1-2 个数量级。
4. DuckDB 的编译执行
DuckDB 是看编译执行最直接的窗口。看看它是怎么设计的：
DuckDB 没有传统意义上的"解释器"——它把查询计划编译成 C++ 风格的模板展开（template expansion），不走 LLVM IR。
// DuckDB 的向量化 + 编译执行
// 它不是火山模型的逐行调用，而是基于 chunk 的向量化
// 但算子的管道还是用了编译方式
// 一个 Filter 算子对应的代码生成（伪码）
void ExecuteFilter(DataChunk& input Expression& expr) {
SelectionVector sel;
idx_t result_count = 0;
// DuckDB 的向量化过滤：一次处理一整个 chunk（默认 2048 行）
for (idx_t i = 0; i < input.size(); i++) {
// 这里不是虚函数调用——而是模板展开的具体逻辑
if (expr.Evaluate(input i)) {
sel[result_count++] = i;
}
}
// 只保留符合条件的行
input.Slice(sel result_count);
}DuckDB 也不是"纯编译"——它的算子内部有循环，但算子间不是在 next() 虚函数上传递数据，而是编译时确定的类型安全接口。
DuckDB 的架构师的描述："我们在编译时把查询计划展开成一组高度特化的函数调用链，而不在运行时通过虚函数动态分发。"
作为用户，你不必关心这些内部——但跑下面的查询就能感受到区别：
.timer on
SELECT item_type
sum(value) as total_value
FROM vault_items
WHERE value > 500
GROUP BY item_type;DuckDB 会把 WHERE、GROUP BY、SUM 编译成一个紧密耦合的执行路径，而不是三个独立算子来回调用。
5. PostgreSQL LLVM JIT 实践
PostgreSQL 15+ 的 JIT 用 LLVM 编译关键路径——不是整张计划，只是关键段落。
哪些部分被编译了？
JIT 覆盖的范围：
Volcano Model Framework ← 不编译，保留 next() 调用
Expression Evaluation ← 编译 (JIT_Expression)
WHERE 条件、函数调用等
Tuple Deforming ← 编译 (JIT_TupleDeform)
把磁盘格式拆成列值
聚合函数的计算 ← 编译 (JIT_Agg)开启 JIT 的影响：
-- 准备：复杂表达式查询
SET jit = on;
SET jit_above_cost = 10000; -- 查询代价超过这个值才启用 JIT
SET jit_optimize_above_cost = 100000; -- 超过此值启用 LLVM 优化
EXPLAIN (ANALYZE TIMING)
SELECT * reward * (1 + difficulty_multiplier / 100) AS adjusted_reward
FROM quests
WHERE reward * difficulty_multiplier + bonus > 1000
AND (status = 'completed' OR status = 'in_progress');输出中会出现：
JIT:
Functions: 6
Options: Inlining false Optimization false Expressions true Deforming true
Timing: 2.132 ms (generation) + 0.283 ms (inlining) + 0.421 ms (optimization)
+ 0.123 ms (emission) = 2.959 ms两笔帐：JIT 编译花了 2.959ms，执行省了一些表达式树解释的时间。如果查询本身就不到 10ms，JIT 那 3ms 编译开销就白花了。
什么时候 JIT 是负资产？
查询执行时间
10s
JIT 收益区
1s
100ms JIT 灰色区
10ms
JIT 亏损区（编译 > 执行）
JIT 编译时间 ~3ms几条经验：
- 单次查询 > 1 秒：JIT 值得开
- 单次查询 < 50ms：JIT 不开白不开——不，不开更好
- OLTP 短查询（微秒级）：千万别开
这也是 PostgreSQL 默认 jit_above_cost = 100000 的原因——别让编译时间吃掉查询时间。
6. Hyper / Umbra 的全编译哲学
Thomas Neumann（慕尼黑工大教授，HyPer/Umbra 的创造者）有句名言：
"The best way to avoid interpretation overhead is to not interpret."
他的意思很明确：不要想着优化解释执行，要从根本上不解释。
HyPer（Hyper 是 "Hybrid OLTP & OLAP Engine" 的缩写，不是虚拟化 Hypervisor）的全编译核心：
// HyPer 的代码生成（概念）：一次生成一个完整查询函数的 LLVM IR
// 不再有 iterator / next() 调用
// 输入查询：
// SELECT name FROM adventurers WHERE level > 50 AND class = 'Paladin';
// 近似生成的 LLVM IR（概念级，不是真 IR）：
void query_kernel() {
// 1. 直接读取页面
for (page in table_pages("adventurers")) {
for (row in page) {
// 2. 直接解压 tuple → 列值（不需虚函数）
int level = deformat_int(row LEVEL_OFFSET);
// 3. 直接计算条件
if (level > 50) {
char* class_name = deformat_str(row CLASS_OFFSET);
if (str_eq(class_name "Paladin")) {
// 4. 直接输出
char* name = deformat_str(row NAME_OFFSET);
output->append(name);
}
}
}
}
}没有 FilterNode 对象，没有 ProjectionNode 对象，没有 child_->next()——只有连续的循环、连续的比较、连续的内存写入。
Umbra 作为 HyPer 的后继，更进一步引入了自适应编译（adaptive compilation）。它观察查询实际执行的情况，在运行时动态调整生成的代码。例如，如果一个哈希表的分区数太大，Umbra 会重新生成一个带有更少分区的代码版本。
深入冒险
Pipeline Breaking 的详细分析
但不是所有查询都能编成一段连续循环。看这个查询：
SELECT a.name MAX(q.reward)
FROM adventurers a JOIN quests q ON a.adventurer_id = q.adventurer_id
WHERE a.class = 'Paladin'
GROUP BY a.name
ORDER BY MAX(q.reward) DESC;查询管道中的打断点：
Pipeline 1: Scan(adventurers) → Filter(class='Paladin') → Hash Build
端点：Hash Table 构建完成才能输出
↕（Pipeline Break：物化到哈希表）
Pipeline 2: Scan(quests) → Hash Probe → Hash Group By
端点：GROUP BY 需要所有数据到齐
↕（Pipeline Break：物化到聚合哈希表）
Pipeline 3: Sort(reward DESC) → Limit每个 Pipeline Breaker 处，数据库都得物化中间结果——写入内存或磁盘。物化点越多，编译执行的收益被物化成本吃掉得越多。
编译执行的内存开销
编译执行也需要更多内存：代码段占缓存、物化中间结果占内存、LLVM 优化过程本身也吃内存。在内存紧巴巴的环境里（嵌入式数据库、lambda 函数），编译执行不一定划算。
常见陷阱
陷阱 1：JIT 编译时间 > 查询收益
一条 20ms 的查询，JIT 编译花了 5ms，执行省了 2ms——净亏 3ms，还多占了 CPU。
-- 这类查询不要开 JIT：
SELECT count(*) FROM small_table WHERE id = 42;陷阱 2：认为 DuckDB 是"纯编译"
DuckDB 经常和编译执行画等号——但它实际上是向量化执行 + 编译友好的模板结构。它的算子内部不逐行跑，而是处理 Data Chunk。它不是纯编译（像 HyPer），也不是纯解释（像 PostgreSQL 火山模型）。它是向量化解释，用 batch 放大计算密度。
陷阱 3：认为 "编译执行 = LLVM"
Llvm 只是编译执行的落地方式之一。DuckDB 的模板元编程、HyPer 的 LLVM IR 生成、甚至是 SQLite 的字节码虚拟机（VDBE）都是"编译"的不同程度。编译执行的核心是消除运行时动态分发，不一定是生成原生机器码。
陷阱 4：PostgreSQL JIT 开与关的影响
SET jit = on;
-- 如果查询代价小于 jit_above_cost，JIT 不会被触发
-- 但每个查询仍然会走一次 JIT 代价检查
-- 在 PG 16 中这个检查微乎其微实际影响可以忽略，但如果你在微秒级 OLTP 查询中强行关掉 JIT，性能差异可以观测到。
通关挑战
- 热身：解释为什么
SELECT * FROM t WHERE id = 1用解释执行比编译执行更好 - 挑战：在 PostgreSQL 中执行一个复杂表达式查询（至少 5 个算数运算 + 2 个函数调用），对比 JIT 开和关的执行时间：
SET jit = off;
-- 执行查询并记录时间
SET jit = on;
-- 同样查询，查看 JIT 的编译时间占比- 观察：对 DuckDB 的 TPC-H SF1 跑 Q1（最复杂的单表聚合），用
.timer on观察执行时间，理解为什么这类查询在编译/向量化引擎中表现极好
验收标准
- 能解释火山模型中每次
next()调用的虚函数代价及其对 CPU 流水线的影响 - 能区分表达式编译、管道编译、全编译三种不同程度的编译执行
- 知道 DuckDB 和 HyPer/Umbra 的编译执行方式的核心差异
- 能够判断什么场景下 JIT 不值得（短查询、OLTP）
- 理解 Pipeline Breaker 的概念及其对编译执行的影响
常见卡点
| 卡点 | 原因 |
|---|---|
| 觉得 JIT 对所有查询都有益 | 编译本身有开销；短查询净亏 |
| 认为火山模型只存于关系数据库 | 很多分布式查询引擎也用类似的拉取模型 |
| 混淆向量化执行和编译执行 | 向量化（批量处理数据）可以搭配解释或编译；DuckDB 两者都用 |
| 以为 PostgreSQL JIT 编译整个查询 | 实际上只编译了表达式和 tuple 解压部分 |
现在不需要理解
- LLVM IR 的具体指令格式及优化 Pass
- Adaptive Query Execution（运行时调整计划）
- JIT 在多线程环境下的代码缓存策略
- Umbra 的 adaptive indexing 机制
旅人笔记
火山模型的每次
next()都是一副枷锁——CPU 把时间花在间接跳转上，而不是真正干活上。编译执行丢掉枷锁，把整段查询变成连贯的机器码。但枷锁也有存在理由：灵活、省内存、短查询不需要编译成本。选哪种执行方式，看你的查询是"翻整座仓库"还是"找一把钥匙"。