Among all relational operators the most difficult one to process and optimize is the <firstterm>join</firstterm>. The number of possible query plans grows exponentially with the number of joins in the query. Further optimization effort is caused by the support of a variety of <firstterm>join methods</firstterm> (e.g., nested loop, hash join, merge join in <productname>PostgreSQL</productname>) to process individual joins and a diversity of <firstterm>indexes</firstterm> (e.g., B-tree, hash, GiST and GIN in <productname>PostgreSQL</productname>) as access paths for relations. リレーショナル演算子の中で、処理と最適化が一番難しいのは結合です。 実行可能な問い合わせ計画の数は問い合わせの中に含まれる結合の数によって指数関数的に増加します。 個々の結合や、多様なインデックス（例えばPostgreSQLのB-tree、ハッシュ、GiST、GINなど）をリレーションのアクセスパスとして処理するため、様々な結合メソッド（例えばPostgreSQLのネステッドループ、ハッシュ結合、マージ結合など）を提供することが、さらなる最適化を行わなければならない腐心の原因となっています。

The normal <productname>PostgreSQL</productname> query optimizer performs a <firstterm>near-exhaustive search</firstterm> over the space of alternative strategies. This algorithm, first introduced in IBM's System R database, produces a near-optimal join order, but can take an enormous amount of time and memory space when the number of joins in the query grows large. This makes the ordinary <productname>PostgreSQL</productname> query optimizer inappropriate for queries that join a large number of tables. 通常のPostgreSQL問い合わせオプティマイザは、候補ストラテジ空間にわたってしらみつぶしに近い検索を行います。 IBMのSystem Rデータベースで初めて導入された、このアルゴリズムはほぼ最適な結合順を生成しますが、問い合わせ内の結合数が増えると膨大な処理時間とメモリ空間を必要とします。 このため、通常のPostgreSQL問い合わせオプティマイザは結合するテーブル数の多い問い合わせには向いていません。

The Institute of Automatic Control at the University of Mining and Technology, in Freiberg, Germany, encountered some problems when it wanted to use <productname>PostgreSQL</productname> as the backend for a decision support knowledge based system for the maintenance of an electrical power grid. The DBMS needed to handle large join queries for the inference machine of the knowledge based system. The number of joins in these queries made using the normal query optimizer infeasible. ドイツ、フライブルグにあるUniversity of Mining and TechnologyのInstitute of Automatic Controlでは、送電網の保守のための意志決定知識ベースシステムのためのバックエンドとしてPostgreSQL DBMSを使おうとしたため問題が起こりました。 そのDBMSは知識ベースシステムの推論マシンのために、大規模な結合の問い合わせを処理する必要があったのです。 こうした問い合わせに含まれる結合数を行うことは、通常の問い合わせオプティマイザでは実現不可能でした。

In the following we describe the implementation of a <firstterm>genetic algorithm</firstterm> to solve the join ordering problem in a manner that is efficient for queries involving large numbers of joins. 以下では、多数の結合を持つ問い合わせを効率的に行うことができるように、結合順問題を解決する遺伝的アルゴリズムの実装を説明します。