■2-03■ 問い合わせ処理の流れ
問い合わせ処理
バックエンドプロセスでの、問い合わせ処理の流れを【図.2-3】に示します。図.2-3 問い合わせ処理の流れ
(1)パーサ(構文解析器)
クライアントから送られた問い合わせ文の構文解析を行い、問い合わせツリーを作ります。
(2)書き換えシステム
問い合わせツリーに対して、定義されたルールをもとに問い合わせツリーを書き換えます。
ルールはシステムカタログ“pg_rewrite”に保存されています。
(3)プランナ/オプティマイザ
プランナは、問い合わせ計画を列挙します。オプティマイザは、最も効率的な問い合わせ計画を選択します。
問い合わせ計画とは、問い合わせを実行するときにどの方式でテーブルを検索するか、複数のテーブルがある場合、どの順序、どのテーブル結合方式で検索するかを記述したものです。検索方式、テーブル結合方式については【2-04】の解説を参照してください。
なお、PostgreSQLは非常に複雑な問い合わせ(デフォルトではテーブルを11以上含む場合) に対して、列挙による問い合わせ計画選択をあきらめ、“遺伝的アルゴリズムによる問い合わせ最適化”(補足 1)という手法を用います。
(4)エクゼキュータ
オプティマイザの選択した問い合わせ計画に沿って問い合わせを実行します。
補足
(1)「遺伝的アルゴリズムによる問い合わせ最適化」はPostgreSQL の特徴のひとつで、University of Mining and Technology のInstitute of Automatic Control(ドイツ、フライブルグ)で実装されました。
遺伝的アルゴリズムは組合せ最適化問題に対するヒューリスティックな解法のひとつで、最良ではないが良好な答えを高速に見つけ出す手法です。
通常、オプティマイザは問い合わせ文の実行計画を選ぶために、問い合わせ文に含まれるリレーションの評価順序とテーブル結合方式について、すべての組合せのコストを計算します。よってコスト計算時間は問い合わせ文のリレーション数によって指数的に増え、ある程度以上の複雑な問い合わせの最適化を行うことは不可能です。
そこで、遺伝的アルゴリズムにより最適ではないが良好なリレーションの評価順序を求め、それにもとづいて複雑な問い合わせに対し高速な検索を行います。
問題の定式化(モデル化)は巡回セールスマン問題をベースとして行っているようです(最も短時間にすべての都市を廻る組合せ→最も低コストですべてのリレーションを評価する組合せ)。
遺伝的アルゴリズムに関する解説書は数多く出版されていますが、残念ながら問い合わせ最適化への応用は「PostgreSQL 開発者ガイド遺伝的問い合わせ最適化」しか資料がありません。
[PREVIOUS][UP][NEXT]