Orasort: Oracleの失効した特許により5倍高速なカラムソート

Oracleのソートアルゴリズムの特許が失効し、パブリックドメインで利用可能になりました。 Oracleは世界で最も人気のあるデータベース製品の一つです。非常に複雑なアプリケーションが、その重要なデータとトランザクションのためにOracleに依存しています。Oracleは、データベースをより高速で信頼性の高いものにするために、多くの最適化技術を発明しなければなりませんでした。それらの発明の一つが、データベーステーブルのソート技術です。OracleはOrasortというアルゴリズムを発明し、ソートを5倍高速化しました。Oracleチームは、それをインテリジェントに実装しただけでなく、CPUレベルでも最適化しました。この記事では、プログラマー経験のない人でも理解できるように、Orasortアルゴリズムを簡単な言葉で説明します。 このアルゴリズムの特許はMark Callaghanによって登録されました。2024年に20年の期間が満了した後、Orasortの特許は自動的に失効し、パブリックドメインに入りました。このアルゴリズムがどのように機能するか、AWSのようなクラウド企業やオープンソースコミュニティがどのようなメリットを得ているか、その他の重要なことを見ていきます。 Orasortがどのように機能するかを理解する前に、従来のソートがどのように機能し、それがOracleのパフォーマンスにどのように影響したかを理解する必要があります。 DBMSにおける従来のソートの仕組み 文字単位のソート 従来のソートアルゴリズムでは、一方の文字列の各文字が、もう一方の文字列の対応する文字と比較されます。ソートは、文字列間で文字ごとに実行されます。最初の文字だけをソートするのではなく、例えば「A」で始まる値の場合、データベースは「A」で始まる値だけでなく、「A」で始まる値もソートする必要があります。 以下の例を考えてみましょう。 「A」で始まる値が2つあります。 Apple Amazon 今、この2つの単語の間でソートが始まります。「A」は両方の単語で同じです。次に、2番目の文字を調べる必要があります。「P」が「M」と比較され、M < P であるため、2番目の文字に基づいて決定が行われます。昇順は次のようになります。 Apple Amazon 上記の比較は簡単でした。DBMSは2文字を比較するだけで済みました。次に、次の例を考えてみましょう。 Applet Apples この場合、最後の文字まで比較が続き、昇順は次のようになります。 Apples Applet 次の例を考えてみましょう。 Apple is good Apple is bad この場合、比較にはより多くのCPUサイクルが必要になります。昇順は次のようになります。 Apple is bad Apple is good このように、従来のソートは機能します。どれほど時間がかかるか想像できるでしょう。 Orasortが救世主として登場 従来のソート方法は、文字単位の比較、つまり1バイト比較を使用していました。Orasortは、OracleチームがCPUレジスタを活用した非常にスマートなアイデアを考案しました。CPUレジスタは自然に8バイトのサイズであるため、Oracleが2つの文字列から8バイトを抽出して比較する場合、比較にはより少ないレジスタとより少ないCPUサイクルが必要です。Oracleは両方の値から最初の8バイトを抽出し、それらのバイトを64ビット整数に変換します。次に、各値は単一の64ビット整数になり、比較されるもう一方の値でも同じプロセスが発生します。決定が下された場合、比較は停止します。そうでない場合は、次の8バイトを取得し、比較を続行します。 生涯無料コンテンツを購読してください。購読フォーム メール 購読 Orasortが提供するメリット オープンソースデータベース 公開されて以来、Orasortはオープンソースコミュニティに多大なメリットをもたらしています。MySQLやPostgreSQLを含むオープンソースデータベースは、Orasortを統合し、実験を行っています。 クラウドコンピューティングのコスト削減 企業はビジネスのためにクラウドサービスを使用しています。Orasortは、CPUサイクルの削減により運用コストを低減します。 DSS（DeepSystemStuff）では、週に2〜3回、深く調査された記事を公開しています。ぜひ訪問してください。 Orasortのハイレベルプロセス キー抽出と正規化 テーブルに1万件のレコードがあり、「email」という名前の列がソートのために選択されたとします。その場合、1万件のレコードがバッファにRAMにロードされます。ただし、これらのレコードはすべての値とともにフェッチされるわけではありません。各レコードに対してキーとIDのみが生成されます。これらのレコードは、ソートが行われるソート領域にロードされます。ここで、前述のOrasortプロセスが、RAMの一部であるこのソート領域で実行されます。しかし、レコードが数百万件ある場合はどうでしょうか？Oracleはすべてのレコードポインタをバッファにロードすることはできません。この場合、Oracleはデータの複数の部分を作成し、将来の使用のためにディスクに保持します。その後、それらの部分を一度に1つずつRAMにロードします。 ソートされたデータをディスクに書き戻す 書き込みは非同期タスクであり、Oracleは一度にすべてのソート済みデータを書き込むアプローチを取りません。中間書き込みアプローチを使用しており、Orasortが実行されている間、書き込みを継続します。書き込みが完了すると、最終的なマージがディスク上で行われます。 DSSは通常のテックブログではありません。私たちはオープンソースプロジェクトを研究し、テックジャーナリストとして行動し、ほぼすべてのテクニカルプラットフォームに関する深い技術情報をお届けします。購読を検討してください。私たちは、このような記事への生涯無料アクセスが得られるコミュニティを構築しています。購読フォーム メール 購読