甲骨文新排序算法性能提升约5倍，发明背后故事揭秘！

发布时间：2026/7/11 4:34:14

2026年1月2日，星期五

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

专利 [US7680791B2](https://patents.google.com/patent/US7680791B2) 已过期，这是作者在甲骨文（Oracle）工作时发明的。它 [被应用于10gR2版本](https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf)，与甲骨文之前使用的排序算法相比，性能提升了约5倍。作者期待有一天能看到它的开源实现。该专利对算法有很好的描述，得益于知识产权律师充分利用了作者撰写的功能和设计文档，比一般的专利更容易阅读。

该专利涉及一种新的内存排序算法，目前还缺个合适的名称。其特点如下：

公共前缀跳过：在可行的情况下，跳过比较键字节的前缀部分。
自适应：在快速排序（quicksort）和最高有效位基数排序（most - significant digit radix sort）之间切换。
键子串缓存：缓存键的接下来几个字节，减少CPU缓存未命中情况。
排序完成前产生结果：在排序完成前，就可产生排序后的输出，提供给查询的其余部分，或溢出到磁盘进行外部排序。

更新：这种排序算法需要个名称，“公共前缀跳过自适应快速排序（common prefix skipping adaptive quicksort）”太长，作者建议叫“Orasort”。

它的诞生过程

2000年至2005年，作者在甲骨文从事查询处理工作。作者不清楚自己为何开始这项工作，老板和同事也没提过相关建议。当时 [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 一样，将键中的字节缓存到一个数组中。不同的是，它在深入子分区时可缓存接下来需要比较的几个字节，而非仅键的前几个字节，能显著改善内存系统性能，减少缓存未命中情况。

早期实现

大概在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二级缓存）的Windows PC。此外，作者还能使用一台配备900MHz [UltraSPARC IV](https://en.wikipedia.org/wiki/UltraSPARC_IV)（或IV +）CPU的新Sun服务器，以及一台配备PA RISC CPU的HP服务器。

作者还实现了其他一些先进算法，包括 Alphasort 和甲骨文之前使用的排序算法。测试发现：

当键大于8字节时，作者的新排序算法比其他算法快得多。
在作者那台旧的奔腾3 CPU上，新排序算法的速度比在Sun UltraSPARC IV上更快。

第一个发现对作者是好消息，第二个发现对Sun的股东来说就不乐观了。作者一直没弄明白UltraSPARC IV性能差的原因，可能是缓存延迟问题。

实际实现

取得出色测试结果后，就进入功能和设计规范评审阶段。作者记得有两个问题：

稳定性问题：旧的排序算法稳定，新的排序算法不稳定，作者不记得当时如何解决这个问题。
最坏情况问题：新排序算法存在一种不太可能出现但很糟糕的最坏情况，问题在于快速排序每次选基准都选到最坏的基准。不过新算法不简单，它每次从键的样本中选取中位数作为基准（样本大小可能是5）。于是作者进行数学计算评估风险，由于涉及数字大、概率小，作者需要一个支持任意精度算术的库或工具，最终用Scheme实现。在大多数情况下，性能提升足以弥补少数情况下的风险。

在甲骨文数据库管理系统中实现该算法后，作者将其与旧的排序算法比较，结果显示新排序算法通常比旧算法快约5倍。之后，作者又将其与SyncSort比较，作者不记得他们是否有DeWitt条款，所以不分享具体结果，但可以说，甲骨文的新排序算法表现非常出色。

结局

新的排序算法 [被应用于10gR2版本](https://www.oracle.com/technetwork/database/performance/twp-general-sort-performance-10gr2--130000.pdf)，并在一篇白皮书中得到介绍。作者还收到拉里·埃里森（Larry Ellison）的一封简短邮件，感谢作者所做的工作。不过在甲骨文，晋升和奖金都需要长期积累，这成了作者离开甲骨文的动力——先是去了一家初创公司，然后又去了谷歌和Facebook。

离开甲骨文后，作者大部分时间花在改进MySQL上。像MySQL和PostgreSQL这样优秀的开源数据库管理系统，对甲骨文的新许可证收入构成挑战。虽然甲骨文是更强大的数据库管理系统，但并非每个人都需要或负担得起它。

关于我

[Mark Callaghan](https://www.blogger.com/profile/09590445221922043181)，更多信息请访问：https://smalldatum.github.io/ ，[查看我的完整资料](https://www.blogger.com/profile/09590445221922043181)

博客存档

[2026](http://smalldatum.blogspot.com/2026/)（33篇）
- [6月](http://smalldatum.blogspot.com/2026/06/)（6篇）
- [4月](http://smalldatum.blogspot.com/2026/04/)（6篇）
- [3月](http://smalldatum.blogspot.com/2026/03/)（8篇）
- [2月](http://smalldatum.blogspot.com/2026/02/)（6篇）
- [1月](http://smalldatum.blogspot.com/2026/01/)（7篇）
  - [24核CPU上CPU密集型插入基准测试与Postgres对比……](http://smalldatum.blogspot.com/2026/01/cpu-bound-insert-benchmark-vs-postgres.html)
  - [24核及……上IO密集型插入基准测试与MySQL对比](http://smalldatum.blogspot.com/2026/01/io-bound-insert-benchmark-vs-mysql-on.html)
  - [24核及……上CPU密集型插入基准测试与MySQL对比……](http://smalldatum.blogspot.com/2026/01/cpu-bound-insert-benchmark-vs-mysql-on.html)
  - [在IO密集型sysbench测试中调试Postgres的性能回归……](http://smalldatum.blogspot.com/2026/01/debugging-regressions-with-postgres-in.html)
  - [小型服务器上Postgres与tproc - c对比](http://smalldatum.blogspot.com/2026/01/postgres-vs-tproc-c-on-small-server.html)
  - [固态硬盘、掉电保护和fsync延迟](http://smalldatum.blogspot.com/2026/01/ssds-power-loss-protection-and-fsync.html)
  - [公共前缀跳过、自适应排序](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html)
[2025](http://smalldatum.blogspot.com/2025/)（63篇）
[2024](http://smalldatum.blogspot.com/2024/)（101篇）
[2023](http://smalldatum.blogspot.com/2023/)（131篇）
[2022](http://smalldatum.blogspot.com/2022/)（46篇）
[2021](http://smalldatum.blogspot.com/2021/)（36篇）
[2020](http://smalldatum.blogspot.com/2020/)（60篇）
[2019](http://smalldatum.blogspot.com/2019/)（62篇）
[2018](http://smalldatum.blogspot.com/2018/)（36篇）
[2017](http://smalldatum.blogspot.com/2017/)（84篇）
[2016](http://smalldatum.blogspot.com/2016/)（36篇）
[2015](http://smalldatum.blogspot.com/2015/)（51篇）
[2014](http://smalldatum.blogspot.com/2014/)（55篇）

评论区

[Alexey](https://www.linkedin.com/in/localstorm/) [2026年1月2日下午12:36](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment=1767386216445#c6613696980973391273)
在甲骨文，晋升和奖金都需要长期的积累。
那么，这个“长期积累”具体指什么呢？
[Mark Callaghan](https://www.blogger.com/profile/09590445221922043181) [2026年1月2日下午3:42](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment=1767397330998#c1851529451284273066) 抛开互联网泡沫时期的美好时光不谈，与作者在其他地方的经历相比，甲骨文的奖励（主要是晋升）往往会有所延迟。所以，如果你工作表现出色并在那里长期任职，最终会得到晋升，但你在其他公司的同行可能晋升得更快。
[Mikael Ronstrom](https://www.blogger.com/profile/07134215866292829917) [2026年1月2日下午1:43](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment=1767390181735#c8246368621724999725)
并行排序问题仍然很有趣。作者最近对RonDB做的一项改进是实现了并行排序索引扫描。RonDB使用分片分区（从有序索引的角度来看）。因此，每个分区都会按排序顺序输出行，但需要进行合并排序才能以全局排序顺序提供结果。以前，这会导致“单线程”排序索引扫描，而现在通过实现分区在等待“下一个”消息时可以继续扫描的功能，实现了并行化。不过，合并排序本身可能还有改进的空间，可以将其改为多线程。作者会阅读博客，看看是否有一些有趣的技巧可以进一步提高速度。
[Mark Callaghan](https://www.blogger.com/profile/09590445221922043181) [2026年1月2日下午3:46](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment=1767397595450#c8844772379816237931) 是的，并行排序很有趣。由于甲骨文的并行操作架构，作者当时不需要解决这个问题。
对于快速合并排序，有以下建议：
1. N路堆有一些优化方法，RocksDB就采用了其中一些方法。谷歌AI通过 [这篇文章](https://www.google.com/search?q=rocksdb+n-way+heap+merge) 为作者提供了很好的概述。
2. 偏移值编码可能会有帮助，但这种方法并不广为人知。值得庆幸的是，Goetz Graefe正在重新推广它。如果你查看论文末尾对IBM的引用，会发现一些可以加快合并速度的方法，特别是引用7——[https://arxiv.org/abs/2210.00034](https://arxiv.org/abs/2210.00034)。
[Mikael Ronstrom](https://www.blogger.com/profile/07134215866292829917) [2026年1月2日下午5:23](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment=1767403381716#c3119258184993776810) 谢谢，作者会去看看。