48.3. PostgreSQLの遺伝的問い合わせ最適化(GEQO

GEQOのモジュールは、問い合わせ最適化問題をあたかもよく知られている巡回セールスマン問題(TSP)のように扱います。 可能な問い合わせプランは、整数の文字列として符号化されます。 それぞれの文字列は、問い合わせの1つのリレーションから次へと結合の順番を表します。 例えば、以下の結合ツリーは整数文字列「4-1-3-2」によって符号化されています。

   /\
  /\ 2
 /\ 3
4  1

これが意味するのは、まずリレーション「4」と「1」を、次に「3」を、そして「2」を結合するということです。 ここで1、2、3、4はPostgreSQLオプティマイザ内でリレーションIDを表します。

GEQOモジュールの部品は D. WhitleyのGenitorアルゴリズムを適合させたものです。

PostgreSQLにおけるGEQO実装の特有な特徴は下記の様なものです。

GEQOモジュールにより、PostgreSQL問い合わせオプティマイザが、大きな結合問い合わせをしらみつぶし検索以外の方法で実行することが可能になります。

48.3.1. PostgreSQL GEQOの今後の実装作業

遺伝的アルゴリズムのパラメータ設定を改善するためにはまだ課題が残っています。 src/backend/optimizer/geqo/geqo_main.cgimme_pool_sizegimme_number_generationsというルーチンでは、次の2つの相反する要求を満たす妥協点を見つけなければいけません。

最も基本的なレベルでは、TSP用に設計されたGAアルゴリズムを用いた問い合わせ最適化の解法が適切かどうかは明確ではありません。 TSPの場合は、部分文字列(巡回経路の一部)に関連付けられたコストは残りの巡回経路と独立していますが、これは問い合わせ最適化の場合には確実に成り立ちません。 したがって、辺再組合せ交叉が最も有効な突然変異手続きかどうかは疑わしいと言えます。