8. パース、リライト、オプティマイズ の GEQO の join組み合わせパターン数

[choplin]

joinのplan treeは組み合わせ数を限定する為に、left deep treeのみを対象にしていることに触れたほうがいいかも知れません。n! である理由が明確になるので。

[snaga]

ここ、自分もまだよく分かってないんですよね。実は。 講義中も飛ばしてしまったところなので。 もうちょっと頭の中を整理したら説明を追加したいと思います。

ちなみに、この辺のGEQOの説明ってコード読むべし？ READMEか何かありましたっけ？

[choplin]

GEQOそのものではなくて、Join OrderingをDPでやるかGEQOでやるかの選択なので、コードだとココらへんですね。 https://github.com/postgres/postgres/blob/REL9_3_4/src/backend/optimizer/path/allpaths.c#L1495

READMEだとbackend/optimiser/READMEのJoin Tree Constructionとか https://github.com/postgres/postgres/blob/REL9_3_4/src/backend/optimizer/README#L67

GEQOじゃない場合の計算量はstandard_join_searchの実装を読めば分かるはず（読んでませんが…）

あと、コード眺めてたらLeft Deep Tree以外も考慮しているみたいです。すいません、間違ってました。