著者: このドキュメントはMartin Utesch(<utesch@aut.tu-freiberg.de>)によって、ドイツ、フライブルグにあるUniversity of Mining and TechnologyのInstitute of Automatic Controlのために書かれました。
リレーショナル演算子の中で、処理と最適化が一番難しいのは結合です。 ある問い合わせに答えるための計画の侯補は、その問い合わせが持つ結合の数によって指数的に増えます。 更なる最適化の努力は様々な結合メソッドのサポートによってなされます(例えばPostgreSQLの入れ子ループ、ハッシュ結合、マージ結合など)。 これは個々の結合や様々なインデックス(例えばPostgreSQLのR-tree、B-tree、ハッシュなど)をリレーションのアクセスパスとして処理することによるものです。
現在のPostgreSQLオプティマイザの実装は、ストラテジの侯補空間のしらみつぶしに近い検索を行います。 "System R"データベースで初めて導入された、このアルゴリズムはほぼ最適な結合順を生成しますが、問い合わせ内の結合数が増えると膨大な処理時間とメモリ空間を必要とします。 このため、通常のPostgreSQL問い合わせオプティマイザは結合するテーブル数の多い問い合わせには向いていません。
ドイツ、フライブルグにあるUniversity of Mining and TechnologyのInstitute of Automatic Controlでは、送電網の保守のための意志決定知識ベースシステムのためのバックエンドとしてPostgreSQL DBMSを使おうとしたため問題が起こりました。 そのDBMSは知識ベースシステムの推論マシンのために、大きな結合の問い合わせを処理する必要があったのです。
可能な問い合わせ計画の探策性能に問題があったため、新しい最適化技術の開発が必要とされるようになりました。
以下では、多数の結合を持つ問い合わせを効率的に行なうことができるように、結合順問題を解決する遺伝的アルゴリズムの実装を説明します。