Implementing Sorting in Database Systems

[mrdrivingduck]

Implementing_Sorting.pdf

虽然大部分人对内存排序算法和外存排序算法都比较熟悉，但商业数据库内实现的排序各有各的不同。本文旨在为研究者介绍 DBMS 中的一些实用但鲜为人知的排序技术。

为了保证商用数据库的实用性，排序算法必须在较易维护的同时，在不同的 workload 和操作条件下都保持有效性和鲁棒性。因为 DBMS 中可能用到排序的地方太多了：

• 用户需要排序后的查询结果 ORDER BY
• 逻辑一致性校验（外键约束检验）
• 物理一致性校验（索引匹配检验）
• 非结构化数据处理
• 压缩、复制、恢复

本文主要讨论查询处理中的排序，以及维护 B-Tree 索引的排序。这两种排序需要解决的问题基本覆盖了排序需要解决的全部问题。

本文聚焦三种排序：

• 内存排序：除了广为人知的快速排序、堆排序，还讨论了与 CPU cache 以及加速比较相关的技术
• 外部排序：除了外部归并排序，还讨论了其各类变种
• 专门为数据库场景实现的排序优化技术，如内存管理

本文假设数据库是一个关系型数据库，内存远不够装下所有数据。不考虑排序的 稳定性，因为任何排序算法都能够通过为 key 添加一个 rank 来使排序稳定。

[mrdrivingduck]

2. Internal Sort: Avoiding and Speeding Comparisions

2.1 Comparision-Based Sorting versus Distrubtion Sort

传统的数据库排序都是由基于比较的排序算法实现的，比如快速排序或内部归并排序；而不是基于分布的排序算法，比如基数排序。然而，基于比较的排序一定会包含条件分支，这就导致了潜在的分支预测失败引发 CPU 的 stall。虽然现代 CPU 有着高效的分支预测硬件，但是数据库内排序的比较结果是不可预测的。这就让基于分布的排序算法有了吸引力。

虽然基于分布的排序算法有着更少的 CPU stall 和更少的 data cache 或 TLB miss，但暂未取代 DBMS 内基于比较的排序算法。原因如下：

1. 如果排序的 key 过长，或排序 key 包含重复，那么会为算法引入额外的复杂性
2. 基数排序仅当数据均匀分布时最有效，但这个前提很难被满足
3. 如果输入数据已经大部分有序，那么基数排序的最初几趟排序非常低效
4. Cache efficiency -> small runs?

2.2 Normalized Keys

内存排序的两个主要操作：

1. 键值比较（或其它对 key 的操作，比如基数排序）
2. 数据移动

优化第一个步骤是非常复杂的，因为排序有时涉及到多个列，每个列有着自己的数据类型、长度、排序方向等。

由于每一条记录在一次排序中都会参与很多次比较，因此在排序前后对记录进行 reformat 看似是值得的。比如，当对一百万条记录进行排序时，每条记录都会参与超过 20 次的比较；如果比较牵扯到多个列及其数据类型、长度、精度、排序顺序，那么一次比较将需要几百条指令。如果使用对每一条记录进行编码和解码后可以加速排序，且编码和解码的代价小于这几百条指令，那么键值比较是可以被优化的。

快速比较的最优格式是简单的二进制字符串，因为其既保留了顺序，又不会造成信息丢失，还能够轻易利用硬件上的加速。对复杂 key 的比较可以简化为十几条指令的字符串比较，并能够在比较完之后把字符串复原为记录。因此，排序 key 的 normalization 很早就出现在 DBMS 内了。

一些 key 规范化的例子：

• 如果排序 key 跨越多个列，那么将多个列的编码拼接
• 倒序排序：将 key 的编码按位取反
• NULL 值处理：如果 NULL 值被视为是最小值，那么编码为 0-bit
• 无符号整数：对大端存放的数据需要更改字节序
• 带符号整数：以浮点数的形式编码
• 国际化字符：使用 OS 或库提供的内置函数转换为可比较的字符串
• 变长字符串：使用小于任何合法字符的字符作为终结符

格式化主要针对会被排序的 key，但也可以应用到整条记录上。如果预先知道某些列不需要被排序，那么在编码时，这些列可以不需保持顺序，快速拷贝到编码中。

[mrdrivingduck]

2.3 Order-Preserving Compression

对数据压缩，但保留数据间的大小顺序关系。效率没有无序压缩高，但优于完全不压缩。

2.4 Cache-Optimized Techniques

现在处理器可以在一个时钟周期内执行多条指令，而一次 cache miss 可能会浪费几十个甚至上百个时钟周期。因此，使排序比较时的指令数量减少，不如减少 cache miss 的有效性更高。其中，减少代码尺寸相当重要，尤其是内层循环的比较操作。Key 的规范化使得原先复杂的比较操作的指令数量大大减少，直至能够完全放入 CPU cache。

数据 cache 和指令 cache 同样重要。通过将数据结构进行内存对齐，或者将数据移动变为指针移动，都可以减少数据 cache miss。