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 CPU600MHz128KB二级缓存的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这样优秀的开源数据库管理系统对甲骨文的新许可证收入构成挑战。虽然甲骨文是更强大的数据库管理系统但并非每个人都需要或负担得起它。相关文章链接[大型服务器上CPU密集型sysbench测试Postgres 12到19 beta1](http://smalldatum.blogspot.com/2026/06/cpu-bound-sysbench-on-large-server.html)展示了在小型服务器上使用Postgres 12到19 beta1版本进行sysbench测试的结果。[LSM数学重新审视最小化写放大的层数](http://smalldatum.blogspot.com/2019/01/lsm-math-revisiting-number-of-levels.html)用数学方法解释了采用分层压缩的LSM树中最小化写放大的层数。[固态硬盘、掉电保护和fsync延迟](http://smalldatum.blogspot.com/2026/01/ssds-power-loss-protection-and-fsync.html)介绍了对使用O_DIRECT打开的文件每次写入时调用fsync或fdatasync的影响进行测量的结果。[在Ubuntu 22.04上管理AMD CPU频率](http://smalldatum.blogspot.com/2024/10/managing-cpu-frequency-for-amd-on.html)讲述了为使用于基准测试的服务器具备稳定性能且不过热所做的工作。关于我[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篇标签[ann - benchmarks](http://smalldatum.blogspot.com/search/label/ann-benchmarks)9篇[benchmark](http://smalldatum.blogspot.com/search/label/benchmark)2篇[clang](http://smalldatum.blogspot.com/search/label/clang)1篇[database economics](http://smalldatum.blogspot.com/search/label/database%20economics)14篇[db_bench](http://smalldatum.blogspot.com/search/label/db_bench)21篇[fsync](http://smalldatum.blogspot.com/search/label/fsync)3篇[gcc](http://smalldatum.blogspot.com/search/label/gcc)1篇[hammerdb](http://smalldatum.blogspot.com/search/label/hammerdb)5篇[history](http://smalldatum.blogspot.com/search/label/history)16篇[informix](http://smalldatum.blogspot.com/search/label/informix)1篇[innodb](http://smalldatum.blogspot.com/search/label/innodb)122篇[insert benchmark](http://smalldatum.blogspot.com/search/label/insert%20benchmark)32篇[jemalloc](http://smalldatum.blogspot.com/search/label/jemalloc)5篇[leveldb](http://smalldatum.blogspot.com/search/label/leveldb)14篇[linux](http://smalldatum.blogspot.com/search/label/linux)2篇[lua](http://smalldatum.blogspot.com/search/label/lua)1篇[m](http://smalldatum.blogspot.com/search/label/m)1篇[malloc](http://smalldatum.blogspot.com/search/label/malloc)4篇[mariadb](http://smalldatum.blogspot.com/search/label/mariadb)27篇[mongodb](http://smalldatum.blogspot.com/search/label/mongodb)114篇[myrocks](http://smalldatum.blogspot.com/search/label/myrocks)83篇[mysql](http://smalldatum.blogspot.com/search/label/mysql)471篇[mysql. innodb](http://smalldatum.blogspot.com/search/label/mysql.%20innodb)2篇[oracle](http://smalldatum.blogspot.com/search/label/oracle)2篇[percona](http://smalldatum.blogspot.com/search/label/percona)1篇[performance](http://smalldatum.blogspot.com/search/label/performance)23篇[pgvector](http://smalldatum.blogspot.com/search/label/pgvector)9篇[postgres](http://smalldatum.blogspot.com/search/label/postgres)149篇[postgresql](http://smalldatum.blogspot.com/search/label/postgresql)86篇[profound](http://smalldatum.blogspot.com/search/label/profound)4篇[qdrant](http://smalldatum.blogspot.com/search/label/qdrant)1篇[rant](http://smalldatum.blogspot.com/search/label/rant)14篇[regressions](http://smalldatum.blogspot.com/search/label/regressions)4篇[review](http://smalldatum.blogspot.com/search/label/review)3篇[rocksdb](http://smalldatum.blogspot.com/search/label/rocksdb)305篇[sort](http://smalldatum.blogspot.com/search/label/sort)1篇[speedb](http://smalldatum.blogspot.com/search/label/speedb)1篇[splinterdb](http://smalldatum.blogspot.com/search/label/splinterdb)1篇[sql](http://smalldatum.blogspot.com/search/label/sql)1篇[sysbench](http://smalldatum.blogspot.com/search/label/sysbench)74篇[tcmalloc](http://smalldatum.blogspot.com/search/label/tcmalloc)2篇[tproc - c](http://smalldatum.blogspot.com/search/label/tproc-c)5篇[vacuum](http://smalldatum.blogspot.com/search/label/vacuum)1篇[vector](http://smalldatum.blogspot.com/search/label/vector)9篇[wiredtiger](http://smalldatum.blogspot.com/search/label/wiredtiger)1篇评论区[Alexey](https://www.linkedin.com/in/localstorm/) [2026年1月2日 下午12:36](http://smalldatum.blogspot.com/2026/01/common-prefix-skipping-adaptive-sort.html?showComment1767386216445#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?showComment1767397330998#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?showComment1767390181735#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?showComment1767397595450#c8844772379816237931) 是的并行排序很有趣。由于甲骨文的并行操作架构作者当时不需要解决这个问题。对于快速合并排序有以下建议N路堆有一些优化方法RocksDB就采用了其中一些方法。谷歌AI通过 [这篇文章](https://www.google.com/search?qrocksdbn-wayheapmerge) 为作者提供了很好的概述。偏移值编码可能会有帮助但这种方法并不广为人知。值得庆幸的是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?showComment1767403381716#c3119258184993776810) 谢谢作者会去看看。