# 实验 09：代码生成（Code Generation）

> 把查询计划从"一条元组一条元组地解释执行"，改成"针对这条查询生成一段专用源码、编译成字节码再跑"，看看能快多少。

## 一、实验目标

完成本实验后，你应该能够：

1. 说出 Volcano / 迭代器模型（iterator model）的接口约定 `open() / next() / close()`，并区分 **pull（拉）** 与 **push（推）** 两种驱动方向。
2. 指出解释执行的四类开销来源：函数调用、属性查找、通用分派、谓词求值。
3. 读懂 `compile(emit)` 的代码生成套路：把父算子的代码片段当作参数一层层往下传，最后拼出一段嵌套循环。
4. 用 Python 的 `compile()` / `exec()` 把生成的代码编译成字节码并执行。
5. 测量三种执行范式的耗时（解释执行、解释执行 + 通用分派、编译执行），算出加速比。
6. 写出差异测试（differential testing）：验证解释执行与编译执行的结果完全一致。
7. 说明什么时候不该用编译执行（编译开销 > 执行收益）。

## 二、预备知识

### 2.1 元组与算子

一条元组（tuple）在本实验中是一个字典：

```python
{"title": "DB101", "author": "Alice", "price": 8.5}
```

一个算子（operator）是对元组流做一次变换的东西。本实验用到四类：

| 算子 | 作用 | 输入 | 输出 |
| --- | --- | --- | --- |
| `Scan` | 从存储文件读元组 | — | 元组流 |
| `Filter` | 按谓词筛掉元组 | 元组流 | 元组流 |
| `SHJ` | 简单哈希连接（simple hash join） | 两个元组流 | 元组流 |
| `Count` / `Print` | 汇（sink），消费元组不往上推 | 元组流 | 一个数字 / 屏幕输出 |

### 2.2 Volcano / 迭代器模型

Volcano 模型（也称迭代器模型）出自 Graefe, *Volcano, An Extensible and Parallel Query Evaluation System*, IEEE TKDE 6(1), 1994, pp.120–135。每个算子实现三个方法：

```
open()   准备好内部状态（打开文件、建哈希表、复位计数器）
next()   返回下一条元组（pull 模型）/ 处理一条推上来的元组（push 模型）
close()  释放资源（关文件、清哈希表）
```

**pull 模型**（经典 Volcano）：父算子主动向下"拉"。

```
   Print ──next()──► SHJ ──next()──► Filter ──next()──► Scan
   ◄────tuple─────  ◄────tuple────  ◄─────tuple─────
```

**push 模型**：叶子算子主动向上"推"，本实验的教学 DBMS 用这种。

```
   Scan ──tuple──► Filter ──tuple──► SHJ ──tuple──► Print
```

push 模型下，"next()" 的语义变成"处理一条刚被推上来的元组"，本实验代码里叫 `interpret_next(tup)`。

push 模型的一个直接好处：算子之间不需要保存"我拉到哪了"的状态，数据一直待在寄存器/缓存里往上走，这也是它更容易被编译的原因。

### 2.3 解释执行的开销在哪

解释执行时，查询计划是一棵**对象树**，执行就是在这棵树上反复做方法调用。以 `price < 10` 这条谓词为例，处理一条元组要付出：

| 开销来源 | 具体动作 | 代价 |
| --- | --- | --- |
| 函数调用 | `Scan.interpret_next` → `Filter.interpret_next` → `SHJ.interpret_next` → `Count.interpret_next` | 每元组 4 次 Python 函数调用 |
| 属性查找 | `self.parent`、`self.pred`、`self.ht` | 字典/属性查找 |
| 通用分派 | 算子不知道父算子是谁，只能走 `self.parent.interpret_next(tup)` | 一次动态绑定 |
| 谓词求值 | `eval("price < 10", {}, tup)` | 每次都要重新编译表达式、建名字空间 |

在真实的 C/C++ 数据库里，前三项同样存在（虚函数调用、指针追逐）。第四项在教学实现里尤其夸张：`eval()` 每次都要解析字符串。

### 2.4 编译执行（以数据为中心的代码生成）

编译执行的思路是：既然查询计划在**执行前**就完全确定了，那就别在运行时反复分派，直接生成一段"只服务于这一条查询"的代码。

```
输入：查询计划（对象树）
输出：一段源码，形如

    import pickle
    num_tuples = 0
    ht = dict()
    with open('persons.pkl', 'rb') as f:
        for tup in pickle.load(f):
            ht.setdefault(tup['name'], list()).append(tup)
    with open('books.pkl', 'rb') as f:
        for tup in pickle.load(f):
            if tup['price'] < 10:
                for tup2 in ht.get(tup['author'], list()):
                    tup = tup | tup2
                    num_tuples += 1
```

对照解释执行，编译后的代码里：

- 没有算子对象，没有方法调用 —— 生成的是嵌套的 `for` 循环；
- 谓词被**内联**进循环体，写成 `if tup['price'] < 10:` 这样一个普通的比较；
- 元组始终在局部变量 `tup` 里，不需要跨函数传递。

这种风格叫**以数据为中心**（data-centric）的代码生成，也叫"pipeline fission / 算子融合"。出自 Neumann, *Efficiently Compiling Efficient Query Plans for Modern Hardware*, VLDB 2011（用 LLVM 编译，集成于 HyPer）。

### 2.5 另一种流派：向量化

向量化（vectorization）出自 Boncz et al., MonetDB/X100, CIDR 2005。它不改执行模型，而是把"一次处理一条元组"改成"一次处理一批（例如 1024 条）"，算子内部用紧凑数组和循环处理。

两种流派的对比（Kersten et al., PVLDB 2018）：

| 维度 | 向量化 | 以数据为中心的编译 |
| --- | --- | --- |
| 隐藏 cache miss 延迟 | 更擅长（批内并行度天然存在） | 较弱 |
| CPU 指令数 | 较多（要物化批次、管理批边界） | 更少 |
| 适合的负载 | 数据量大、cache 装不下 | cache-resident（数据能装进缓存） |
| 实现复杂度 | 较低，改算子内部即可 | 较高，要写代码生成器 |

一句话记忆：**向量化擅长"等内存"，编译擅长"少干活"**。

### 2.6 什么时候不该编译

编译不是免费的：要生成代码、要调用编译器、生成的代码要被加载，这些都要时间。PostgreSQL 的 JIT 就设了阈值（官方文档给出的默认值）：

| 参数 | 默认值 | 含义 |
| --- | --- | --- |
| `jit_above_cost` | 100000 | 估算代价超过这个值才启用 JIT |
| `jit_inline_above_cost` | 500000 | 超过这个值才做函数内联 |
| `jit_optimize_above_cost` | 500000 | 超过这个值才做优化编译 |

官方立场：JIT 主要有利于**长运行、CPU 密集的分析型查询**；短查询的编译开销常常大于收益，反而更慢。

这条规则在本实验里同样适用——步骤 7 会让你测出"编译本身花了多久"，并算出需要跑多少遍才能回本。

## 三、实验原理

### 3.1 `compile(emit)` 的递归套路

代码生成的关键设计是参数 `emit`。

`emit` 是一段**字符串**，含义是"当一条元组到达我这里时，接下来要执行的代码"。生成过程从汇算子（sink）开始，往叶子方向递归：

```
Count.compile()
    emit = "num_tuples += 1"
         │
         ▼
SHJ.compile("num_tuples += 1")
    生成： 建哈希表
          左孩子.compile("ht.setdefault(tup['name'],...).append(tup)")
          右孩子.compile("for tup2 in ht.get(tup['author'],...):\n    tup = tup|tup2\n    num_tuples += 1")
         │
         ▼
Filter.compile("for tup2 in ...")
    编译谓词： "price < 10"  →  "tup['price'] < 10"
    返回：     孩子.compile("if tup['price'] < 10:\n    " + indent(emit))
         │
         ▼
Scan.compile("if tup['price'] < 10: ...")
    返回：     "with open('books.pkl','rb') as f:\n    for tup in pickle.load(f):\n        " + indent(emit, 2)
```

每一步都做同一件事：**把父算子给的 `emit` 包进自己这一层的控制流里，再传给子算子**。递归到叶子时，整棵计划就被"展开"成了一段嵌套代码。

这个套路叫 continuation passing（续延传递），是手写代码生成器最省事的写法。

### 3.2 缩进处理

拼接字符串时必须处理缩进，否则生成的 Python 代码语法错误。工具函数：

```python
@staticmethod
def indent_emit_(emit, n=1):
    indent = "    " * n
    return f"\n{indent}".join(emit.split("\n"))
```

含义：把 `emit` 的每一行（除第一行）前面加上 `n` 层缩进，使其整体嵌进上一层的循环体/分支体。

### 3.3 谓词编译

`Filter` 持有字符串谓词 `"price < 10"`。生成代码时要把它改写成字典访问形式：

```python
import re
compiled_pred = re.sub("([a-zA-Z]+)", r"tup['\1']", "price < 10")
# 结果： "tup['price'] < 10"
```

正则 `([a-zA-Z]+)` 匹配连续的字母串（属性名），替换成 `tup['属性名']`。数字、运算符、空格不受影响。

**这个改写的代价是 O(谓词长度)，而且只做一次。** 对比解释执行里每条元组都要跑一次 `eval()` —— 这是编译执行最大的一块收益。

### 3.4 哈希连接的编译形态

`SHJ` 有两个孩子：左孩子建哈希表（build），右孩子探测（probe）。编译结果：

```
ht = dict()                                  ← 建表语句
<左孩子的循环，emit = 插入哈希表>              ← build 阶段
<右孩子的循环，emit = 查表 + 合并 + 父 emit>   ← probe 阶段
```

注意 probe 阶段有一句 `tup = tup | tup2`：把探测到的元组与哈希到的元组合并成一个新字典（`|` 是 Python 3.9+ 的字典合并运算符），然后**复用同一个变量名 `tup`**。这样上层的 `emit` 不需要改变量名，代码生成器好写。

### 3.5 参考图件

| 图件 | 内容 |
| --- | --- |
| `../figures/fig_codegen.png` | 解释执行与编译执行的耗时对比 |
| `../figures/fig_push_pipeline.png` | push 模型下算子的连接与元组流向 |

## 四、实验环境与准备

### 4.1 环境要求

| 项目 | 要求 |
| --- | --- |
| Python | 3.10 及以上（用到字典合并运算符 `|`，需 3.9+） |
| 必装库 | 无，只用标准库 `pickle` / `re` / `time` / `random` |
| 选装库 | `matplotlib`（步骤 8 画图） |
| 参考实现 | `notebooks/CodeGen.ipynb` |
| 参考模块 | `system/query_processing/operators.py` 的 `compile()` / `interpret_*()` |
| 参考测试 | `system/tests/test_code_gen.py`（差异测试） |

### 4.2 数据规模

本实验用 `books` 与 `persons` 各 **60,000** 条。第 6 节的实测数据在此规模下取得。

> 说明：`notebooks/CodeGen.ipynb` 里的 `number_of_tuples` 默认是 10,000（为了让 CI 跑得快）。本指导书把它调到 60,000 以对齐实测数据。若机器较慢，改回 10,000 也能跑通全部流程，但**数字会不同**，请填写你自己的实测值。

### 4.3 数据生成方式

notebook 用 `faker` 生成人名和书名。为了让本指导书的代码零外部依赖，改用纯随机数：

- `persons`：60,000 条，姓名从一个大小为 12,000 的姓名池中抽取（因此存在重名）；
- `books`：60,000 条，`price` 在 `[0, 100)` 上均匀分布，`author` 从同一个姓名池中抽取。

因为人名有重复，`name = author` 这个连接条件可能一本书匹配到多个 person，所以连接结果的行数会明显多于"`price < 10` 的书的数量"。本机实测结果为 **29,891 行**。本实验的数据生成固定了随机种子（`random.seed(42)`），这份代码在任何 CPython 上都应逐位复现。

## 五、实验步骤

### 步骤 1：生成数据并写入"存储"

用 `pickle` 把元组列表写进文件，模拟数据库的存储层。

```python
import pickle, random

N = 60_000          # persons 与 books 各 60,000 条
NAME_POOL = 12_000  # 姓名池大小，故意小于 N 以产生重名

random.seed(42)

persons = [
    {"name": f"Person{random.randrange(NAME_POOL)}",
     "birthday": f"19{random.randrange(70, 100)}-01-01"}
    for _ in range(N)
]

books = [
    {"title": f"Book{i}",
     "author": f"Person{random.randrange(NAME_POOL)}",
     "price": random.random() * 100}
    for i in range(N)
]

with open("persons.pkl", "wb") as f:
    pickle.dump(persons, f)
with open("books.pkl", "wb") as f:
    pickle.dump(books, f)

print("persons:", len(persons), " books:", len(books))
```

### 步骤 2：实现 push 模型的算子（解释执行）

```python
import math, re


class Operator:
    """所有算子的基类。"""

    def __init__(self, parent, children):
        self.parent = parent
        self.children = children or []

    def set_parent(self, parent):
        self.parent = parent

    @staticmethod
    def indent_emit_(emit, n=1):
        """把 emit 的每一行（除首行）缩进 n 层。"""
        indent = "    " * n
        return f"\n{indent}".join(emit.split("\n"))


class Scan(Operator):
    """从 pickle 文件读元组，往上推。"""

    def __init__(self, file, num_tuples=math.inf):
        super().__init__(None, [])
        self.file = file
        self.num_tuples = num_tuples

    # ---- 解释执行 ----
    def interpret_open(self):
        with open(self.file, "rb") as f:
            i = 0
            for tup in pickle.load(f):
                if i < self.num_tuples:
                    self.parent.interpret_next(tup)
                    i += 1
                else:
                    break

    # ---- 编译执行 ----
    def compile(self, emit=None):
        if self.num_tuples == math.inf:
            return (f"with open('{self.file}', 'rb') as f:\n"
                    f"    for tup in pickle.load(f):\n"
                    f"        {self.indent_emit_(emit, 2)}")
        return (f"with open('{self.file}', 'rb') as f:\n"
                f"    i = 0\n"
                f"    for tup in pickle.load(f):\n"
                f"        if i < {self.num_tuples}:\n"
                f"            {self.indent_emit_(emit, 3)}\n"
                f"            i += 1\n"
                f"        else:\n"
                f"            break")


class Filter(Operator):
    """按谓词筛元组。"""

    def __init__(self, child, pred):
        super().__init__(None, [child])
        self.pred = pred
        child.set_parent(self)

    def interpret_open(self):
        self.children[0].interpret_open()

    def interpret_next(self, tup):
        if eval(self.pred, {}, tup):
            self.parent.interpret_next(tup)

    def compile(self, emit=None):
        compiled_pred = re.sub("([a-zA-Z]+)", r"tup['\1']", self.pred)
        return self.children[0].compile(
            f"if {compiled_pred}:\n    {self.indent_emit_(emit)}"
        )


class SHJ(Operator):
    """简单哈希连接：左孩子建表，右孩子探测。"""

    def __init__(self, left_child, right_child, left_attr, right_attr):
        super().__init__(None, [left_child, right_child])
        self.left_attr = left_attr
        self.right_attr = right_attr
        left_child.set_parent(self)
        right_child.set_parent(self)

    def interpret_open(self):
        self.ht = {}
        self.is_build_phase = True
        self.children[0].interpret_open()
        self.is_build_phase = False
        self.children[1].interpret_open()

    def interpret_next(self, tup):
        if self.is_build_phase:
            self.ht.setdefault(tup[self.left_attr], []).append(tup)
        else:
            for tup2 in self.ht.get(tup[self.right_attr], []):
                self.parent.interpret_next(tup | tup2)

    def compile(self, emit=None):
        return (
            "ht = dict()\n"
            + self.children[0].compile(
                f"ht.setdefault(tup['{self.left_attr}'], list()).append(tup)")
            + "\n"
            + self.children[1].compile(
                f"for tup2 in ht.get(tup['{self.right_attr}'], list()):\n"
                f"    tup = tup | tup2\n"
                f"    {self.indent_emit_(emit)}")
        )


class Count(Operator):
    """汇算子：统计元组条数，不往上推。"""

    def __init__(self, child):
        super().__init__(None, [child])
        child.set_parent(self)

    def interpret_open(self):
        self.num_tuples = 0
        self.children[0].interpret_open()

    def interpret_next(self, tup):
        self.num_tuples += 1

    def compile(self):
        return "import pickle\n\nnum_tuples = 0\n" + \
            self.children[0].compile("num_tuples += 1")
```

### 步骤 3：搭建查询计划

对应 SQL：

```sql
SELECT *
FROM persons JOIN books
     ON name = author
WHERE price < 10
```

```python
def create_qep(sf=1.0):
    """sf 是规模因子（scale factor），用来控制每个 Scan 读多少条元组。"""
    n = int(N * sf)
    scan_persons = Scan("persons.pkl", n)
    scan_books = Scan("books.pkl", n)
    filter_books = Filter(scan_books, "price < 10")
    join = SHJ(scan_persons, filter_books, "name", "author")
    return Count(join)


plan = create_qep()
plan.interpret_open()
print("解释执行结果:", plan.num_tuples)
```

`sf`（scale factor，规模因子）是无量纲的比例系数，取值 `0 < sf ≤ 1`，表示"每个 Scan 只读全表的 `sf` 比例"。步骤 7 会用它画出不同规模下的耗时曲线。

### 步骤 4：打印生成的源码

```python
code = plan.compile()
print(code)
```

预期输出（结构如下，具体缩进以实际打印为准）：

```python
import pickle

num_tuples = 0
ht = dict()
with open('persons.pkl', 'rb') as f:
    i = 0
    for tup in pickle.load(f):
        if i < 60000:
            ht.setdefault(tup['name'], list()).append(tup)
            i += 1
        else:
            break
with open('books.pkl', 'rb') as f:
    i = 0
    for tup in pickle.load(f):
        if i < 60000:
            if tup['price'] < 10:
                for tup2 in ht.get(tup['author'], list()):
                    tup = tup | tup2
                    num_tuples += 1
            i += 1
        else:
            break
```

对照 2.4 节：谓词 `price < 10` 被内联成了 `if tup['price'] < 10:`，看不到任何算子对象和方法调用。

### 步骤 5：编译成字节码并执行

```python
def run_compiled(plan):
    """生成代码 → 编译成字节码 → 执行，返回计数结果。"""
    code = plan.compile()
    ns = {}
    exec(compile(code, "<generated>", "exec"), ns)
    return ns["num_tuples"]


print("编译执行结果:", run_compiled(plan))
```

也可以按 notebook 的做法落盘、用 `py_compile` 生成 `.pyc`、再用子进程跑：

```python
from py_compile import compile as pyc_compile
import subprocess

code = plan.compile()
with open("codegen.py", "w", encoding="utf-8") as f:
    f.write(code)
with open("codegen.pyc", "w", encoding="utf-8"):
    pass
pyc_compile("codegen.py", "codegen.pyc", doraise=True)
subprocess.call(["python", "codegen.pyc"])
```

> 注意：走子进程的方式会额外付一次 Python 解释器启动开销（通常为几十毫秒量级），做性能对比时会掩盖代码生成本身的收益。步骤 7 的计时用进程内的 `exec` 版本。

### 步骤 6：差异测试——两种执行方式结果必须一致

```python
def normalized_interpret(plan):
    plan.interpret_open()
    return plan.num_tuples


for sf in (0.1, 0.25, 0.5, 0.75, 1.0):
    p = create_qep(sf)
    a = normalized_interpret(p)
    b = run_compiled(p)
    print(f"sf={sf:<5} 解释={a:<8} 编译={b:<8} 一致={a == b}")
    assert a == b, "解释执行与编译执行结果不一致！"
```

预期：五个规模下全部 `一致=True`。

这一步就是**差异测试**（differential testing）：同一条查询用两条完全不同的执行路径跑，结果必须逐字节相同。它是编译器类代码最重要的测试手段——仓库里的 `system/tests/test_code_gen.py` 用的就是这个方法。

### 步骤 7：几种执行范式的耗时对比

前面的 `Filter.interpret_next` 用的是 `eval(self.pred, {}, tup)`，每条元组都要重新解析一次表达式字符串，这是最慢的一种做法（notebook 里就是这么写的）。真实系统不会这样，它会把谓词**预编译**成一个可调用对象，然后每条元组调用一次。所以这里补两个变体，一共比较四种范式：

| 范式 | 谓词求值方式 |
| --- | --- |
| A 解释执行（`eval` 字符串） | 每条元组重新解析表达式字符串 |
| B 解释执行（预编译谓词函数） | 表达式编译一次，每条元组调用一次函数 |
| C 解释执行（多一层通用分派） | 在 B 之上再包一层 lambda |
| D 生成专用代码 | 谓词内联进循环，没有函数调用 |

```python
class PredFnFilter(Filter):
    """把谓词预编译成代码对象，每条元组调用一次。"""

    def __init__(self, child, pred):
        super().__init__(child, pred)
        self.pred_code = compile(pred, "<pred>", "eval")

    def interpret_next(self, tup):
        if eval(self.pred_code, {}, tup):
            self.parent.interpret_next(tup)


class DispatchFilter(Filter):
    """在谓词求值外面再包一层通用函数分派，模拟真实的通用谓词接口。"""

    def __init__(self, child, pred):
        super().__init__(child, pred)
        self.pred_fn = lambda tup: eval(self.pred, {}, tup)

    def interpret_next(self, tup):
        if self.pred_fn(tup):
            self.parent.interpret_next(tup)


def create_qep_with(filter_cls, sf=1.0):
    n = int(N * sf)
    scan_persons = Scan("persons.pkl", n)
    scan_books = Scan("books.pkl", n)
    filter_books = filter_cls(scan_books, "price < 10")
    join = SHJ(scan_persons, filter_books, "name", "author")
    return Count(join)


import time

def measure(fn, repeat=5):
    """跑 repeat 次，返回每次耗时（毫秒）的列表。"""
    out = []
    for _ in range(repeat):
        t0 = time.perf_counter()
        fn()
        out.append((time.perf_counter() - t0) * 1000)
    return out


def median(xs):
    return sorted(xs)[len(xs) // 2]


rows = []
for sf in (0.1, 0.25, 0.5, 0.75, 1.0):
    p_a = create_qep(sf)                                  # A: eval 字符串
    p_b = create_qep_with(PredFnFilter, sf)               # B: 预编译谓词
    p_c = create_qep_with(DispatchFilter, sf)             # C: 多一层分派
    p_d = create_qep(sf)                                  # D: 编译执行

    t_a = median(measure(lambda: p_a.interpret_open()))
    t_b = median(measure(lambda: p_b.interpret_open()))
    t_c = median(measure(lambda: p_c.interpret_open()))
    t_d = median(measure(lambda: run_compiled(p_d)))

    rows.append((sf, t_a, t_b, t_c, t_d))
    print(f"sf={sf:<5} A={t_a:8.2f}  B={t_b:8.2f}  C={t_c:8.2f}  D={t_d:8.2f} ms"
          f"   B/D={t_b / t_d:.2f}x")
```

预期趋势：**`D < B < A < C`**。理由：

- `B` 比 `A` 快：B 只执行已编译的代码对象，A 每条元组还要解析一次字符串。
- `C` 比 `A` 慢：C 在 A 之上多包了一层 Python 函数调用。
- `D` 最快：谓词内联，根本没有函数调用。

`B/D` 这一列就是"解释执行 vs 编译执行"的加速比——**A 与 C 的差距反映的是 `eval` 的字符串解析成本，不是执行模型的差异**，看加速比时只用 B/D。

> 关于小 `sf` 时的比值不稳定：`pickle.load(f)` 会把整个文件反序列化出来，这份开销**与 `sf` 无关**，是一个常数。当 `sf` 很小时它占了大头，四种范式的耗时被拉平，比值失去参考意义。要看清差距，用 `sf ≥ 0.75` 的数据（实测 sf = 0.5 时 B/D 仍会反转成 0.87×）。彻底去掉这个干扰的办法见 8.7 题（改用内存 `Relation` 算子）。

### 步骤 8：把编译开销单独拆出来

代码生成不是免费的，把三个阶段分开计时：

```python
p = create_qep()

code = p.compile()                                  # 阶段 1：生成源码
t0 = time.perf_counter()
code = p.compile()
t_gen = (time.perf_counter() - t0) * 1000

t0 = time.perf_counter()
bytecode = compile(code, "<generated>", "exec")      # 阶段 2：编译字节码
t_comp = (time.perf_counter() - t0) * 1000

t0 = time.perf_counter()
ns = {}
exec(bytecode, ns)                                   # 阶段 3：执行
t_exec = (time.perf_counter() - t0) * 1000

print(f"生成源码  {t_gen:.3f} ms")
print(f"编译字节码 {t_comp:.3f} ms")
print(f"执行      {t_exec:.3f} ms")

t_int = median(measure(lambda: create_qep_with(PredFnFilter).interpret_open()))
overhead = t_gen + t_comp
saved = t_int - t_exec
print(f"解释执行(B) {t_int:.3f} ms，编译执行(D) {t_exec:.3f} ms")
print(f"每执行一次省下 {saved:.3f} ms，需要跑 {overhead / saved:.3f} 次才能回本")
```

这里用 B 作为解释执行的基线，因为它是"逐条调用谓词函数"的合理解释执行，与 D 可比。

你会看到一个反直觉的结果：**回本次数接近 0**。原因是 CPython 的 `compile()`（源码 → 字节码）非常便宜，通常不到 1 毫秒。

由此引出一个重要对比：

| 系统 | 编译什么 | 一次性开销 | 是否需要阈值 |
| --- | --- | --- | --- |
| 本实验（CPython） | Python 源码 → 字节码 | 亚毫秒级 | 几乎不需要 |
| HyPer / LLVM | C++ IR → 优化的机器码 | 毫秒到百毫秒级 | 需要 |
| PostgreSQL JIT | 表达式 → LLVM IR → 机器码 | 毫秒级 | 需要（`jit_above_cost`） |

优化编译器（LLVM）要做寄存器分配、指令选择、循环优化，代价远高于 Python 的字节码编译。这就是为什么真实数据库必须设阈值——**编译开销的量级决定了是否值得**。

### 步骤 9：画图（可选）

需要 `matplotlib`：

```python
import matplotlib.pyplot as plt

sf = [r[0] for r in rows]
fig, ax = plt.subplots()
ax.plot(sf, [r[1] for r in rows], "o-", label="A 解释执行（eval 字符串）")
ax.plot(sf, [r[2] for r in rows], "s-", label="B 解释执行（预编译谓词）")
ax.plot(sf, [r[3] for r in rows], "d-", label="C 解释执行（多一层分派）")
ax.plot(sf, [r[4] for r in rows], "^-", label="D 编译执行")
ax.set_xlabel("规模因子 sf")
ax.set_ylabel("耗时 (ms)")
ax.legend()
ax.grid(alpha=0.3)
plt.show()
```

## 六、观测记录表

### 6.1 数据规模

| 项目 | 值 |
| --- | --- |
| `persons` 条数 | 60,000 |
| `books` 条数 | 60,000 |
| 姓名池大小 | 12,000 |
| 连接结果行数（实测） | 29,891 |
| 你的连接结果行数 | |

### 6.2 执行范式耗时（本指导书代码口径，books = 60,000，命中 29,891，sf = 1.0，5 次中位数）

| 范式 | 执行方式 | 参考实测 | 你的实测值 | 相对 D 的倍数 |
| --- | --- | ---: | ---: | ---: |
| A | 解释执行（每条元组 `eval` 字符串） | 约 570–600 ms | | |
| B | 解释执行（逐条调用谓词函数） | 约 110–125 ms | | |
| C | 解释执行（多一层通用分派） | 约 610–690 ms | | |
| D | 生成专用代码（谓词内联进循环） | 约 100–116 ms | | 1.00 |

加速比参考值：**约 1.05–1.1×**（B/D，sf = 1.0）。

请自己算出你的加速比并填在下面：

```
我的加速比（B/D） = ______ / ______ = ______
```

**关于 A 这一行**：本指导书的 `Filter` 用的是 `eval(self.pred, {}, tup)`，每条元组都要重新解析表达式字符串，耗时会明显高于 B（本环境实测高出数倍）。这个差距反映的是 `eval` 的字符串解析成本，**不是执行模型的差异**，看加速比时不要用它。

**为什么只有约 1.1 倍，而图件里是 1.47 倍？** 本表是**本指导书代码的口径**：`Scan` 每次执行都要 `pickle.load` 把 60,000 本书的字典反序列化出来，这笔开销与执行范式无关，却是总耗时的大头（sf = 1.0 时约占九成）。四条耗时都被这个常数垫高，B/D 的差距被摊薄；去掉它（8.7 题的内存 `Relation` 方案）就回到图件口径——解释 5.18 ms / 通用分派 5.90 ms / 生成代码 3.52 ms（1.47×）。

**关于你的数字**：绝对值随机器变化，量级参考即可。重点核对**相对关系**（sf ≥ 0.75 时 `D < B < A < C`）与**趋势**（随 `sf` 增大 B/D 缓慢拉大）。sf 较小时四种范式被 `pickle.load` 常数拉平，sf = 0.5 时 B/D 甚至会反转（实测 0.87×），属正常现象。

### 6.3 编译开销拆分

| 阶段 | 你的实测值 |
| --- | --- |
| 生成源码 | |
| 编译字节码 | |
| 执行生成的字节码 | |
| 前两项合计（一次性开销） | |
| 每执行一次省下的时间 | |
| 回本所需的执行次数 | |

### 6.4 差异测试结果

| 规模因子 sf | 解释执行结果 | 编译执行结果 | 是否一致 |
| --- | ---: | ---: | --- |
| 0.1 | | | |
| 0.25 | | | |
| 0.5 | | | |
| 0.75 | | | |
| 1.0 | | | |

### 6.5 概念核对

| 说法 | 对 / 错 | 理由 |
| --- | --- | --- |
| 编译执行的加速主要来自"少读磁盘" | | |
| 编译执行生成的代码里没有算子对象 | | |
| 查询越短越适合编译执行 | | |
| 差异测试能发现"结果对但性能差"的问题 | | |

### 6.4 三套计时口径对照

同一份"代码生成"主题，三个入口会给出三套不同的数字——**先分清口径，再比大小**：

| 口径 | 入口 | 数据 | 数字 | 说明 |
| --- | --- | --- | --- | --- |
| A：图件/讲义 | `fig_codegen` 图与讲义 3.2 节 | 内存数据、无反序列化；books = 60,000，命中 29,895 | 解释 5.18 / 通用分派 5.90 / 生成 3.52 ms（1.47×） | 纯执行模型的差距 |
| B：笔记本计时单元 | `CodeGen.ipynb` 计时 cell（子进程） | books = 10,000，命中 1,198 | 解释 159.4 ms / "compiler" 约 1150–1460 ms | "compiler" 高出来的部分几乎全是 Python 解释器启动开销 |
| C：笔记本进程内 | 同一笔记本改为进程内执行 | books = 10,000 | sf = 1.0：159.4 / 20.0 ms（约 8×） | 去掉子进程后差距立刻显形 |
| 本表 | 本指导书步骤 1–7 | 含 `pickle.load` 常数；books = 60,000，命中 29,891 | 约 110–125 / 610–690 / 100–116 ms（B/D ≈ 1.05–1.1×） | 常数垫高全体，摊薄差距 |

差异来源，按影响从大到小：① 是否每条元组 `eval` 字符串；② 是否走子进程；③ 是否含 `pickle.load` 反序列化常数；④ 数据规模与命中率。**不要**把 5.18 ms 说成"运行笔记本会看到的值"，也**不要**把笔记本柱状图上的 1000+ ms 说成"编译执行的代价"。

## 七、思考题

1. 解释执行处理一条元组要调用几次 Python 函数？请把 `Scan → Filter → SHJ → Count` 这条链上的调用逐一列出来。
2. 生成的代码里有一句 `tup = tup | tup2`。为什么要**覆盖** `tup` 而不是用新变量名 `tup3`？如果改成新变量名会有什么问题？
3. 本实验测得加速比 1.47×。论文（Neumann, VLDB 2011）报告的加速比通常高得多。列出至少三个导致本实验加速比偏低的原因。
4. 谓词编译用了正则 `re.sub("([a-zA-Z]+)", r"tup['\1']", pred)`。如果谓词写成 `price < 10 and author != ''`，改写结果是什么？这个改写对哪些谓词会出错？
5. 步骤 8 算出"回本所需的执行次数"。请说明这个数字与 PostgreSQL 的 `jit_above_cost = 100000` 在思想上有什么联系。
6. 为什么向量化在 cache 装不下数据时比编译执行更有优势？反过来，为什么编译执行在 cache-resident 负载下更优？
7. 本实验的 `Scan` 在解释执行和编译执行里都用了 `pickle.load(f)` 一次性把整个文件读进内存。这会对结论产生什么影响？如何改进？
8. 差异测试能保证什么、不能保证什么？举例说明一个"通过了差异测试但仍然是错的"的实现。

## 八、思考题答案与解析

### 8.1 题 1

以 push 模型、从 `Scan(books)` 出发的一条元组为例（它通过了谓词并在哈希表里命中 1 条）：

| 序号 | 调用 | 说明 |
| --- | --- | --- |
| 1 | `Scan.interpret_open` 的循环体 → `self.parent.interpret_next(tup)` | 叶子推动 |
| 2 | `Filter.interpret_next(tup)` | 谓词求值 |
| 3 | `Filter` → `self.parent.interpret_next(tup)` | 继续上推 |
| 4 | `SHJ.interpret_next(tup)` | 探测阶段，循环体里每条 `tup2` 一次 |
| 5 | `SHJ` → `self.parent.interpret_next(tup \| tup2)` | 合并后上推 |
| 6 | `Count.interpret_next(tup)` | 计数 |

`Scan(persons)` 那条链类似，但 `SHJ` 处于 build 阶段，不会调用父算子，所以少第 5、6 步。

计数要点：**每处理一条元组，链条上有 3~4 次 Python 方法调用**。一次 Python 方法调用的成本在几十到上百纳秒量级，而生成的代码里这些调用全部消失，只剩循环体内的字典访问。这是 1.47× 加速的主要来源。

用代码量一下纯函数调用的代价：

```python
class Sink:
    def f(self, x):
        return x + 1

s = Sink()
n = 2_000_000
t0 = time.perf_counter()
for i in range(n):
    s.f(i)
print("方法调用:", (time.perf_counter() - t0) / n * 1e9, "ns/次")

t0 = time.perf_counter()
for i in range(n):
    pass
print("空循环  :", (time.perf_counter() - t0) / n * 1e9, "ns/次")
```

两者相减即为单次方法调用的净开销（具体数字需自行实测确认）。

### 8.2 题 2

原因是**代码生成器写起来简单、生成的代码也简单**。

`emit` 是父算子交给子算子的一段代码，它里面的变量名必须和子算子放入作用域的变量名一致。`SHJ` 的探测阶段把"当前元组"放在变量 `tup` 里；上层的 `emit`（这里是 `num_tuples += 1`，不需要访问元组）以及更上层的 `Filter` 生成的 `if tup['price'] < 10:` 都假定元组变量叫 `tup`。

如果改成 `tup3 = tup | tup2`，那么后续所有代码里的 `tup` 都要改成 `tup3`，而 `emit` 是**字符串**，改名意味着要么做一次字符串替换（脆弱、易错），要么引入一层变量别名（多一次赋值开销）。

直接覆盖 `tup` 的代价是：合并前那个"探测到的元组"在循环体后续代码里访问不到了。对本实验的查询没有影响（后续只用到合并结果），但如果上层还要单独访问探测侧的列，就需要保留两个变量。

### 8.3 题 3

至少四点：

1. **实现语言不同。** 论文用 LLVM 把查询编译成优化的机器码，可以做寄存器分配、循环展开、常量传播、向量化指令选择。本实验编译成的是 **Python 字节码**，仍然由 CPython 解释器逐条执行，只是省掉了 Python 层的函数调用。收益的天花板低得多。
2. **编译开销没有摊薄。** 本实验每次都重新生成 + 重新编译（`compile()`），步骤 8 会测出这部分是毫秒级的一次性开销。论文里编译开销被长查询的执行时间摊薄了。
3. **瓶颈不同。** 论文面对的是内存内、CPU 密集的负载，指令数就是瓶颈。本实验里 `pickle.load(f)` 一次性反序列化整个文件，这部分开销巨大且与执行模型无关，把指令数的差异稀释掉了。
4. **查询太简单。** 本查询只有 1 个过滤 + 1 个连接。算子越多、流水线越长，解释执行的方法调用开销越大，编译执行的收益也越大。可以用更深的计划验证这一点（扩展任务 9.1）。

### 8.4 题 4

改写结果：

```python
import re
print(re.sub("([a-zA-Z]+)", r"tup['\1']", "price < 10 and author != ''"))
```

实际输出：

```
tup['price'] < 10 tup['and'] tup['author'] != ''
```

**这个结果就是错的**。关键字 `and` 也被当成了属性名，改写成 `tup['and']`，生成的代码要么抛 `KeyError`，要么引用到不存在的列。

这条正则只在**最简单的谓词**上正确，例如 `price < 10`（单个属性名 + 运算符 + 数字常量）。

会出错的谓词：

| 谓词 | 改写结果 | 问题 |
| --- | --- | --- |
| `price < 10.5` | `tup['price'] < 10.5` | 数字不匹配 `[a-zA-Z]+`，正常 |
| `price < 10 and author != ''` | `tup['price'] < 10 tup['and'] tup['author'] != ''` | 关键字 `and` 被当成属性名 |
| `title LIKE 'DB%'` | `tup['title'] LIKE tup['DB']%` | `LIKE` 不是 Python 运算符；字符串常量 `'DB'` 被当成属性名 |
| `author == 'Alice'` | `tup['author'] == tup['Alice']` | 字符串常量被当成属性名 |
| `abs(price) < 10` | `tup['abs'](tup['price']) < 10` | 函数名 `abs` 被改写 |
| `a_b > 1`（属性名含下划线） | `tup['a']_tup['b'] > 1` | 下划线不在 `[a-zA-Z]` 里，属性名被切开 |
| `a[0] > 1` | `tup['a'][0] > 1` | 碰巧可用，但语义不是我们想要的 |

根本问题：这个正则**不区分标识符的种类**（属性名、函数名、字符串常量、关键字），也不支持下标、下划线、点号。它只是教学用的最小实现，能跑通本实验的 `price < 10` 就够了——但你必须知道它的边界在哪里。

正确的做法不是改进正则，而是写一个真正的表达式解析器（或复用 `ast` 模块）：

```python
import ast

class Rewriter(ast.NodeTransformer):
    def visit_Name(self, node):
        return ast.Subscript(
            value=ast.Name(id="tup", ctx=ast.Load()),
            slice=ast.Constant(value=node.id),
            ctx=ast.Load(),
        )

def compile_expr(pred):
    tree = ast.parse(pred, mode="eval")
    tree = Rewriter().visit(tree)
    ast.fix_missing_locations(tree)
    return ast.unparse(tree)

print(compile_expr("price < 10 and author != 'Alice'"))
```

`ast` 模块能正确区分 `Name`（标识符）、`Constant`（常量）、`Call`（函数调用），只在 `Name` 节点上做改写。

### 8.5 题 5

思想完全一致：**只有执行阶段的收益超过编译阶段的开销时，才启用编译**。

- PostgreSQL 用查询优化器估算出的**代价**（cost，一个无量纲的估算值）作为代理指标：估算代价 > 100000 才 JIT。代价与预计要处理的元组数、要调用的表达式次数正相关，因此它近似代表"执行阶段的规模"。
- 本实验步骤 8 直接算出 `回本次数 = (生成 + 编译) / (每次省下的时间)`，是同一个不等式解出来的显式形式：
  ```
  一次性开销 < 执行次数 × 每次省下的时间
  ```
- 差别只在度量方式：PostgreSQL 用**事前估算**（不需要真的跑），本实验用**事后实测**（已经跑过了）。

推论：同一个查询如果会被反复执行（例如预编译的存储过程、参数化查询反复调用），编译开销可以被多次摊薄，此时阈值应该下调；反之，一次性即席查询应保守启用。

### 8.6 题 6

**cache 装不下（数据量大）时，执行时间的很大一部分是等内存。** 向量化一次处理一批（例如 1024 条）元组，批内的多次内存访问彼此独立，CPU 可以在等第一条的同时发出第二条、第三条的请求，延迟被重叠隐藏了（memory-level parallelism）。编译执行生成的代码是逐元组的循环，一次访问完成后才能发起下一次，遇到 cache miss 就真的停住等。所以在"等内存"占主导时，向量化更快。

**cache-resident（数据能装进缓存）时，内存访问几乎不耗时，瓶颈变成 CPU 指令数。** 此时：

- 向量化要付出额外的批管理开销：填充批次、传递批边界、在算子之间物化中间结果数组。这些是纯开销。
- 编译执行把整条流水线融合成一个循环，元组始终在寄存器里，中间结果从不物化。指令数明显更少。

结论出自 Kersten et al., PVLDB 2018 的实验对比：**向量化更擅长隐藏 cache miss 延迟；以数据为中心的编译所需 CPU 指令更少，更适合 cache-resident 负载**。

记忆方法：数据小 → 少干活（编译）；数据大 → 会等待（向量化）。

### 8.7 题 7

`pickle.load(f)` 会把整个文件一次性反序列化成一个 Python 列表，**两种执行范式都要付这份代价，而且它在总时间里占大头**。

影响：

- 实测的加速比（1.47×）被**低估**了。因为分子分母里都含有一大块与执行模型无关的常数，比值被拉向 1。
- 换句话说，如果只看"元组处理"这一段，编译执行的相对优势会比 1.47× 更明显。

改进办法：

1. 把 `pickle.load` 挪到计时之外——预先把 `persons`、`books` 读成内存列表，`Scan` 改成 `Relation`（直接遍历内存列表）。这样测出来的就是纯粹的元组处理时间。
2. 用 `Relation` 算子替代 `Scan`：

```python
class Relation(Operator):
    def __init__(self, name, data):
        super().__init__(None, [])
        self.name = name
        self.data = data

    def interpret_open(self):
        for tup in self.data:
            self.parent.interpret_next(tup)

    def compile(self, emit=None):
        return (f"for tup in DATA['{self.name}']:\n"
                f"    {self.indent_emit_(emit)}")
```

注意 `compile` 生成的代码引用了全局变量 `DATA`，执行时要在 `exec` 的名字空间里提供它：

```python
DATA = {"persons": persons, "books": books}
ns = {"DATA": DATA}
exec(compile(code, "<generated>", "exec"), ns)
```

用这个版本重跑步骤 7，对比加速比的变化（需自行实测确认）。

### 8.8 题 8

**能保证**：两条执行路径在给定输入上产生相同的输出。它能高效抓出"代码生成逻辑写错"这类 bug——例如缩进错误导致代码块位置不对、谓词编译错误、连接顺序写反、变量覆盖出错。这类 bug 单独看某一方的输出很难发现，一对比就暴露。

**不能保证**：

- **正确性之外的性质**。性能退化了（生成的代码仍然正确但很慢），差异测试不会报错。
- **未被测试覆盖的路径**。差异测试只对跑过的查询有效。下面就是一个"通过了差异测试但仍然错误"的例子：

```python
class BadFilter(Filter):
    def compile(self, emit=None):
        # 只对形如 "attr < 常数" 的谓词做了改写，其他谓词原样输出
        if "<" not in self.pred:
            compiled = self.pred            # 忘了改写成 tup['...'] 形式
        else:
            compiled = re.sub("([a-zA-Z]+)", r"tup['\1']", self.pred)
        return self.children[0].compile(
            f"if {compiled}:\n    {self.indent_emit_(emit)}")
```

如果差异测试只跑了 `price < 10` 这一条谓词，这个实现会通过测试（它走了 `<` 分支，改写正确）。但一旦查询里出现 `price > 10` 或 `price == 10`，生成的代码就是 `if price > 10:`，执行时抛 `NameError` 或引用到错误的变量。

所以差异测试必须配合**谓词/查询模板的枚举**：至少覆盖 `<`、`>`、`==`、`!=`、`AND`、`OR`、字符串常量、函数调用这些组合。

## 九、扩展任务（选做）

### 9.1 更深的查询计划

把查询改成三表连接（`persons ⋈ books ⋈ orders`），或加上 `AND` 连接的复合谓词（`price < 10 and author != 'X'`），重跑步骤 7。预测加速比会变大还是变小？用实测验证。

### 9.2 实现 `Print` 与 `Collect` 汇算子

按 `Count` 的写法补上这两个：

```python
class Print(Operator):
    def interpret_next(self, tup):
        print(tuple(tup.values()))

    def compile(self):
        return "import pickle\n\n" + \
            self.children[0].compile("print(tuple(tup.values()))")
```

`Collect` 把结果收进 `result = list()`。用它们验证生成的代码与解释执行的逐行输出一致。

### 9.3 把代码生成换成 `ast` 实现

用 8.4 题里的 `Rewriter` 替换正则改写，并让 `compile()` 直接返回 `ast` 节点树而不是字符串。比较两种生成器的代码量与可维护性。

### 9.4 加上聚合

实现一个 `GroupBy` 算子（按 `author` 分组计数）。它在解释执行里要维护一个字典，在编译执行里会生成什么样的一段代码？实现并测速。

### 9.5 读源码

读 `system/query_processing/operators.py` 里 `Scan` / `Filter` / `SHJ` / `SemiJ` / `Print` / `Collect` / `Count` 的 `compile()`，与你自己的实现逐行对照。再读 `system/tests/test_code_gen.py`，看差异测试是怎么组织的。

### 9.6 阅读

- Neumann, *Efficiently Compiling Efficient Query Plans for Modern Hardware*, VLDB 2011。
- Kersten et al., *Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask*, PVLDB 2018。
- Boncz et al., *MonetDB/X100: Hyper-Pipelining Query Execution*, CIDR 2005。

## 十、常见错误与排查

| 现象 | 原因 | 处理 |
| --- | --- | --- |
| 生成的代码抛 `IndentationError` | 拼接时没调 `indent_emit_`，或缩进层数不对 | 检查每层 `compile()` 里的 `indent_emit_(emit, n)`，`n` 等于该层新增的嵌套层数 |
| 生成的代码抛 `NameError: name 'tup' is not defined` | `emit` 里的变量名与生成代码中放入作用域的变量名不一致 | 统一用 `tup`；`SHJ` 里用 `tup = tup \| tup2` 覆盖而不是新建变量 |
| 生成的代码抛 `NameError: name 'pickle' is not defined` | 汇算子的 `compile()` 忘了加 `import pickle` | 在 `Count` / `Print` / `Collect` 的 `compile()` 开头拼上 `"import pickle\n\n"` |
| `exec` 后取不到 `num_tuples` | 没给 `exec` 传名字空间字典 | `ns = {}; exec(bytecode, ns); print(ns["num_tuples"])` |
| 编译执行结果与解释执行不一致 | 缩进/变量覆盖/连接顺序三处之一写错 | 用步骤 4 打印源码人工核对；用 `sf=0.05` 的小规模先跑通 |
| `TypeError: unsupported operand type(s) for \|` | Python 版本低于 3.9 | 升级到 3.9+，或改成 `{**tup, **tup2}` |
| 谓词里的字符串常量被改写成 `tup['Alice']` | 正则改写不区分常量与属性名 | 改用 `ast` 模块做改写（见 8.4 题） |
| 编译执行比解释执行还慢 | 数据量太小，编译开销没被摊薄，或 `pickle.load` 占主导 | 增大 `N`；用步骤 8 拆开计时；改用 `Relation` 算子去掉反序列化开销 |
| 用子进程跑 `.pyc` 时耗时几十毫秒 | 子进程包含 Python 解释器启动开销 | 性能对比改用进程内 `exec`（步骤 5 的第一个版本） |
| `py_compile` 报 `doraise` 相关的语法错误 | 生成的代码本身有语法错误 | 先把 `print(code)` 的输出粘到 `.py` 文件里单独跑一遍 |
| 每次运行结果行数不同 | 数据生成用了随机且没固定种子 | 在生成数据前 `random.seed(42)`；两份数据用同一个种子 |
| `FileNotFoundError: persons.pkl` | 步骤 1 没跑，或工作目录不对 | 先跑步骤 1；确认 `.pkl` 生成在当前工作目录 |
| 计时波动大 | 后台进程干扰、只跑了 1 次 | 跑 5 次取中位数；关闭其他程序；用 `time.perf_counter()` |

## 附：本实验引用的文献与默认值

| 条目 | 出处 / 说明 |
| --- | --- |
| Volcano / 迭代器模型 | Graefe, *Volcano*, 1990；接口为 `open()` / `next()` / `close()`；push 模型由叶子驱动、元组向上推 |
| 以数据为中心的编译 | Neumann, *Efficiently Compiling Efficient Query Plans for Modern Hardware*, VLDB 2011（用 LLVM 编译，集成于 HyPer） |
| 向量化 | Boncz et al., MonetDB/X100, CIDR 2005 |
| 向量化 vs 编译 | Kersten et al., PVLDB 2018：向量化更擅长隐藏 cache miss 延迟；以数据为中心的编译所需 CPU 指令更少，更适合 cache-resident 负载 |
| PostgreSQL JIT 默认值 | `jit_above_cost` = 100000；`jit_inline_above_cost` = 500000；`jit_optimize_above_cost` = 500000 |
| PostgreSQL 官方立场 | JIT 主要有利于长运行、CPU 密集的分析型查询；短查询编译开销常大于收益 |