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