結合したテーブルの再配置の概要

実際のアプリケーションシナリオでは、複数のテーブルを結合することが一般的です。結合の実行効率は、各テーブルの結合順序に左右されます。

例えば：

SELECT * FROM t1, t2, t3 WHERE t1.a=t2.a AND t3.a=t2.a;

このクエリでは、テーブルを次の 2 つの順序で結合できます。

• t1はt2に結合し、次にt3に結合します。
• t2はt3に結合し、次にt1に結合します。

t1 と t3 のデータ量と分布は異なるため、これら 2 つの実行順序では異なるパフォーマンスが現れる場合があります。

したがって、オプティマイザは結合順序を決定するアルゴリズムを必要とします。現在、TiDBでは以下の2つの結合したテーブルの再配置アルゴリズムが使用されています。

• 貪欲アルゴリズム：結合に参加するすべてのノードの中で、TiDBは行数が最も少ないテーブルを選択し、他の各テーブルとの結合結果をそれぞれ推定します。そして、結合結果が最小となるペアを選択します。その後、TiDBは同様のプロセスを繰り返し、次のラウンドに向けて他のノードを選択して結合します。このプロセスは、すべてのノードが結合を完了するまで続きます。
• 動的プログラミング アルゴリズム: 結合に参加するすべてのノード間で、TiDB は可能なすべての結合順序を列挙し、最適な結合順序を選択します。

例: 結合したテーブルの再配置の貪欲アルゴリズム

前述の 3 つのテーブル (t1、t2、t3) を例に挙げます。

まず、TiDB は結合操作に参加するすべてのノードを取得し、行番号の昇順にノードをソートします。

その後、行数が最も少ないテーブルが選択され、それぞれ他の2つのテーブルと結合されます。TiDBは出力結果セットのサイズを比較し、結果セットが小さい方のテーブルを選択します。

その後、TiDBは次の選択ラウンドに進みます。4つのテーブルを結合しようとすると、TiDBは出力結果セットのサイズを比較し続け、結果セットが小さい方のペアを選択します。

この場合、結合されるテーブルは 3 つだけなので、TiDB は最終的な結合結果を取得します。

例: 結合したテーブルの再配置の動的計画法アルゴリズム

前述の3つのテーブル（t1、t2、t3）を例に挙げると、動的計画法アルゴリズムはすべての可能性を列挙できます。したがって、 t1テーブル（行数が最も少ないテーブル）から開始する必要がある貪欲アルゴリズムと比較すると、動的計画法アルゴリズムは次のように結合順序を列挙できます。

この選択が貪欲アルゴリズムよりも優れている場合、動的プログラミング アルゴリズムはより適切な結合順序を選択できます。

すべての可能性が列挙されるため、動的プログラミングアルゴリズムはより多くの時間を消費し、統計の影響を受けやすくなります。

結合したテーブルの再配置アルゴリズムの選択

TiDBの結合したテーブルの再配置アルゴリズムの選択は、変数tidb_opt_join_reorder_thresholdによって制御されます。結合したテーブルの再配置に参加するノードの数がこのしきい値を超える場合、TiDBは貪欲アルゴリズムを使用します。それ以外の場合は、TiDBは動的計画法アルゴリズムを使用します。

結合したテーブルの再配置アルゴリズムの制限

現在の結合したテーブルの再配置アルゴリズムには次の制限があります。

• 結果セットの計算方法によって制限されるため、アルゴリズムでは最適な結合順序を確実に選択することはできません。
• 結合したテーブルの再配置アルゴリズムの外部結合のサポートは、 tidb_enable_outer_join_reorderシステム変数によって制御されます。
• 現在、動的プログラミング アルゴリズムでは、外部結合の結合したテーブルの再配置を実行できません。

現在、TiDBでは結合順序を強制するSTRAIGHT_JOIN構文がサポートされています。詳細については構文要素の説明を参照してください。