| PostgreSQL 9.1.5文書 | ||||
|---|---|---|---|---|
| 前のページ | 巻戻し | 第 51章遺伝的問い合わせ最適化 | 早送り | 次のページ |
GEQOのモジュールは、問い合わせ最適化問題をあたかもよく知られている巡回セールスマン問題（TSP）のように扱います。 可能な問い合わせプランは、整数の文字列として符号化されます。 それぞれの文字列は、問い合わせの1つのリレーションから次へと結合の順番を表します。 例えば、以下の結合ツリーは整数文字列「4-1-3-2」によって符号化されています。
/\ /\ 2 /\ 3 4 1
これが意味するのは、まずリレーション「4」と「1」を、次に「3」を、そして「2」を結合するということです。 ここで1、2、3、4はPostgreSQLオプティマイザ内でリレーションIDを表します。
PostgreSQLにおけるGEQO実装の特有な特徴は下記の様なものです。
定常状態GAの使用（世代全体の置き換えではなく、個体の中で適応度の低いものだけの置き換え）は、改良された問い合わせ計画へ素早い収束を可能にします。 これは、妥当な時間内での問い合わせ処理にはきわめて重要です。
GAによるTSPの解決策の辺損失を低く抑えるため、非常に適した辺再組合せ交叉を使用します。
TSPの合法な巡回を行うために必要な修復処理を要求しないように、遺伝的演算子の突然変異は無視しています。
GEQOモジュールの部品は D. WhitleyのGenitorアルゴリズムを適合させたものです。
GEQOモジュールにより、PostgreSQL問い合わせオプティマイザが、大きな結合問い合わせをしらみつぶし検索以外の方法で実行することが可能になります。
GEQOの計画作成では、個々のリレーションのスキャンに対する計画を生成するために標準のプランナが使用されます。 そして、結合計画が遺伝的手法を用いて展開されます。 上で示した通り、 結合計画候補はそれぞれ、基本リレーションの結合順によって表現されています。 初期段階では、GEQOコードは単純にランダムに取り得る結合順をいくつか生成します。 考慮された結合順それぞれについて、標準プランナコードが呼び出され、その結合順を使用して問い合わせを行った場合のコストを推定します。 （結合順の各段階において、全体で3つの取り得る結合戦略が考慮されます。 そして、あらかじめ決められたリレーションスキャン計画もすべて利用可能です。 推定コストとはこれらの可能性の中から最も安価なものです。） より低い推定コストの結合順を、より高い推定コストのものより"より高い適応度"と判断します。 遺伝的アルゴリズムは適応度が低い候補を破棄します。 そして、より多く合致する候補の遺伝子を組み合わせて、つまり、検討すべき新しい順序を作成するために既知の低コスト結合順をランダムに位置を選択して、新しい候補が生成されます。 事前に設定された数まで結合順を検討するまで、この処理が繰り返されます。 そして、この検索の間にもっとも優れたものが、最終的な計画を生成するために使用されます。
初期の群を選択する時、および、その後の最善の候補の突然変異の時に無作為な選択がなされますので、この処理は生来非決定論的なものです。 選択された計画の予期せぬ変化を避けるために、GEQOアルゴリズムの各実行では乱数生成器を現在のgeqo_seedパラメータ設定で再スタートさせます。 geqo_seedとその他のGEQOパラメータが変更されない限り、一定の問い合わせ（と統計のようなプランナへの他の入力）に対しては同じ計画が生成されます。 異なる検索パスで実験するためには、geqo_seedを変更してみて下さい。
遺伝的アルゴリズムのパラメータ設定を改善するためにはまだ課題が残っています。
src/backend/optimizer/geqo/geqo_main.cのgimme_pool_sizeとgimme_number_generationsというルーチンでは、次の2つの相反する要求を満たす妥協点を見つけなければいけません。
問い合わせ計画の最適性
計算時間
現在の実装では、各結合順候補の適応度は標準プランナの結合選択と、一から作成したコスト推定コードを実行して推定されます。 異なる候補が同様の副結合順で使用されるにつれて、多くの作業が繰り返されることになります。 これは、副結合のコスト推定を記憶することで、非常に高速になるはずです。 この状態を記憶するために要するメモリ量が非合理的に拡大することを防止することが問題です。
最も基本的なレベルでは、TSP用に設計されたGAアルゴリズムを用いた問い合わせ最適化の解法が適切かどうかは明確ではありません。 TSPの場合は、部分文字列（巡回経路の一部）に関連付けられたコストは残りの巡回経路と独立していますが、これは問い合わせ最適化の場合には確実に成り立ちません。 したがって、辺再組合せ交叉が最も有効な突然変異手続きかどうかは疑わしいと言えます。