The GEQO module is intended for the solution of the query optimization problem similar to a traveling salesman problem (TSP). Possible query plans are encoded as integer strings. Each string represents the join order from one relation of the query to the next. E. g., the query tree
GEQO モジュールは、巡回セールスマン問題( TSP )に似た問い合わせ最適化問題の解決を目的とし ています。問い合わせ計画の候補を整数の文字列としてコード化します。 各文字列は、問い合わせ内のリレーションをどういう順番で join を行なうかを表します。 例えば、
/\ /\ 2 /\ 3 4 1is encoded by the integer string '4-1-3-2', which means, first join relation '4' and '1', then '3', and then '2', where 1, 2, 3, 4 are relids in Postgres. という問い合わせツリーは、'4-1-3-2' という整数の文字列にコード化さ れます。この文字列は、まず、'4' と '1' リレーションの結合を行ない、 次にこの結合したものと '3' 、そしてその次に '2' と結合することを意 味します。ここで 1、2、3、4 は Postgres におけるリレーション識別子を示します。 ※relidをリレーション識別子と訳
Parts of the GEQO module are adapted from D. Whitley's Genitor algorithm.
GEQO モジュールの一部は D. Whitley 氏の Genitor アルゴリズムを適合させたものです。
Specific characteristics of the GEQO implementation in Postgres are:
Postgres における GEQO の実装固有の特徴を以下に示します。
Usage of a steady state GA (replacement of the least fit individuals in a population, not whole-generational replacement) allows fast convergence towards improved query plans. This is essential for query handling with reasonable time;
(集団内の全世代を置き換えるのではなく、最低限適合した個体の置換 えを行なう) 安定状態 GA を使用することにより、優れた問い合わせ計画への高速収束が可能です。 これは、妥当な時間内で問い合わせ処理を行なうために必要不可欠なもの です。
Usage of edge recombination crossover which is especially suited to keep edge losses low for the solution of the TSP by means of a GA;
特に、GA による TSP 解決用に考 えられた、エッジでのロスを低く抑える、 エッジ再交配交叉 の使用。
Mutation as genetic operator is deprecated so that no repair mechanisms are needed to generate legal TSP tours.
TSPにおいて合法的な巡回を行なわせるために必要とな る回復処理が不要になるように、遺伝的演算子の突然変異を低めにしていま す。
The GEQO module gives the following benefits to the Postgres DBMS compared to the Postgres query optimizer implementation:
GEQO モジュールは Postgres の問い合わせオブティマイザの実装 と比較して、Postgres DBMS に以下の利点を 与えます。
Handling of large join queries through non-exhaustive search;
しらみつぶし検索を使用しない、大規模な join 問い合 わせ処理。
Improved cost size approximation of query plans since no longer plan merging is needed (the GEQO module evaluates the cost for a query plan as an individual).
計画のマージが不要になった( GEQO は問い合わせ計 画のコスト評価を個別に行ないます。)ことによる、問い合わせ計画のコス トサイズ概算処理の改良。