Chapter 24. データベースシステムにおける遺伝的問い合わせ最適化

Table of Contents
遺伝的アルゴリズム (GA)
Postgres における遺伝的問い合わせ最適化(GEQO
Postgres GEQO におけ る今後の実装作業

著者: Written by Martin Utesch for the Institute of Automatic Control at the University of Mining and Technology in Freiberg, Germany.

ドイツ、フライブルグの鉱業技術大学自動制御研究所向けに Martin Utesch 氏によ り記述されました。


Among all relational operators the most difficult one to process and optimize is the join. The number of alternative plans to answer a query grows exponentially with the number of joins included in it. Further optimization effort is caused by the support of a variety of join methods (e.g., nested loop, index scan, merge join in Postgres) to process individual joins and a diversity of indices (e.g., r-tree, b-tree, hash in Postgres) as access paths for relations.

全てのリレーショナル演算子の中で、処理や最適化が最も難しいものは join です。問い合わせ中の join の数が多くなるにしたがって、それに応答するために取り得る計画の数が指数的 に増えていきます。個々の join や、リレーションへのア クセス経路としての多種の インデックス(例えば、 Postgres における、r-tree、b-tree、ハッシュ) を処理するための多様な 結合方法 (例えば、 Postgres における、入れ子状ループ、インデック ススキャン、マージ結合)をサポートすることは、更なる最適化の改良を引き起 こします。

The current Postgres optimizer implementation performs a near- exhaustive search over the space of alternative strategies. This query optimization technique is inadequate to support database application domains that involve the need for extensive queries, such as artificial intelligence.

現在の Postgres オブティマイザの実装は、 代替ストラテジ空間に対する しらみつぶし検索 です。この程度の問い合わせ最適化技術では、人工知能のような大規模な 問い合わせを必要とするデータベースアプリケーション領域をサポートす るにはまだ不十分です。

The Institute of Automatic Control at the University of Mining and Technology, in Freiberg, Germany, encountered the described problems as its folks wanted to take the Postgres DBMS as the backend for a decision support knowledge based system for the maintenance of an electrical power grid. The DBMS needed to handle large join queries for the inference machine of the knowledge based system.

ドイツ、フライブルグの鉱業技術大学自動制御研究所では、上のような問 題に遭遇しました。そこでは Postgres DBMS を、電力グリッド保守用の意思決定支援知識ベースシステムのバック エンドとして選択したのです。その DBMS には、知識ベースシステムの推論 マシンのための大規模な join 問い合わせを扱う能力が 必要でした。

Performance difficulties within exploring the space of possible query plans arose the demand for a new optimization technique being developed.

取り得る問い合わせ計画の空間内の探求による性能の向上は困難であったた め、新しい最適化技術の開発要求が高まりました。

In the following we propose the implementation of a Genetic Algorithm as an option for the database query optimization problem.

以降、データベース問い合わせに関する最適化問題のオプションとして、 遺伝的アルゴリズム の実装を提案します。