無料スクリプト配布のPHP.TO   PHPの実用的なtips PHPマニュアル MySQLマニュアル Apacheマニュアル PostgreSQLマニュアル マニュアル検索    

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

リレーショナル演算子の中で、処理と最適化が一番難しいのは 結合 です。 実行可能な問い合わせ計画の数は問い合わせの中に含まれる結合の数によって指数関数的に増加します。 個々の結合や、多様な インデックス (例えば PostgreSQL のB-tree、ハッシュ、GiST、GINなど)をリレーションのアクセスパスとして処理するため、様々な 結合メソッド (例えば PostgreSQL の入れ子ループ、ハッシュ結合、マージ結合など)を提供することが、さらなる最適化を行わなければならない腐心の原因となっています。

通常の PostgreSQL 問い合わせオプティマイザは、候補ストラテジ空間にわたって しらみつぶしに近い検索 を行います。 IBMのSystem Rデータベースで初めて導入された、このアルゴリズムはほぼ最適な結合順を生成しますが、問い合わせ内の結合数が増えると膨大な処理時間とメモリ空間を必要とします。 このため、通常の PostgreSQL 問い合わせオプティマイザは結合するテーブル数の多い問い合わせには向いていません。

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

以下では、多数の結合を持つ問い合わせを効率的に行うことができるように、結合順問題を解決する 遺伝的アルゴリズム の実装を説明します。


powered by SEO.CUG.NET