8.1. 複雑な最適化問題としての問い合わせ処理

リレーショナル演算子の中で、処理と最適化が一番難しいのは 結合です。ある問い合わせに答えるための計画の侯補は、 その問い合わせが持つ結合の数によって指数的に増えます。 更なる最適化の努力は色々な結合メソッドのサポートに よってなされます（例：Postgresの入れ子ループ、 ハッシュ結合、マージ結合)。これは個々の結合や様々な インデックス(例：Postgres のr-tree, b-tree, ハッシュ)をリレーションのアクセスパスとして 処理するためです。

現在のPostgresオプティマイザの実装は、 戦略の侯補空間のしらみつぶしに近い検索を行います。 この問い合わせ最適化技術は、大規模な問い合わせを必要とするデータベース アプリケーションのドメイン(人工知能など)をサポートするには向いていません。

ドイツ、フライブルグにある University of Mining and Technology の Institute of Automatic Control では、電力グリッドの保守のため の意志決定知識ベースシステムのためのバックエンドとして Postgres DBMSを使おうとしたため問題が起こりました。その DBMS は 知識ベースシステムの推論マシンのために、大きな結合 の問い合わせを処理する必要があったのです。

可能な問い合わせ計画の探策性能に問題があったため、 新しい最適化技術の開発が必要とされるようになりました。

そこで、データベース問い合わせ最適化問題へのオプションとして、 遺伝的アルゴリズムの実装を提案します。