实验 10：共享扫描（Shared Scan）

> 三个查询都要扫同一张 40 万行的表，是扫三遍，还是扫一遍把三个查询的结果一起挑出来？

一、实验目标

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

1. 说出全表扫描（full table scan）的代价构成，并区分**读取元组次数**与**墙钟时间**两个不同的指标。
2. 定义选择性（selectivity），并用它估算扫描结果的大小。
3. 实现四种扫描做法：每查询各扫一遍、共享扫描 + 每个查询一份结果列表、共享扫描 + 单个列表打标签。
4. 用计数器实证"共享扫描把 I/O 量降到 `1/Q`"（Q 是查询个数）。
5. 解释本实验最反直觉的现象：**在本机 Python 实现下，共享扫描的墙钟时间未必更短，但它仍然有意义**。
6. 说明真实数据库中 I/O 与 CPU 的相对地位，以及为什么真实系统会采用共享扫描。

二、预备知识

2.1 全表扫描

关系 `stuff` 有 `n` 条元组。查询：

```sql
SELECT * FROM stuff WHERE a = 7
```

如果没有索引，数据库只能把每一条元组读出来，逐个检查谓词 `a = 7`。这就是全表扫描。

```
元组 0 读 → 检查 → 丢弃
元组 1 读 → 检查 → 丢弃
元组 2 读 → 检查 → 命中 → 加入结果
...
元组 n-1 读 → 检查 → 丢弃
```

读取元组次数 = `n`，与谓词命中多少无关。

2.2 选择性（selectivity）

选择性 σ（sigma）是一个无量纲的比例，取值在 `[0, 1]` 之间：

```
σ_q = |结果_q| / n
```

含义：查询 `q` 命中的元组占全表的比例。`σ_q` 越小，谓词越"挑剔"。

本实验：`a` 与 `b` 都在 `[0, 100]` 上均匀取值（共 101 个可能值），所以 `a = 7` 的期望选择性是：

```
σ = 1 / 101 ≈ 0.0099
```

`n = 400,000` 时，期望命中条数：

```
400,000 × (1/101) ≈ 3,960
```

三个查询的实测结果都在 3,900 ~ 4,100 之间，与估算吻合。

2.3 为什么 I/O 才是真实数据库的瓶颈

数据库的表在磁盘上，读取一个页面（page，通常 4 KB ~ 16 KB）的成本远大于在内存里做一次整数比较。

一个简化的代价模型：

```
Cost(扫描) = P × (t_seek + t_transfer) + n × t_cpu
```

符号含义与单位：

| 符号 | 含义 | 典型量级（需自行实测确认） |
| --- | --- | --- |
| `P` | 扫描的页面数 | 个 |
| `t_seek` | 单次寻道 + 旋转延迟 | 毫秒级（机械盘）/ 微秒级（SSD） |
| `t_transfer` | 传输一页的时间 | 微秒级 |
| `n` | 元组条数 | 条 |
| `t_cpu` | 每元组 CPU 处理时间 | 纳秒 ~ 微秒级 |

数量级对比：`t_seek` 比 `t_cpu` 大 **3 到 6 个数量级**。所以只要 `P` 足够大，第一项完全主导，第二项可以忽略。

**这正是共享扫描的立论基础**：如果能让 `P` 从"扫 Q 遍"降到"扫 1 遍"，第一项就降到 `1/Q`，哪怕第二项（CPU）稍微变大，总成本仍然下降。

2.4 缓冲池（buffer pool）

真实数据库不会真的读 Q 遍磁盘。它在内存里有一块缓冲池，第一遍扫描把页面读进来，第二遍可能命中缓存。

这是否让共享扫描变得没必要？不是。原因：

1. 表往往远大于缓冲池，第二遍扫描时第一遍的页面早就被淘汰了。
2. 即便全部命中缓存，扫描本身仍然要把 `n` 条元组从页面里解析（deserialize）成内存对象，这部分 CPU 开销也不小。
3. 缓冲池命中率是概率性的，不能作为优化的依据。

共享扫描的价值在于：**确定性**地把读取量降到 `1/Q`，而不是指望运气。

2.5 共享扫描的三种组织方式

设同时有 `Q` 个查询 `q₁, ..., q_Q` 要扫同一张表。

```
做法一：每查询各扫一遍（independent scan）
for q in queries:
for tup in table: ← 扫 Q 遍
if pred_q(tup): result_q.append(tup)

做法二：共享扫描 + 每个查询一份结果列表
results = {q: [] for q in queries}
for tup in table: ← 只扫 1 遍
for q in queries:
if pred_q(tup): results[q].append(tup)

做法三：共享扫描 + 单个列表 + 打标签（tagging）
for tup in table: ← 只扫 1 遍
tags = [q for q in queries if pred_q(tup)]
if tags: result.append(Result(tup, tags))
```

做法三与做法二的差别在**结果的存储形态**：

• 做法二：一条元组若同时命中 2 个查询，会被存 2 份。

• 做法三：一条元组只存 1 份，用标签列表指明它属于哪些查询。

当查询之间结果重叠度高时，做法三节省内存；重叠度低时，做法三还要额外存标签，反而更占。

三、实验原理

3.1 读取量的对比

设 `Q` 为查询个数，`n` 为元组条数。

| 做法 | 读取元组次数 | 谓词求值次数 | 结果列表条目数 |
| --- | ---: | ---: | ---: |
| 一、独立扫描 | `n · Q` | `n · Q` | `Σ_q \|结果_q\|` |
| 二、共享扫描 + 分列表 | `n` | `n · Q` | `Σ_q \|结果_q\|` |
| 三、共享扫描 + 打标签 | `n` | `n · Q` | `\|∪_q 结果_q\|` |

关键观察：

• **读取元组次数**：从 `n·Q` 降到 `n`，即降到 `1/Q`。这是共享扫描的全部收益来源。

• **谓词求值次数**：三种做法**完全一样**，都是 `n·Q`。共享扫描一点都没省 CPU。

• **结果条目数**：做法三只在有重叠时才更省，因为 `|∪_q 结果_q| ≤ Σ_q |结果_q|`，等号成立于各查询结果互不相交时。

本实验 `Q = 3`、`n = 400,000`：

```
做法一读取量 = 400,000 × 3 = 1,200,000
做法二/三读取量 = 400,000
比值 = 1,200,000 / 400,000 = 3 ← 正好等于 Q
```

3.2 本实验的反直觉现象（必须理解）

在**纯 Python** 实现下测墙钟时间，你会看到共享扫描**不比**独立扫描快，甚至更慢。原因：

1. **独立扫描的内层循环极简**：`for tup in data: if tup.a == 7: ...`，每元组一次属性访问 + 一次比较。
2. **共享扫描的内层循环多了两层**：`for tup in data: for q in queries: ...`，而且要把谓词表达成 `el.__dict__[attr] == const` 这样的**动态属性查找**，每元组要查 `Q` 次字典。
3. 在 Python 里，一次 `obj.__dict__[key]` 加一次函数调用的开销，远大于一次直接的属性比较。于是共享扫描"省掉的读取"根本抵不过"多出来的动态查找"。

**但结论仍然是共享扫描有意义**，因为：

• 本实验的"读取"是遍历一个 Python 列表，成本极低，不能代表数据库的 I/O。真实数据库的"读取一次元组"包含页面调度、磁盘/网络传输、元组解析，成本高几个数量级。

• 本实验实测：共享扫描把**读取元组次数**从 1,200,000 降到 400,000，即 **1/3**。这个收益是确定性的、与实现语言无关的。

• 真实系统里 I/O 主导总成本，所以节省 `2/3` 的 I/O 是决定性的。

一句话：**看指标要看对，本实验正确的观测指标是"读取元组次数"，不是墙钟时间。**

3.3 怎么让共享扫描在 CPU 上也赢

想让共享扫描在 Python 里也快，办法是消除动态查找：

1. **把谓词编译成闭包**：`preds = [(lambda t, k=7: t.a == k) for ...]`，避免 `__dict__[attr]`。
2. **用实验 09 的代码生成**：为每个查询生成专用代码，把 `Q` 个谓词全部内联进同一个循环体。这样每元组仍是 `Q` 次比较，但没有函数调用与字典查找。
3. **用位图标签**：把 `Q` 个布尔结果打包成一个整数的 `Q` 个位，用位运算一次算出标签。
4. **按属性分组**：把同一属性上的多个等值谓词合并成一次字典查找（例如 `b=32` 与 `b=1` 都查 `b`，可以一次取值比较两次）。

扩展任务 9.2、9.3 会做其中两项。

3.4 参考图件

| 图件 | 内容 |
| --- | --- |
| `../figures/fig_shared_scan.png` | 独立扫描与共享扫描的读取元组次数对比 |

四、实验环境与准备

4.1 环境要求

| 项目 | 要求 |
| --- | --- |
| Python | 3.10 及以上 |
| 必装库 | 无，只用标准库 `random` / `dataclasses` / `time` / `typing` |
| 选装库 | `matplotlib`（步骤 7 画图） |
| 参考实现 | `notebooks/Shared-Scan.ipynb` |

4.2 数据

`n = 400,000` 条元组，每条有两个整数属性 `a` 与 `b`，都在 `[0, 100]` 上均匀取值。

查询有三个：

```sql
SELECT * FROM stuff WHERE a = 7; -- q1
SELECT * FROM stuff WHERE b = 32; -- q2
SELECT * FROM stuff WHERE b = 1; -- q3
```

> 关于结果条数：`a`、`b` 各有 101 个可能取值，所以每个查询的期望命中数是 `400,000 / 101 ≈ 3,960`。本机某次实测得到 `[4006, 3992, 3927]`；本指导书代码用 `random.seed(42)` 时给出 `[3982, 3979, 3940]`。两者都在期望值附近的小范围内波动，属正常抽样误差。**你的数字以实际运行为准**，重要的是三个算法给出的结果彼此一致。

五、实验步骤

步骤 1：生成数据

```python
import random
from dataclasses import dataclass
from typing import Dict, List

n = 400_000

@dataclass
class Stuff:
"""一条元组，两个整数属性。"""
a: int
b: int

random.seed(42)
data: List[Stuff] = [
Stuff(random.randint(0, 100), random.randint(0, 100))
for _ in range(n)
]

print("元组条数:", len(data))
print("前 5 条:", data[:5])
```

步骤 2：定义查询与读取计数器

计数器是本实验的核心观测工具。每次"从表里取出一条元组"就加一。

```python
tuples_read = 0 # 全局计数器：读取了多少条元组

def reset_counter():
global tuples_read
tuples_read = 0

queries_dict: Dict[str, Dict[str, object]] = {
"q1": {"attribute": "a", "constant": 7},
"q2": {"attribute": "b", "constant": 32},
"q3": {"attribute": "b", "constant": 1},
}
```

步骤 3：算法一——每查询各扫一遍

```python
def scan(data: List[Stuff], attribute: str, constant: int) -> List[Stuff]:
"""扫描全表，返回属性等于常量的所有元组。"""
global tuples_read
res: List[Stuff] = []
for el in data:
tuples_read += 1 # 每读一条元组计一次
if el.__dict__[attribute] == constant:
res.append(el)
return res

reset_counter()
result_independent: Dict[str, List[Stuff]] = {
key: scan(data, entry["attribute"], entry["constant"])
for key, entry in queries_dict.items()
}
print("读取元组次数:", tuples_read)
print("各查询结果条数:", {k: len(v) for k, v in result_independent.items()})
```

预期输出（`random.seed(42)`）：

```
读取元组次数: 1200000
各查询结果条数: {'q1': 3982, 'q2': 3979, 'q3': 3940}
```

`1,200,000 = 400,000 × 3`，正好是 `n · Q`。

步骤 4：算法二——共享扫描，每个查询一份结果列表

```python
def shared_scan(data: List[Stuff],
queries_dict: Dict[str, Dict[str, object]]
) -> Dict[str, List[Stuff]]:
"""只扫一遍，为每个查询维护一份结果列表。"""
global tuples_read
res: Dict[str, List[Stuff]] = {k: [] for k in queries_dict}
for el in data:
tuples_read += 1 # 整表只扫一遍
for key, entry in queries_dict.items():
if el.__dict__[entry["attribute"]] == entry["constant"]:
res[key].append(el)
return res

reset_counter()
result_shared = shared_scan(data, queries_dict)
print("读取元组次数:", tuples_read)
print("各查询结果条数:", {k: len(v) for k, v in result_shared.items()})
```

预期输出：

```
读取元组次数: 400000
各查询结果条数: {'q1': 3982, 'q2': 3979, 'q3': 3940}
```

读取量降到 `1/3`，结果条数**完全不变**。

步骤 5：算法三——共享扫描，单个列表 + 打标签

```python
@dataclass
class Result:
"""一条结果元组，附一个标签列表，指明它属于哪些查询。"""
result: Stuff
relevant_for_queries: List[str]

def shared_scan_with_tagging(data: List[Stuff],
queries_dict: Dict[str, Dict[str, object]]
) -> List[Result]:
"""只扫一遍，命中的元组只存一份，用标签标明归属。"""
global tuples_read
res: List[Result] = []
for el in data:
tuples_read += 1
tags: List[str] = []
for key, entry in queries_dict.items():
if el.__dict__[entry["attribute"]] == entry["constant"]:
tags.append(key)
if len(tags) > 0: # 只有至少命中一个查询才存
res.append(Result(el, tags))
return res

def join_result_list_with_bit_lists(tagged: List[Result]
) -> Dict[str, List[Stuff]]:
"""把打标签的结果还原成 {查询: 结果列表} 的字典，便于对比。"""
out: Dict[str, List[Stuff]] = {}
for item in tagged:
for key in item.relevant_for_queries:
out.setdefault(key, []).append(item.result)
return out

reset_counter()
tagged = shared_scan_with_tagging(data, queries_dict)
result_tagged = join_result_list_with_bit_lists(tagged)
print("读取元组次数:", tuples_read)
print("结果列表条目数:", len(tagged))
print("各查询结果条数:", {k: len(v) for k, v in result_tagged.items()})
```

预期输出：

```
读取元组次数: 400000
结果列表条目数: 11825
各查询结果条数: {'q1': 3982, 'q2': 3979, 'q3': 3940}
```

`11825` 是三个查询结果**并集**的大小；而 `3982 + 3979 + 3940 = 11901` 是"分列表"版本的条目总数。两者之差 `11901 − 11825 = 76`，说明有 76 条元组同时命中了两个查询。

估算验证：`a` 与 `b` 独立，所以

```
P(a=7 且 b=32) = (1/101) × (1/101) ≈ 9.8 × 10⁻⁵
P(a=7 且 b=1) = (1/101) × (1/101) ≈ 9.8 × 10⁻⁵
期望重叠条数 = 400,000 × 2 × 9.8 × 10⁻⁵ ≈ 78
```

实测 76，与估算吻合。（`q2` 与 `q3` 都作用在 `b` 上，`b=32` 与 `b=1` 互斥，所以它们之间没有重叠。）

步骤 6：三种算法的结果一致性

```python
def sort_key(lst):
"""把结果列表转成可比较的规范形式（按 a、b 排序）。"""
return sorted((t.a, t.b) for t in lst)

ok = True
for key in queries_dict:
a = sort_key(result_independent[key])
b = sort_key(result_shared[key])
c = sort_key(result_tagged[key])
same = (a == b == c)
ok = ok and same
print(f"{key}: 独立={len(a)} 共享={len(b)} 标签={len(c)} 一致={same}")

print("三种算法结果完全一致:", ok)
```

预期：三个查询都是 `一致=True`。

> 为什么比较前要排序？共享扫描的内层是按 `queries_dict` 的顺序遍历，而独立扫描是按查询逐个执行，产生结果列表的**顺序**可能不同；但集合内容必须相同。关系是无序集合，只有排好序才能逐项比较。

步骤 7：测量墙钟时间（会看到反直觉的结果）

```python
import time

def measure(fn, repeat=5):
out = []
for _ in range(repeat):
t0 = time.perf_counter()
fn()
out.append((time.perf_counter() - t0) * 1000)
return sorted(out)[len(out) // 2]

t_ind = measure(lambda: {k: scan(data, e["attribute"], e["constant"])
for k, e in queries_dict.items()})
t_sha = measure(lambda: shared_scan(data, queries_dict))
t_tag = measure(lambda: shared_scan_with_tagging(data, queries_dict))

print(f"独立扫描 {t_ind:8.2f} ms")
print(f"共享扫描 {t_sha:8.2f} ms")
print(f"共享扫描+标签 {t_tag:8.2f} ms")
```

请把结果填进 6.3 表。在多数 Python 环境里你会看到 `t_sha` 与 `t_ind` 接近，甚至 `t_sha > t_ind`。**这是正常的**，原因见 3.2 节。

把两种指标并排写出来，你就能看清矛盾所在：

```python
print(f"独立扫描: 读取 {400_000 * 3:,} 条，耗时 {t_ind:.2f} ms")
print(f"共享扫描: 读取 {400_000:,} 条，耗时 {t_sha:.2f} ms")
print(f"读取量降到 1/3，但耗时比为 {t_sha / t_ind:.2f}")
```

步骤 8：让 I/O 占主导，重做对比

把"读一条元组"人为变贵——模拟一次真实的 I/O（例如加一段微小的固定开销），再看共享扫描是否反超。

```python
IO_COST_PER_TUPLE = 0.0 # 每条元组的模拟 I/O 开销（秒）

def simulated_io():
"""模拟读一条元组的 I/O 开销。用一段不会被优化掉的计算占位。"""
if IO_COST_PER_TUPLE <= 0:
return
deadline = time.perf_counter() + IO_COST_PER_TUPLE
while time.perf_counter() < deadline:
pass

def scan_io(data, attribute, constant):
res = []
for el in data:
simulated_io()
if el.__dict__[attribute] == constant:
res.append(el)
return res

def shared_scan_io(data, queries_dict):
res = {k: [] for k in queries_dict}
for el in data:
simulated_io()
for key, entry in queries_dict.items():
if el.__dict__[entry["attribute"]] == entry["constant"]:
res[key].append(el)
return res

for io_cost in (0.0, 2e-7, 1e-6):
IO_COST_PER_TUPLE = io_cost
ti = measure(lambda: {k: scan_io(data, e["attribute"], e["constant"])
for k, e in queries_dict.items()}, repeat=3)
ts = measure(lambda: shared_scan_io(data, queries_dict), repeat=3)
print(f"每条元组 I/O 开销 {io_cost * 1e6:5.2f} μs -> "
f"独立 {ti:8.1f} ms 共享 {ts:8.1f} ms 共享/独立 = {ts / ti:.2f}")
```

> 说明：`IO_COST_PER_TUPLE` 是一个模块级全局变量，改它就能调节模拟的 I/O 成本。数值 `2e-7` 秒 = 0.2 微秒，`1e-6` 秒 = 1 微秒。选多大的值、以及你机器上共享扫描在哪个值上反超，需自行实测确认。

本环境实测的一组结果：

```
每条元组 I/O 开销 0.00 μs -> 独立 168.5 ms 共享 245.1 ms 共享/独立 = 1.46
每条元组 I/O 开销 0.20 μs -> 独立 640.4 ms 共享 312.2 ms 共享/独立 = 0.49
每条元组 I/O 开销 1.00 μs -> 独立 1604.7 ms 共享 720.0 ms 共享/独立 = 0.45
```

读这张表：

• `io_cost = 0` 时比值 **> 1**：纯 CPU 场景，共享扫描更慢，与 3.2 节一致。

• `io_cost` 增大后比值降到 **远小于 1**：I/O 开始主导，共享扫描反超。

• 比值没有立刻降到 `1/3`，因为 CPU 那部分（`n·Q·t_cpu`）在两种做法里是**一样的**，无法被摊掉。继续增大 `io_cost`（例如 10 μs），比值会进一步趋近 `1/3`——这是理论下界。

这就是"真实数据库里 I/O 主导，所以共享扫描有意义"的直接演示。**你的数字需自行实测确认**，重点看比值随 `io_cost` 单调下降这个趋势。

步骤 9：单元测试（可选）

用多组随机查询做端到端一致性测试：

```python
import unittest

class SharedScanTest(unittest.TestCase):

def test_scans_end_to_end(self):
rnd = random.Random(7)
test_data = [Stuff(rnd.randint(0, 20), rnd.randint(0, 20))
for _ in range(2000)]
for _ in range(5):
qs = {f"q{i}": {"attribute": "a" if rnd.random() < 0.5 else "b",
"constant": rnd.randint(0, 20)}
for i in range(10)}
r1 = {k: scan(test_data, e["attribute"], e["constant"])
for k, e in qs.items()}
r2 = shared_scan(test_data, qs)
r3 = join_result_list_with_bit_lists(
shared_scan_with_tagging(test_data, qs))
for k in qs:
self.assertEqual(sort_key(r1[k]), sort_key(r2[k]))
self.assertEqual(sort_key(r1[k]), sort_key(r3[k]))

unittest.main(argv=["ignored", "-v"], exit=False)
```

六、观测记录表

6.1 基本信息

| 项目 | 值 |
| --- | --- |
| 元组条数 `n` | 400,000 |
| 查询个数 `Q` | 3 |
| 属性 `a` / `b` 的取值范围 | 0 ~ 100（共 101 个值） |
| 每个查询的理论期望命中数 | `400,000 / 101 ≈ 3,960` |

6.2 读取元组次数（核心指标）

| 做法 | 理论值 | 实测值 | 相对独立扫描的倍数 |
| --- | ---: | ---: | ---: |
| 独立扫描（扫 3 遍） | `n·Q = 1,200,000` | | 1.00 |
| 共享扫描（分列表） | `n = 400,000` | | |
| 共享扫描（打标签） | `n = 400,000` | | |

本机实测：独立扫描读取 **1,200,000** 次，共享扫描读取 **400,000** 次，正好是 `1/3`。

6.3 墙钟时间（会让人意外的指标）

| 做法 | 实测 ms | 你的实测值 | 相对独立扫描的倍数 |
| --- | ---: | ---: | ---: |
| 独立扫描 | | | 1.00 |
| 共享扫描（分列表） | | | |
| 共享扫描（打标签） | | | |

结论填写：

```
共享扫描的墙钟时间 ______（更短 / 接近 / 更长），
但读取元组次数降到 ______。
原因是：______________________________________________
```

6.4 结果一致性

| 查询 | 独立扫描条数 | 共享扫描条数 | 打标签条数 | 三者一致 |
| --- | ---: | ---: | ---: | --- |
| q1 (`a=7`) | | | | |
| q2 (`b=32`) | | | | |
| q3 (`b=1`) | | | | |

本机实测的条数为 `[4006, 3992, 3927]`；本指导书代码（`seed=42`）给出 `[3982, 3979, 3940]`。三种算法给出的结果**完全一致**。

6.5 打标签版本的内存占用

| 指标 | 值 | 说明 |
| --- | ---: | --- |
| `Σ_q \|结果_q\|` | | 分列表版本的条目总数 |
| `\|∪_q 结果_q\|` | | 打标签版本的条目总数 |
| 两者之差 | | 等于"被多个查询共同命中的元组"的重复计数 |

6.6 模拟 I/O 开销的影响

| 每条元组 I/O 开销 | 独立扫描 ms | 共享扫描 ms | 共享/独立 |
| --- | ---: | ---: | ---: |
| 0.0 μs | | | |
| 0.2 μs | | | |
| 1.0 μs | | | |
| 你测出的反超点 | | | |

七、思考题

1. 本实验中，三个查询的选择性各是多少？用实测条数算出来（保留 4 位小数）。
2. 为什么共享扫描把读取元组次数降到 `1/Q`，但**谓词求值次数一点没省**？请用公式说明。
3. 打标签版本（算法三）在什么情况下比分列表版本（算法二）更省内存？什么情况下更费？给出判据。
4. 本实验测出共享扫描的墙钟时间不比独立扫描短。请列出至少三条具体原因。
5. 既然如此，为什么真实数据库仍然采用共享扫描？请结合 2.3 节的代价公式说明。
6. 如果三个查询的选择性分别是 0.5、0.5、0.5（各命中一半），共享扫描还划算吗？请分别就"读取量"和"结果内存"两个维度讨论。
7. 把共享扫描与实验 09 的代码生成结合起来会怎样？描述生成的代码长什么样。
8. 如果这 `Q` 个查询不是同时到达，而是在扫描过程中陆续到达（第 100,000 条时才来第 4 个查询），共享扫描该怎么处理？这带来什么新问题？
9. `scan()` 用 `el.__dict__[attribute]` 做动态属性查找。改成什么样能让它更快？给出代码并说明代价。

八、思考题答案与解析

8.1 题 1

选择性定义 `σ_q = |结果_q| / n`，`n = 400,000`。

用本指导书代码（`seed=42`）的实测条数 `[3982, 3979, 3940]`：

```
σ(q1) = 3982 / 400000 = 0.0099550
σ(q2) = 3979 / 400000 = 0.0099475
σ(q3) = 3940 / 400000 = 0.0098500
```

用本机另一次实测 `[4006, 3992, 3927]`：

```
σ(q1) = 4006 / 400000 = 0.0100150
σ(q2) = 3992 / 400000 = 0.0099800
σ(q3) = 3927 / 400000 = 0.0098175
```

理论期望 `1/101 ≈ 0.0099010`。两组实测都在它附近波动，偏差来自随机抽样。

用代码直接算：

```python
for k, v in result_independent.items():
print(k, len(v), round(len(v) / n, 6))
```

8.2 题 2

读取元组次数：

• 独立扫描：外层 `Q` 次，每次内层 `n` 次 → `n · Q`。

• 共享扫描：只有一层 `n` 次的循环 → `n`。

比值 `n / (n·Q) = 1/Q`。

谓词求值次数：

• 独立扫描：每条元组对每个查询判一次 → `n · Q`。

• 共享扫描：每条元组在内层 `for q in queries` 里对每个查询判一次 → `n · Q`。

**完全一样**。因为"要判断这条元组属于哪些查询"这个工作量，与"分几遍扫"无关：`Q` 个查询 × `n` 条元组 = `n·Q` 次判断，这是信息论意义上的下界（除非用索引或谓词间的蕴含关系做剪枝）。

所以共享扫描省的是**数据读取**，不是**计算**。理解这一点，就能理解为什么在 CPU 主导的场景（本实验的 Python 实现）里它不快。

8.3 题 3

记：

• `S = Σ_q |结果_q|`：分列表版本的条目总数（含重复）。

• `U = |∪_q 结果_q|`：打标签版本的条目总数（去重）。

• 每条标签的开销为 `c`（一个字符串引用的列表）。

分列表版本占用 ≈ `S`。
打标签版本占用 ≈ `U + U·c`（每条元组一份，外加标签列表）。

判据：

• **更省**：当查询之间结果重叠大，即 `U << S`。极端情况：三个查询结果完全相同，`U = S/3`，打标签版本省 `2/3`。

• **更费**：当查询结果几乎不相交，`U ≈ S`，此时打标签版本还要多付 `U·c` 的标签开销，反而更占。

• 临界条件：`U · (1 + c) < S`，即重叠度 `S/U > 1 + c`。

本实验实测：`S = 11901`，`U = 11825`，`S/U ≈ 1.0064`，远小于 `1 + c`。所以**本实验里打标签版本的内存优势微乎其微**，因为三个查询分别作用在 `a` 和 `b` 两个不同属性上，结果几乎不相交（只有 76 条元组同时命中）。

想看到打标签版本的优势，构造重叠的查询集合，例如 `a=7`、`a=7`、`a=7`（三个相同的查询），此时 `S = 3 × 3982 = 11946`，`U = 3982`，比值 3.0，省 `2/3`。

8.4 题 4

至少四条：

1. **动态属性查找。** 共享扫描的内层是 `el.__dict__[entry["attribute"]] == entry["constant"]`，每条元组每个查询要做三次字典查找：`entry["attribute"]` 一次、`el.__dict__[...]` 一次、`entry["constant"]` 一次。独立扫描里 `el.a == 7` 是一次直接属性访问加一个字面常量。
2. **多一层循环。** 共享扫描是嵌套两层 `for`，内层 `for key, entry in queries_dict.items()` 每元组要建立一次迭代器并做一次元组解包。
3. **读取本身太便宜。** 本实验的"读取一条元组"就是遍历 Python 列表取一个元素，成本约几十纳秒；而共享扫描多出来的动态查找成本是同等量级的几倍。省下的读取根本抵不过多出的查找。
4. **结果 append 的对象不同。** 打标签版本还要为每条命中元组新建一个 `Result` 对象并建一个标签列表，多两次对象分配。分列表版本虽然不用建新对象，但内层循环本身的开销已经吃掉了收益。

用代码验证第 1 点：

```python
import timeit

el = data[0]
entry = queries_dict["q1"]
number = 300_000

for label, fn in [
("直接属性 + 字面常量 ", lambda: el.a == 7),
("__dict__ + 字面常量 ", lambda: el.__dict__["a"] == 7),
("完整动态查找 ", lambda: el.__dict__[entry["attribute"]]
== entry["constant"]),
]:
t = timeit.timeit(fn, number=number)
print(f"{label} {t / number * 1e9:6.1f} ns/次")
```

在本环境（CPython 3.13 + Windows）实测，三者依次约为 43 ns、72 ns、95 ns 每次，完整动态查找约为直接访问的 2 倍多。**你的数字需自行实测确认**，重点看相对关系。

注意：第一次调用 `timeit` 常带有预热效应，若结果反常（例如动态比直接还快），把 `number` 调大或调换测量顺序再试。

8.5 题 5

把 2.3 节的代价公式写开：

```
Cost(独立扫描) = Q · P · (t_seek + t_transfer) + n·Q · t_cpu
Cost(共享扫描) = 1 · P · (t_seek + t_transfer) + n·Q · t_cpu
```

两式相减：

```
Cost(独立) − Cost(共享) = (Q − 1) · P · (t_seek + t_transfer) > 0
```

**第二项（CPU）完全相同，被抵消了。** 也就是说：只要页面数 `P > 0`，共享扫描一定不亏；`P` 越大越赚。

而 `t_seek + t_transfer` 比 `t_cpu` 大 3 到 6 个数量级，所以第一项的节省是决定性的。

本实验之所以看不出这个优势，是因为本实验的"读取"没有 `(t_seek + t_transfer)` 这一项——数据已经在内存里了。步骤 8 人为加上这一项后，就能看到共享扫描反超。

这也解释了为什么共享扫描在真实系统（MySQL、PostgreSQL、SQL Server 的 scan sharing / QPop 类优化）里是标准配置，而在内存型教学 DBMS 里看不出效果。

8.6 题 6

设 `n = 1,000,000`，`Q = 3`，三个查询各命中一半（`σ = 0.5`），且结果相互独立随机。

**读取量维度**：

• 独立扫描：`n·Q = 3,000,000`。

• 共享扫描：`n = 1,000,000`。

• 读取量仍然降到 `1/3`。**共享扫描在读取维度上永远划算**，与选择性无关——因为选择性只影响"输出多少"，不影响"要读多少"。

**结果内存维度**：

• 分列表版本：`S = 3 × 500,000 = 1,500,000` 个元组引用。

• 打标签版本：`U = |∪|`。三个各占一半的随机集合，并集比例为 `1 − (1−0.5)³ = 1 − 0.125 = 0.875`，即 `U = 875,000`。

• 比值 `S/U = 1,500,000 / 875,000 ≈ 1.71`。此时打标签版本明显更省。

结论：**选择性越高（结果越大、重叠越多），打标签版本的内存优势越明显；选择性越低，两种版本内存接近，分列表版本反而更简单。**

另外要注意：选择性高也意味着结果总量接近 `n`，此时真正的问题变成"结果太大放不下"，共享扫描省下的 I/O 收益会被结果物化的开销吃掉。真实系统在这种情况下会考虑流水线执行而非物化。

8.7 题 7

把 `Q` 个谓词全部内联进同一个循环体。生成的代码大致是：

```python
result_q1 = list()
result_q2 = list()
result_q3 = list()
for tup in data:
if tup.a == 7:
result_q1.append(tup)
if tup.b == 32:
result_q2.append(tup)
if tup.b == 1:
result_q3.append(tup)
```

对比解释执行：

• 没有 `queries_dict` 的字典查找，常量 `7`、`32`、`1` 都是字面量；

• 没有 `el.__dict__[...]` 的动态查找，`tup.a` 是编译期确定的属性访问；

• 没有 `for q in queries` 这一层循环，`Q` 个 `if` 被展开。

这正是实验 09 里 `compile(emit)` 的套路：把父算子的代码片段往下传，`Filter` 把自己的谓词包成一个 `if`。多个查询就是多个 sink，各自把 `result_qN.append(tup)` 作为 `emit` 传下去，最终融合成一个循环。

按这条路走，共享扫描在 CPU 上也能真正赢过独立扫描。扩展任务 9.3 就做这件事。

8.8 题 8

这就是所谓的**动态共享扫描 / QPop** 问题。三种处理策略：

| 策略 | 做法 | 代价 | 问题 |
| --- | --- | --- | --- |
| 不加入 | 新查询等下一轮扫描 | 延迟高 | 简单，但要等很久 |
| 立即加入 | 新查询从当前位置开始参与，只拿到后半段结果 | 结果不完整 | 必须由上层补扫前 `k` 条 |
| 回绕补扫 | 新查询加入后，扫描到表尾再回头补扫前 `k` 条 | 多读 `k` 条 | 需要记住起点，实现复杂 |

带来的新问题：

1. **结果不完整**是最难处理的：调用者拿到的是"部分结果"，需要额外的机制（补扫、或声明只返回部分）来保证语义正确。
2. **谓词集合动态变化**：如果查询可以在扫描中途加入或退出，代码生成就不能在扫描开始前一次性完成，需要支持增量重编译或回退到解释执行。
3. **公平性**：晚到的查询只享受了部分共享，如何计费/调度是调度器层面的问题。
4. **事务隔离**：不同查询可能在不同的快照（snapshot）上跑，能否共享扫描取决于 MVCC 版本是否一致。

真实系统（如 QPop）会估算"新查询加入的收益 vs 补扫的代价"，动态决定是否加入。

8.9 题 9

改成**编译期绑定属性的闭包**：

```python
def make_pred(attribute: str, constant: int):
"""返回一个绑定了属性名与常量的谓词闭包。"""
if attribute == "a":
return lambda el: el.a == constant
if attribute == "b":
return lambda el: el.b == constant
raise ValueError("unknown attribute: " + attribute)

def scan_fast(data, pred):
res = []
for el in data:
if pred(el):
res.append(el)
return res

preds = {k: make_pred(e["attribute"], e["constant"])
for k, e in queries_dict.items()}
result_fast = {k: scan_fast(data, p) for k, p in preds.items()}
```

为什么更快：属性名 `attribute` 在 `make_pred` 里被"固化"成 `el.a` 或 `el.b` 这种直接访问，循环里不再查字典；`constant` 变成闭包里的局部变量，比字典查找快。

**代价**：

1. 要预先枚举所有可能的属性名（上面的 `if attribute == "a"`），属性多了就难维护。可以用 `operator.attrgetter(attribute)` 自动生成一次 getter：

```python
from operator import attrgetter

def make_pred2(attribute: str, constant: int):
get = attrgetter(attribute) # 只构造一次
return lambda el: get(el) == constant
```

`attrgetter` 是 C 实现，比 `el.__dict__[attribute]` 快，但仍然是一次函数调用。

2. 闭包本身是一次 Python 函数调用，仍有调用开销。要彻底消除，只能上代码生成（见 8.7 题）。
3. 牺牲了灵活性：`make_pred` 只支持已知的属性名，动态属性（例如 schema 变更）需要重建闭包。

九、扩展任务（选做）

9.1 改变查询个数 Q

把 `Q` 从 3 改成 10、50，重跑步骤 3–5，验证"读取量比值恒等于 `Q`"。同时观察墙钟时间比值如何变化——`Q` 越大，共享扫描的 CPU 劣势越明显（内层循环变长），但读取优势也越大。

9.2 用位图标签

把标签列表换成一个整数，第 `i` 位表示是否命中第 `i` 个查询：

```python
def shared_scan_bitmap(data, queries):
"""queries: [(attribute, constant), ...]，返回 [(tuple, bitmask), ...]"""
res = []
for el in data:
mask = 0
for i, (attr, const) in enumerate(queries):
if el.__dict__[attr] == const:
mask |= (1 << i)
if mask:
res.append((el, mask))
return res

def decode_bitmap(tagged, nq):
out = {i: [] for i in range(nq)}
for el, mask in tagged:
for i in range(nq):
if mask & (1 << i):
out[i].append(el)
return out
```

比较它与原版打标签实现的内存占用（`sys.getsizeof`）与耗时。位图版本在 `Q ≤ 64` 时打包成一个整数，标签开销极小。

9.3 用代码生成融合多个谓词

按 8.7 题的思路，写一个 `compile_shared_scan(queries)`，生成源码后 `exec`：

```python
def compile_shared_scan(queries):
lines = ["def run(data):"]
for i in range(len(queries)):
lines.append(f" r{i} = list()")
lines.append(" for tup in data:")
for i, (attr, const) in enumerate(queries):
lines.append(f" if tup.{attr} == {const}:")
lines.append(f" r{i}.append(tup)")
lines.append(" return [" + ", ".join(f"r{i}" for i in range(len(queries))) + "]")
return "\n".join(lines)

src = compile_shared_scan([("a", 7), ("b", 32), ("b", 1)])
print(src)
ns = {}
exec(src, ns)
res = ns["run"](data)
print([len(r) for r in res])
```

与算法一、二、三对比耗时，看它是否能在 CPU 上也赢。

9.4 按属性分组优化

`q2` 与 `q3` 都作用在属性 `b` 上。可以先把 `b` 取出来一次，再比较两次：

```python
def shared_scan_grouped(data, queries_by_attr):
res = {k: [] for k in queries_by_attr}
for el in data:
for attr, consts in queries_by_attr.items():
v = el.__dict__[attr] # 每个属性只取一次
for key, c in consts:
if v == c:
res[key].append(el)
return res
```

`queries_by_attr = {"a": [("q1", 7)], "b": [("q2", 32), ("q3", 1)]}`。当同一属性上有多个谓词时，这样能省掉重复的属性查找。

9.5 增加规模

把 `n` 提到 `4,000,000`，重复步骤 3–7，看墙钟时间的比值是否变化（理论上不会，因为比值由每条元组的相对开销决定，与 `n` 无关）。用实测验证。

十、常见错误与排查

| 现象 | 原因 | 处理 |
| --- | --- | --- |
| 三种算法的结果"不一致" | 直接比较列表，但生成顺序不同 | 比较前排序（步骤 6 的 `sort_key`） |
| `读取元组次数` 不是 1,200,000 / 400,000 | 计数器忘了 `reset_counter()`，或加在了错误的位置 | 每次算法前 `reset_counter()`；计数器加在**取元组**的循环里，不是谓词成立时 |
| 计数器加了但数值不变 | `tuples_read` 在函数内被当成局部变量 | 在函数开头写 `global tuples_read` |
| 打标签版本的条目数与 `Σ` 相等 | 三个查询结果不相交，这是正常的 | 见 8.3 题；想看到差异就构造重叠查询 |
| 共享扫描比独立扫描慢，以为代码错了 | 正常现象，见 3.2 节 | 改看"读取元组次数"这个指标；或跑步骤 8 加上模拟 I/O |
| `RecursionError` 或内存不足 | `n` 太大，`Stuff` 对象开销高 | 减小 `n`；或改用元组列表 `[(a, b), ...]` 代替 dataclass |
| 步骤 8 的循环跑不完 | `IO_COST_PER_TUPLE` 设得太大，总时间 = `n·Q·io_cost` | 从 `2e-7`（0.2 微秒）起步；先估算 `400000 × 3 × io_cost` |
| `NameError` 于步骤 8 的辅助函数 | 函数定义在调用之后就执行了代码 | 按步骤顺序从上到下执行；辅助函数要定义在使用之前 |
| `TypeError` 于 `Stuff` 的构造 | 属性顺序或类型不对 | `Stuff(a, b)` 两个位置参数都是 `int` |
| 每次运行结果条数不同 | 没固定随机种子 | `random.seed(42)`；单元测试里用独立的 `random.Random(7)` 实例 |
| `unittest.main` 阻塞或报错 | 在 Jupyter 里默认参数会读取 `sys.argv` | 用 `unittest.main(argv=["ignored", "-v"], exit=False)` |
| 误以为缓冲池让共享扫描失去意义 | 见 2.4 节 | 表大于缓冲池时命中率极低；共享扫描提供的是确定性收益 |
| 用 `el.__dict__[attr]` 时属性名拼错 | 运行时不会报错，只会返回空结果 | 打印 `data[0].__dict__.keys()` 核对属性名 |

附：本实验引用的概念与出处

| 条目 | 说明 |
| --- | --- |
| 全表扫描 | 无索引时逐条读取并判定谓词，读取元组次数 = `n` |
| 选择性 σ | `σ_q = \|结果_q\| / n`，无量纲，取值 `[0, 1]` |
| 共享扫描 | 多个查询共用一次表扫描，读取元组次数从 `n·Q` 降到 `n` |
| 打标签（tagging） | 命中的元组只存一份，用标签列表/位掩码标明它属于哪些查询 |
| 代价模型 | `Cost = P·(t_seek + t_transfer) + n·t_cpu`；`t_seek` 比 `t_cpu` 大 3~6 个数量级 |
| 缓冲池 | 内存中的页面缓存；表大于缓冲池时重复扫描无法靠缓存避免 |
| 动态共享扫描 | 查询在扫描中途加入的处理问题，需补扫或声明部分结果 |