一項 20 年前的 Oracle 排序算法專利到期，開源數(shù)據(jù)庫集體受益

作者 | Renato Losio

譯者 | 田橙

近日，一篇文章披露，Oracle 公司一項關(guān)于高速排序方法的 專利已經(jīng)到期，這意味著開源數(shù)據(jù)庫可以自由使用這一算法。該排序算法的發(fā)明者 Mark Callaghan 指出，這種誕生于 20 年前的技術(shù)，能夠顯著加速對相似數(shù)據(jù)的排序過程，有望讓數(shù)據(jù)庫系統(tǒng)在性能和效率上實現(xiàn)進一步提升。

這項編號為 US7680791B2 的專利于 2010 年授予 Oracle Corporation，描述了一種利用“公共前綴字節(jié)”進行數(shù)據(jù)排序的方法。Callaghan 建議將這一排序算法稱為 “Orasort”。該方法的核心目標(biāo)，是解決排序過程中反復(fù)比較相似鍵值前綴所帶來的效率問題。

具體而言，該算法融合了多種技術(shù)手段，包括：在比較鍵值時跳過公共前綴、在快速排序（quicksort）與基數(shù)排序（radix sort）之間自適應(yīng)切換、緩存鍵值子串以減少緩存未命中，以及在排序尚未完全結(jié)束時提前輸出部分結(jié)果。

由于排序過程中數(shù)據(jù)會被拆分為更小的分組，組內(nèi)鍵值往往共享更長的前綴。該算法會記錄這些共享部分，在比較時直接跳過它們；在合適的情況下切換到更高效的排序方式；并預(yù)先加載下一步所需的字節(jié)，從而減少無效計算、提升整體性能。

Callaghan 曾先后任職于 Oracle、Google 和 Facebook，是資深數(shù)據(jù)庫專家。他回顧了這一專利的誕生過程，并解釋了其當(dāng)下重新受到關(guān)注的原因：

我是在 Oracle 工作期間發(fā)明了這個算法，它最終被集成進 10gR2 版本中，官方宣稱相比 Oracle 之前使用的排序算法，性能提升約 5 倍。我一直希望有一天能看到它的開源實現(xiàn)。這項專利對算法的描述非常清晰，比大多數(shù)專利都更容易閱讀。值得慶幸的是，負(fù)責(zé)知識產(chǎn)權(quán)的律師充分利用了我當(dāng)時撰寫的功能和設(shè)計文檔。

這一消息迅速引發(fā)社區(qū)關(guān)注，開發(fā)者開始討論如何將該算法引入并優(yōu)化 MySQL、PostgreSQL 等數(shù)據(jù)庫系統(tǒng)。Flooid.in 的 CTO、ScaleArc 前創(chuàng)始人 Varun Singh 表示：

細(xì)節(jié)完整到這種程度，你甚至可以把它和專利文檔一起丟進一個 AI agent 里，直接開始實現(xiàn)。Mark 太厲害了。

在另一條討論中，Google 的數(shù)據(jù)庫工程師 Hannu Krosing 嘗試借助 Gemini，分別使用 Python、C 和 C++ 對該算法進行了實現(xiàn)。文章指出，Oracle 內(nèi)存排序算法在當(dāng)年實現(xiàn)了約 5 倍于舊方案的性能提升，甚至因此收到了 Oracle 創(chuàng)始人 Larry Ellison 的致謝郵件。Callaghan 回憶道：

當(dāng)我把它集成進 Oracle DBMS 后，就能直接與舊排序算法對比。新算法通常快了大約 5 倍。后來我又把它和 SyncSort 做了比較。我不記得他們是否有 DeWitt Clause（限制公開對比結(jié)果的條款），所以不便透露具體數(shù)據(jù)，但可以說，Oracle 的新排序算法在對比中表現(xiàn)非常出色。

對此，Charles Thayer 評論道：

我以前從沒認(rèn)真考慮過，一個排序算法在什么時候可以輸出第一個結(jié)果，以盡早開始響應(yīng)流、降低延遲。（快速排序在這方面應(yīng)該相對有優(yōu)勢。）這項工作很有意思。

截至目前，Oracle 共持有超過 52,000 項專利，其中仍包含大量與數(shù)據(jù)庫技術(shù)相關(guān)的專利，例如自管理數(shù)據(jù)庫架構(gòu)、數(shù)據(jù)庫性能優(yōu)化方法等，涵蓋自動調(diào)優(yōu)、高效數(shù)據(jù)存儲等數(shù)據(jù)庫管理的多個關(guān)鍵領(lǐng)域。

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

聲明：本文為 InfoQ 翻譯，未經(jīng)許可禁止轉(zhuǎn)載。