引言：SQL 是算法的宝库
SQL（Structured Query Language）是一种声明式语言。用户只需指定'想要什么'（What），而无需关心'如何实现'（How）。这个'How'就是数据库管理系统（DBMS）如 PostgreSQL、MySQL、Oracle 等需要解决的问题。数十年来，数据库领域的专家们将无数经典的算法和数据结构优化后融入 DBMS 的核心引擎中，使得一条简单的 SQL 语句背后可能是数个诺贝尔奖级别算法的高效协作。
理解这些算法，不仅能让我们写出更高效的 SQL，更能将这些思想应用于其他的编程和系统设计场景中。
第一章：排序算法（ORDER BY）
SQL 语句：SELECT * FROM users ORDER BY age DESC, name ASC;
原理与实现
DBMS 不会在所有场景下都使用一种排序算法。它会根据数据量、内存大小、是否涉及索引等因素智能选择最优策略。
- 内存排序（当数据可完全放入内存）：
- 快速排序（Quicksort）：是内排序中最常见的算法。它是一种分治算法，通过选择一个'基准'元素将数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。平均时间复杂度为 O(n log n)。
- 内省排序（Introsort）：是 C++ STL
sort()的实现，也可能是现代 DBMS 的选择。它结合了快速排序、堆排序和插入排序的优点：- 开始使用快速排序。
- 当递归深度超过一定 level（如
log(n)）时，转为堆排序（Heapsort）以避免快排的最坏情况 O(n²)。 - 当数据量很小（如 < 16）时，转为插入排序（Insertion Sort），因为插入排序在小数组上常数因子极小，非常快。
- 外部排序（当数据量巨大，无法放入内存）：
- 归并排序（Merge Sort）：是外部排序的基石。其核心是'分而治之'和'归并'。
- 实现步骤（以两路归并为例）：
- 阶段一：排序阶段 (Run Generation)：
- 数据库每次读取一定数量的数据页（Page）到内存中。
- 用内排序算法（如快排）对这些数据进行排序。
- 将排序好的数据作为一个'有序段'（Sorted Run）写回磁盘。重复此过程，直到处理完所有数据，生成多个有序段。
- 阶段二：合并阶段 (Merge Phase)：
- 打开所有有序段文件。
- 每次从每个有序段中读取一部分数据到内存的'输入缓冲区'。
- 使用一个'最小堆'或简单的比较，从所有缓冲区当前元素中选出最小的（或最大的，取决于 ORDER BY）输出到'输出缓冲区'。
- 输出缓冲区满则写回磁盘，并清空。
- 当一个输入缓冲区为空时，从对应的有序段文件中读取下一批数据。
- 重复直到所有有序段的数据都被处理完毕，最终生成一个完全有序的大文件。
- 阶段一：排序阶段 (Run Generation)：
代码文字实现（外部排序简化版）：
def external_sort(data_iterator, chunk_size, key_func):
"""外部排序生成器"""
runs = []
:
chunk = []
:
_ (chunk_size):
chunk.append((data_iterator))
StopIteration:
chunk:
chunk.sort(key=key_func)
run_file = write_chunk_to_disk(chunk)
runs.append(run_file)
iterators = [(read_chunk_from_disk(run)) run runs]
heap = []
i, it (iterators):
:
value = (it)
heapq.heappush(heap, (key_func(value), i, value, it))
StopIteration:
heap:
key, idx, value, it = heapq.heappop(heap)
value
:
next_value = (it)
heapq.heappush(heap, (key_func(next_value), idx, next_value, it))
StopIteration:
run runs:
os.remove(run)
