クエリ最適化

出典: フリー百科事典『ウィキペディア（Wikipedia）』

クエリ最適化（—さいてきか、Query optimization）とは、多くのデータベース管理システム (DBMS) の持つ機能であり、クエリを実行する最も効率的な方法を決定する。クエリオプティマイザ（Query optimizer）とも言う。クエリオプティマイザは、入力されたクエリについて考えられるクエリ実行計画群を評価し、どれが最も効率的か決定する。コストに基づいたクエリオプティマイザでは、個々の計画のコストを見積もり、最もコストの低い計画を選ぶ。コストはクエリ実行時コストであり、入出力(I/O)操作数、CPU時間、その他から決定する。評価されるクエリ実行計画群は、可能なアクセス経路（例えば、インデックス検索、シーケンシャル検索）と結合アルゴリズム（例えば、ソートマージ結合、ハッシュ結合、入れ子ループ）の組み合わせから生成される。探索空間は入力されたSQLクエリによっては非常に大きくなる可能性もある。

クエリ最適化をユーザーが直接操作することはできない。クエリがデータベースサーバ (DBMS) に対して発行され、パーサーが構文解析すると、その結果がクエリオプティマイザに送られ、クエリ最適化が行われる。

参考: 関係代数#問い合わせ最適化

[編集] 実装

クエリ最適化では、クエリ実行計画を「計画ノード」による木構造で表現することが多い。計画ノードにはクエリ実行に必要な1つの操作が格納されている。そのようなノードを木構造に配置すると、木の底から頂点に向かって中間結果が上がってくると見ることができる。各ノードには0個以上の子ノードがあり、それら子ノードの出力が親ノードの入力として使用される。例えば、結合ノードには2個の子ノードがあり、それぞれが結合の2つのオペランド (演算対象) となっている。一方、ソートノードの子ノードは1つである（ソートすべきオペランド）。葉の部分のノードはディスクを検索した結果を生み出し、例えばインデックス検索やシーケンシャル検索を行う。

[編集] 結合の順序

あるクエリ実行計画の性能は表の結合順序に大きく依存する。例えば、3つの表 A（10行）、B（1,000,000行）、C（1,000,000行）を結合する場合、B と C を先に結合する計画の方が A と C を先に結合する計画よりも遥かに時間がかかる。多くのクエリ最適化では、自然結合 (Join) の順序を動的計画法アルゴリズムで決定する。これはIBMのSystem Rプロジェクトで採用された方法である。このアルゴリズムは次のように2段階で動作する:

まず、クエリ内の全ての関係にアクセスする全ての方法を求める。クエリ内の各関係はシーケンシャル検索でアクセスできる。ある関係のインデックスがクエリ内の述語の回答として使える場合、インデックス検索も使用可能である。各関係について、オプティマイザは関係を検索する最も安価な方法を記録し、同時に特定のソートされた順のレコード群を生成する関係検索の最も安価な方法も記録する。
次にオプティマイザは関係間の結合条件を調べる。それぞれの関係のペアについて、オプティマイザはそのDBMSに実装された使用可能な結合アルゴリズムを調べる。そしてそれぞれの関係のペアを結合する最も安価な方法を保持すると同時に、特定のソートされた順の出力を生成する結合方法も保持する。
そして、上で求められた2つの関係の結合フェーズの結果と3つめの関係も含めたクエリ実行計画のコストを計算する。

このようにして、クエリ実行計画は最終的にその関係についての全てのクエリの結合を生成する。注意すべき点として、このアルゴリズムでは interesting order と呼ばれるソートされた結果を生成するクエリ実行計画も保持しているのである。動的計画法では、あるクエリ実行計画と別のクエリ実行計画が同じコストならソート順がよい方を選ぶ。これは2つの理由により行われる。まず、特定のソート順ではクエリ処理の後の方で余分なソートをする必要がなくなる。そして、うまくソートされた結果は、データがかたまっているため、その後の結合が高速化される可能性がある。

歴史的には、System R のクエリ最適化は left-deep クエリ実行計画のみを考慮していた（左側から順に実行するものとする方式）。すなわち、2つの表の結合をまず行って、その結果と別の表を結合していく。このヒューリスティックは考慮すべき計画数を減らすが（n! から 4^n）、最適なクエリ実行計画を見逃す可能性がある。このヒューリスティックは入れ子ループなどの結合アルゴリズムでは、一度には外の関係の1つのタプル（別名「行」）のみを必要とするという観測結果から出てきたものである。従って、left-deep クエリ実行計画では常にメモリ上に保持すべきタプル数が少なくて済み、外側の関係との結合計画は1つのタプルが生成されるまで行えばよく、その後内側の関係を検索する（これを「パイプライン」と呼ぶ）。

その後、クエリ最適化は、結合演算子の両方のオペランドが別の結合の中間結果であるような複雑なクエリ実行計画にも拡張された。そのような計画は並列コンピュータでは分割して並行に計算できるので、特に重要となってきた。

[編集] 入れ子型SQLクエリのクエリ実行計画

最近の関係データベース管理システム (RDBMS) のデータベース言語 SQL によるクエリは、関係代数における単なる選択と結合以上のことを行う。特に SQLクエリは、「GROUP BY」や「EXISTS」や「NOT EXISTS」を使った SELECT-PROJECT-JOIN ブロックの入れ子となっていることが多い。場合によってはそのような入れ子型SQLクエリを平坦化して1つの SELECT-PROJECT-JOIN クエリにすることもできるが、常に可能というわけではない。入れ子型SQLクエリのクエリ実行計画にも従来の動的計画法を使うこともできるが、そうするとクエリ最適化にかかる時間はどんどん大きくなってくる。そこでいくつかのDBMSではクエリのグラフモデルを使ったルールベースの手法を採用している。

[編集] コスト見積もり

クエリ最適化の最も困難な問題は、複数のクエリ実行計画のコストを正確に見積もることである。オプティマイザはクエリ実行コストの数学的モデルを使ってクエリ実行計画を見積もる。この数学的モデルはクエリ計画の結果の濃度（cardinality）すなわちタプル数 (行数) に強く依存している。そしてそれはさらにクエリ内の述語の選択結果の見積もりに依存している。従来から、データベースシステムはヒストグラムなどを使って各桁（カラム）の値の分布をかなり詳しく統計を取っており、それによって述語の選択結果を見積もる。この技法は個々の述語の選択結果の見積もりについてはうまく機能する。しかし多くのクエリは述語の論理積を使っており、例えば select count(*) from R, S where R.make='Honda' and R.model='Accord' などとなっている。クエリ内の述語は相互に関連が深いことが多い（例えば、model='Accord' は make='Honda' の一部である）。しかし一般に論理積による選択結果を見積もることは非常に困難である。選択結果の見積もりと述語の相互関係を捉えられないという問題により、クエリオプティマイザは不適切なクエリ実行計画を選択してしまう。これは大きなデータの変更があったときなど、データベース管理者が定期的にデータベースの統計情報を更新しなければならない理由の1つでもある。

[編集] 関連項目

関係代数#問い合わせ最適化

[編集] 参考文献

Chaudhuri, Surajit (1998年). "An Overview of Query Optimization in Relational Systems". Proceedings of the ACM Symposium on Principles of Database Systems: pages 34–43.
Ioannidis, Yannis (1996年3月). "Query optimization". ACM Computing Surveys 28 (1).