MySQLソース:JOINシーケンス選択の複雑さ
7012 ワード
MySQLオプティマイザコードを見ていると、比較的簡単/コードがはっきりしている部分になるはずです.MySQLオプティマイザには2つの自由度があります.シングルテーブルアクセス方式、マルチテーブル順序選択です.前述したMySQLシングルテーブルアクセスのいくつかの考慮(ref/rangeなど)について説明したが,本稿ではJOINの順序選択における複雑さの解析を紹介する.
複数のテーブルがJOINを必要とする場合、MySQLはまず2つの特殊な状況を処理します.1つは定数テーブルで、1つは外部接続による順序依存関係です.前者は常に関連の一番前に置かれ、後者は遍歴するときに考えられる.本稿では,上記2点を無視して,JOIN順選択時の複雑さをマクロ的に見る.
パラメータが設定されているprune_level(デフォルト)後、MySQLは「極めて」貪欲な方法で順序を取得します.設定されていない場合は、限られた窮挙を使用して「最適」の実行計画を取得します.
1.限られた貧乏行為
有限窮挙はパラメータpruneのみレベルがオフの場合にのみ使用されます.デフォルトではprune_レベル時に開きます.だから、MySQLは普通はそうしません.pruneだけ知りたいならレベルが開いたときは、このセクションを直接スキップして、貪欲なMySQLを参考にします.
パラメータprune_を閉じるlevel後、MySQLは基本的に貧乏で、「有限」とは、関連テーブルの数が63を超えると(search_depthのデフォルト値)、最大深さに達し、MySQLは複数の段階に分けて貧乏になることを意味します.関連テーブルの数が少ない場合(search_depthより小さい場合)、MySQLは可能性をすべて挙げ、JOIN順序ごとのコストを計算し、実行計画として最も低いコストを選択します.この部分のアルゴリズムの複雑さについては、コード注釈に詳しく説明されていますが、関数greedy_を読むことをお勧めします.searchのコメント先.次に、注釈セクションの2つの偽コードを説明します.プロセス全体を説明します.
1.1 greedy_search
ここでの(t,a)はbest_extensionは、次のJOINが必要なテーブルtを返し、決定されたアクセス方法はaである.上のコードでは、実行計画の拡張は関数best_によって行われます.extension、初期pplanは空で、doループは最終的な実行計画を出力します.
1.2 best_extension
best_extensionで関数bestを呼び出すextension_by_limited_searchは再帰ループを完了し、その入力は部分実行計画(pplan)とそのコストであり、関数の目的は次の関連テーブルを見つけることである.考え方は簡単で、すべての残りのテーブルを遍歴し、各テーブルに対して、対応する「ローカル」最適実行計画を計算します.もちろん、この「ローカル」最適計算はこの関数を呼び出すので、これは深さ優先の遍歴です.
偽コード(また誰かが私がコードを貼ったと言ったのではないでしょうか):
1つの説明:遍歴するたびに、現在の最適コストよりもコストが大きいことが発見されると、あきらめて深く進まない.
1.3簡単なまとめ
1.4複雑度分析
したがって、複雑度はO(N*N^search_depth/search_depth)である可能性がある.もしsearch_depth>Nではアルゴリズムの複雑さはO(N!)である.通常MySQLオプティマイザ解析の複雑さはO(N!)です.
1.5境界状況
極端なケースは2つあります.
-JOINが必要なテーブルの数がsearchより小さい場合depthの場合,ここでは深さ優先の貧挙に退化して最適実行計画を決定する.
-search_depth=1の場合、関数は「極めて」貪欲なアルゴリズムに劣化し、現在の残りのテーブルからコストを最小限に抑え、現在の実行計画を拡張します.
残りの状況は上の2つの間にある.
2.欲張りMySQL
パラメータprune_を開いたlevel(デフォルトでオン)にすると、MySQLは実行計画を窮屈な方法で拡張するのではなく、残りのテーブルで最も少ないレコード数にアクセスするテーブルを直接選択します.MySQLマニュアルによると、経験的には、このような「educated guess」は、最適な実行計画をほとんど漏らさないが、検索空間を大幅に縮小することができるという.最適な実行計画が漏れているのではないかと疑う場合は、パラメータを閉じてみてください.もちろん、検索空間が大きくなり、オプティマイザの実行時間が長くなります.
このパラメータは深さ優先探索に役立ち,深さ探索を行う際にcurrent_に基づいてrecord_countとcurrent_read_time、これが良い実行計画かどうかを確定します.(本来は計算コスト決定を再帰的に呼び出す必要がある)
以下に、簡単な疑似コードの説明を示します.
説明:
(1)擬似コードに依存関係は考慮されていない.最初のテーブルのCOSTはいつも計算されます.
(2)pplanとT[0…N-1]に対してpplanとT[0]、T[1]…T[N-1]との関連付け後のそれぞれのcurrent_のみを計算するrecord_count、それに基づいて、pplanはどのテーブルJOINに従うべきかを選択します.最初のテーブル(検索ツリーの一番左のブランチ)がその代価を計算するのを除いて、他のすべてのブランチはトンボが水を点すように1級だけ計算され、深さの再帰計算は行われません.
(3)これは非常に急進的な最適化方式であるように見える.
3.開始前のソート
MySQLは、JOIN順序の決定を開始する前に、テーブルごとにアクセス可能なレコード数に基づいて、一度ソートします.このステップは余計に見えますが、貧しい検索を行うと、計画を実行するために探知する必要がある深さを大幅に減らすことができます.
実行計画を評価するとき、現在のcostが最適な実行計画よりも大きいことがステップで発見された場合、すぐに評価を終了します.これは、最適な実行計画が最初に見つかった場合、評価が少なくなることを意味します.テーブルがスキャンする必要があるロー数が少ないほど、先に使用すればするほど良いと考えられます.もちろん、ここでのソート評価ではJOIN条件は使用されていないので、スキャンが多く必要なように見えますが、JOINを加えて以降はスキャンが少ない記録しか必要ないかもしれません.
4.関数呼び出しスタック
#0 best_access_path
#1 best_extension_by_limited_search
#2 greedy_search
#3 choose_plan
#4 make_join_statistics
#5 JOIN::optimize
関連記事 2008-12-05--MySQLにおけるJoinの基本実現原理 2009-11-08--MySQLにおけるLEFTJOINのメインテーブル 2009-04-14--MySqlランダム読み出しデータ 2012-03-26--Mysqlソース学習-Thread Manager 2008-10-30--limitクエリーを使用しながら合計レコード数を取得:SQL_CALC_FOUND_ROWSとFOUND_ROWS() 2012-02-13--タイプ変換がMySQL選択インデックスに与える影響 2010-06-01--mysql server上の小さなテクニック 2012-12-23--MySQL TPCHテストツールパンフレット 2012-12-05--初心者必見:一歩で到着するInnoDB 2012-12-05--MySQL最適化のDiscuzフォーラムMySQL汎用最適化 ラベル:join,MySQLソース分析
複数のテーブルがJOINを必要とする場合、MySQLはまず2つの特殊な状況を処理します.1つは定数テーブルで、1つは外部接続による順序依存関係です.前者は常に関連の一番前に置かれ、後者は遍歴するときに考えられる.本稿では,上記2点を無視して,JOIN順選択時の複雑さをマクロ的に見る.
パラメータが設定されているprune_level(デフォルト)後、MySQLは「極めて」貪欲な方法で順序を取得します.設定されていない場合は、限られた窮挙を使用して「最適」の実行計画を取得します.
1.限られた貧乏行為
有限窮挙はパラメータpruneのみレベルがオフの場合にのみ使用されます.デフォルトではprune_レベル時に開きます.だから、MySQLは普通はそうしません.pruneだけ知りたいならレベルが開いたときは、このセクションを直接スキップして、貪欲なMySQLを参考にします.
パラメータprune_を閉じるlevel後、MySQLは基本的に貧乏で、「有限」とは、関連テーブルの数が63を超えると(search_depthのデフォルト値)、最大深さに達し、MySQLは複数の段階に分けて貧乏になることを意味します.関連テーブルの数が少ない場合(search_depthより小さい場合)、MySQLは可能性をすべて挙げ、JOIN順序ごとのコストを計算し、実行計画として最も低いコストを選択します.この部分のアルゴリズムの複雑さについては、コード注釈に詳しく説明されていますが、関数greedy_を読むことをお勧めします.searchのコメント先.次に、注釈セクションの2つの偽コードを説明します.プロセス全体を説明します.
1.1 greedy_search
4997 procedure greedy_search
4998 input: remaining_tables
4999 output: pplan;
5000 {
5001 pplan = ;
5002 do {
5003 (t, a) = best_extension(pplan, remaining_tables);
5004 pplan = concat(pplan, (t, a));
5005 remaining_tables = remaining_tables - t;
5006 } while (remaining_tables != {})
5007 return pplan;
5008 }
ここでの(t,a)はbest_extensionは、次のJOINが必要なテーブルtを返し、決定されたアクセス方法はaである.上のコードでは、実行計画の拡張は関数best_によって行われます.extension、初期pplanは空で、doループは最終的な実行計画を出力します.
1.2 best_extension
best_extensionで関数bestを呼び出すextension_by_limited_searchは再帰ループを完了し、その入力は部分実行計画(pplan)とそのコストであり、関数の目的は次の関連テーブルを見つけることである.考え方は簡単で、すべての残りのテーブルを遍歴し、各テーブルに対して、対応する「ローカル」最適実行計画を計算します.もちろん、この「ローカル」最適計算はこの関数を呼び出すので、これは深さ優先の遍歴です.
偽コード(また誰かが私がコードを貼ったと言ったのではないでしょうか):
5171 @code
5172 procedure best_extension_by_limited_search(
5173 pplan in, // in, partial plan of tables-joined-so-far
5174 pplan_cost, // in, cost of pplan
5175 remaining_tables, // in, set of tables not referenced in pplan
5176 best_plan_so_far, // in/out, best plan found so far
5177 best_plan_so_far_cost,// in/out, cost of best_plan_so_far
5178 search_depth) // in, maximum size of the plans being considered
5179 {
5180 for each table T from remaining_tables
5181 {
5182 // Calculate the cost of using table T as above
5183 cost = complex-series-of-calculations;
5184
5185 // Add the cost to the cost so far.
5186 pplan_cost+= cost;
5187
5188 if (pplan_cost >= best_plan_so_far_cost)
5189 // pplan_cost already too great, stop search
5190 continue;
5191
5192 pplan= expand pplan by best_access_method;
5193 remaining_tables= remaining_tables - table T;
5194 if (remaining_tables is not an empty set
5195 and
5196 search_depth > 1)
5197 {
5198 best_extension_by_limited_search(pplan, pplan_cost,
5199 remaining_tables,
5200 best_plan_so_far,
5201 best_plan_so_far_cost,
5202 search_depth - 1);
5203 }
5204 else
5205 {
5206 best_plan_so_far_cost= pplan_cost;
5207 best_plan_so_far= pplan;
5208 }
5209 }
5210 }
5211 @endcode
1つの説明:遍歴するたびに、現在の最適コストよりもコストが大きいことが発見されると、あきらめて深く進まない.
1.3簡単なまとめ
：
partial plan
N
：
N search_depth， search_depth ，
， ： N-depth
1.4複雑度分析
したがって、複雑度はO(N*N^search_depth/search_depth)である可能性がある.もしsearch_depth>Nではアルゴリズムの複雑さはO(N!)である.通常MySQLオプティマイザ解析の複雑さはO(N!)です.
1.5境界状況
極端なケースは2つあります.
-JOINが必要なテーブルの数がsearchより小さい場合depthの場合,ここでは深さ優先の貧挙に退化して最適実行計画を決定する.
-search_depth=1の場合、関数は「極めて」貪欲なアルゴリズムに劣化し、現在の残りのテーブルからコストを最小限に抑え、現在の実行計画を拡張します.
残りの状況は上の2つの間にある.
2.欲張りMySQL
パラメータprune_を開いたlevel(デフォルトでオン)にすると、MySQLは実行計画を窮屈な方法で拡張するのではなく、残りのテーブルで最も少ないレコード数にアクセスするテーブルを直接選択します.MySQLマニュアルによると、経験的には、このような「educated guess」は、最適な実行計画をほとんど漏らさないが、検索空間を大幅に縮小することができるという.最適な実行計画が漏れているのではないかと疑う場合は、パラメータを閉じてみてください.もちろん、検索空間が大きくなり、オプティマイザの実行時間が長くなります.
このパラメータは深さ優先探索に役立ち,深さ探索を行う際にcurrent_に基づいてrecord_countとcurrent_read_time、これが良い実行計画かどうかを確定します.(本来は計算コスト決定を再帰的に呼び出す必要がある)
以下に、簡単な疑似コードの説明を示します.
：
pplan ( ) short for partial plan
N remaining table ( ， )
N T[0] T[1] ... T[N-1]
：
Function best_extension(pplan,N)
Foreach T in T[0...N-1]
let P(pplan,T) := add T to pplan
let current_record_count := #row of P(pplan,T)
let current_read_time := #read time of P(pplan,T)
if [
T is Not The First Table in T[0...N-1] AND
current_record_count >= best_record_count AND
current_read_time >= best_read_time
]
"P(pplan,T) is a bad plan! SKIP it!!!!!!!"
END
let best_record_count := min(best_record_count, current_record_count )
let best_read_time := min(best_read_time,current_read_time)
best_extension(P(pplan,T),N-1);
END
説明:
(1)擬似コードに依存関係は考慮されていない.最初のテーブルのCOSTはいつも計算されます.
(2)pplanとT[0…N-1]に対してpplanとT[0]、T[1]…T[N-1]との関連付け後のそれぞれのcurrent_のみを計算するrecord_count、それに基づいて、pplanはどのテーブルJOINに従うべきかを選択します.最初のテーブル(検索ツリーの一番左のブランチ)がその代価を計算するのを除いて、他のすべてのブランチはトンボが水を点すように1級だけ計算され、深さの再帰計算は行われません.
(3)これは非常に急進的な最適化方式であるように見える.
3.開始前のソート
4753 my_qsort( join->best_ref + join->const_tables,
4754 join->tables - join->const_tables, sizeof( JOIN_TAB*),
4755 straight_ join ? join_tab_cmp_straight : join_tab_cmp);
MySQLは、JOIN順序の決定を開始する前に、テーブルごとにアクセス可能なレコード数に基づいて、一度ソートします.このステップは余計に見えますが、貧しい検索を行うと、計画を実行するために探知する必要がある深さを大幅に減らすことができます.
実行計画を評価するとき、現在のcostが最適な実行計画よりも大きいことがステップで発見された場合、すぐに評価を終了します.これは、最適な実行計画が最初に見つかった場合、評価が少なくなることを意味します.テーブルがスキャンする必要があるロー数が少ないほど、先に使用すればするほど良いと考えられます.もちろん、ここでのソート評価ではJOIN条件は使用されていないので、スキャンが多く必要なように見えますが、JOINを加えて以降はスキャンが少ない記録しか必要ないかもしれません.
4.関数呼び出しスタック
#0 best_access_path
#1 best_extension_by_limited_search
#2 greedy_search
#3 choose_plan
#4 make_join_statistics
#5 JOIN::optimize
関連記事