前回まででLeft Deep Treeの話をしてきました。今回は実際にTiDBでJoin Orderを決める際のデフォルトのアルゴリズム、Greedy Solverを見ていきます。
アルゴリズムはDP(動的計画法）とGreedyの２つありますが、この選択は tidb_opt_join_reorder_threathold というパラメーターによって制御されており、このパラメーターの値より結合するテーブル数が多い場合はGreedyが利用されます。
デフォルトは0になっており、基本的に結合が発生するとGreedyが利用されるというわけです。
論理最適化
Join Orderを決める（TiDBでは、Join Reorderと呼ばれています）アルゴリズムの前に、それを呼び出す論理最適化部分のコードを見ていきます。
最適化のエントリーポイントは、logicalOptimize です。
論理最適化では、あらかじめ決められたルールを順番に適用していきます(logicalOptRuleインターフェースのoptimizeメソッドを呼び出す)が、その中の一つにJoin Reorderを行うjoinReOrderSolverがあります。
このjoinReOrderSolver::optimizeメソッドはoptimizeRecursive メソッドを呼び出し、ここで実際の最適化が行われます。
Join Reorder
optimizeRecursive では、ヒント句の処理などを省略すると、だいたい下記のような流れになっています。
1. Join Groupの抽出
複数のJOINが連続して行われるとき、例えば SELECT ... FROM A JOIN B JOIN C ... みたいな場合に、この一連のJOINをフラットにした配列を作成します。
この関数の中には今回立ち入りませんが、コメントにある通り一連のJOINのツリーをフラットにしたグループを返します。
2. GreedyまたはDPの適用
冒頭説明したGreedyの判定をここで行っています。
というところで、次回はGreedyの中身 joinReorderGreedySolver::solve を見ていきたいと思います。
おまけ: ヒントとOuter Join
コードを読んでいくと、ヒント(Leading Hint)とOuter Joinの判定が散乱しているのがわかります。これはヒントやOuter JoinはJoin Orderを固定する効果を持つからだと思われます。
SQLではJOINしたテーブルに別名をつけることもできるので、その別名に対してヒントがあるとその構造を保存するといったロジックがあり、コーナーケースの把握は大変だと思いました。
TiDB ユーザーグループ「TiUG」ブログです。 TiDBにまつわるMeetup など行っていますので、ぜひご興味持たれたら気軽に参加ください。 <connpass> tiug.connpass.com/ <Discord> discord.gg/FqNgZ4UCwa
Discussion