Postgres GEQO におけ る今後の実装作業

基本的な改善

問い合わせ処理完了時のメモリ開放についての改善

With large join queries the computing time spent for the genetic query optimization seems to be a mere fraction of the time Postgres needs for freeing memory via routine MemoryContextFree, file backend/utils/mmgr/mcxt.c. Debugging showed that it get stucked in a loop of routine OrderedElemPop, file backend/utils/mmgr/oset.c. The same problems arise with long queries when using the normal Postgres query optimization algorithm.

大規模 join 問い合わせの際に、遺伝的問い合わせ最 適化で使われる演算時間は、 backend/utils/mmgr/mcxt.c ファイルの MemoryContextFree 処理を使って Postgres がメモリ開放を行なう時に必要とす る時間の ごく一部 に過ぎないようです。デバッグ してみると、backend/utils/mmgr/oset.c ファイル の OrderedElemPop 処理内のループで時間がかかっ ていました。同じ問題は通常の Postgres 問い合わせ最適化アルゴリズムを使って長い問い合わせを行なった時にも発 生します。

遺伝的アルゴリズムのパラメータ設定についての改善

In file backend/optimizer/geqo/geqo_params.c, routines gimme_pool_size and gimme_number_generations, we have to find a compromise for the parameter settings to satisfy two competing demands:

backend/optimizer/geqo/geqo_params.c ファイルの gimme_pool_size 処理と gimme_number_generations 処理において、次の 2 つ の相反する要求をみたすようなパラメータ設定の妥協点を見つけなければいけ ません。

  • Optimality of the query plan

    問い合わせ計画の最適性

  • Computing time

    計算時間

整数オーバーフローについてよりよい解決策の探求

In file backend/optimizer/geqo/geqo_eval.c, routine geqo_joinrel_size, the present hack for MAXINT overflow is to set the Postgres integer value of rel->size to its logarithm. Modifications of Rel in backend/nodes/relation.h will surely have severe impacts on the whole Postgres implementation.

backend/optimizer/geqo/geqo_eval.c ファイルの geqo_joinrel_size 処理において、 rel->size という Postgres 整数値の対数を設定するために、 MAXINT オーバーフローという問題を解決しなければいけません。 backend/nodes/relation.h ファイルの Rel の変更は、確実に Postgres 全般に大きく影響を与えることにな ります。

メモリ枯渇についての解決策の探求

Memory exhaustion may occur with more than 10 relations involved in a query. In file backend/optimizer/geqo/geqo_eval.c, routine gimme_tree is recursively called. Maybe I forgot something to be freed correctly, but I dunno what. Of course the rel data structure of the join keeps growing and growing the more relations are packed into it. Suggestions are welcome :-(

問い合わせ内に 10 個以上のリレーションがあると、メモリを使い果たして しますことがあります。 backend/optimizer/geqo/geqo_eval.c ファイルでは gimme_tree 処理が再帰的に呼び出されます。おそら く何かをちゃんと開放していないのだと考えているですが、まだ判明できて いません。もちろん joinrel データ構造体はリレーションがあればあるほ ど肥大していきます。何か解決策がないでしょうか :-(

参考資料

GEQアルゴリズム関連情報

The Hitch-Hiker's Guide to Evolutionary Computation, Jrg Heitktter 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..

FAQ in comp.ai.genetic is available at Encore.

comp.ai.geneticの FAQ は Encore から入手できます。

File planner/Report.ps in the 'postgres-papers' distribution.

'postgres-papers' 配布物内の planner/Report.ps ファイル。