Orasort: Oracleの失効した特許により5倍高速なカラムソート
Orasort: 5x faster column-sorting with an expired patent from Oracle (deepsystemstuff.com)
要約
Oracleが開発したOrasortというカラムソートアルゴリズムの特許が2024年に失効し、パブリックドメインとなりました。このアルゴリズムは、CPUレジスタを活用して従来の文字単位の比較よりも約5倍高速なソートを実現します。これにより、オープンソースデータベースやクラウドコンピューティング分野でのコスト削減に貢献しています。
全文翻訳
Orasortとは? Oracleのソートアルゴリズムを分かりやすく解説
Oracleのソートアルゴリズムの特許が失効し、パブリックドメインになりました。それがOrasortです。
Oracleは世界で最も人気のあるデータベース製品の一つです。
非常に複雑なアプリケーションが、クリティカルなデータやトランザクションのためにOracleに依存しています。
Oracleは、データベースをより高速で信頼性の高いものにするために、多くの最適化技術を発明する必要がありました。
その発明の一つが、データベーステーブルのためのソート技術です。
OracleはOrasortというアルゴリズムを発明し、ソート速度を5倍にしました。Oracleチームはそれをインテリジェントに実装しただけでなく、CPUレベルで最適化しました。
この記事では、経験のないプログラマーでも理解できるような簡単な言葉でOrasortアルゴリズムを説明します。
このアルゴリズムの特許はMark Callaghanによって登録されていました。
2024年に20年の期間が満了した後、Orasortの特許は自動的に失効し、パブリックドメインに入りました。
このアルゴリズムがどのように機能するか、AWSのようなクラウド企業やオープンソースコミュニティがどのような恩恵を受けているか、その他の重要なことを見ていきます。
Orasortの仕組みを理解する前に、従来のソートがどのように機能し、それがOracleのパフォーマンスにどのような影響を与えていたかを理解する必要があります。
DBMSにおける従来のソートの仕組み
この記事はR/Programmingで10時間トップランクでした。ぜひ最後までお読みください。
文字単位のソート
従来のソートアルゴリズムでは、一方の文字列の各文字が、もう一方の文字列の対応する文字と比較されます。
ソートは、2つの文字列間で文字ごとに実行されます。
最初の文字だけでソートするのではなく、例えば「A」で始まる値の場合、データベースは「A」で始まる値もソートする必要があります。
以下の例を考えてみましょう。
「A」で始まる2つの値があります。
Apple
Amazon
ここで、これらの2つの単語間のソートが始まります。
両方の単語で「A」は同じです。
次に、2番目の文字を調べる必要があります。「P」と「M」が比較され、M < P であるため、2番目の文字に基づいて決定が行われます。
昇順は次のようになります。
Amazon
Apple
上記の比較は簡単でした。DBMSは2文字しか比較する必要がありませんでした。
次に、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バイトを取得し、比較を続行します。
私たちを購読して、生涯無料コンテンツを入手してください。
MicrosoftがSQL ServerをMicrosoft Windowsと統合しようとした方法はこちら
Orasortが提供するメリット
オープンソースデータベース
公開されて以来、Orasortはオープンソースコミュニティに多大なメリットをもたらしています。
MySQLやPostgreSQLを含むオープンソースデータベースはOrasortを統合し、実験を行っています。
クラウドコンピューティングのコスト削減
企業はビジネスのためにクラウドサービスを利用しています。OrasortはCPUサイクルの削減により運用コストを低減します。
DSS (DeepSystemStuff) では、週に2〜3回、深く調査された記事を公開しています。プログラミング言語の基本から、Linuxの内部構造、ガベージコレクタの内部構造、VM Wareの内部構造、Kubernetesのソースコード解説など、複雑な記事まで、DSSですべての記事を見つけることができます。
Orasortのハイレベルなプロセス
キーの抽出と正規化
テーブルに1万件のレコードがあり、'email'という名前のカラムがソートのために選択されたとします。
すると、1万件のレコードがバッファにロードされます。
ただし、これらのレコードはすべての値とともにフェッチされるわけではありません。各レコードのキーとIDのみが生成されます。
これらのレコードはソート領域にロードされ、そこでソートが行われます。
ここで、前述したOrasortプロセスが、RAMの一部であるこのソート領域で実行されます。
しかし、レコードが数百万件ある場合はどうでしょうか? Oracleはすべてのレコードポインタをバッファにロードできません。
この場合、Oracleはデータの複数の部分を作成し、後で使用するためにディスクに保持します。その後、それらの部分を1つずつRAMにロードします。
ソート済みデータをディスクに書き戻す
書き込みは非同期タスクであり、Oracleは一度にすべてのソート済みデータを書き込むアプローチを取りません。
中間書き込みアプローチを使用しており、Orasortが実行されている間に書き込みを続けます。書き込みが完了すると、最終的なマージがディスク上で行われます。