共通プレフィックススキッピング、アダプティブソート
Common prefix skipping, adaptive sort (smalldatum.blogspot.com)
要約
この記事は、データベースソートアルゴリズムにおける「共通プレフィックススキッピング」と「アダプティブソート」という革新的な技術について解説しています。これらの技術は、特にキーが長い場合にソートパフォーマンスを大幅に向上させ、Oracle Database 10gR2に実装されました。
全文翻訳
特許 US7680791B2 の期限が切れました。これは私がOracle在籍中に考案したもので、10gR2 に搭載され、Oracleが当時使用していたソートアルゴリズムと比較して約5倍の性能向上が謳われました。いつかオープンソース実装が実現することを願っています。特許にはアルゴリズムの良い説明が含まれており、典型的な特許よりもはるかに読みやすいです。幸いなことに、IP弁護士は私が書いた機能設計書と設計書をうまく活用してくれました。
この特許は、名前が必要な新しいインメモリソートアルゴリズムに関するものです。主な特徴は以下の通りです。
- 共通プレフィックスのスキップ
- 可能な限りキーバイトのプレフィックスの比較をスキップします。
- 適応的
- クイックソートと最上位桁(MSD)ラディックスソートを切り替えます。
- キー部分文字列キャッシュ
- キーの次の数バイトをキャッシュすることで、CPUキャッシュミスを削減します。
- ソート完了前に結果を生成
- ソートが完了する前に、ソート済みの出力を(クエリの残りの部分に、または外部ソートのためにディスクにスピルして)生成できます。
更新:
- ソートアルゴリズムには名前が必要ですが、「common prefix skipping adaptive quicksort」は長すぎます。そこで、Orasort を提案します。
誕生の経緯
2000年から2005年まで、私はOracleでクエリ処理を担当していました。この取り組みをなぜ始めたのかは定かではありませんし、上司や同僚から指示されたわけでもありません。しかし、Sort Benchmark コンテストが活発で、技術論文を読む時間が多くありました。おそらく Alphasort の論文に触発されたのかもしれません。
Sort Benchmark はソートアルゴリズムの技術水準を進歩させましたが、ベンチマークに適したアルゴリズム(短いキーで均一な分布に焦点を当てる)を奨励する側面もありました。しかし、DBMSでソートされるキーは多くの場合8バイトよりも長く、隣接する行のキーには長い共通プレフィックスが含まれることがよくあります。
そこで、眠りにつく際にこのことを考え続け、多くの夜を経て、分割統治法によるソートでは、アルゴリズムがデータのサブパーティションに下降するにつれて、各サブパーティション内のキーの共通プレフィックスが長くなる可能性が高いことに気づきました。
- アルゴリズムが下降中に共通プレフィックスの長さを記憶できれば、比較中に共通プレフィックスをスキップしてCPUオーバーヘッドを節約できます。
- アルゴリズムが共通プレフィックスの長さが長くなるタイミングを学習できれば、クイックソートから次のバイトを使用して最上位桁(MSD)ラディックスソートに切り替え、その後クイックソートに戻ることができます。
- Alphasort のように、キーからバイトを配列にキャッシュできます。しかし、Alphasort とは異なり、下降するにつれて、キーの最初の数バイトのみをキャッシュするのではなく、比較に必要な次の数バイトをキャッシュできます。これにより、メモリシステム(キャッシュミスが少ない)の動作が大幅に改善されます。
初期実装
これは2003年頃、自宅から職場にアクセスできるようになる前かもしれません。経営陣にこれがやる価値があることを納得させるための結果が必要でした。私は自宅にあった古い PowerPCベースのMac で概念実証を開始し、Yellow Dog Linux をインストールして第二の人生を得ました。
いくつかの試行錯誤を経て、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ですが、誰もが必要としているわけでも、誰もがそれを購入できるわけでもありません。