クエリの最適化

クエリ最適化は、多くのリレーショナルデータベース管理システムや、 NoSQL、グラフデータベースなどの他のデータベースの機能です。クエリオプティマイザーは、可能なクエリプランを考慮して、特定のクエリを実行する最も効率的な方法を決定しようとします。^[1]

一般的に、クエリオプティマイザはユーザーが直接アクセスすることはできません。クエリがデータベースサーバーに送信され、パーサーによって解析されると、クエリオプティマイザに渡され、そこで最適化が行われます。^{[2] [3]ただし、一部のデータベースエンジンでは、}ヒントを使用してクエリオプティマイザをガイドできます。

クエリとは、データベースから情報を求めることです。クエリは、「社会保障番号123-45-6789 の人の住所を検索する」という単純なものから、「配偶者より収入が少ない 30 歳から 39 歳のカリフォルニア州の就業中の既婚男性全員の平均給与を検索する」という複雑なものまであります。クエリの結果は、要求された情報が得られるようにデータベースの行を処理することによって生成されます。データベース構造は複雑なため、ほとんどの場合、特にそれほど単純ではないクエリの場合、クエリに必要なデータは、さまざまな方法、さまざまなデータ構造、さまざまな順序でデータベースにアクセスすることによって収集できます。^[4]方法によって、通常、処理時間は異なります。同じクエリの処理時間は、選択した方法に応じて、1 秒未満から数時間まで、大きなばらつきがあります。自動化されたプロセスであるクエリ最適化の目的は、特定のクエリを最短時間で処理する方法を見つけることです。時間の大きな変動がクエリの最適化を実行する理由ですが、すべての可能性の中から最適なクエリ プランを正確に見つけることは、通常は非常に複雑で、それ自体に時間がかかり、コストがかかりすぎ、多くの場合は事実上不可能です。したがって、クエリの最適化では、通常、いくつかの常識的な代替案を比較して、妥当な時間内に「十分に良い」プランを提供することで、最適値を近似しようとします。このプランは、通常、最良の結果から大きく逸脱しません。

最適なクエリ プランを見つけるのにかかる時間と選択の質の間にはトレードオフがあります。オプティマイザは、最適な答えを自分で選択しない可能性があります。データベース管理システムの品質によって、この 2 つをバランスさせる方法が異なります。コストベースのクエリ オプティマイザは、さまざまなクエリ プランのリソース フットプリントを評価し、これをプラン選択の基準として使用します。^{[5] [6]}これらは、考えられる各クエリ プランに推定「コスト」を割り当て、コストが最も小さいプランを選択します。コストは、必要な I/O 操作の数、CPU パスの長さ、ディスク バッファ スペースの量、ディスク ストレージ サービス時間、並列処理ユニット間の相互接続の使用、およびデータ ディクショナリから決定されるその他の要素の観点から、クエリを評価する実行時コストを見積もるために使用されます。調査されるクエリ プランのセットは、考えられるアクセス パス (プライマリ インデックス アクセス、セカンダリ インデックス アクセス、フル ファイル スキャンなど) とさまざまなリレーショナル テーブル結合手法 (マージ結合、ハッシュ結合、製品結合など) を調べることによって形成されます。SQLクエリの複雑さによっては、検索空間が非常に大きくなることがあります。最適化には 2 つの種類があります。これらは、クエリを解決するためのリレーショナル代数のシーケンスを生成する論理最適化と、各操作を実行する手段を決定するために使用される物理最適化で構成されます。

ほとんどのクエリ オプティマイザは、クエリ プランを「プラン ノード」のツリーとして表します。プラン ノードは、クエリを実行するために必要な単一の操作をカプセル化します。ノードはツリーとして配置され、中間結果がツリーの下部から上部に流れます。各ノードには 0 個以上の子ノードがあります。子ノードは、出力が親ノードへの入力として送られるノードです。たとえば、結合ノードには 2 つの子ノードがあり、これらは 2 つの結合オペランドを表します。一方、ソート ノードには 1 つの子ノード (ソートされる入力) があります。ツリーの葉は、インデックススキャンやシーケンシャル スキャンを実行するなど、ディスクをスキャンして結果を生成するノードです。

クエリ プランのパフォーマンスは、主にテーブルを結合する順序によって決まります。たとえば、サイズがそれぞれ 10 行、10,000 行、1,000,000 行の 3 つのテーブル A、B、C を結合する場合、最初に B と C を結合するクエリ プランは、最初に A と C を結合するクエリ プランよりも実行に数桁長い時間がかかります。ほとんどのクエリ オプティマイザーは、IBM のSystem Rデータベース プロジェクト^{[引用が必要]によって開発された}動的プログラミングアルゴリズムを使用して結合順序を決定します。このアルゴリズムは、次の 2 つの段階で機能します。

1. まず、クエリ内の各リレーションにアクセスするすべての方法が計算されます。クエリ内のすべてのリレーションは、順次スキャンを介してアクセスできます。クエリ内の述語に答えるために使用できるリレーションにインデックスがある場合は、インデックス スキャンも使用できます。各リレーションについて、オプティマイザーは、リレーションをスキャンする最も安価な方法と、特定のソート順でレコードを生成するリレーションをスキャンする最も安価な方法を記録します。
2. 次に、オプティマイザは、結合条件が存在する関係の各ペアの結合を検討します。各ペアについて、オプティマイザはDBMSによって実装されている利用可能な結合アルゴリズムを検討します。オプティマイザは、特定の並べ替え順序に従って出力を生成する関係の各ペアを結合する最も安価な方法に加えて、関係の各ペアを結合する最も安価な方法も保持します。
3. 次に、前のフェーズで生成された各 2 リレーション プランをクエリ内の残りのリレーションと結合して、3 リレーション クエリ プランがすべて計算されます。

並べ替え順序により、クエリの処理中に後で発生する冗長な並べ替え操作を回避できます。また、特定の並べ替え順序では、データが特定の方法でクラスター化されるため、後続の結合が高速化されます。

現代のリレーショナル DBMS への SQL クエリは、選択と結合以上のことを行います。特に、SQL クエリは、group by、exists、not exists 演算子を使用して、SPJ ブロック (Select-Project-Join) の複数のレイヤーをネストすることがよくあります。場合によっては、このようなネストされた SQL クエリを select-project-join クエリにフラット化できますが、常にそうできるとは限りません。ネストされた SQL クエリのクエリ プランは、結合順序付けに使用されるのと同じ動的プログラミング アルゴリズムを使用して選択することもできますが、クエリの最適化時間が大幅に増加する可能性があります。そのため、一部のデータベース管理システムでは、クエリ グラフ モデルを使用する代替のルールベースのアプローチを使用しています。^[7]

クエリ最適化における最も難しい問題の 1 つは、代替クエリ プランのコストを正確に見積もることです。オプティマイザは、クエリ実行コストの数学的モデルを使用してクエリ プランのコストを算出します。このモデルは、クエリ プラン内の各エッジを通過するカーディナリティ、つまりタプルの数の推定値に大きく依存します。カーディナリティの推定値は、クエリ内の述語の選択係数の推定値に依存します。従来、データベース システムは、ヒストグラムなど、各列の値の分布に関するかなり詳細な統計値を使用して選択性を推定します。この手法は、個々の述語の選択性の推定に適しています。ただし、多くのクエリには、などの述語の結合があります。クエリ述語は多くの場合、相関性が高く (たとえば、を意味する)、一般に結合の選択性を推定するのは非常に困難です。カーディナリティの推定値が不十分で相関関係が捕捉されないことが、クエリ オプティマイザが不適切なクエリ プランを選択する主な理由の 1 つです。これは、データベース管理者が、特に大規模なデータのロード/アンロード後に、データベース統計情報を定期的に更新する必要がある理由の 1 つです。 select count(*) from R where R.make='Honda' and R.model='Accord'model='Accord'make='Honda'

従来のクエリ最適化では、クエリ プランが単一のコスト メトリック (通常は実行時間) に従って比較され、各クエリ プランのコストが不確実性なく計算できることを前提としています。実際には両方の前提が破られることがあり^[8]、研究文献ではこれらの制限を克服する従来のクエリ最適化の複数の拡張が研究されてきました。これらの拡張された問題のバリアントは、単一のクエリ プランのコストをモデル化する方法と最適化の目標の点で異なります。

従来のクエリ最適化では、各クエリ プランを 1 つのスカラー コスト値に関連付けます。パラメトリック クエリ最適化^[9]では、クエリ プランのコストは最適化時に値が不明なパラメータに依存すると想定しています。このようなパラメータは、たとえば、最適化時には完全に指定されていないが実行時に提供されるクエリ述語の選択性を表すことができます。したがって、パラメトリック クエリ最適化では、各クエリ プランを、多次元パラメータ空間から 1 次元コスト空間にマップするコスト関数に関連付けます。

最適化の目標は通常、考えられるパラメータ値の組み合わせすべてに対して最適となる可能性のあるすべてのクエリ プランを生成することです。これにより、関連するクエリ プランのセットが生成されます。実行時に、実際のパラメータ値が判明すると、そのセットから最適なプランが選択されます。パラメトリック クエリ最適化の利点は、最適化 (一般に非常にコストのかかる操作) が実行時に回避されることです。

多くの場合、実行時間に加えて、クエリ プランの比較に関連する他のコスト メトリックがあります。たとえば、クラウド コンピューティングのシナリオでは、実行にかかる時間だけでなく、実行コストの面でもクエリ プランを比較する必要があります。または、近似クエリ最適化のコンテキストでは、実行オーバーヘッドを削減して近似結果を取得するために、入力データのランダムに選択されたサンプルに対してクエリ プランを実行できます。このような場合、代替クエリ プランは、実行時間だけでなく、生成されるデータの精度や信頼性の面でも比較する必要があります。

多目的クエリ最適化^[10]は、クエリプランのコストをコストベクトルとしてモデル化し、各ベクトル要素が異なるコストメトリックに従ってコストを表します。従来のクエリ最適化は、コスト空間の次元（つまり、コストベクトル要素の数）が1である多目的クエリ最適化の特殊なケースと考えることができます。

異なるコスト メトリックは互いに矛盾する場合があります (たとえば、クラウド コンピューティング シナリオでは、実行時間が最小のプランと実行料金が最小の別のプランがある場合があります)。したがって、最適化の目標は、すべてのコスト メトリックを最小にするクエリ プランを見つけることではなく、さまざまなコスト メトリック間の最適な妥協点を実現するクエリ プランを見つけることです。最適な妥協点は、ユーザーの好みによって異なります (たとえば、クラウド シナリオでは、一部のユーザーはより安価なプランを好む一方で、他のユーザーはより高速なプランを好む場合があります)。したがって、最適化の目標は、オプティマイザーへの入力として提供されるユーザー設定の仕様に基づいて最適なクエリ プランを見つけること (たとえば、ユーザーは異なるコスト メトリック間の重みを定義して相対的な重要性を表現したり、特定のメトリックにハード コスト境界を定義したりできます)、またはパレート最適クエリ プランのセットの近似値 (つまり、すべてのメトリックに従って他のどのプランよりもコストが高くないプラン) を生成して、ユーザーがそのプラン セットから好ましいコスト トレードオフを選択できるようにすることです。

多目的パラメトリッククエリ最適化^[8]は、パラメトリックおよび多目的クエリ最適化を一般化します。プランは複数のコストメトリックに従って比較され、プランコストは最適化時に値が不明なパラメータに依存する場合があります。したがって、クエリプランのコストは、多次元パラメータ空間から多次元コスト空間への関数としてモデル化されます。最適化の目的は、パラメータ値とユーザーの好みの可能な組み合わせごとに最適なクエリプランのセットを生成することです。

多くのツールでは、クエリ実行プランを表示して、どの操作の処理コストが最も高いかを示します。Microsoft SMS、ApexSQLPlan、Hana、Tableau などがその例です。これらのプランで見つかった問題を修正すると、実行時間が数十パーセント短縮され、場合によっては 2 次元検索が線形検索に短縮される可能性があります。

最も基本的かつ単純な最適化チェックリストの 1 つは、ほとんどの RDMS が効率的に実行するように設計されている操作を使用することです。Sargable を参照してください。

• 参加選択要因
• クエリの書き換え
• 検索可能なクエリ