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

为什么做这个实验

`ORDER BY title LIMIT 10` 只想要前 10 行，可"全排序后截断"会把 100 万行从头排到尾，然后把其中 99.999% 的结果扔掉。既然绝大部分排序结果都要丢弃，为什么还要排完？

替代做法很朴素：顺序扫一遍表，手里始终只攥着"目前见过的最小的 k 行"——那是一个大小 k 的堆。新来的行只要比堆里最大的那个还大，就直接丢弃。扫完，堆里就是答案。

于是账变成：

| 策略 | 时间 | 辅助内存 |
| --- | --- | --- |
| 全排序后截断（sort-and-cut） | O(n log n) | O(n) |
| 堆扫描（queue-based scan） | **O(n log k)** | **O(k)** |

n = 10⁶、k = 10 时，`log₂n ≈ 19.9` 对 `log₂k ≈ 3.3`，理论与实测都指向一个数量级的差距。

但本实验最值得记住的不是"堆法快"，而是它的**反例**：k 增大到 100,000（约为 n 的十分之一）时，堆法反而比全排序**慢一倍**。任何优化都有适用区间，复杂度记号不能替你做决策。这个实验就是要把这条边界亲手量出来。

运行前准备

1. **依赖**：本笔记本用 `faker` 造 40 条演示数据。末尾"放大到 100 万行"那一节改用标准库 `random` 造数据（`faker` 逐条生成 100 万行会非常慢），画图用 `matplotlib`。缺失时安装：

```bash
python -m pip install faker matplotlib
```

`heapq`、`dataclasses`、`functools`、`unittest`、`time` 都是标准库。
2. **执行顺序**：从上到下逐单元运行。单元测试用到前面定义的 `Book`、`sort_and_cut`、`queue_based_scan`。
3. **单元测试**：`unittest.main(argv=["ignored", "-v"], defaultTest="MyTest", verbosity=2, exit=False)` 在 Jupyter 里必须这样传 `argv` 与 `exit=False`，否则它会去读 Jupyter 的启动参数并报错、或跑完把内核关掉。

要执行的是这条查询

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

语义：把 `books` 按 `title` 升序排列，返回排最前的 10 行。

注意 **`LIMIT 10` 不带 `ORDER BY` 是另一回事**——不指定顺序时，SQL 不承诺返回哪 10 行，执行器可以任取。本实验只讨论带 `ORDER BY` 的情形。

二叉堆：30 秒版

**堆**（heap）是一棵完全二叉树，每个节点不大于（小顶堆）其子节点，所以树根永远是全体最小的那个。Python 标准库 `heapq` 实现的是小顶堆，底层就是一个列表：

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

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

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

我们要的是"当前最小的 k 个"，所以要能随时取出**这 k 个里最大的那个**——那是**最大堆**的行为。`heapq` 只有小顶堆，惯用技巧有两条：

1. 键是数字时，取负号再入堆；
2. 键是字符串等不可取负的类型时，用一个包装类把比较方向反过来（本笔记本的 `Book.__lt__` 就是这么干的）。

堆法为什么正确

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

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

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

n 行扫完，堆里就是全表最小的 k 个，最后排序这 k 个输出（O(k log k)，可忽略）。堆顶即"当前第 k 小"。

数据库里的对应物

真实执行器不会把整行复制来复制去，而是维护 `(键, 行标识)` 的 k 元素堆；有合适索引（排序列上的 B+ 树）时甚至不用扫全表，沿索引顺序读 k 行即可。

在 PostgreSQL 里可以看到这个机制：对一条 `ORDER BY ... LIMIT k` 的查询执行 `EXPLAIN ANALYZE`，若 `Sort` 节点显示 `Sort Method: top-N heapsort`，就说明执行器用的是堆法而不是全排序。本实验用纯 Python 模拟的是"无索引、顺序扫描"这一最朴素也最常见的场景。

生成假数据

40 条 `Book`，每条有 `author` 与 `title` 两个字符串字段。规模小是为了让你把打印出来的结果逐条看完、亲手核对两种算法给出的是同一批行。

这里有个容易看错的地方

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

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

def __lt__(self, other):
return self.title > other.title # 注意方向是反的
```

`__lt__` **故意把比较方向反转**：`a < b` 当且仅当 `a.title > b.title`。这么做的唯一目的是让 `heapq` 的小顶堆表现出**最大堆**的行为——`heap[0]` 恒为堆内 title 最大的行。

由此引出两条纪律，违反任何一条都会得到莫名其妙的结果：

1. **`Book` 的 `__lt__` 只服务于堆。** 别用它来判断"哪本书的 title 更小"，那会得出相反的答案。
2. **判断语义时用真实顺序**。代码里写 `if book.title < result[0].title:` 用的是字符串自己的比较，语义是"比当前第 k 小还小"。这里**不能**写成 `book < result[0]`。

算法 1：全排序后截断（sort-and-cut）

```python
def sort_and_cut(data, k=10):
books = data.copy()
k = min(len(data), k)
books.sort(reverse=True)
return books[:k]
```

三步：复制一份、排序、取前 k 个。

**注意 `reverse=True`。** 因为 `Book.__lt__` 是反的，`books.sort()` 升序排出来的其实是 title **降序**；加 `reverse=True` 之后才是 title 升序，`books[:k]` 才是 title 最小的 k 行。这个细节如果没想清楚，很容易以为代码写错了。

**代价**：时间 O(n log n)，内存 O(n)——至少要能放下全部行的有序副本。

**问题**：我们只要 10 行，却把 1,000,000 行全排了一遍。这正是下一个算法要消除的浪费。

难道只能这样吗

表有一百万行时，全排序要做约 `n·log₂n ≈ 2×10⁷` 次比较，最后只留 10 行。**99.999% 的工作被扔掉了。**

换个角度：回答"最小的 10 行是哪些"这个提问，真的需要知道第 11 小和第 12 小的相对顺序吗？不需要。我们只需要一条"当前门槛"——第 10 小的那个值。任何比门槛大的行，都可以立刻丢弃，连排序都不用参与。

这就是**部分排序**（partial sort）的思路，也是数据库执行器实现 Top-k 的标准方式。

算法 2：堆扫描（queue-based scan）

```python
def queue_based_scan(data, k=10):
books = data.copy()
k = min(len(data), k)
result = books[:k].copy()
heapq.heapify(result) # O(k) 建堆，堆顶是堆内 title 最大者
for book in books[k:]:
if book.title < result[0].title: # 先和堆顶比一次，O(1)
heapq.heappushpop(result, book) # 换入并保持堆性质，O(log k)
result.sort(reverse=True)
return result
```

四步要看懂：

1. **建堆**：取前 k 行，`heapify` 成堆。因为 `Book.__lt__` 反转了，`result[0]` 是**堆内 title 最大**的那行，也就是"当前第 k 小"。
2. **先和堆顶比一次**（`if book.title < result[0].title`）：绝大多数行都比堆顶大，这一步就能 O(1) 直接丢弃，**省掉一次 O(log k) 的堆调整**。这是堆法实测很快的重要原因之一。
3. **换入**：只有比堆顶小的行才 `heappushpop`——先把新行放入，再弹出（现在的）最大者，堆大小始终为 k。
4. **最后只排 k 个**：`result.sort(reverse=True)`，同样因为 `__lt__` 反转，加 `reverse=True` 才得到 title 升序。

**代价**：时间 O(n log k)——n 次与堆顶的 O(1) 比较，加上不超过 n 次 O(log k) 的堆调整；内存 O(k)。

重复键（ties）怎么办

有重复 title 时，边界上"哪一行入选"是不确定的：`sort_and_cut` 由排序的稳定性与初始顺序决定，`queue_based_scan` 由堆的内部结构决定。但两法返回的 **title 序列一定一致**（单元测试正是按 title 比较的）。

若要求结果完全可复现，给比较键追加一个唯一次级键，例如 `key=lambda b: (b.title, b.row_id)`，两法用同一个键即可。

单元测试：两种算法必须给出相同结果

测试做的事：造 1000 条随机数据，跑两种算法，用 `assertListEqual` 比对 `sort_and_cut` 与 `queue_based_scan` 的结果列表；重复 10 轮。

三个要看懂的点：

1. **为什么能直接比较两个 `Book` 列表？** 因为 `Book.__eq__` 是按 `title` 定义的。所以断言比较的是 title 序列，而不是"是不是同一个对象"。**这正是处理 ties 的正确姿势**：具体哪一行入选可能不同，但 title 序列必须一致。
2. **顺序也必须一致。** 两种算法最后都做了 `sort(reverse=True)`（在反转的 `__lt__` 下即 title 升序），所以输出顺序可比。若你改写算法时去掉了最后那次排序，断言会失败——这时要先按 title 排序再比。
3. **这是差异测试**：同一件事用两条不同路径做，结果必须一致。它是验证"改写等价"最有效的手段。

运行后应看到 `Ran 1 test ... OK`。

放大到 100 万行：把三种区间量出来

40 条数据看不出快慢。下面这段代码可以直接粘进**新建的代码单元**运行。注意：**不要**用 `faker` 造 100 万行（逐条生成会很慢），改用标准库 `random`：

```python
import heapq
import random
import time
from dataclasses import dataclass
from functools import total_ordering
from statistics import median

@total_ordering
@dataclass(eq=False)
class Book:
author: str
title: str
def __eq__(self, other): return self.title == other.title
def __lt__(self, other): 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)]

def sort_and_cut(data, k=10):
books = data.copy()
k = min(len(data), k)
books.sort(reverse=True)
return books[:k]

def queue_based_scan(data, k=10):
books = data.copy()
k = min(len(data), k)
result = books[:k].copy()
heapq.heapify(result)
for book in books[k:]:
if book.title < result[0].title:
heapq.heappushpop(result, book)
result.sort(reverse=True)
return result

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

N = 1_000_000
data = make_books(N) # 两种策略共用同一份数据

print(f"{'k':>8} {'全排序(ms)':>12} {'堆扫描(ms)':>12} {'堆/排序':>10}")
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} {t_heap / t_sort:>10.2f}")
```

实测结果（本案例库，n = 1,000,000，5 次中位数）

| k | 全排序后截断 (ms) | 堆扫描 (ms) | 堆/排序 |
| ---: | ---: | ---: | ---: |
| 10 | 301.0 | 17.7 | **0.06（快 17 倍）** |
| 100 | 302.6 | 20.5 | 0.07（快 15 倍） |
| 1,000 | 304.3 | 27.6 | 0.09（快 11 倍） |
| 10,000 | 354.5 | 91.5 | 0.26（快 3.9 倍） |
| 100,000 | 350.6 | 738.4 | **2.11（堆反而慢一倍）** |

**你的数字请以自己的运行为准**，重点看形状：小 k 时两条曲线差一个数量级，大 k 时交叉。

三个区间，以及为什么大 k 会翻盘

1. **k 很小（≤ 1,000）**：随机数据里能挤进前 k 的元素比例约 `k/n`，绝大多数行在第 2 步的 O(1) 比较里就被丢弃；堆本身只有几十到几千个元素，常驻 CPU 缓存。堆法大胜，且耗时对 k 不敏感（17.7 → 27.6 ms）。
2. **k 中等（10³ ~ 10⁴）**：命中率与堆深都在涨，差距收窄到 3.9 倍。
3. **k 接近 n（10⁵ 对 10⁶）**：约 10% 的行要进堆，堆调整次数 ≈ `0.1n × log₂(10⁵) ≈ 1.7×10⁶` 次；堆本身有数 MB，超出 CPU 缓存后每次调整都要沿十几层指针跳，全是缓存未命中。而对面的 Timsort 是一条高度优化的 C 代码路径，顺序访存。**此消彼长，堆法反而更慢。**

所以 `O(n log k) < O(n log n)` 在这里失去了指导意义——复杂度记号隐藏了**常数因子**与**访存模式**。真实系统里的经验做法也是一样：k/n 超过百分之几，就该重新实测，而不是照着复杂度记号选算法。

内存维度：这才是堆法最稳的优势

即便墙钟上翻车，堆法的内存优势始终成立：任何时刻只保留 k 行，而全排序要放下全部 n 行（加上排序本身的工作区）。

在数据库里这有实际后果：排序放不进 `work_mem`（PostgreSQL 默认 4 MB）就要转成**外部排序**（见实验 11），把中间结果写盘再多路归并，I/O 代价成倍上升。堆法只要 k 行就能工作，k = 10 时几乎不占内存，也就永远不会触发外排。

执行器该怎么选

真实系统不会硬编码"Top-k 一律用堆"，而是由优化器按代价切换：估算 `k` 与预计扫描行数 `n` 的比值，比值小（百分之几以内）走堆法，否则走全排序；若 k 行本身已经放不进排序可用内存（`work_mem`），堆法的 O(k) 内存优势就不存在了，也要重新考虑；若有能提供所需顺序的索引，则优先走索引。

要点不在具体阈值，而在方法论：**用代价估算选执行路径，用实测标定阈值。**

思考题与详解

**1. 用大 O 记号比较两种策略的时间与内存，并代入 n = 10⁶、k = 10 算出比较次数的量级差。**

<details><summary>答案要点</summary>

| 策略 | 时间 | 内存 |
| --- | --- | --- |
| 全排序后截断 | O(n log n) | O(n) |
| 堆扫描 | O(n log k) | O(k) |

n = 10⁶、k = 10 时，`log₂n ≈ 19.93`、`log₂k ≈ 3.32`：

```
全排序比较次数 ≈ n·log₂n = 10⁶ × 19.93 ≈ 2.0 × 10⁷
堆扫描比较次数 ≈ n（与堆顶的 1 次比较）+ 命中数 × log₂k
≈ 10⁶（命中比例仅 k/n = 10⁻⁵，堆调整可忽略）
```

量级差约 20 倍。实测加速约 17 倍，与理论接近但略低——Python 解释器开销摊平了一部分差距。

</details>

**2. `queue_based_scan` 里先做一次 `book.title < result[0].title` 的比较，而不是直接 `heappushpop`。这次比较省掉了什么？**

<details><summary>答案要点</summary>

`heappushpop` 无论结果如何都会做一次"放入再弹出"的堆调整，代价 O(log k)。先和堆顶比一次（O(1)），就能在"新元素不如堆顶"时直接跳过这次调整。

随机数据下能通过这次比较的元素比例是 `k/n`（k = 10、n = 10⁶ 时约十万分之一），也就是说约 `(1 − k/n)·n ≈ 10⁶` 次堆调整被省掉了。

代价：多写一行代码、多一次字符串比较。收益：绝大多数行被 O(1) 拒掉。**这也是堆法在小 k 时耗时对 k 极不敏感的原因**——主体开销就是这一次次 O(1) 比较。

</details>

**3. 为什么 k = 100,000 时堆法反而比全排序慢？至少给出两个原因，并说明为什么"O(n log k) < O(n log n)"此时不再有指导意义。**

<details><summary>答案要点</summary>

1. **命中率暴涨。** 从 `k/n = 10⁻⁵` 升到约 10%，约 10⁵ 次真实的堆调整，每次 `log₂(10⁵) ≈ 17` 层。
2. **堆超出缓存。** 10 万个包装对象的堆有数 MB，远超 CPU 缓存，每次调整沿 17 层指针跳，几乎每次都是缓存未命中。
3. **对面更强。** Timsort 是 C 实现、顺序访存，还能利用运行中发现的局部有序段。

为什么复杂度记号失去指导意义：`O(n log k)` 里被当作常数的东西（一次比较的实际开销、一次堆调整的访存代价）在两种策略里**差别巨大**。堆法的"一次操作"是纯 Python 字节码 + 随机访存，全排序的"一次操作"是 C 代码 + 顺序访存。记号只比较操作次数，不比较单次操作的成本，也不比较访存模式。

**结论**：k/n 超过百分之几就该重新实测，别照着复杂度记号选算法。

</details>

**4. 重复 title（ties）会让两种策略结果不同吗？如何让结果完全可复现？**

<details><summary>答案要点</summary>

**在 title 序列上不会不同，在具体行上可能不同。**

• `sort_and_cut`：由排序算法的稳定性与初始顺序决定（Python 的 Timsort 是稳定的，取原顺序靠前的那些行）。

• `queue_based_scan`：由堆的内部结构决定，可能取到另一批同键行。

但两法返回的 **title 序列必然一致**——单元测试正是按 title 比较的（`Book.__eq__` 也只比 title）。

要完全可复现，给比较键追加一个唯一次级键，两法用同一个键：

```python
key=lambda b: (b.title, b.row_id)
```

这样同键行之间的先后顺序也被唯一确定，两种策略（以及任何稳定的实现）都会给出同一批行。

</details>

**5. 如果表有 1 亿行、单机内存装不下，两种策略各会遇到什么问题？堆法的 O(k) 内存优势此时体现在哪里？**

<details><summary>答案要点</summary>

**全排序**：必须物化全部行（至少是全部排序键），装不下就要转**外部排序**——分批排序写入临时文件，再多趟归并（见实验 11）。I/O 次数随数据量增长，代价 `2N × 趟数` 页。PostgreSQL 里一旦超过 `work_mem`（默认 4 MB）就会走这条路。

**堆扫描**：从头到尾只维护 k 行工作集，1 亿行流式扫过即可，内存依旧 O(k)，**永远不会触发外排**。

这就是流式 / 管道执行器偏爱堆法的根本原因：它把一个可能落盘的排序，变成了一个纯流式的操作。

外排序为什么要写盘？因为归并需要同时访问多个顺串的当前位置，内存放不下这些顺串，就只能把它们落到文件里再按页读回来。

</details>

**6. `LIMIT 10` 去掉 `ORDER BY` 后，数据库还需要排序吗？返回的 10 行有保证吗？**

<details><summary>答案要点</summary>

**不需要排序。** 没有 `ORDER BY` 时 SQL 不承诺任何顺序，执行器可以任取 10 行（实际常表现为按扫描顺序返回前 10 行）。

**返回的 10 行没有任何保证**：哪 10 行取决于执行计划、扫描顺序、并发情况，同一条 SQL 在不同版本或不同数据分布下可能返回不同的行。

这也是本实验标题的另一半：同样的 `LIMIT`，带不带 `ORDER BY`，成本天差地别——一个只要 O(k)，一个要 O(n log n)。写 SQL 时必须清楚自己要的是哪一种。

</details>

**7. 若在 `title` 列上建有 B+ 树索引，执行器可以怎样不扫全表就回答这个查询？什么情况下索引方案会失效？**

<details><summary>答案要点</summary>

**可行做法**：B+ 树的叶子层按键值有序并用链表串起来。执行器从最左叶子开始沿链顺序读，读满 10 行即停。成本 `O(log n + k)`——一次树下降定位到最左叶子（O(log n)），加上读 k 行。**与 n 的大小基本无关**，比任何扫描方案都快。

**失效情形**：

• 查询带了走不了该索引的谓词，例如 `WHERE author = 'X' ORDER BY title LIMIT 10` 而 `author` 上没有索引。此时必须先扫（或过滤）出候选集，再对候选集做 Top-k。

• 需要按别的列排序：`ORDER BY price LIMIT 10`（索引在 `title` 上），索引有序性用不上。

• `ORDER BY` 的方向与索引不一致且不支持反向扫描，或排序列上有表达式/函数。

一般判据：**索引的有序性能否直接提供查询要求的顺序，以及过滤条件能否在该索引上被满足**。

</details>

**8. 把数据改成"已按 title 基本有序"（例如 90% 的行局部有序），Timsort 的表现会怎么变？堆扫描呢？这对计时实验的设计有什么提醒？**

<details><summary>答案要点</summary>

• **Timsort 会显著变快。** 它专门检测数据中已有的升序 / 降序段（run）并直接归并这些段，基本有序的数据接近 O(n)。

• **堆扫描几乎不变。** 它做的是流式比较，不利用全局有序性；命中率取决于数据分布，与是否已排序关系不大（已排序数据下命中集中在前段，但总比较次数仍是 n）。

**对计时实验的提醒**：

1. **必须用乱序随机数据测最坏情形。** 若无意中用了有序或部分有序的数据，会把全排序测得虚快，得到"堆法没什么优势"的错误结论。
2. **两种策略必须在同一份数据上跑**，且各自跑在数据的**副本**上（排序会修改列表）。
3. **多次运行取中位数**，用 `time.perf_counter()`；单次计时受 GC 与系统调度影响太大。

</details>