{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 实验 12：Top-k 查询——为什么不该为取 10 行排 100 万行\n", "\n", "## 为什么做这个实验\n", "\n", "`ORDER BY title LIMIT 10` 只想要前 10 行，可\"全排序后截断\"会把 100 万行从头排到尾，然后把其中 99.999% 的结果扔掉。既然绝大部分排序结果都要丢弃，为什么还要排完？\n", "\n", "替代做法很朴素：顺序扫一遍表，手里始终只攥着\"目前见过的最小的 k 行\"——那是一个大小 k 的堆。新来的行只要比堆里最大的那个还大，就直接丢弃。扫完，堆里就是答案。\n", "\n", "于是账变成：\n", "\n", "| 策略 | 时间 | 辅助内存 |\n", "| --- | --- | --- |\n", "| 全排序后截断（sort-and-cut） | O(n log n) | O(n) |\n", "| 堆扫描（queue-based scan） | **O(n log k)** | **O(k)** |\n", "\n", "n = 10⁶、k = 10 时，`log₂n ≈ 19.9` 对 `log₂k ≈ 3.3`，理论与实测都指向一个数量级的差距。\n", "\n", "但本实验最值得记住的不是\"堆法快\"，而是它的**反例**：k 增大到 100,000（约为 n 的十分之一）时，堆法反而比全排序**慢一倍**。任何优化都有适用区间，复杂度记号不能替你做决策。这个实验就是要把这条边界亲手量出来。\n" ], "id": "85967e31-71a6-46fe-83f5-3c005cf3f66b" }, { "cell_type": "markdown", "id": "674ea06c", "metadata": {}, "source": [ "## 运行前准备\n", "\n", "1. **依赖**：本笔记本用 `faker` 造 40 条演示数据。末尾\"放大到 100 万行\"那一节改用标准库 `random` 造数据（`faker` 逐条生成 100 万行会非常慢），画图用 `matplotlib`。缺失时安装：\n", "\n", "```bash\n", "python -m pip install faker matplotlib\n", "```\n", "\n", " `heapq`、`dataclasses`、`functools`、`unittest`、`time` 都是标准库。\n", "2. **执行顺序**：从上到下逐单元运行。单元测试用到前面定义的 `Book`、`sort_and_cut`、`queue_based_scan`。\n", "3. **单元测试**：`unittest.main(argv=[\"ignored\", \"-v\"], defaultTest=\"MyTest\", verbosity=2, exit=False)` 在 Jupyter 里必须这样传 `argv` 与 `exit=False`，否则它会去读 Jupyter 的启动参数并报错、或跑完把内核关掉。\n" ] }, { "cell_type": "markdown", "id": "9528e8b5-4817-46df-98d1-75bf3d3d367f", "metadata": {}, "source": [ "## 要执行的是这条查询\n", "\n", "``` sql\n", "SELECT * \n", "FROM books\n", "ORDER BY title\n", "LIMIT 10\n", "```\n", "\n", "语义：把 `books` 按 `title` 升序排列，返回排最前的 10 行。\n", "\n", "注意 **`LIMIT 10` 不带 `ORDER BY` 是另一回事**——不指定顺序时，SQL 不承诺返回哪 10 行，执行器可以任取。本实验只讨论带 `ORDER BY` 的情形。\n", "\n", "### 二叉堆：30 秒版\n", "\n", "**堆**（heap）是一棵完全二叉树，每个节点不大于（小顶堆）其子节点，所以树根永远是全体最小的那个。Python 标准库 `heapq` 实现的是小顶堆，底层就是一个列表：\n", "\n", "- `heapify(lst)`：把列表原地调整成堆，O(len)。\n", "- `heappush(h, x)` / `heappop(h)`：插入 / 弹出最小元素，O(log len)。\n", "- `heappushpop(h, x)`：**先放入 x 再弹出最小者**，一次调整完成，比\"先 push 再 pop\"快。\n", "\n", "我们要的是\"当前最小的 k 个\"，所以要能随时取出**这 k 个里最大的那个**——那是**最大堆**的行为。`heapq` 只有小顶堆，惯用技巧有两条：\n", "\n", "1. 键是数字时，取负号再入堆；\n", "2. 键是字符串等不可取负的类型时，用一个包装类把比较方向反过来（本笔记本的 `Book.__lt__` 就是这么干的）。\n", "\n", "### 堆法为什么正确\n", "\n", "记第 i 行扫过之后，堆中恰好是\"目前见过的所有行里 title 最小的 k 个\"。归纳：\n", "\n", "- **初始**：读入前 k 行建堆，命题成立。\n", "- **归纳**：新行 x 到来。若 `x.title ≥ 堆顶`（k 个中最大者），x 不可能属于新的前 k 小，丢弃后命题仍成立；若 `x.title < 堆顶`，则堆顶被淘汰、x 进入，堆中仍是\"目前最小的 k 个\"。\n", "\n", "n 行扫完，堆里就是全表最小的 k 个，最后排序这 k 个输出（O(k log k)，可忽略）。堆顶即\"当前第 k 小\"。\n", "\n", "### 数据库里的对应物\n", "\n", "真实执行器不会把整行复制来复制去，而是维护 `(键, 行标识)` 的 k 元素堆；有合适索引（排序列上的 B+ 树）时甚至不用扫全表，沿索引顺序读 k 行即可。\n", "\n", "在 PostgreSQL 里可以看到这个机制：对一条 `ORDER BY ... LIMIT k` 的查询执行 `EXPLAIN ANALYZE`，若 `Sort` 节点显示 `Sort Method: top-N heapsort`，就说明执行器用的是堆法而不是全排序。本实验用纯 Python 模拟的是\"无索引、顺序扫描\"这一最朴素也最常见的场景。\n" ] }, { "cell_type": "markdown", "id": "05088ba1-38d6-493d-a6d6-176152f56a4e", "metadata": {}, "source": [ "## 生成假数据\n", "\n", "40 条 `Book`，每条有 `author` 与 `title` 两个字符串字段。规模小是为了让你把打印出来的结果逐条看完、亲手核对两种算法给出的是同一批行。\n", "\n", "### 这里有个容易看错的地方\n", "\n", "```python\n", "@total_ordering\n", "@dataclass(eq=False)\n", "class Book:\n", " author: str\n", " title: str\n", "\n", " def __eq__(self, other):\n", " return self.title == other.title\n", "\n", " def __lt__(self, other):\n", " return self.title > other.title # 注意方向是反的\n", "```\n", "\n", "`__lt__` **故意把比较方向反转**：`a < b` 当且仅当 `a.title > b.title`。这么做的唯一目的是让 `heapq` 的小顶堆表现出**最大堆**的行为——`heap[0]` 恒为堆内 title 最大的行。\n", "\n", "由此引出两条纪律，违反任何一条都会得到莫名其妙的结果：\n", "\n", "1. **`Book` 的 `__lt__` 只服务于堆。** 别用它来判断\"哪本书的 title 更小\"，那会得出相反的答案。\n", "2. **判断语义时用真实顺序**。代码里写 `if book.title < result[0].title:` 用的是字符串自己的比较，语义是\"比当前第 k 小还小\"。这里**不能**写成 `book < result[0]`。\n" ] }, { "cell_type": "code", "id": "e8cb3442-39a2-41ff-823a-b5f7ef3f07ba", "metadata": { "ExecuteTime": { "end_time": "2024-09-06T06:09:44.236837Z", "start_time": "2024-09-06T06:09:44.184004Z" } }, "source": [ "from faker import Faker\n", "\n", "fake = Faker()\n", "fake.seed_instance(42)\n", "\n", "from dataclasses import dataclass\n", "import heapq\n", "from functools import total_ordering\n", "\n", "number_of_tuples = 40\n", "\n", "\n", "@total_ordering\n", "@dataclass(eq=False)\n", "class Book:\n", " author: str\n", " title: str\n", "\n", " def __eq__(self, other):\n", " return self.title == other.title\n", "\n", " def __lt__(self, other):\n", " return self.title > other.title\n", "\n", "\n", "# create some fake data mimicking tuples in a relation:\n", "data = [Book(fake.name(), fake.sentence()) for f in range(number_of_tuples)]\n", "data[:10]" ], "outputs": [ { "data": { "text/plain": [ "[Book(author='Nicholas Parker', title='None join yeah.'),\n", " Book(author='Debra Miller', title='Company worker natural himself add need.'),\n", " Book(author='Kimberly Garza', title='Along other along news toward.'),\n", " Book(author='Christopher Edwards', title='Worry top administration provide about reach.'),\n", " Book(author='Kim Fitzpatrick', title='Kitchen wife right successful law.'),\n", " Book(author='Amanda Roberson', title='Third ask few night.'),\n", " Book(author='Haley Turner', title='Hair mission cultural wish shoulder.'),\n", " Book(author='Lisa Smith', title='Marriage chair person guy deep future senior.'),\n", " Book(author='Cynthia Fernandez', title='Play plan number entire push child.'),\n", " Book(author='Jennifer Reese', title='Cultural beautiful subject relate here side happen.')]" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 1 }, { "cell_type": "markdown", "id": "e8ca52a6-73fa-4324-98aa-ca8f48207ae5", "metadata": {}, "source": [ "## 算法 1：全排序后截断（sort-and-cut）\n", "\n", "```python\n", "def sort_and_cut(data, k=10):\n", " books = data.copy()\n", " k = min(len(data), k)\n", " books.sort(reverse=True)\n", " return books[:k]\n", "```\n", "\n", "三步：复制一份、排序、取前 k 个。\n", "\n", "**注意 `reverse=True`。** 因为 `Book.__lt__` 是反的，`books.sort()` 升序排出来的其实是 title **降序**；加 `reverse=True` 之后才是 title 升序，`books[:k]` 才是 title 最小的 k 行。这个细节如果没想清楚，很容易以为代码写错了。\n", "\n", "**代价**：时间 O(n log n)，内存 O(n)——至少要能放下全部行的有序副本。\n", "\n", "**问题**：我们只要 10 行，却把 1,000,000 行全排了一遍。这正是下一个算法要消除的浪费。\n" ] }, { "cell_type": "code", "id": "1fe469e7-6987-4fd1-b795-2554b7a68d08", "metadata": { "ExecuteTime": { "end_time": "2024-09-06T06:09:44.240087Z", "start_time": "2024-09-06T06:09:44.237741Z" } }, "source": [ "def sort_and_cut(data, k=10):\n", " # make a deep copy to start with the unchanged data:\n", " books = data.copy()\n", "\n", " # handle the case that k is larger than the data:\n", " k = min(len(data), k)\n", "\n", " # standard sort:\n", " books.sort(reverse=True)\n", "\n", " # cut list to just show the first k elements:\n", " return books[:k]\n", "\n", " # so we throw everything away except the first ten elements, that is smart, not...\n", "\n", "\n", "sort_and_cut(data)" ], "outputs": [ { "data": { "text/plain": [ "[Book(author='Garrett Myers', title='All three money her.'),\n", " Book(author='Kimberly Garza', title='Along other along news toward.'),\n", " Book(author='Bill Reyes', title='Baby exist next current.'),\n", " Book(author='Charles Rivera', title='Bill you arrive quality environment significant hand.'),\n", " Book(author='Mrs. Lisa Bird', title='Card important forward sport yard care through baby.'),\n", " Book(author='Pamela Davis', title='Clearly indeed our discuss among prevent somebody vote.'),\n", " Book(author='Debra Miller', title='Company worker natural himself add need.'),\n", " Book(author='Jennifer Reese', title='Cultural beautiful subject relate here side happen.'),\n", " Book(author='Deborah Powell', title='Drug quality visit modern ability side.'),\n", " Book(author='Theresa Callahan', title='Easy field compare significant.')]" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 2 }, { "cell_type": "markdown", "id": "b27249fc-f49e-48ea-9031-1c29316771c5", "metadata": {}, "source": [ "## 难道只能这样吗\n", "\n", "表有一百万行时，全排序要做约 `n·log₂n ≈ 2×10⁷` 次比较，最后只留 10 行。**99.999% 的工作被扔掉了。**\n", "\n", "换个角度：回答\"最小的 10 行是哪些\"这个提问，真的需要知道第 11 小和第 12 小的相对顺序吗？不需要。我们只需要一条\"当前门槛\"——第 10 小的那个值。任何比门槛大的行，都可以立刻丢弃，连排序都不用参与。\n", "\n", "这就是**部分排序**（partial sort）的思路，也是数据库执行器实现 Top-k 的标准方式。\n" ] }, { "cell_type": "markdown", "id": "1d4a5adc-25d2-41c6-a3f2-25ef7f7cff11", "metadata": {}, "source": [ "## 算法 2：堆扫描（queue-based scan）\n", "\n", "```python\n", "def queue_based_scan(data, k=10):\n", " books = data.copy()\n", " k = min(len(data), k)\n", " result = books[:k].copy()\n", " heapq.heapify(result) # O(k) 建堆，堆顶是堆内 title 最大者\n", " for book in books[k:]:\n", " if book.title < result[0].title: # 先和堆顶比一次，O(1)\n", " heapq.heappushpop(result, book) # 换入并保持堆性质，O(log k)\n", " result.sort(reverse=True)\n", " return result\n", "```\n", "\n", "四步要看懂：\n", "\n", "1. **建堆**：取前 k 行，`heapify` 成堆。因为 `Book.__lt__` 反转了，`result[0]` 是**堆内 title 最大**的那行，也就是\"当前第 k 小\"。\n", "2. **先和堆顶比一次**（`if book.title < result[0].title`）：绝大多数行都比堆顶大，这一步就能 O(1) 直接丢弃，**省掉一次 O(log k) 的堆调整**。这是堆法实测很快的重要原因之一。\n", "3. **换入**：只有比堆顶小的行才 `heappushpop`——先把新行放入，再弹出（现在的）最大者，堆大小始终为 k。\n", "4. **最后只排 k 个**：`result.sort(reverse=True)`，同样因为 `__lt__` 反转，加 `reverse=True` 才得到 title 升序。\n", "\n", "**代价**：时间 O(n log k)——n 次与堆顶的 O(1) 比较，加上不超过 n 次 O(log k) 的堆调整；内存 O(k)。\n", "\n", "### 重复键（ties）怎么办\n", "\n", "有重复 title 时，边界上\"哪一行入选\"是不确定的：`sort_and_cut` 由排序的稳定性与初始顺序决定，`queue_based_scan` 由堆的内部结构决定。但两法返回的 **title 序列一定一致**（单元测试正是按 title 比较的）。\n", "\n", "若要求结果完全可复现，给比较键追加一个唯一次级键，例如 `key=lambda b: (b.title, b.row_id)`，两法用同一个键即可。\n" ] }, { "cell_type": "code", "id": "68407bdb-35bf-448e-8bf8-3d56e1c9c900", "metadata": { "ExecuteTime": { "end_time": "2024-09-06T06:09:44.243178Z", "start_time": "2024-09-06T06:09:44.240675Z" } }, "source": [ "def queue_based_scan(data, k=10):\n", " \"\"\"Scan input stream keeping the currently seen smallest k elements in a max-heap.\n", " This is an example of partial sorting. Note that the heap-based implementation only\n", " requires O(k) memory and has a time complexity of O(n log k) where n is the number of\n", " elements in the input stream. This is much more efficient than sorting the whole array\n", " first and then selecting the top-k elements (as done above).\n", " \"\"\"\n", "\n", " # make a deep copy to start with the unchanged data:\n", " books = data.copy()\n", "\n", " # handle the case that k is larger than the data:\n", " k = min(len(data), k)\n", "\n", " # just copy the first 10 elements:\n", " result = books[:k].copy()\n", "\n", " # create a max heap on these elements (in linear time):\n", " heapq.heapify(result)\n", "\n", " # for all remaining elements from the dataset:\n", " for book in books[k:]:\n", " # is the current element smaller than the top-element? (watch out for ties)\n", " if book.title < result[0].title:\n", " # remove the current max element from the heap and replace it with book:\n", " # also establish heap-properties afterwards\n", " heapq.heappushpop(result, book)\n", "\n", " # from the heap create a sorted list\n", " # note: just popping each element and then reversing would do the same\n", " result.sort(reverse=True)\n", "\n", " return result\n", "\n", "\n", "queue_based_scan(data)" ], "outputs": [ { "data": { "text/plain": [ "[Book(author='Garrett Myers', title='All three money her.'),\n", " Book(author='Kimberly Garza', title='Along other along news toward.'),\n", " Book(author='Bill Reyes', title='Baby exist next current.'),\n", " Book(author='Charles Rivera', title='Bill you arrive quality environment significant hand.'),\n", " Book(author='Mrs. Lisa Bird', title='Card important forward sport yard care through baby.'),\n", " Book(author='Pamela Davis', title='Clearly indeed our discuss among prevent somebody vote.'),\n", " Book(author='Debra Miller', title='Company worker natural himself add need.'),\n", " Book(author='Jennifer Reese', title='Cultural beautiful subject relate here side happen.'),\n", " Book(author='Deborah Powell', title='Drug quality visit modern ability side.'),\n", " Book(author='Theresa Callahan', title='Easy field compare significant.')]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 3 }, { "metadata": {}, "cell_type": "markdown", "source": [ "## 单元测试：两种算法必须给出相同结果\n", "\n", "测试做的事：造 1000 条随机数据，跑两种算法，用 `assertListEqual` 比对 `sort_and_cut` 与 `queue_based_scan` 的结果列表；重复 10 轮。\n", "\n", "三个要看懂的点：\n", "\n", "1. **为什么能直接比较两个 `Book` 列表？** 因为 `Book.__eq__` 是按 `title` 定义的。所以断言比较的是 title 序列，而不是\"是不是同一个对象\"。**这正是处理 ties 的正确姿势**：具体哪一行入选可能不同，但 title 序列必须一致。\n", "2. **顺序也必须一致。** 两种算法最后都做了 `sort(reverse=True)`（在反转的 `__lt__` 下即 title 升序），所以输出顺序可比。若你改写算法时去掉了最后那次排序，断言会失败——这时要先按 title 排序再比。\n", "3. **这是差异测试**：同一件事用两条不同路径做，结果必须一致。它是验证\"改写等价\"最有效的手段。\n", "\n", "运行后应看到 `Ran 1 test ... OK`。\n" ], "id": "4b3da84cd9ac5ea" }, { "cell_type": "code", "id": "a1a72522-100f-4579-8769-fae5300c31d4", "metadata": { "ExecuteTime": { "end_time": "2024-09-06T06:09:44.776192Z", "start_time": "2024-09-06T06:09:44.243741Z" } }, "source": [ "import unittest\n", "\n", "\n", "class MyTest(unittest.TestCase):\n", "\n", " # the following function will be called before every test-function:\n", "\n", " def create_data(self, number_of_tuples):\n", " self.data = [\n", " Book(fake.name(), fake.sentence()) for f in range(number_of_tuples)\n", " ]\n", "\n", " def test_topk_results_end_to_end(self):\n", " for _ in range(10):\n", " self.create_data(1000)\n", " res1 = sort_and_cut(self.data)\n", " res2 = queue_based_scan(self.data)\n", " self.assertListEqual(res1, res2)\n", "\n", "\n", "# Run the unit test without shutting down the jupyter kernel\n", "# notice that this call will look for all test classes, i.e.\n", "# all classes inheriting from unittest.TestCase\n", "# each of these functions will be executed once\n", "# unittest.main(argv=['ignored', '-v'], verbosity=2, exit=False)\n", "\n", "# only execute a specific Test-class:\n", "unittest.main(argv=[\"ignored\", \"-v\"], defaultTest=\"MyTest\", verbosity=2, exit=False)" ], "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "test_topk_results_end_to_end (__main__.MyTest.test_topk_results_end_to_end) ... ok\n", "\n", "----------------------------------------------------------------------\n", "Ran 1 test in 0.527s\n", "\n", "OK\n" ] }, { "data": { "text/plain": [ "" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 4 }, { "cell_type": "markdown", "id": "7a3fb813", "metadata": {}, "source": [ "## 放大到 100 万行：把三种区间量出来\n", "\n", "40 条数据看不出快慢。下面这段代码可以直接粘进**新建的代码单元**运行。注意：**不要**用 `faker` 造 100 万行（逐条生成会很慢），改用标准库 `random`：\n", "\n", "```python\n", "import heapq\n", "import random\n", "import time\n", "from dataclasses import dataclass\n", "from functools import total_ordering\n", "from statistics import median\n", "\n", "@total_ordering\n", "@dataclass(eq=False)\n", "class Book:\n", " author: str\n", " title: str\n", " def __eq__(self, other): return self.title == other.title\n", " def __lt__(self, other): return self.title > other.title\n", "\n", "def make_books(n, seed=42):\n", " rng = random.Random(seed)\n", " words = [\"alpha\", \"bravo\", \"charlie\", \"delta\", \"echo\", \"fox\", \"golf\", \"hotel\"]\n", " return [Book(rng.choice(words) + str(rng.randrange(10**6)),\n", " rng.choice(words) + str(rng.randrange(10**6))) for _ in range(n)]\n", "\n", "def sort_and_cut(data, k=10):\n", " books = data.copy()\n", " k = min(len(data), k)\n", " books.sort(reverse=True)\n", " return books[:k]\n", "\n", "def queue_based_scan(data, k=10):\n", " books = data.copy()\n", " k = min(len(data), k)\n", " result = books[:k].copy()\n", " heapq.heapify(result)\n", " for book in books[k:]:\n", " if book.title < result[0].title:\n", " heapq.heappushpop(result, book)\n", " result.sort(reverse=True)\n", " return result\n", "\n", "def bench(fn, repeat=5):\n", " times = []\n", " for _ in range(repeat):\n", " t0 = time.perf_counter()\n", " fn()\n", " times.append((time.perf_counter() - t0) * 1000)\n", " return median(times)\n", "\n", "N = 1_000_000\n", "data = make_books(N) # 两种策略共用同一份数据\n", "\n", "print(f\"{'k':>8} {'全排序(ms)':>12} {'堆扫描(ms)':>12} {'堆/排序':>10}\")\n", "for k in [10, 100, 1000, 10_000, 100_000]:\n", " t_sort = bench(lambda: sort_and_cut(data, k))\n", " t_heap = bench(lambda: queue_based_scan(data, k))\n", " print(f\"{k:>8} {t_sort:>12.1f} {t_heap:>12.1f} {t_heap / t_sort:>10.2f}\")\n", "```\n", "\n", "### 实测结果（本案例库，n = 1,000,000，5 次中位数）\n", "\n", "| k | 全排序后截断 (ms) | 堆扫描 (ms) | 堆/排序 |\n", "| ---: | ---: | ---: | ---: |\n", "| 10 | 301.0 | 17.7 | **0.06（快 17 倍）** |\n", "| 100 | 302.6 | 20.5 | 0.07（快 15 倍） |\n", "| 1,000 | 304.3 | 27.6 | 0.09（快 11 倍） |\n", "| 10,000 | 354.5 | 91.5 | 0.26（快 3.9 倍） |\n", "| 100,000 | 350.6 | 738.4 | **2.11（堆反而慢一倍）** |\n", "\n", "**你的数字请以自己的运行为准**，重点看形状：小 k 时两条曲线差一个数量级，大 k 时交叉。\n", "\n", "### 三个区间，以及为什么大 k 会翻盘\n", "\n", "1. **k 很小（≤ 1,000）**：随机数据里能挤进前 k 的元素比例约 `k/n`，绝大多数行在第 2 步的 O(1) 比较里就被丢弃；堆本身只有几十到几千个元素，常驻 CPU 缓存。堆法大胜，且耗时对 k 不敏感（17.7 → 27.6 ms）。\n", "2. **k 中等（10³ ~ 10⁴）**：命中率与堆深都在涨，差距收窄到 3.9 倍。\n", "3. **k 接近 n（10⁵ 对 10⁶）**：约 10% 的行要进堆，堆调整次数 ≈ `0.1n × log₂(10⁵) ≈ 1.7×10⁶` 次；堆本身有数 MB，超出 CPU 缓存后每次调整都要沿十几层指针跳，全是缓存未命中。而对面的 Timsort 是一条高度优化的 C 代码路径，顺序访存。**此消彼长，堆法反而更慢。**\n", "\n", "所以 `O(n log k) < O(n log n)` 在这里失去了指导意义——复杂度记号隐藏了**常数因子**与**访存模式**。真实系统里的经验做法也是一样：k/n 超过百分之几，就该重新实测，而不是照着复杂度记号选算法。\n", "\n", "### 内存维度：这才是堆法最稳的优势\n", "\n", "即便墙钟上翻车，堆法的内存优势始终成立：任何时刻只保留 k 行，而全排序要放下全部 n 行（加上排序本身的工作区）。\n", "\n", "在数据库里这有实际后果：排序放不进 `work_mem`（PostgreSQL 默认 4 MB）就要转成**外部排序**（见实验 11），把中间结果写盘再多路归并，I/O 代价成倍上升。堆法只要 k 行就能工作，k = 10 时几乎不占内存，也就永远不会触发外排。\n", "\n", "### 执行器该怎么选\n", "\n", "真实系统不会硬编码\"Top-k 一律用堆\"，而是由优化器按代价切换：估算 `k` 与预计扫描行数 `n` 的比值，比值小（百分之几以内）走堆法，否则走全排序；若 k 行本身已经放不进排序可用内存（`work_mem`），堆法的 O(k) 内存优势就不存在了，也要重新考虑；若有能提供所需顺序的索引，则优先走索引。\n", "\n", "要点不在具体阈值，而在方法论：**用代价估算选执行路径，用实测标定阈值。**\n", "" ] }, { "cell_type": "markdown", "id": "1e051dde", "metadata": {}, "source": [ "## 思考题与详解\n", "\n", "**1. 用大 O 记号比较两种策略的时间与内存，并代入 n = 10⁶、k = 10 算出比较次数的量级差。**\n", "\n", "
答案要点\n", "\n", "| 策略 | 时间 | 内存 |\n", "| --- | --- | --- |\n", "| 全排序后截断 | O(n log n) | O(n) |\n", "| 堆扫描 | O(n log k) | O(k) |\n", "\n", "n = 10⁶、k = 10 时，`log₂n ≈ 19.93`、`log₂k ≈ 3.32`：\n", "\n", "```\n", "全排序比较次数 ≈ n·log₂n = 10⁶ × 19.93 ≈ 2.0 × 10⁷\n", "堆扫描比较次数 ≈ n（与堆顶的 1 次比较）+ 命中数 × log₂k\n", " ≈ 10⁶（命中比例仅 k/n = 10⁻⁵，堆调整可忽略）\n", "```\n", "\n", "量级差约 20 倍。实测加速约 17 倍，与理论接近但略低——Python 解释器开销摊平了一部分差距。\n", "\n", "
\n", "\n", "**2. `queue_based_scan` 里先做一次 `book.title < result[0].title` 的比较，而不是直接 `heappushpop`。这次比较省掉了什么？**\n", "\n", "
答案要点\n", "\n", "`heappushpop` 无论结果如何都会做一次\"放入再弹出\"的堆调整，代价 O(log k)。先和堆顶比一次（O(1)），就能在\"新元素不如堆顶\"时直接跳过这次调整。\n", "\n", "随机数据下能通过这次比较的元素比例是 `k/n`（k = 10、n = 10⁶ 时约十万分之一），也就是说约 `(1 − k/n)·n ≈ 10⁶` 次堆调整被省掉了。\n", "\n", "代价：多写一行代码、多一次字符串比较。收益：绝大多数行被 O(1) 拒掉。**这也是堆法在小 k 时耗时对 k 极不敏感的原因**——主体开销就是这一次次 O(1) 比较。\n", "\n", "
\n", "\n", "**3. 为什么 k = 100,000 时堆法反而比全排序慢？至少给出两个原因，并说明为什么\"O(n log k) < O(n log n)\"此时不再有指导意义。**\n", "\n", "
答案要点\n", "\n", "1. **命中率暴涨。** 从 `k/n = 10⁻⁵` 升到约 10%，约 10⁵ 次真实的堆调整，每次 `log₂(10⁵) ≈ 17` 层。\n", "2. **堆超出缓存。** 10 万个包装对象的堆有数 MB，远超 CPU 缓存，每次调整沿 17 层指针跳，几乎每次都是缓存未命中。\n", "3. **对面更强。** Timsort 是 C 实现、顺序访存，还能利用运行中发现的局部有序段。\n", "\n", "为什么复杂度记号失去指导意义：`O(n log k)` 里被当作常数的东西（一次比较的实际开销、一次堆调整的访存代价）在两种策略里**差别巨大**。堆法的\"一次操作\"是纯 Python 字节码 + 随机访存，全排序的\"一次操作\"是 C 代码 + 顺序访存。记号只比较操作次数，不比较单次操作的成本，也不比较访存模式。\n", "\n", "**结论**：k/n 超过百分之几就该重新实测，别照着复杂度记号选算法。\n", "\n", "
\n", "\n", "**4. 重复 title（ties）会让两种策略结果不同吗？如何让结果完全可复现？**\n", "\n", "
答案要点\n", "\n", "**在 title 序列上不会不同，在具体行上可能不同。**\n", "\n", "- `sort_and_cut`：由排序算法的稳定性与初始顺序决定（Python 的 Timsort 是稳定的，取原顺序靠前的那些行）。\n", "- `queue_based_scan`：由堆的内部结构决定，可能取到另一批同键行。\n", "\n", "但两法返回的 **title 序列必然一致**——单元测试正是按 title 比较的（`Book.__eq__` 也只比 title）。\n", "\n", "要完全可复现，给比较键追加一个唯一次级键，两法用同一个键：\n", "\n", "```python\n", "key=lambda b: (b.title, b.row_id)\n", "```\n", "\n", "这样同键行之间的先后顺序也被唯一确定，两种策略（以及任何稳定的实现）都会给出同一批行。\n", "\n", "
\n", "\n", "**5. 如果表有 1 亿行、单机内存装不下，两种策略各会遇到什么问题？堆法的 O(k) 内存优势此时体现在哪里？**\n", "\n", "
答案要点\n", "\n", "**全排序**：必须物化全部行（至少是全部排序键），装不下就要转**外部排序**——分批排序写入临时文件，再多趟归并（见实验 11）。I/O 次数随数据量增长，代价 `2N × 趟数` 页。PostgreSQL 里一旦超过 `work_mem`（默认 4 MB）就会走这条路。\n", "\n", "**堆扫描**：从头到尾只维护 k 行工作集，1 亿行流式扫过即可，内存依旧 O(k)，**永远不会触发外排**。\n", "\n", "这就是流式 / 管道执行器偏爱堆法的根本原因：它把一个可能落盘的排序，变成了一个纯流式的操作。\n", "\n", "外排序为什么要写盘？因为归并需要同时访问多个顺串的当前位置，内存放不下这些顺串，就只能把它们落到文件里再按页读回来。\n", "\n", "
\n", "\n", "**6. `LIMIT 10` 去掉 `ORDER BY` 后，数据库还需要排序吗？返回的 10 行有保证吗？**\n", "\n", "
答案要点\n", "\n", "**不需要排序。** 没有 `ORDER BY` 时 SQL 不承诺任何顺序，执行器可以任取 10 行（实际常表现为按扫描顺序返回前 10 行）。\n", "\n", "**返回的 10 行没有任何保证**：哪 10 行取决于执行计划、扫描顺序、并发情况，同一条 SQL 在不同版本或不同数据分布下可能返回不同的行。\n", "\n", "这也是本实验标题的另一半：同样的 `LIMIT`，带不带 `ORDER BY`，成本天差地别——一个只要 O(k)，一个要 O(n log n)。写 SQL 时必须清楚自己要的是哪一种。\n", "\n", "
\n", "\n", "**7. 若在 `title` 列上建有 B+ 树索引，执行器可以怎样不扫全表就回答这个查询？什么情况下索引方案会失效？**\n", "\n", "
答案要点\n", "\n", "**可行做法**：B+ 树的叶子层按键值有序并用链表串起来。执行器从最左叶子开始沿链顺序读，读满 10 行即停。成本 `O(log n + k)`——一次树下降定位到最左叶子（O(log n)），加上读 k 行。**与 n 的大小基本无关**，比任何扫描方案都快。\n", "\n", "**失效情形**：\n", "\n", "- 查询带了走不了该索引的谓词，例如 `WHERE author = 'X' ORDER BY title LIMIT 10` 而 `author` 上没有索引。此时必须先扫（或过滤）出候选集，再对候选集做 Top-k。\n", "- 需要按别的列排序：`ORDER BY price LIMIT 10`（索引在 `title` 上），索引有序性用不上。\n", "- `ORDER BY` 的方向与索引不一致且不支持反向扫描，或排序列上有表达式/函数。\n", "\n", "一般判据：**索引的有序性能否直接提供查询要求的顺序，以及过滤条件能否在该索引上被满足**。\n", "\n", "
\n", "\n", "**8. 把数据改成\"已按 title 基本有序\"（例如 90% 的行局部有序），Timsort 的表现会怎么变？堆扫描呢？这对计时实验的设计有什么提醒？**\n", "\n", "
答案要点\n", "\n", "- **Timsort 会显著变快。** 它专门检测数据中已有的升序 / 降序段（run）并直接归并这些段，基本有序的数据接近 O(n)。\n", "- **堆扫描几乎不变。** 它做的是流式比较，不利用全局有序性；命中率取决于数据分布，与是否已排序关系不大（已排序数据下命中集中在前段，但总比较次数仍是 n）。\n", "\n", "**对计时实验的提醒**：\n", "\n", "1. **必须用乱序随机数据测最坏情形。** 若无意中用了有序或部分有序的数据，会把全排序测得虚快，得到\"堆法没什么优势\"的错误结论。\n", "2. **两种策略必须在同一份数据上跑**，且各自跑在数据的**副本**上（排序会修改列表）。\n", "3. **多次运行取中位数**，用 `time.perf_counter()`；单次计时受 GC 与系统调度影响太大。\n", "\n", "
\n", "" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.3" } }, "nbformat": 4, "nbformat_minor": 5 }