Postgres における，遺伝的問い合わせの最適化 (GEQO)

GEQOモジュールは，旅行するセールスマンの問題 (TSP)と同じような，問い合わせ最適化の問題の 解決を目的としています． 可能性のある問い合わせプランは，整数の文字列としてエンコード されます．各文字列は，問い合わせの中の 1 つのリレーションから 次のリレーションへのjoin順序を表しています． たとえば，問い合わせツリー

       /\
      /\ 2
     /\ 3
    4  1

GEQOモジュールの一部は，D. Whitley の Genitor アルゴリズムに適合しています．

PostgresにおけるGEQO 実装系固有の特性として，以下のものが挙げられます．

• 安定状態(steady state)GA (母集団中の全世代の置き換えでなく，最後にマッチした個体の置き換え) の使用法として，改良型問い合わせプランに向かった，高速の一点集中 を許している．これは，妥当な時間内で問い合わせ処理を行うために 必要不可欠なものです．

• 特にGAによるTSPの解決のため， エッジでのロスを低く押さえるように考えられた エッジ再結合異種交配の使用．

• 遺伝的演算子としての突然変異を行わないようになっているので，合法的な TSPツアーを生成するための回復メカニズムを必要と しません．

GEQOモジュールは，Postgres問い合わせ最適化実装系と比較して，Postgres DBMS に以下の利点を与えます．

• しらみつぶし的でない検索を通した，大規模なjoin 問い合わせ処理．

• 問い合わせプランのコストサイズ概算処理が改善されており，もはやプラン マージが必要ではなくなりました(GEQO モジュールは 問い合わせプランのコストを個体として評価します)．