TiDBソースコード輪読会補遺: Join Order Greedy Solver(2)

Join Order Greedy Solverの二回目です。今回は、joinReorderGreedySolver::solve を読んでいきます。

https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder_greedy.go#L45

Greedy Solverの動きについては、TiDBのドキュメントにも記載があります。
https://docs.pingcap.com/tidb/stable/join-reorder

前回では、Greedy Solverが呼ばれるまでの過程を説明しました。

• 論理最適化のステップの一つとしてJoin Reorderがある。
• Join Reorderでは論理実行計画の中の一連のJoinから、Joinの構造をフラットにしたJoin Groupを作成する。
• それらに対してDPもしくはGreedy Solverを適用する。(Greedyがデフォルト）

では、Greedy Solverについて中の処理を見ていきます。

1. Join Groupのコストの算出

まず、[]LogicalPlan であるJoin Groupから []*jrNode を作成します。jrNode構造体は、LogicalPlanとそのコストの組です。Joinの並べ替えを行う際に、このコストを使います。
https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder.go#L216-L219

コストの算出は、baseSingleGroupJoinOrderSolver::generateJoinOrderNode で行われます。ここではJoin Groupの各ノードのコスト（再帰的に子供のコストも積算する）を計算して、jrNodeを作成しています。具体的には、統計情報から行数を取得し、それをコストとしています。
https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder_greedy.go#L47

これで、イメージ的にはJoinするそれぞれのテーブルについて、それぞれのテーブルの行数をコストとするリストができたことになります。

2. ソート

jrNodeのスライスを、コスト順でソートしています。
https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder_greedy.go#L61

Greedy SolverではまずJoinコストが最小となる２つのテーブルを見つけ、次にそのJoin済みテーブルとのJoinコストが最小となる追加の1テーブルを見つけ、、、という処理を繰り返します。
一般的に駆動表の行が小さい方が処理は速くなることからこうしているものと思います。

3. Greedyアルゴリズム

その後、ソート済みの jrNodeのスライスに対して、Greedyアルゴリズムを適用していきます。
Greedyアルゴリズムは、joinReorderGreedySolver::constructConnectedJoinTree で実装されています。

Greedyアルゴリズムの実装は下記のようになっています。

1. join Groupの最初の要素を結果ツリーの初期値とする。
2. 結果ツリーに追加するものがなくなるまでループ
   2.1 join Groupのすべての要素に対して、結果ツリーとのJoinコストを算出する
   2.2 Joinコストが最小となる要素を、結果ツリーに追加する。結果ツリー <- Join(結果ツリー, 要素)
   2.3 追加した要素はjoin Groupから削除して、2.1に戻る
3. 結果ツリーを返す

これにより、例えば [A,B,C,D]というjoin Groupが与えられたときに、JOIN(JOIN(JOIN(A,B),C),D) というようなLeft Deep Treeが作られます。

実際のコードで 2.1 の部分を見てみます。
https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder_greedy.go#L103-L111

結果ツリーと要素のJoinが可能かどうか、可能ならばどのようなJoinにするかを決め、結果のツリーを返すのが joinReorderGreedySolver::checkConnectionAndMakeJoin です。

3.1 Joinコスト計算の詳細

作成されたツリーのコストの計算は、二段階になっていて、

1. 新しく作られたJoinの統計情報の算出
2. 上記を元に、Joinの累積コストを算出

となっています。上記の計算が LogicalPlan::recursiveDeriveStats で、下記の計算が baseSingleGroupJoinOrderSolver::calcJoinCumCost です。

LogicalPlan::recursiveDeriveStats は再帰的に子供に適用され、最終的に LogicalPlan::DeriveStats を呼び出します。このインターフェースはLogicalPlanの種類ごとに実装されています。おそらく今回のメインターゲットとなる、LogicalJoin::DeriveStats を見てみます。

https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/stats.go#L808-L816

ここではコスト計算の詳細には立ち入りませんが、Joinに利用するカラムのNDV（ユニークな種類の数）を元に行数を見積もっています。コメントに記載の式によれば

$$\text{RowCount} = \frac{N(s) \times N(t)}{V(s.key) \times V(t.key)} \times \min(V(s.key), V(t.key)) = \frac{N(s) \times N(t)}{\max(V(s.key),V(t.key))}$$

• N(t) は テーブルtの行数
• V(t.key) はt.keyのNDV

です。これは結合するとき、相手側のテーブルで平均何行引けるかを考えてみるとわかりやすいかもしれません。あるキー値があったとき、そのキー値に対応する相手側のテーブルの行数は、平均 N/Vとなります。

それぞれのJoinでこのような行数の統計ができたところで、Join全体の累積コストを算出します。
コスト計算は baseSingleGroupJoinOrderSolver::calcJoinCumCost で、
https://github.com/pingcap/tidb/blob/42b624cbdedbd2f29386427fae0c539041647e09/pkg/planner/core/rule_join_reorder.go#L683-L686

このように意外と単純です。Join結果の行数見積り + 左側の子供の累積コスト + 右側の子供の累積コスト です。

これでGreedy Solverの解説はだいたい終わりです。solve メソッドは最後に baseSingleGroupJoinOrderSolver::makeBushyJoin で、Greedy Solverが作ったツリーが複数ある場合は、それを再帰的に連結します。

どういった場合にツリーが複数できるかは調べていませんが、コメントによれば直積となる場合、つまり結合条件なしで結合する場合と思われます。(Cross Joinです)

Further Reading

Greedy Solverの実装を見て以外とシンプルだなと思ったかもしれません。DBによってJoin Reorderの実装は様々で、どのようなバリエーションがあるかは次のリンクに詳しいです。

https://www.alibabacloud.com/blog/join-reorder---core-technology-of-polardb-for-xscale-optimizer_600508

上記のリンクによれば、各データベースの実装は次の表のようになっているそうです。

Join Reorder Algorithm	Default Database	INFO
Greedy Heuristic Join Reorder Algorithm for Single Sequence	TiDB	Left Deep Tree
Greedy Heuristic Join Reorder Algorithm for Multiple Sequences	Flink, Drill, and PolarDB distributed edition	Left Deep Tree, you can compare N Join sequences and select the one with the lower cost.
Genetic Algorithm	PostgreSQL	This feature is enabled only when the number of tables is greater than 12. The Join sequence is unstable each time.
Join Reorder Algorithm for Depth-First Enumeration	MySQL	Left Deep Tree, when the number of tables is less than or equal to 7, the algorithm complexity is N! and dynamic planning is not used.
Join Reorder Algorithm for Bottom-Up Enumeration	PostgreSQL	Bottom-Up dynamic planning enumeration of Left Deep Tree or Bushy Join Tree search space
Join Reorder Algorithm for Top-Down Enumeration Based on Rule Transformation	PolarDB distributed edition, SQLServer, and CockroachDB	Top-Down dynamic planning enumeration of Left Deep Tree or Bushy Join Tree, which can be used for space pruning and mixed with other optimization rules for global optimization.