PostgreSQL
PrevChapter 50. データベースシステムにおける,遺伝的問い合わせの最適化Next

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

関連するすべての演算子間において,処理や最適化が最も困難なのは 結合(join)です. 問い合わせの中に含まれるjoinが多くなると, それに答えるための選択手段が指数的に増えて行きます. 個々のjoinや,リレーションへのアクセス経路 としての多種多様な索引(たとえば r-tree, b-tree,Postgresにおけるハッシュ) を処理するために,さまざまな結合方法(join methods)(たとえば入れ子になったループ,索引スキャン, Postgresにおけるマージ結合)を サポートしながら,さらに進んだ最適化への努力がなされています.

現在におけるPostgres最適化機構の実装 においては,まったく新しい構造を持つデータ空間に対して,しらみつぶし的な検索を行っています. このような問い合わせ最適化技術程度では,人工知能のような大規模 問い合わせの際に必要となるようなデータベース・アプリケーション 領域をサポートするにはまだ不十分です.

ドイツのフレイバーグにある鉱業技術大学の自動制御研究所では,上記の ような問題に遭遇しました.人々はPostgres DBMS を,電子パワーグリッド保守用意志決定サポート知識ベースシステム のためのバックエンドとして選択したのです.その DBMS では,知識 ベースシステムの推論マシンのための大掛かりなjoin 問い合わせが必要だったのです.

およそ考えうるすべての問い合わせに関する可能性を探って行くうちに, 性能を上げることが次第に困難なことが分かってきて,新しい最適化技術 を開発する必要に迫られてきました.

以下に示すように,データベース問い合わせに関する最適化の難問に 対するオプションとして,我々は遺伝的アルゴリズムの実装を提案します.


PrevHomeNext
データベースシステムにおける,遺伝的問い合わせの最適化Up遺伝的アルゴリズム(Genetic Algorithms(GA))