PostgreSQL | ||
---|---|---|
Prev | Chapter 50. データベースシステムにおける,遺伝的問い合わせの最適化 | Next |
GEQOモジュールは,旅行するセールスマンの問題 (TSP)と同じような,問い合わせ最適化の問題の 解決を目的としています. 可能性のある問い合わせプランは,整数の文字列としてエンコード されます.各文字列は,問い合わせの中の 1 つのリレーションから 次のリレーションへのjoin順序を表しています. たとえば,問い合わせツリー
/\ /\ 2 /\ 3 4 1は整数の文字列 '4-1-3-2' によりエンコードされます.ここで, 1, 2, 3, 4 はPostgresにおいて relids されているもので,最初は '4' で,続いて '1', '3', '2' の順での結合されています.
GEQOモジュールの一部は,D. Whitley の Genitor アルゴリズムに適合しています.
PostgresにおけるGEQO 実装系固有の特性として,以下のものが挙げられます.
安定状態(steady state)GA (母集団中の全世代の置き換えでなく,最後にマッチした個体の置き換え) の使用法として,改良型問い合わせプランに向かった,高速の一点集中 を許している.これは,妥当な時間内で問い合わせ処理を行うために 必要不可欠なものです.
特にGAによるTSPの解決のため, エッジでのロスを低く押さえるように考えられた エッジ再結合異種交配の使用.
遺伝的演算子としての突然変異を行わないようになっているので,合法的な TSPツアーを生成するための回復メカニズムを必要と しません.
GEQOモジュールは,Postgres問い合わせ最適化実装系と比較して,Postgres DBMS に以下の利点を与えます.
しらみつぶし的でない検索を通した,大規模なjoin 問い合わせ処理.
問い合わせプランのコストサイズ概算処理が改善されており,もはやプラン マージが必要ではなくなりました(GEQO モジュールは 問い合わせプランのコストを個体として評価します).
Prev | Home | Next |
遺伝的アルゴリズム(Genetic Algorithms(GA)) | Up | PostgresGEQOに関する 将来の実装作業. |