クエリ最適化
あるクエリ実行計画の性能は関係 (表) を結合する順序に大きく依存する。例えば、3つの表A(10行)、B(1,000,000行)、C(1,000,000行)を結合する場合、BとCを先に結合する計画の方がAとCを先に結合する計画よりも遥かに時間がかかる。多くのクエリ最適化では、自然結合 (join) の順序を動的計画法アルゴリズムで決定する。これはIBMのSystem Rプロジェクトで採用された方法である。このアルゴリズムは次のように2段階で動作する:
まず、クエリ内の全ての関係にアクセスする全ての方法を求める。クエリ内の各関係はシーケンシャル検索でアクセスできる。ある関係のインデックスがクエリ内の述語の回答として使える場合、インデックス検索も使用可能である。各関係について、オプティマイザは関係を検索する最も安価な方法を記録し、同時に特定のソートされた順のレコード群を生成する関係検索の最も安価な方法も記録する。
次にオプティマイザは関係間の結合条件を調べる。それぞれの関係のペアについて、オプティマイザはそのDBMSに実装された使用可能な結合アルゴリズムを調べる。そしてそれぞれの関係のペアを結合する最も安価な方法を保持すると同時に、特定のソートされた順の出力を生成する結合方法も保持する。
そして、上で求められた2つの関係の結合フェーズの結果と3つめの関係も含めたクエリ実行計画のコストを計算する。
このようにして、クエリ実行計画は最終的にその関係についての全てのクエリの結合を生成する。