共通プレフィックススキッピング、アダプティブソート

Friday, January 2, 2026 Common prefix skipping, adaptive sort US7680791B2の特許が失効しました。私はOracleに在籍中にこれを発明し、以前のOracleで使用されていたソートアルゴリズムと比較して約5倍のパフォーマンス向上を謳って10gR2に搭載されました。いつかオープンソース実装が実現することを願っています。特許にはアルゴリズムの良い説明が含まれており、典型的な特許よりもはるかに読みやすいです。幸いなことに、IP弁護士は私が書いた機能設計書と設計書をうまく活用してくれました。 これは、名前が必要な新しいインメモリソートアルゴリズムの特許です。主な特徴は以下の通りです。 共通プレフィックススキッピング 可能な場合は、キーバイトのプレフィックスの比較をスキップします。 アダプティブ クイックソートと最上位桁基数ソートを切り替えます。 キーサブストリングキャッシング キーの次の数バイトをキャッシュすることでCPUキャッシュミスを減らします。 ソート完了前に結果を生成します。 ソートが完了する前に、ソート済み出力を（クエリの残りの部分に、または外部ソートのためにディスクにスピルするために）生成できます。 更新： ソートアルゴリズムには名前が必要で、「common prefix skipping adaptive quicksort」は長すぎます。そこで「Orasort」を提案します。 どのようにして生まれたか 2000年から2005年まで、私はOracleでクエリ処理を担当していました。なぜこの取り組みを始めたのかは定かではありませんし、上司や同僚から提案されたわけでもありません。しかし、ソートベンチマークコンテストが活発で、技術論文を読む時間がたくさんありました。おそらく、Alphasortの論文に触発されたのでしょう。 ソートベンチマークはソートアルゴリズムの技術水準を進歩させましたが、ベンチマークに適したアルゴリズム（短いキーで均一な分布に焦点を当てる）を奨励しました。しかし、DBMSによってソートされるキーは8バイトよりもはるかに長く、隣接する行はキーに長い共通プレフィックスを持つことがよくあります。 そこで、眠りにつく間にこのことを考え、多くの夜を経て、分割統治法ソートでは、アルゴリズムがデータのサブパーティションに下降するにつれて、各サブパーティションのキーの共通プレフィックスが長くなる可能性が高いことに気づきました。 アルゴリズムが下降中にキーの共通プレフィックスの長さを記憶できれば、比較中に共通プレフィックスをスキップしてCPUオーバーヘッドを節約できます。 共通プレフィックスの長さが長くなったときにアルゴリズムが学習できれば、クイックソートから最上位桁（MSD）基数ソートに切り替えて、共通プレフィックスの次のバイトを使用し、その後クイックソートに戻ることができます。 アルゴリズムは、Alphasortのように、キーからバイトを配列にキャッシュできます。しかし、Alphasortとは異なり、下降するにつれて、キーの最初の数バイトのみをキャッシュするのではなく、比較に必要な次の数バイトをキャッシュできます。これにより、メモリシステム（キャッシュミスが少ない）の動作が大幅に改善されます。 初期実装 これは2003年頃、自宅から会社のコンピューターにアクセスできるようになる前かもしれません。経営陣にこれがやる価値があることを納得させる結果を得る必要がありました。私は自宅にあった古いPowerPCベースのMacで概念実証を開始しました。Yellow Dog Linuxをインストールした後、このMacは第二の人生を得ました。 いくつかのイテレーションの後、PowerPCで良好な結果が得られました。そこで、ソースコードを職場に持ち込み、他のCPUでテストを繰り返しました。デスクにはSunワークステーションと、6年前のPentium 3 CPU（600MHz、128kb L2キャッシュ）を搭載したWindows PCがありました。その他、900MHz UltraSPARC IV（またはIV+）CPUを搭載した新しいSunサーバーと、PA RISC CPUを搭載したHPサーバーにアクセスできました。 また、Alphasortを含む他の最先端アルゴリズムと、Oracleが使用していた古いソートアルゴリズムも実装しました。テストから学んだことは以下の通りです。 私の新しいソートは、キーが8バイトより大きい場合に他のアルゴリズムよりもはるかに高速でした。 私の新しいソートは、Sun UltraSPARC IVよりも古いPentium 3 CPUの方が高速でした。 最初の点は私にとって素晴らしいニュースでしたが、2番目の点はSunの株主にとってはあまり良いニュースではありませんでした。UltraSPARC IVのパフォーマンスがなぜ悪かったのか、私は決して知りませんでした。キャッシュへのレイテンシが原因だったのかもしれません。 実際の Среализация 素晴らしい結果が得られたので、機能設計と設計レビューの時期が来ました。2つの問題点を覚えています。 古いソートは安定していましたが、新しいソートは安定していませんでした。 この懸念がどのように対処されたかは覚えていません。 新しいソートには、悪いが可能性は低い最悪ケースがあります。 問題は、クイックソートがピボットを選択するたびに最悪のピボットを選択する場合の最悪ケースです。新しいソートは単純ではなく、ピボットを選択するたびにキーのサンプルのメディアンを使用していました（サンプルサイズは5だったかもしれません）。そこで、リスクを推定するために数学的な計算を行いました。数値が大きく確率が小さいことを考えると、任意精度演算をサポートするライブラリまたはツールが必要になり、Scheme実装を使用することになりました。ほとんどの場合の速度向上は、ごく一部の場合のリスクを正当化しました。 そして、Oracle DBMS内にこれを実装した後、古いソートと比較することができました。新しいソートは、古いソートよりも約5倍高速であることが多かったです。次に、SyncSortと比較しました。DeWitt Clauseがあったかどうかは覚えていないので結果は共有しませんが、Oracleの新しいソートは比較すると素晴らしかったと言えます。 終わり 新しいソートは10gR2に搭載され、ホワイトペーパーで紹介されました。ラリー・エリソンから感謝の短いメールも受け取りました。昇進やボーナスは、Oracleでのキャリアでは長期的な視点が必要だったため、待たなければなりませんでした。そして、それが私がOracleを離れるための唯一の動機となりました。まずスタートアップへ、そしてGoogleとFacebookへと移りました。 Oracleを離れた後、MySQLを改善することに多くの時間を費やしました。MySQLやPostgreSQLのような優れたオープンソースDBMSは、Oracleの新しいライセンス収入には貢献しませんでした。Oracleはより優れたDBMSですが、誰もが必要とするわけでも、誰もが購入できるわけでもありません。 January 02, 2026 Email ThisBlogThis!Share to XShare to FacebookShare to Pinterest Labels: oracle, sort 5 comments: Alexey January 2, 2026 at 12:36 PM > A promotion or bonus would have to wait as you had to play the long-game in your career at Oracle What's that long game is then? ReplyDeleteReplies Mark Callaghan January 2, 2026 at 3:42 PM Ignoring the good times during the dot-com boom, rewards (mostly promotions) tended to be delayed relative to what I experienced elsewhere. So if you do good work and stay there long enough then you will be promoted, but your peers at other companies were moving up faster. DeleteRepliesReply Mikael Ronstrom January 2, 2026 at 1:43 PM The parallel sort problem is still interesting, one of my most recent changes to RonDB was to implement a parallel sorted index scan. RonDB uses sharded partitions (from an ordered index point of view). So each partition delivers rows in sorted order, but a merge sort is required to provide the results in global sorted order. Previously this led to a "single-threaded" sorted index scan, but now it is parallelised by implementing a capability for partitions to continue scanning while waiting for the "next" message. However the merge sort itself can probably be improved and made multi-threaded. I will read your blog to see if there are some interesting tidbits that can improve the speed even more. ReplyDeleteReplies Mark Callaghan January 2, 2026 at 3:46 PM Yes, parallel is interesting. Given the Oracle architecture for parallel operations, I didn't have to solve for that. For fast merge: 1) there are optimizations for an N-way heap and RocksDB uses some of them, Google AI had a nice overview for me via https://www.google.com/search?q=rocksdb+n-way+heap+merge 2) offset-value coding can help, but wasn't widely known. Thankfully, Goetz Graefe is making it known again and if you check the references to IBM at the end of the paper there are things that make merges faster, especially reference 7 -- https://arxiv.org/abs/2210.00034 DeleteRepliesReply Mikael Ronstrom January 2, 2026 at 5:23 PM Thx, will have a look DeleteRepliesReply ReplyAdd comment Load more... Newer Post Older Post Home Subscribe to: Post Comments (Atom) CPU-bound sysbench on a large server: Postgres 12 to 19 beta1 This has results from sysbench on a small server with Postgres versions 12 through 19 beta1. Sysbench is run with high concurrency (40 conne... LSM math: revisiting t