Optimizer

PostgreSQLのOptimizerは、Parser/Rewriterで作成されたQuery structureを受け取り、Executorが使うPlan structureを生成する。

Optimizerは利用可能な全てのアクセスパスを生成し、最もコストが小さいパスを選択する。
テーブルへのアクセスはTable ScanとIndex Scanのどちらがいいのか、Index ScanならばどのIndexを使うのがいいのかということが検討される。また、テーブルのJoin方法はNested Loop Join, Merge Join, Hash Joinのどれがいいのか、どの順番でテーブルをJoinするのがいいのかということも検討される。

例えば、select * from tab1, tab2 where tab1.key = tab2.keyというSQLの場合、まず、tab1とtab2のそれぞれについて、単純なTable Scanと利用可能な全てのIndex Scanのコストを計算する。次にtab1とtab2のJoin方法について、Nested Loop Join, Merge Join, Hash Joinの各コストを計算し、もっともコストが低い方法を選択する。Nested Loop Join, Hash Joinについては、tab1とtab2のどちらのテーブルがOuter Tableになるかによってもコストが違うため、両方のケースを計算する。(Merge JoinはどっちがOuterでも関係ない)

あるテーブルのアクセスコストのうちTable Scanが最も低い場合でも、Index Scanを使うほうがトータルコストが低くなることがある。例えばMerge Joinはタプルがソートされている必要があるが、Table Scanの場合はタプルがソートされていないため、Table Scanの後にソートする必要がある。B-Tree Index Scanの場合はタプルがソートされているので、IndexのキーとMerge Joinに必要なキーが一致する場合、そのままMerge Joinへの入力に使うことができる。Order by句にも同様のことがいえて、Indexとキーが一致する場合、ソート処理を省略できる。Merge Joinを実行した場合はその結果もソートされているので、さらに別のテーブルを同じキーでMerge Joinする場合、ソートが省略できる。
つまり、それぞれのテーブルのアクセス方法やジョイン方法について、単純にコストが一番低い方法を選択するだけではだめで、次に実行するジョイン方法などについて全ての利用可能な方法を考慮し、どの組合せがトータルコストが低くなるかを求めなければならない。(実際にはOptimizerの各フェーズでコストが高くて使えないパスを間引いており、評価するアクセスパスの組合せが爆発的に増えないように工夫されている。)

また、Optimizerの前処理では、選択肢を増やし最適化を実行しやすくするために、Queryの情報を書き換えている。
例えば以下のようなinline viewを使用したSQLがあるとして、

select ..省略.. from tab1, 
    (select tab2.key, tab2.data, tab3.data 
     from tab2, tab3 where tab2.key = tab3.key) iview
where tab1.key = iview.key 

このままではテーブルをJoinする順番は次の方法しかない。
(1)tab2とtab3をJoinしたあと、tab1をJoinする
Optimizerではinline viewを上位のSQLにマージして、以下のように変換する。

select ..省略.. from tab1, tab2, tab3
where tab1.key = tab2.key 
and tab2.key = tab3.key

これで次の選択肢が増える。
(2)tab1とtab2をJoinしたあと、tab3をJoinする
ここでwhere句をみると、tab1.key = tab2.key, tab2.key = tab3.keyから、tab1.key = tab3.keyが明らかなので、Optimizerはwhere句に以下の情報を加える。

select ..省略.. from tab1, tab2, tab3
where tab1.key = tab2.key 
and tab2.key = tab3.key
and tab1.key = tab3.key  -- この条件が追加される

これで次の選択肢が増える。
(3)tab1とtab3をJoinしたあと、tab2をJoinする