他のバージョンの文書 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

Chapter 8. 遺伝的問い合わせ最適化

Table of Contents
8.1. 複雑な最適化問題としての問い合わせ処理
8.2. 遺伝的アルゴリズム
8.3. PostgreSQLの遺伝的問い合わせ最適化(GEQO
8.4. さらに深く知るには

著者: このドキュメントはMartin Utesch()によって、ドイツ、フライブルグにあるUniversity of Mining and TechnologyのInstitute of Automatic Controlのために書かれました。

8.1. 複雑な最適化問題としての問い合わせ処理

リレーショナル演算子の中で、処理と最適化が一番難しいのは結合です。ある問い合わせに答えるための計画の侯補は、その問い合わせが持つ結合の数によって指数的に増えます。さらなる最適化の努力はさまざまな結合メソッドのサポートによってなされます(たとえばPostgreSQLの入れ子ループ、ハッシュ結合、マージ結合など)。これは個々の結合やさまざまなインデックス(たとえばPostgreSQLのR-tree、B-tree、ハッシュなど)をリレーションのアクセスパスとして処理することによるものです。

現在のPostgreSQLオプティマイザの実装は、ストラテジの侯補空間のしらみつぶしに近い検索を行います。この問い合わせ最適化技術は、大規模な問い合わせを必要とするデータベースアプリケーションのドメイン(人工知能など)をサポートするには向いていません。

ドイツ、フライブルグにあるUniversity of Mining and TechnologyのInstitute of Automatic Controlでは、送電網の保守のための意志決定知識ベースシステムのためのバックエンドとしてPostgreSQL DBMSを使おうとしたため問題が起こりました。そのDBMSは知識ベースシステムの推論マシンのために、大きな結合の問い合わせを処理する必要があったのです。

可能な問い合わせ計画の探策性能に問題があったため、新しい最適化技術の開発が必要とされるようになりました。

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