OracleがもっていたソートアルゴリズムのUS7680791B2特許が昨年11月28日で期限切れとなり開放されました。
US7680791B2 - Method for sorting data using common prefix bytes - Google Patents
この記事で紹介されていた。
Expired Oracle Patent Opens Fast Sorting Algorithm to Open Source Databases - InfoQ
この記事で、「特許が詳細なのでAIに入れたらすぐ実装できる」みたいなことを書いてあったので、試しにClaudeさんに渡してみたらすぐ実装してくれた。
一応ソースのリンクは貼っておいたけど、自分で試してみると楽しいと思う。あと、解説も軽く書いたけど、リンク貼ってAIさんに聞くほうがいいと思う。
アルゴリズムとしては次の3つがキー
- Common Prefix Skipping Quicksort: CPS-QS
- キーの先頭の共通部分を比較しない()
- Key Substring Caching
- 共通プレフィクスの次の2バイトをキャッシュする
- Adaptive Quicksort(AQS)
- QuickSortとRadixSortを切り替えながら使う
まず3つにパーティションを分けるQuickSortを行って、共通プレフィクスが増えたらRadix Sortで共通プレフィクスの次のバイトで256分割して、さらにQuickSort、という感じ。
そうすると、データベースでよくある最初のn件を取得とか、メモリからあふれるときにディスクに書くとかと相性がよいということらしい。
最初はSonnetさんに実装してもらってベンチマークとかを作りこんで、それからOpusさんに最適化を頼んだら、ちゃんと実装されていないといって作り直してくれた。
https://gist.github.com/kishida/660d1993a3c64cd2437ea1f14bac2a81
結果的には、Javaの標準ソートのほうがだいたい速くて、やっぱJava標準ライブラリの最適化はすごいねぇとOpusさんも言ってました。
ところで、このアルゴリズムがOracle 10gR2に組み込まれたとき、ラリーエリソンから短い感謝のメールを受け取ったものの、昇進やボーナスはしばらくOracleに在籍しないとダメよってなったのが退職のきっかけだったという話で、世知辛い。
Small Datum: Common prefix skipping, adaptive sort
