MySQL源碼:JOIN順序選擇的復雜度

來源：懂視網(wǎng) 責編：小采時間：2020-11-09 13:13:56

MySQL源碼:JOIN順序選擇的復雜度

MySQL源碼:JOIN順序選擇的復雜度:在看MySQL優(yōu)化器代碼過程中，這應該是相對較簡單/代碼較清晰的部分了。MySQL優(yōu)化器有兩個自由度：單表訪問方式，多表順序選擇。前文已經(jīng)介紹過MySQL單表訪問的一些考量(ref/range等)，本文將介紹JOIN在順序選擇上的復雜度分析。當有多個表需要JOIN的時

推薦度：

點擊下載本文 文檔為doc格式

導讀MySQL源碼:JOIN順序選擇的復雜度:在看MySQL優(yōu)化器代碼過程中，這應該是相對較簡單/代碼較清晰的部分了。MySQL優(yōu)化器有兩個自由度：單表訪問方式，多表順序選擇。前文已經(jīng)介紹過MySQL單表訪問的一些考量(ref/range等)，本文將介紹JOIN在順序選擇上的復雜度分析。當有多個表需要JOIN的時

在看MySQL優(yōu)化器代碼過程中，這應該是相對較簡單/代碼較清晰的部分了。MySQL優(yōu)化器有兩個自由度：單表訪問方式，多表順序選擇。前文已經(jīng)介紹過MySQL單表訪問的一些考量(ref/range等)，本文將介紹JOIN在順序選擇上的復雜度分析。當有多個表需要JOIN的時候，M

在看MySQL優(yōu)化器代碼過程中，這應該是相對較簡單/代碼較清晰的部分了。MySQL優(yōu)化器有兩個自由度：單表訪問方式，多表順序選擇。前文已經(jīng)介紹過MySQL單表訪問的一些考量(ref/range等)，本文將介紹JOIN在順序選擇上的復雜度分析。

當有多個表需要JOIN的時候，MySQL首先會處理兩類特殊情況，一個是常數(shù)表，一個是由于外連接導致順序依賴關(guān)系。前者總是放在關(guān)聯(lián)的最前面，后者會在遍歷的時候考慮。本文將忽略上面兩點，從較宏觀角度看JOIN順序選擇時候的復雜度。

在設置了參數(shù)prune_level(默認設置)后，MySQL使用"極其"貪婪的方式獲取順序。如果未設置，則使用了有限窮舉獲取"最優(yōu)"的執(zhí)行計劃。

1. 有限窮舉

有限窮舉只在參數(shù)prune_level關(guān)閉時才使用，默認情況prune_level時打開的。所以，MySQL一般不這么做。如果只想了解prune_level打開的時候，直接跳過本節(jié)，參考貪婪的MySQL。

在關(guān)閉參數(shù)prune_level后，MySQL基本上就是窮舉了，說"有限"是指，當關(guān)聯(lián)表的數(shù)量超過63時(search_depth的默認值)，達到最大深度， MySQL將分多個階段窮舉。當關(guān)聯(lián)表的數(shù)量較少的時候(小于search_depth)，MySQL會窮舉所有可能，然后計算每個JOIN順序的成本，選擇成本最低的作為其執(zhí)行計劃。關(guān)于這部分的算法復雜度，在代碼注釋中有較為詳細的描述，建議閱讀函數(shù)greedy_search的注釋先。下面是注釋部分的兩段偽代碼，很好的描述了整個過程：

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。上面的代碼中，執(zhí)行計劃的擴展由函數(shù)best_extension，初始pplan為空，do循環(huán)結(jié)束輸出最終的執(zhí)行計劃。

1.2 best_extension

best_extension中調(diào)用函數(shù)best_extension_by_limited_search完成遞歸遍歷，其輸入是部分執(zhí)行計劃(pplan)和它的成本，函數(shù)目的是找到下一個關(guān)聯(lián)的表。思路很簡單，遍歷所有剩余表，對每一個表，計算對應的"局部"最優(yōu)執(zhí)行計劃，當然計算這個“局部”最優(yōu)仍然是調(diào)用這個函數(shù)，所以這是一個深度優(yōu)先的遍歷。

偽代碼(是不是又有人說我總貼代碼了)：

 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

一個說明：在每次遍歷的時候，一旦發(fā)現(xiàn)成本大于當前的最優(yōu)成本，則放棄，不再繼續(xù)深入。

1.3 簡單的小結(jié)

函數(shù)的輸入：
	部分執(zhí)行計劃 partial plan
	N個剩余表
函數(shù)

輸出：當 N search_depth，返回search_depth個表的最優(yōu)執(zhí)行計劃，并合并到部分執(zhí)行計劃遞歸調(diào)用該函數(shù)，輸入為：當前部分執(zhí)行計劃剩余表N-depth

1.4 復雜度分析

join-complex

所以，復雜度可能是O(N*N^search_depth/search_depth)。如果search_depth > N 那么算法的復雜度就是O(N!)。通常MySQL優(yōu)化器分析的復雜度都是O(N!)。

1.5 邊界情形

有兩個比較極端的情況：

– 當需要JOIN的表的數(shù)量小于search_depth時，這里就退化為一個深度優(yōu)先的窮舉確定最優(yōu)執(zhí)行計劃

– 當search_depth = 1的時候，函數(shù)退化為"極其"貪婪的算法，每次從當前的剩余的表中取一個成本最小的，來擴展當前的執(zhí)行計劃

剩余的情況就是介于上面兩者之間。

2. 貪婪的MySQL

在打開了參數(shù)prune_level(默認開啟)后，MySQL不再使用窮舉的方式擴展執(zhí)行計劃，而是在剩余表中直接選取訪問最少紀錄數(shù)的表。按照MySQL手冊上的描述是：根據(jù)經(jīng)驗來看，這種”educated guess”基本不會漏掉最優(yōu)的執(zhí)行計劃，但是卻可以大大(dramatically )縮小搜索空間。要是你懷疑漏掉了某個最優(yōu)的執(zhí)行計劃，你可以考慮關(guān)閉參數(shù)試試，當然這會導致搜索空間增大，優(yōu)化器執(zhí)行時間偏長。

這個參數(shù)在深度優(yōu)先搜索中起作用，在進行深度探索時，根據(jù)current_record_count和current_read_time，來確定，這是不是一個好的執(zhí)行計劃。(原本是需要遞歸調(diào)用計算成本確定)

下面是一個簡單的偽代碼描述：

場景：
pplan 	當前部分執(zhí)行計劃(初始為空) short for partial plan
N remaining table 	當前剩余表(初始化時，為除了常數(shù)表之外的所有表)
	這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) 偽代碼中未考慮依賴關(guān)系。第一個表的COST總是會計算出來。

(2) 面對pplan和T[0...N-1]時，只計算pplan與T[0],T[1]…T[N-1]的關(guān)聯(lián)后各自的current_record_count，并以此為依據(jù)選擇，pplan應該跟哪一個表JOIN。除了第一個表(搜索樹的最左邊的那各分支)會遞推計算其代價，其他所有分支都只是蜻蜓點水般只計算一級，而不會深度遞歸計算。

(3) 這看起來這是一個非常激進的優(yōu)化方式。

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順序之前會根據(jù)每個表可能訪問的紀錄數(shù)，進行一次排序。這一步看似多余，但是當窮舉搜索時，可以大大的減少執(zhí)行計劃需要探測的深度。

當評估某個執(zhí)行計劃的時候，如果某一步發(fā)現(xiàn)當前的cost已經(jīng)大于最優(yōu)的執(zhí)行計劃時，則立即退出評估。這意味著，如果最先找到最優(yōu)的執(zhí)行計劃，那么需要做的評估將會少很多。如果某個表需要掃描的行數(shù)越少，那么可以初步認為越先使用越好。當然，因為這里的排序評估是沒有使用JOIN條件的，所以，看起來需要掃描很多的，也可能加上JOIN以后只需要掃描很少的記錄。