跳过公共前缀与自适应排序算法新技术亮相

背景

2000年至2005年，作者在 Oracle 从事查询处理相关工作。当时 Sort Benchmark 竞赛正在如火如荼地进行，受 Alphasort 论文启发，作者开始思考如何改进数据库管理系统（DBMS）中的排序算法。传统的排序算法在短键、均匀分布的场景下表现优异，但在实际数据库环境中，排序键常常远大于8字节，且相邻行的键往往具有很长的公共前缀。作者在睡前反复思考，经过多个夜晚的构思，最终发明了一种新的内存排序算法。该算法获得了美国专利 US7680791B2，并被集成到 Oracle 10gR2 中，声称比 Oracle 之前使用的排序算法性能提升约5倍。如今该专利已过期，作者期待有开源实现的诞生。

核心内容

该专利描述的是一种需要命名的全新内存排序算法，其主要特性包括：

1. 公共前缀跳过：在可能的情况下，跳过对键字节公共前缀的比较。
2. 自适应切换：在快速排序（quicksort）和最高有效位基数排序（most-significant digit radix sort）之间动态切换。
3. 键子串缓存：通过缓存键的后续字节来减少 CPU 缓存未命中。
4. 排序完成前输出结果：可以在排序尚未完成时，将已排序的输出提供给查询的后续部分，或溢出到磁盘用于外部排序。

由于“公共前缀跳过自适应快速排序”这个名称过于冗长，作者建议将其命名为 Orasort。

算法如何工作

在分治排序过程中，随着算法深入到数据的子分区，每个子分区中键的公共前缀长度往往会增长：

• 如果算法能够在递归下降时记住公共前缀的长度，就可以在比较时跳过该前缀，从而节省 CPU 开销。
• 如果算法能够检测到公共前缀长度增长，就可以从快速排序切换为基于公共前缀下一个字节的 MSD 基数排序，完成后再切回快速排序。
• 算法可以像 Alphasort 一样将键的字节缓存在数组中，但与 Alphasort 不同，它在递归下降时缓存接下来需要比较的字节，而不是仅缓存键的前几个字节，从而显著改善内存系统行为（减少缓存未命中）。

当键长度超过8字节时，Orasort 比许多其他算法快得多。作者在旧款 Pentium 3 CPU 上的测试结果甚至比 Sun UltraSPARC IV 更好。

实际实现中的考量

• 稳定性：旧的排序算法是稳定的，而新算法不稳定。作者不记得当时如何解决这一顾虑。
• 最坏情况：新算法存在一个不太可能发生但很糟糕的最坏情况——当快速排序每次选择枢轴时都选到最差枢轴。但新算法并不天真，它每次从键样本中选取中位数作为枢轴（样本大小可能为5）。作者使用 Scheme 实现任意精度算术库，计算了风险概率，认为在大多数情况下性能提升足以弥补少数情况下的风险。
• 离开 Oracle 后，作者将大部分时间投入到改进 MySQL 上。他认为像 MySQL 和 PostgreSQL 这样优秀的开源 DBMS 对 Oracle 的新许可收入不利。Oracle 是更好的 DBMS，但并非所有人都需要或负担得起。

关键要点

• 核心创新：公共前缀跳过与自适应排序切换相结合，大幅减少不必要的比较和缓存未命中。
• 性能优势：在键长度大于8字节时表现尤为突出，在 Pentium 3 上甚至优于高端 Sun UltraSPARC IV。
• 命名建议：作者提议将这种新算法命名为 Orasort，以代替冗长的“公共前缀跳过自适应快速排序”。
• 专利状态：专利 US7680791B2 已过期，为开源实现扫清了障碍。
• 稳定性与最坏情况：新算法非稳定，且存在理论上的最坏情况，但实际风险极低。
• 开放态度：作者希望未来能有开源实现，让社区受益。

意义与影响

该专利的过期意味着 Orasort 算法可以自由地应用于开源项目和商业产品中，无需支付专利许可费。对于数据库系统、大数据处理、搜索引擎等重度依赖排序操作的领域，这一算法可能带来显著的性能提升，尤其是在处理长键和具有公共前缀的数据集时（如字符串排序、多列排序）。自 Oracle 10gR2 以来的实证表明，5倍左右的性能提升并非夸张。如果 MySQL、PostgreSQL 或其他开源数据库能够集成该算法，将有助于缩小与 Oracle 在排序性能上的差距，降低用户的数据库成本。此外，算法中“排序进行中部分输出”的特性对查询流水线和外部排序场景也很有价值。总的来说，Orasort 的开放是数据库和数据处理领域的一个积极信号，有望推动下一代排序技术的应用。