GEQO モジュールは、巡回セールスマン問題( TSP )に似た問い合わせ最適化問題の解決を目的とし ています。問い合わせ計画の候補を整数の文字列としてコード化します。 各文字列は、問い合わせ内のリレーションをどういう順番で join を行なうかを表します。 例えば、
/\ /\ 2 /\ 3 4 1という問い合わせツリーは、'4-1-3-2' という整数の文字列にコード化さ れます。この文字列は、まず、'4' と '1' リレーションの結合を行ない、 次にこの結合したものと '3' 、そしてその次に '2' と結合することを意 味します。ここで 1、2、3、4 は Postgres におけるリレーション識別子を示します。
GEQO モジュールの一部は D. Whitley 氏の Genitor アルゴリズムを適合させたものです。
Postgres における GEQO の実装固有の特徴を以下に示します。
(集団内の全世代を置き換えるのではなく、最低限適合した個体の置換 えを行なう) 安定状態 GA を使用することにより、優れた問い合わせ計画への高速収束が可能です。 これは、妥当な時間内で問い合わせ処理を行なうために必要不可欠なもの です。
特に、GA による TSP 解決用に考 えられた、エッジでのロスを低く抑える、 エッジ再交配交叉 の使用。
TSPにおいて合法的な巡回を行なわせるために必要とな る回復処理が不要になるように、遺伝的演算子の突然変異を低めにしていま す。
GEQO モジュールは Postgres の問い合わせオブティマイザの実装 と比較して、Postgres DBMS に以下の利点を 与えます。
しらみつぶし検索を使用しない、大規模な join 問い合 わせ処理。
計画のマージが不要になった( GEQO は問い合わせ計 画のコスト評価を個別に行ないます。)ことによる、問い合わせ計画のコス トサイズ概算処理の改良。