实验 12：Top-k 查询——为什么不该为取 10 行排 100 万行

> `ORDER BY title LIMIT 10` 只想要前 10 行，全排序却把 100 万行从头排到尾：本实验对比"排完再截断"与"边扫边维护一个 k 大小的堆"两种做法，量出差距，并找出堆法反过来吃亏的边界。

一、实验目标

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

1. 能解释 SQL 中 `ORDER BY … LIMIT k` 的语义，并说明"全排序后截断"（sort-and-cut）与"堆扫描"（queue-based scan / top-k）两种执行策略的区别。
2. 能写出堆法的复杂度：时间 O(n log k)、辅助内存 O(k)，并能与全排序的 O(n log n)、O(n) 做数量级对比。
3. 能用 Python 的 `heapq` 实现"保持当前最小的 k 个元素"的最大堆（max-heap）技巧，并正确处理重复键（ties）。
4. 能设计计时实验（多次运行取中位数），实测两种策略在 n = 1000000、k 取不同值时的耗时，并填入观测表。
5. 能判断在什么条件下堆法反而比全排序慢，并用常数因子与缓存行为解释原因。

二、预备知识

2.1 查询语义

```sql
SELECT *
FROM books
ORDER BY title
LIMIT 10;
```

含义：把 `books` 表按 `title` 升序排列，返回排最前的 10 行。注意"LIMIT 10 不带 ORDER BY"是另一回事——不指定顺序时返回哪 10 行是不确定的，本实验只讨论带 ORDER BY 的情形。

结果里 10 行之外的 999990 行全部被丢弃。一个自然的追问：**既然 99.999% 的排序结果都要扔掉，为什么还要排完？**

2.2 二叉堆：30 秒版

**堆（heap）**是一棵完全二叉树，且每个节点的值不大于（小顶堆，min-heap）其子节点。于是树根永远是全体元素里最小的那个。Python 标准库 `heapq` 实现的是小顶堆，底层就是一个列表，核心操作：

• `heapify(lst)`：把列表原地调整成堆，O(len)。

• `heappush(h, x)` / `heappop(h)`：插入 / 弹出最小元素，O(log len)。

• `heappushpop(h, x)`：先把 x 放进再弹出最小者，一次调整完成，比"先 push 再 pop"更快。

本实验要的是"当前最小的 k 个"，所以堆里要随时能取出**这 k 个里最大的**——那是一个**最大堆（max-heap）**的行为。`heapq` 只有小顶堆，惯用技巧有两条：

1. 键是数字时，把键取负号再入堆。
2. 键是字符串等不可取负的类型时，用一个小包装类把比较方向反过来（见步骤 3）。

2.3 两种策略的账

设表中行数为 n，要取前 k 行。

**策略一：sort-and-cut（全排序后截断）**

```text
时间：O(n log n) ——任何基于比较的排序的下界
内存：O(n) ——至少要能放下全部行的有序副本
```

n = 10⁶ 时，log₂n ≈ 19.9，比较次数约 n·log₂n ≈ 2×10⁷ 次。

**策略二：queue-based scan（堆扫描）**

先读入前 k 行建一个最大堆；此后每来一行，只和堆顶（当前 k 个中最大者）比较一次：比堆顶小就换入（O(log k)），否则直接丢弃。扫完流即可：

```text
时间：O(n log k) ——n 次与堆顶的 O(1) 比较，加上不超过 n 次 O(log k) 的堆调整
内存：O(k) ——任何时刻只保留 k 行
```

k = 10 时，log₂k ≈ 3.3，堆调整次数约 n·log₂k ≈ 3.3×10⁶ 次，比全排序少一个常数级以上的量级；内存从"放下全表"降到"放下 10 行"。

O(k) 内存这一点在数据库里有实际后果：排序若放不进内存就要外排序（external sort），把中间结果写盘、多路归并。PostgreSQL 的 `work_mem` 参数（默认 4 MB）规定了单个排序节点可用的内存上限，超过即转外排。而堆法只要 k 行就能工作，k = 10 时几乎不占内存。

2.4 一个重要的反例预告

理论复杂度不是全部。实测会看到：k = 100000（k 接近 n 的十分之一）时，堆法（738.4 ms）反而比全排序（350.6 ms）慢一倍。原因先记两个关键词：**常数因子**与**缓存局部性**，细节在思考题里展开。这提醒我们：算法选择要看参数范围，不能只背复杂度记号。

2.5 计时方法约定

比较耗时必须控制变量：

• 每种配置重复运行多次（本实验 5 次），取**中位数**（median），剔除偶发的系统抖动。

• 用 `time.perf_counter()`，它是单调高精度计时器，比 `time.time()` 适合测耗时。

• 排序会修改列表，两种策略都要在数据的**副本**上运行，且副本之间内容一致。

三、实验原理

3.1 堆法为什么正确

记第 i 行扫过之后，堆中恰好是"目前见过的所有行里 title 最小的 k 个"。归纳论证：

• 初始：读入前 k 行建堆，命题成立。

• 归纳：新行 x 到来。若 x.title ≥ 堆顶（k 个中最大者），x 不可能属于新的前 k 小，丢弃后命题仍成立；若 x.title < 堆顶，则堆顶被淘汰、x 进入，堆中仍是"目前最小的 k 个"，命题成立。

n 行扫完，堆里就是全表最小的 k 个，最后排序这 k 个输出（O(k log k)，可忽略）。堆顶即"当前第 k 小"，这也是数据库执行器实现 Top-k 的标准方式（经典文献里常算作部分排序，partial sort）。

3.2 比较次数的粗算

n = 10⁶、k = 10：

```text
全排序比较次数 ≈ n·log₂n = 10⁶ × 19.93 ≈ 2.0 × 10⁷
堆扫描比较次数 ≈ n（与堆顶的 1 次比较） + 命中数 × log₂k
≈ 10⁶ + 很小（k/n = 10⁻⁵，绝大多数元素直接被丢弃） ≈ 10⁶
```

即堆法只要约 1/20 的比较量。但注意 Python 里全排序跑在解释器调用的 C 实现上（Timsort），堆扫描的循环却是纯 Python 字节码，每条"比较"的实际开销不同，所以实测加速比（k = 10 时约 17 倍）低于理论比较次数之比。这也是 2.4 节反例的伏笔：当 k 大到堆操作频繁且堆本身超出缓存时，解释器开销叠加缓存不友好，堆法会被 C 实现的排序反超。

3.3 k 从小到大：三种区间

参考实测（本机，CPython 3.13 + Windows，n = 1000000，5 次中位数，单位 ms）：

| k | 全排序后截断 | 堆扫描 | 堆/排序 |
| --- | --- | --- | --- |
| 10 | 301.0 | 17.7 | 约 1/17 |
| 100 | 302.6 | 20.5 | 约 1/15 |
| 1000 | 304.3 | 27.6 | 约 1/11 |
| 10000 | 354.5 | 91.5 | 约 1/3.9 |
| 100000 | 350.6 | 738.4 | 约 2.1 倍（堆反超） |

三个区间：

1. **k 很小（≤1000）**：堆的命中率低（随机数据里能挤进前 k 的元素比例约 k/n）、堆小到常驻缓存，堆法大胜，且耗时对 k 不敏感。
2. **k 中等（10³～10⁴）**：命中率与堆深都在涨，差距收窄。
3. **k 接近 n（10⁵ 对 10⁶）**：约 10% 的元素要进堆，堆调整次数 ≈ 0.1n·log₂(10⁵) ≈ 1.7×10⁵ 次 × 17 层；堆本身占数 MB，超出 CPU 缓存后每次调整都是多次缓存未命中；而对面的 Timsort 依然是一条高度优化的 C 代码路径。此消彼长，堆法反而更慢。

配套图件画出了这三段曲线：


3.4 数据库里的对应物

真实执行器不会把整行复制来复制去，而是维护 (键, 行标识) 的 k 元素堆；有合适的索引（如在排序列上的 B+ 树）时甚至不用扫全表，直接沿索引顺序读 k 行即可。本实验用纯 Python 模拟的是"无索引、顺序扫描"这一最朴素但最常见的场景。

四、实验环境与准备

1. 进入仓库根目录 `explaindb-main`。
2. 安装依赖：

```bash
pip install faker pandas matplotlib jupyter
```

3. 打开配套 notebook：

```bash
jupyter notebook notebooks/Top-k.ipynb
```

4. notebook 用 40 行小数据演示两种算法并做单元测试；本实验第五章在此基础上把数据量放大到 100 万行做计时。标准库 `heapq`、`statistics` 无需安装。

五、实验步骤

步骤 1：小数据上理解两种算法（对应 notebook）

```python
from dataclasses import dataclass
from functools import total_ordering
import heapq, random

@total_ordering
@dataclass(eq=False)
class Book:
author: str
title: str

def __eq__(self, other):
return self.title == other.title

def __lt__(self, other):
# 故意反转比较方向：让 heapq 的小顶堆表现出"最大堆"的行为，
# 堆顶 heap[0] 恒为堆内 title 最大的行。
return self.title > other.title

def make_books(n, seed=42):
rng = random.Random(seed)
words = ["alpha", "bravo", "charlie", "delta", "echo", "fox", "golf", "hotel"]
return [Book(rng.choice(words) + str(rng.randrange(10**6)),
rng.choice(words) + str(rng.randrange(10**6)))
for _ in range(n)]

data = make_books(8)
for b in sorted(data, key=lambda b: b.title)[:3]:
print(b.title)
```

步骤 2：实现策略一"全排序后截断"

```python
def sort_and_cut(data, k=10):
books = data.copy() # 不改动原数据
k = min(len(data), k)
books.sort(key=lambda b: b.title) # O(n log n)
return books[:k] # 只留前 k 个
```

步骤 3：实现策略二"堆扫描"

```python
def queue_based_scan(data, k=10):
"""顺序扫描，堆中始终保持目前见过的 title 最小的 k 行。
时间 O(n log k)，辅助内存 O(k)。"""
k = min(len(data), k)
result = data[:k].copy()
heapq.heapify(result) # O(k) 建堆；Book.__lt__ 已反转，堆顶是最大 title

for book in data[k:]:
if book.title < result[0].title: # 先和堆顶比一次，O(1)
heapq.heappushpop(result, book) # 换入并保持堆性质，O(log k)

result.sort(key=lambda b: b.title) # 最后只排 k 个
return result
```

两个细节：

• `book.title < result[0].title` 用的是真实顺序（不是反转后的），所以判断语义是"比当前第 k 小还小"。

• 有重复 title（ties）时，"哪一个同键行入选"不确定，但 title 的多重集合一定一致。若要求结果可复现，可在比较键后追加一个次级键（如行号）。

步骤 4：单元测试确认两法等价

```python
import unittest

class TestTopK(unittest.TestCase):
def test_results_match(self):
for trial in range(10):
data = make_books(1000, seed=trial)
self.assertListEqual(
[b.title for b in sort_and_cut(data, 10)],
[b.title for b in queue_based_scan(data, 10)],
)

def test_k_larger_than_n(self):
data = make_books(5, seed=99)
self.assertEqual(len(queue_based_scan(data, 10)), 5)

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

步骤 5：放大到 100 万行并计时

```python
from time import perf_counter
from statistics import median

N = 1_000_000
print("造数据……")
data = make_books(N) # 一次性造好，两种策略共用同一份

def bench(fn, repeat=5):
times = []
for _ in range(repeat):
t0 = perf_counter()
fn()
times.append((perf_counter() - t0) * 1000)
return median(times)

print(f"{'k':>8} {'全排序(ms)':>12} {'堆扫描(ms)':>12}")
for k in [10, 100, 1000, 10_000, 100_000]:
t_sort = bench(lambda: sort_and_cut(data, k))
t_heap = bench(lambda: queue_based_scan(data, k))
print(f"{k:>8} {t_sort:>12.1f} {t_heap:>12.1f}")
```

预期结果与 3.3 节参考实测同方向：k ≤ 1000 时堆法快一个数量级，k = 100000 时堆法反超。绝对数字随机器不同而变化，请以自己的输出为准。

步骤 6：画耗时曲线

```python
import matplotlib.pyplot as plt

ks = [10, 100, 1000, 10_000, 100_000]
ts = [bench(lambda: sort_and_cut(data, k)) for k in ks]
th = [bench(lambda: queue_based_scan(data, k)) for k in ks]

fig, ax = plt.subplots(figsize=(7, 4))
ax.plot(ks, ts, "o-", label="sort and cut")
ax.plot(ks, th, "s-", label="queue-based scan")
ax.set_xscale("log"); ax.set_yscale("log")
ax.set_xlabel("k"); ax.set_ylabel("耗时 (ms)")
ax.set_title(f"Top-k 两种策略（n = {N:,}）")
ax.legend(); ax.grid(True, which="both", ls=":", alpha=0.5)
fig.tight_layout()
plt.show()
```

对照仓库 `教学产出/figures/fig_topk.png` 检查两条曲线的相对形状：小 k 时分离，大 k 时交叉。

步骤 7：验证堆的内存优势（可选）

```python
import sys

k = 10

堆法的工作集：k 行引用 + 堆列表

print("堆法保留行数:", k)

全排序的工作集：整表副本

print("全排序副本行数:", len(data))

用 sys.getsizeof 粗估列表结构本身（不含元素）：

print("k 元素列表 ≈", sys.getsizeof([None] * k), "字节；",
"n 元素列表 ≈", sys.getsizeof([None] * N), "字节")
```

列表结构本身的差距已达数量级；真实数据库里行更宽，全排序往往还要落到磁盘外排（参考 PostgreSQL `work_mem` 默认 4 MB 的设定）。

六、观测记录表

n 固定为 1000000，每格填 5 次运行的中位数。

**表 1：耗时（ms）**

| k | 全排序后截断 | 堆扫描 | 堆/排序 加速比 |
| --- | --- | --- | --- |
| 10 | | | |
| 100 | | | |
| 1000 | | | |
| 10000 | | | |
| 100000 | | | |

**表 2：交叉点探测（自己加测几组 k，找出堆法反超的位置）**

| k | 全排序 (ms) | 堆扫描 (ms) | 谁更快 |
| --- | --- | --- | --- |
| | | | |
| | | | |
| | | | |

**表 3：n 的影响（固定 k = 10）**

| n | 全排序 (ms) | 堆扫描 (ms) |
| --- | --- | --- |
| 100000 | | |
| 500000 | | |
| 1000000 | | |

七、思考题

1. 用大 O 记号比较两种策略的时间与内存，并代入 n = 10⁶、k = 10 算出比较次数的量级差。
2. `queue_based_scan` 里先做一次 `book.title < result[0].title` 的比较，而不是直接 `heappushpop`。这次比较省掉了什么？估计它最多能省多少次堆调整。
3. 为什么 k = 100000 时堆法反而比全排序慢？至少给出两个原因，并说明为什么"O(n log k) < O(n log n)"此时不再有指导意义。
4. 重复 title（ties）会让两种策略结果不同吗？`sort_and_cut` 与 `queue_based_scan` 各自怎么处理同键行？如何让结果完全可复现？
5. 如果表有 1 亿行、单机内存装不下，两种策略各会遇到什么问题？堆法的 O(k) 内存优势此时体现在哪里？外排序为什么要写盘？
6. `LIMIT 10` 去掉 `ORDER BY` 后，数据库还需要排序吗？返回的 10 行有保证吗？
7. 若在 `title` 列上建有 B+ 树索引，执行器可以怎样不扫全表就回答这个查询？什么情况下（查询条件变化后）索引方案会失效？
8. 把数据改成"已按 title 基本有序"（例如 90% 的行局部有序），Timsort 的表现会怎么变？堆扫描呢？这对计时实验的设计有什么提醒？

八、思考题答案与解析

1. 全排序：时间 O(n log n)、内存 O(n)；堆扫描：时间 O(n log k)、内存 O(k)。n = 10⁶、k = 10 时，log₂n ≈ 19.9、log₂k ≈ 3.32：全排序约 2.0×10⁷ 次比较；堆扫描主体是 n 次与堆顶的比较（10⁶ 次）加上极少数命中的 O(log k) 调整（命中比例约 k/n = 10⁻⁵），量级约 1.0×10⁶ 次，差约 20 倍。实测加速约 17 倍，与理论接近但略低——Python 解释器开销摊平了部分差距。
2. `heappushpop` 无论是否需要都会做一次"放入再弹出"的堆调整（O(log k)）；先比较堆顶，可在"新元素不如堆顶"时用 O(1) 直接跳过。随机数据下 k/n 的元素能通过比较（k = 10 时约十万分之一），即约 (1 − k/n)·n ≈ 10⁶ 次堆调整被这次比较省掉。这是堆法实测曲线平坦（对 k 不敏感之外）的重要原因之一。
3. 原因一：命中率从 10⁻⁵ 升到约 10%，约 10⁵ 次真实的堆调整，每次 O(log₂10⁵) ≈ 17 层；原因二：10 万元素加包装对象的堆有数 MB，远超 L2 缓存（参考量级 7 ns 一级延迟的层次结构里，缓存未命中代价成倍放大），每次调整沿着 17 层指针跳来跳去；原因三：对面的 Timsort 是 C 实现、顺序访问内存、还能利用运行中发现的局部有序。结论：复杂度记号隐藏了常数与访存模式，k/n 超过百分之几就该重新实测。
4. 同键行在 k 的边界上"谁进谁出"不确定：`sort_and_cut` 由排序算法的稳定性与初始顺序决定（Timsort 稳定，取原顺序靠前的），`queue_based_scan` 由堆内部结构决定，可能取到不同的具体行，但两法返回的 title 序列一致（测试断言正是按 title 比较）。要完全可复现，给比较键追加唯一次级键：`key=lambda b: (b.title, b.row_id)`，两法用同一键。
5. 全排序必须物化全部行（或至少全部排序键），装不下就外排序：分批排序写入临时文件，再多路归并，I/O 次数随数据量增长；堆扫描从头到尾只维护 k 行工作集，1 亿行流式扫过即可，内存依旧 O(k)。这是流式 / 管道执行器偏爱堆法的根本原因。外排序写盘是因为归并需要随机（或多路顺序）访问中间结果，内存放不下就只能落到文件（PostgreSQL 的 `work_mem` 默认 4 MB，超限即走这条路）。
6. 不需要排序。没有 ORDER BY 时 SQL 不承诺任何顺序，执行器可以任取 10 行（常表现为按扫描顺序返回）。同样的"LIMIT"语义在不同前提下成本天差地别——这正是本实验标题的另一半。
7. 在 title 的 B+ 树索引上从最左叶子开始顺序读，读完 10 行即停：成本 O(log n + k)，与 n 的大小基本无关。失效情形：查询带了不能走该索引的谓词（如 `WHERE author = …` 且 author 无索引），或需要按别的列过滤后再取前 k，此时仍需扫描候选集做 Top-k。
8. Timsort 会显著变快：它专门检测已有的升序/降序段（run），基本有序的数据接近 O(n)。堆扫描几乎不变：它做的是流式比较，不利用全局有序性。提醒：计时实验必须用"乱序随机"数据测最坏情形；若无意中生成了有序数据，会把全排序测得虚快，得到错误结论。步骤 1 用随机词表造数据正是为此。

九、扩展任务（选做）

1. **标准库对照。** 用 `heapq.nsmallest(k, data, key=lambda b: b.title)` 重做计时，与手写堆法比较。提示：`nsmallest` 的关键路径由 C 加速，手写纯 Python 堆大概率更慢；讨论"教学实现"与"工程实现"的差距。
2. **找交叉点。** 在 k ∈ [10⁴, 10⁵] 区间内二分探测"堆法开始慢于排序"的 k*，画出 k*/n 的比值。换几组随机种子重复，看比值是否稳定。提示：每测一个 k 都要重新计时两种策略，数据可复用。
3. **带过滤的 Top-k。** 给 Book 加一个 `year` 字段，实现 `WHERE year >= 2000 ORDER BY title LIMIT 10` 的堆扫描版本（不满足条件的行直接跳过）。讨论：过滤选择性很高（只剩几百行）时，先过滤再全排序是否反而更好？写代码验证你的判断。

十、常见错误与排查

| 现象 | 原因 | 处理 |
| --- | --- | --- |
| 两种策略返回结果不同 | 比较键不一致：一处用 `title`，另一处用对象默认比较 | 两法统一用 `key=lambda b: b.title`；`Book` 的 `__lt__` 反转只服务于堆 |
| `heapq` 报 `unorderable types` 或堆顶不是预期元素 | 忘了 `@total_ordering` 与 `__eq__`，或比较方向没反转 | 对照步骤 1 检查 `Book` 定义；堆顶应为"堆内最大 title" |
| 计时数字每次相差数倍 | 单次计时受 GC、系统调度影响 | 重复 5 次以上取中位数；必要时 `gc.disable()` 包住计时段 |
| 堆法在大 k 时测试断言失败 | `heappushpop` 的语义理解反了（它先 push 后 pop，不是先 pop） | 阅读官方文档确认语义；或拆成 `heappush` + `heappop` 验证 |
| 造 100 万行数据卡住 | 在循环里逐条调 `Faker` | 用步骤 1 的 `random` 词表造数据；Faker 只用于 notebook 小数据演示 |
| 曲线与参考图形状不同 | 纵轴未取对数，或 k 取点太稀疏 | `ax.set_xscale("log")`、`ax.set_yscale("log")`，并在 10⁴～10⁵ 之间加密取点 |
| 全排序把原数据顺序改掉了 | 忘了 `data.copy()`，计时循环互相污染 | 两个策略都必须在副本上运行（见步骤 2、3 的 copy） |