一项 20 年前的 Oracle 排序算法专利到期，开源数据库集体受益

作者 | Renato Losio

译者 | 田橙

近日，一篇文章披露，Oracle 公司一项关于高速排序方法的 专利已经到期，这意味着开源数据库可以自由使用这一算法。该排序算法的发明者 Mark Callaghan 指出，这种诞生于 20 年前的技术，能够显著加速对相似数据的排序过程，有望让数据库系统在性能和效率上实现进一步提升。

这项编号为 US7680791B2 的专利于 2010 年授予 Oracle Corporation，描述了一种利用“公共前缀字节”进行数据排序的方法。Callaghan 建议将这一排序算法称为 “Orasort”。该方法的核心目标，是解决排序过程中反复比较相似键值前缀所带来的效率问题。

具体而言，该算法融合了多种技术手段，包括：在比较键值时跳过公共前缀、在快速排序（quicksort）与基数排序（radix sort）之间自适应切换、缓存键值子串以减少缓存未命中，以及在排序尚未完全结束时提前输出部分结果。

由于排序过程中数据会被拆分为更小的分组，组内键值往往共享更长的前缀。该算法会记录这些共享部分，在比较时直接跳过它们；在合适的情况下切换到更高效的排序方式；并预先加载下一步所需的字节，从而减少无效计算、提升整体性能。

Callaghan 曾先后任职于 Oracle、Google 和 Facebook，是资深数据库专家。他回顾了这一专利的诞生过程，并解释了其当下重新受到关注的原因：

我是在 Oracle 工作期间发明了这个算法，它最终被集成进 10gR2 版本中，官方宣称相比 Oracle 之前使用的排序算法，性能提升约 5 倍。我一直希望有一天能看到它的开源实现。这项专利对算法的描述非常清晰，比大多数专利都更容易阅读。值得庆幸的是，负责知识产权的律师充分利用了我当时撰写的功能和设计文档。

这一消息迅速引发社区关注，开发者开始讨论如何将该算法引入并优化 MySQL、PostgreSQL 等数据库系统。Flooid.in 的 CTO、ScaleArc 前创始人 Varun Singh 表示：

细节完整到这种程度，你甚至可以把它和专利文档一起丢进一个 AI agent 里，直接开始实现。Mark 太厉害了。

在另一条讨论中，Google 的数据库工程师 Hannu Krosing 尝试借助 Gemini，分别使用 Python、C 和 C++ 对该算法进行了实现。文章指出，Oracle 内存排序算法在当年实现了约 5 倍于旧方案的性能提升，甚至因此收到了 Oracle 创始人 Larry Ellison 的致谢邮件。Callaghan 回忆道：

当我把它集成进 Oracle DBMS 后，就能直接与旧排序算法对比。新算法通常快了大约 5 倍。后来我又把它和 SyncSort 做了比较。我不记得他们是否有 DeWitt Clause（限制公开对比结果的条款），所以不便透露具体数据，但可以说，Oracle 的新排序算法在对比中表现非常出色。

对此，Charles Thayer 评论道：

我以前从没认真考虑过，一个排序算法在什么时候可以输出第一个结果，以尽早开始响应流、降低延迟。（快速排序在这方面应该相对有优势。）这项工作很有意思。

截至目前，Oracle 共持有超过 52,000 项专利，其中仍包含大量与数据库技术相关的专利，例如自管理数据库架构、数据库性能优化方法等，涵盖自动调优、高效数据存储等数据库管理的多个关键领域。

https://www.infoq.com/news/2026/01/oracle-patent-sorting-databases/

声明：本文为 InfoQ 翻译，未经许可禁止转载。