Orasort借Oracle过期专利实现列排序提速5倍

背景

Oracle 是全球最流行的数据库产品之一，许多高度复杂的应用依赖 Oracle 存储关键数据和事务。为了提升数据库的速度和可靠性，Oracle 内部发明了大量优化技术。其中一项重要技术是针对数据库表的排序算法——Orasort。该算法由 Mark Callaghan 注册专利，能将排序速度提升 5 倍。Oracle 团队不仅巧妙实现了该算法，还在 CPU 级别进行了深度优化。该专利在 2024 年达到 20 年期限后自动失效，进入公有领域。这意味着云厂商（如 AWS）和开源社区现在可以自由使用 Orasort。

核心内容

传统排序在数据库中的运行方式

传统排序算法采用逐字符比较（即 1 字节比较）。例如，比较两个字符串 "Apple" 和 "Amazon" 时：

• 第一个字符都是 'A'，继续比较第二个字符。
• 'p' 与 'm' 比较，'m' < 'p'，排序结束。
• 升序结果为：Amazon, Apple。

更复杂的例子如 "Applet" 和 "Apples" 需要比较到最后一个字符；"Apple is good" 和 "Apple is bad" 则需要更多 CPU 周期。这种逐字节比较方式非常耗时。

Orasort 的工作原理

Orasort 利用 CPU 寄存器的天然特性。CPU 寄存器通常是 8 字节大小。Orasort 从两个字符串中各提取前 8 个字节，将其转换为一个 64 位整数。这样每个值变成单个 64 位整数，然后用同样的方式处理另一个待比较的值。如果比较结果可以决定顺序，则停止；否则，继续取下一个 8 字节，重复此过程。

这种方法将原本需要逐字节（1 字节）比较的循环，变成了 8 字节一块的比较，大幅减少了所需的寄存器和 CPU 周期，实现了约 5 倍的加速。

Orasort 的高层流程

1. 键提取与规范化
   假设表中有 1 万条记录，选中 "email" 列进行排序。这 1 万条记录会被加载到 RAM 的缓冲区中。不过，并非获取所有字段值，而是仅为每条记录生成键和 ID。这些记录被加载到排序区域（RAM 的一部分），然后开始 Orasort 的比较过程。

2. 处理海量数据
   如果记录数量达到数百万，Oracle 无法将所有记录指针加载到缓冲区。此时，Oracle 将数据分成多个部分存放在磁盘上，然后逐部分加载到 RAM 中排序。

3. 将排序数据写回磁盘
   写入是异步任务。Oracle 不会一次性写入所有排序结果，而是采用中间写入策略：在 Orasort 运行的同时持续写入数据。当全部排序完成后，最终在磁盘上进行合并。

关键要点

• 核心创新：将逐字节（1 字节）比较升级为 8 字节一块比较，利用 CPU 寄存器的 64 位整数运算，减少 CPU 周期。
• 性能提升：排序速度提升约 5 倍，直接提升 Oracle 数据库的查询与索引构建效率。
• 专利状态：Mark Callaghan 注册的 Orasort 专利在 2024 年到期，自动进入公有领域。
• 受益方：开源社区（MySQL、PostgreSQL 等已开始集成与实验）以及云服务商（如 AWS）均可免费使用该算法。
• 成本效益：由于减少了 CPU 周期，云服务的计算成本随之降低。
• 处理大规模数据：对于百万级记录，采用分块磁盘 I/O 与异步写入策略，避免内存溢出。
• 实现细节：键提取只保留排序所需的键和 ID，不加载完整记录，节省内存。

意义与影响

Orasort 进入公有领域对数据库行业和开源生态具有深远影响。传统逐字符排序是数据库性能的常见瓶颈之一，而 Orasort 提供了一种简单却高效的硬件利用思路。开源数据库（如 MySQL、PostgreSQL）可以直接集成该算法，无需再重复造轮子，从而提升自身竞争力。云服务商也能借此降低客户的计算成本，优化服务定价。此外，该案例展示了专利保护期满后技术普及的巨大价值——一项曾属于商业巨头的私有优化技术，如今成为全行业的公共财富，可能催生更多创新（如将类似思想应用于排序之外的字符串比较或数据压缩场景）。对于普通开发者而言，理解 Orasort 也加深了对 CPU 寄存器级别优化的认识，有助于编写更高效的代码。