公共前缀跳过与自适应排序

# 共同前缀跳过，自适应排序 来源：http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html 专利US7680791B2（https://patents.google.com/patent/US7680791B2）已过期。我在Oracle工作期间发明了该算法，并纳入了10gR2（https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf），宣称相比Oracle此前使用的排序算法性能提升约5倍。希望有朝一日能看到开源实现。该专利对算法有很好的描述，比一般专利易读得多。幸好知识产权律师充分利用了我撰写的功能与设计文档。 该专利涉及一种新的内存排序算法，需要命名。特性包括： - 共同前缀跳过 - 自适应 - 键子串缓存 - 在排序完成前即可产生结果 **更新**： - 该排序算法需要一个名称，而*共同前缀跳过自适应快速排序*过于冗长。所以我建议命名为Orasort。 **由来** 2000年至2005年期间，我在Oracle从事查询处理工作。我不确定为何开始这项研究，并非上司或同事的建议。但当时Sort Benchmark（https://sortbenchmark.org/）竞赛正活跃，我也有更多时间阅读技术论文。或许我是受了Alphasort（https://www.cs.cmu.edu/~natassa/courses/15-721/papers/P233.PDF）论文的启发。 虽然Sort Benchmark推动了排序算法的最新技术水平，但也鼓励了那些非常适合基准测试的算法（专注于短键且均匀分布）。但数据库管理系统（DBMS）所排序的键往往远大于8字节，且相邻行的键常具有很长的共同前缀。 于是我在入睡前反复思考，经过许多个夜晚，我意识到：采用分治排序时，随着算法深入到数据子分区，每个子分区中键的共同前缀长度很可能会增长： - 如果算法能在下降过程中记住共同前缀的长度，则可以在比较时跳过共同前缀，从而降低CPU开销 - 如果算法能发现共同前缀长度增长，则可以从快速排序切换到最高有效位（MSD）基数排序，利用共同前缀之后的下一字节进行排序，之后再切回快速排序 - 算法可以将键中的字节缓存到一个数组中，类似Alphasort。但与Alphasort不同的是，随着算法深入，它可以缓存接下来需要比较的若干字节，而不仅仅是缓存键的前几个字节。这在内存系统行为方面表现更佳（更少的缓存缺失）。 **早期实现** 这大概是2003年，当时我们还无法在家访问工作电脑。我需要拿出成果来说服管理层这项工作值得投入。我在家中一台旧的基于PowerPC的Mac（https://en.wikipedia.org/wiki/Power_Macintosh）上开始了概念验证，这台机器在安装了Yellow Dog Linux（https://en.wikipedia.org/wiki/Yellow_Dog_Linux）后焕发了第二春。 经过几轮迭代，我在PowerPC上取得了良好结果。于是我把源代码带到工作场所，在其他我能接触到的CPU上重复测试。我的桌面上有一台Sun工作站和一台配备6年前的奔腾3 CPU（600MHz，128KB L2缓存）的Windows PC。在其他地方，我还能用到一台配备900MHz UltraSPARC IV（https://en.wikipedia.org/wiki/UltraSPARC_IV）（或IV+）CPU的新Sun服务器，以及一台配备PA RISC CPU的HP服务器。 我还实现了其他先进算法，包括Alphasort以及Oracle原有的排序算法。通过测试我了解到： 1. 当键大于8字节时，我的新排序算法远快于其他算法 2. 我的新排序算法在旧的奔腾3 CPU上比在Sun UltraSPARC IV上更快 第一点对我来说是个好消息，第二点对Sun的股东则不那么有利。我一直没搞清楚为什么UltraSPARC IV性能如此糟糕。可能是由于缓存延迟。 取得良好结果后，进入了功能和设计规范评审阶段。我记得有两个问题： - 旧排序是稳定的，新排序则不 - 新排序有一个糟糕但极不可能发生的最坏情况 当我在Oracle DBMS内实现这一算法后，得以与旧排序进行比较。新排序通常比旧排序快约5倍。之后我又将其与SyncSort进行比较。我不记得他们是否有DeWitt条款，所以我不分享具体结果，但我可以说，相比之下Oracle中的新排序表现非常出色。 **结局** 新排序最终纳入10gR2（https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf），并在白皮书中得到介绍。拉里·埃里森还给我发了一封简短的电邮，感谢我的工作。至于晋升或奖金则还需等待——在Oracle的职业生涯需要长期博弈。而这正是我离开Oracle所需的所有动力——先去了初创公司，然后到谷歌和Facebook。 离开Oracle后，我的大部分时间都用于改进MySQL。优秀的开源DBMS（如MySQL和PostgreSQL）对Oracle的新授权收入并不有利。Oracle是更好的DBMS，但并非所有人都需要或负担得起。