クエリ最適化

クエリ最適化とは

クエリ最適化は、データベース管理システム（DBMS）において、データへの問い合わせ（クエリ）を最も効率的に実行するための方法を決定する重要な機能です。クエリオプティマイザとも呼ばれ、入力されたクエリに対して複数の実行計画を評価し、コストが最も低い計画を選択します。

クエリ最適化の仕組み

クエリ最適化は、ユーザーが直接操作することはなく、データベースサーバーにクエリが発行された後、パーサーによる構文解析を経て、クエリオプティマイザに処理が渡されます。クエリオプティマイザは、考えられる実行計画を評価し、コストを算出して最適な計画を決定します。

コストとは

コストは、クエリの実行時コストであり、入出力（I/O）操作数、CPU時間などから算出されます。クエリの実行計画は、可能なアクセス経路（インデックス検索、シーケンシャル検索）と結合アルゴリズム（ソートマージ結合、ハッシュ結合、入れ子ループ）の組み合わせから生成されます。入力されたSQL クエリによっては、探索空間が非常に大きくなることがあります。

クエリ実行計画の表現

クエリ最適化では、クエリ実行計画を「計画ノード」による木構造で表現することが一般的です。各ノードには、クエリ実行に必要な1つの操作が格納されており、木の底から頂点に向かって中間結果が伝播していくように見ることができます。各ノードは0個以上の子ノードを持ち、子ノードの出力が親ノードの入力として使用されます。たとえば、結合ノードは2つの子ノードを持ち、それぞれが結合の2つのオペランドを表します。

結合の順序

クエリ実行計画の性能は、テーブルを結合する順序に大きく依存します。例えば、3つのテーブルA（10行）、B（100万行）、C（100万行）を結合する場合、BとCを先に結合するよりもAとBを先に結合する方が効率的です。多くのクエリ最適化では、自然結合の順序を動的計画法アルゴリズムで決定します。

動的計画法 アルゴリズム

このアルゴリズムは、以下の2段階で動作します。

1. アクセス方法の決定：
クエリ内のすべてのテーブルへのアクセス方法を決定します。シーケンシャル検索やインデックス検索など、テーブルへのアクセス方法を検討し、最もコストの低い方法を記録します。
2. 結合方法の決定：
テーブル間の結合条件を調べ、利用可能な結合アルゴリズムの中から最もコストの低い方法を選択します。同時に、ソートされた順序で結果を生成する方法も考慮します。

これにより、最終的なクエリ実行計画が生成されます。特に注目すべきは、「interesting order」と呼ばれるソートされた結果を生成する計画も考慮される点です。同じコストの計画が複数存在する場合、ソート順が良い方が選択されます。これにより、後続の処理でのソート処理が不要になったり、データの局所性が高まって高速化が期待できます。

Left-deepクエリ実行計画

歴史的には、System Rのクエリ最適化はleft-deepクエリ実行計画のみを考慮していました。これは、2つのテーブルを結合した結果と次のテーブルを結合していく方式です。この方式は、考慮する計画数を減らすことができますが、最適な実行計画を見逃す可能性もあります。しかし、入れ子ループなどの結合アルゴリズムでは、一度に外側のテーブルの1つのタプルのみを必要とするという特性から、メモリ上に保持すべきタプル数を少なくできるという利点があります。

その後、クエリ最適化は、より複雑なクエリ実行計画にも拡張され、並列処理を考慮した計画も扱えるようになりました。

入れ子型SQL クエリの最適化

近年のRDBMSでは、SQL クエリは複雑化しており、入れ子構造になっていることがよくあります。入れ子型SQL クエリを平坦化して1つのクエリに変換できる場合もありますが、常に可能なわけではありません。入れ子型SQL クエリの実行計画にも、従来の動的計画法を適用できますが、計算時間が膨大になることがあります。そこで、一部のDBMSでは、クエリのグラフモデルを使ったルールベースの手法を採用しています。

コスト見積もり

クエリ最適化において最も困難な問題の一つは、複数のクエリ実行計画のコストを正確に見積もることです。オプティマイザは、クエリ実行コストの数学的モデルを使って実行計画を見積もります。このモデルは、クエリ計画の結果の濃度（タプル数）に大きく依存しており、クエリ内の述語の選択結果の見積もりに影響を受けます。

データベースシステムは、ヒストグラムなどの統計情報を使って、各属性の値の分布を詳細に把握しています。しかし、クエリには複数の述語が組み合わされていることが多く、述語間の相関関係を考慮する必要があります。述語の相関関係を正確に捉えることが難しい場合、不適切な実行計画が選択される可能性があります。そのため、データベース管理者は定期的に統計情報を更新する必要があります。

まとめ

クエリ最適化は、DBMSの性能を左右する重要な要素であり、効率的なデータ処理を実現するために不可欠です。DBMSの進化と共に、最適化の手法も複雑化していますが、その本質は常に効率的なクエリ実行計画を見つけることにあります。

クエリ最適化