GEQOのモジュールは、巡回セールスマン問題(TSP ) に似た問い合わせ最適化問題の解決策として意図されています。可能な問い合わせ プランは、整数の文字列としてコード化されます。それぞれの文字列は、問い合わせ の一つのリレーションから次へと結合の順番を表します。 例：この問い合わせツリーは
/\
/\ 2
/\ 3
4 1
整数文字列 '4-1-3-2' によってコード化されています。それが意味するのは、
まずリレーション '4' と '1' 次に、 '3' 、そして '2' を結合するという
ことです。ここで 1, 2, 3, 4 は
Postgresオプティマイザ内で relid
を表します。
GEQOモジュールの一部は D. Whitley の Genitor アルゴリズムを適合させたものです。
PostgresにおけるGEQOの 実装特有の特徴は下記のとおりです。
安定状態GAの使用(世代全体の 置き換えではなく、個体群の中で適合度の低いものだけの置き換え)は、 よりよい問い合わせ計画への素早い収束を可能にします。これは、妥当な時間 内での問い合わせ処理にはきわめて重要なものです；
GAによるTSPの解決策のエッジ損失を 低く抑えるために特別に作られた、エッジ再交配交叉 の使用；
TSP の合法な巡回を行うために必要な回復処理が いらないように、遺伝的演算子の突然変異は低くしてあります。
GEQOモジュールにより Postgres 問い合わせオプティマイザが、大きな結合問い合わせを しらみつぶし探策以外の方法で実行することが可能になります。
遺伝的アルゴリズムのパラメータ設定を改善するためにはまだ課題が残っていま す。 ファイルbackend/optimizer/geqo/geqo_params.c、 ルーチンgimme_pool_size と gimme_number_generationsでは、二つの相反する要求を満たす 妥協点を見つけなければいけません。
問い合わせ計画の最適性
計算時間
GEQアルゴリズム関連情報
The Hitch-Hiker's Guide to Evolutionary Computation , Jg Heitkter and David Beasley, InterNet resource , The Design and Implementation of the Postgres Query Optimizer , Z. Fong, University of California, Berkeley Computer Science Department , Fundamentals of Database Systems , R. Elmasri and S. Navathe, The Benjamin/Cummings Pub., Inc. .
comp.ai.genetic、ホ FAQ 、マ Encore 、ヌクォ、襪海箸♢任④泙后
ファイル planner/Report.ps は 'postgres-papers' 配布物の中にあります。