
引言: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)



