2.5. プランナ/オプティマイザ

2.5.1. 実行可能な計画の生成

プランナ/オプティマイザは、問い合わせの中に現れるリレーションで定義されるインデックスの型に基づいて、どのプランが作られるべきかを決めます。リレーション上で逐次スキャンを行う可能性は常に考えられるため、逐次スキャンのみを使ったプランが例外なく作成されます。リレーション上にインデックス（たとえば B-tree インデックス）が定義され、問い合わせには制約 relation.attribute OPR constant があるとしましょう。もし relation.attribute が B-tree インデックスのキーと一致し OPR が 「<>」以外の場合、リレーションをスキャンする別の計画が B-tree インデックスを使って作られます。さらにインデックスが存在し、問い合わせの制約がインデックスのキーと同じ場合、もっと先の計画が検討されます。

単一のリレーションをスキャンする可能性があるすべての計画が見つかると、リレーションを結合するための計画が作られます。プランナ/オプティマイザはwhere 制約のなかで一致する結合句が存在するすべての 2 つのリレーション（例えばそれに対して where rel1.attr1=rel2.attr2 のような制約が存在する場合）のみを考慮します。プランナ/オプティマイザに考慮された結合の組にはすべての実行可能な計画が作られます。3 つの実行可能な結合戦略です。

• 入れ子反復結合： 左側のリレーションのなかで見つけられたタプルごとに右側のリレーションが 1 回スキャンされます。 この戦略は実装が簡単ですが、時間がかかる場合があります。

• マージソート結合：結合を開始する前に、それぞれのリレーションが結合属性でソートされます。そして 2 つのリレーションは両方とも結合属性で並んでいるという前提でマージされます。それぞれのリレーションがたった 1 回しかスキャンされなくて済むのでこの結合は魅力的です。

• ハッシュ結合:まず右側のリレーションがその結合属性によってハッシュされます。次に左側のリレーションがスキャンされ、見つかったそれぞれのタプルにふさわしい値が、右側のリレーションのタプルを捜し出すためのハッシュキーとして使われます。

2.5.2. 計画のデータ構造

ここで計画の中に出現するノードについてちょっと説明をします。図 \ref{plan} は例 \ref{simple_select} の問い合わせに対して作成された計画を示しています。

計画の頂点にあるノードは MergeJoin ノードで、2 つの子ノードを持ちます。 1つは lefttree フィールドに付随し、2 つ目は righttree フィールドに付随します。それぞれのサブノードは結合の 1 つのリレーションを表現します。上でも触れたように、マージソート結合には各々のリレーションがあらかじめソートされていることが必要です。各々のサブプランに Sort ノードがあるのはそのためです。問い合わせ（s.sno > 2）でさらに与えられる制約は可能な限り下に押し出され、相応するサブプランのノード SeqScan の qpqualフィールドに付随されます。

MergeJoin ノードの mergeclauses フィールドに付随されたリストは結合属性に関する情報を持っています。mergeclauses リスト（ターゲットリストにもあります）に現れる VAR ノードにある verno フィールドの値、65000 と 65001 は現在のノードのタプルではなく次の「深さ」のノード（つまりサブプランの頂点にあるノード）が使われるべきだということを意味しています。

図 \ref{plan} に出て来るすべての Sort と SeqScan ノードはターゲットリストを所有しますが、スペースが足りないため MergeJoin ノードに対するのものだけが描かれています。

プランナ/オプティマイザによって実行されるもう 1 つのタスクは、Expr と Operノードの中で演算子 ID を調整することです。始めのほうで述べたように、PostgreSQL はさまざまな種類のデータ型をサポートている上にユーザー定義の型までも使用できます。そのような大量の関数や演算子を維持するためにシステムテーブルにそれらを格納しておくことが必要となります。 各々すべての関数や演算子は一意な演算子 ID が与えられます。 制約等のなかで使われる属性の型などに基づいて、それにふさわしい演算子 ID が使わなければいけません。