本文來源于數(shù)據(jù)庫架構(gòu)之美，作者數(shù)據(jù)庫架構(gòu)之美
我們知道MySQL沒有hash join，也沒有merge join，所以在連接的時候只有一種算法nest loop join，nl join使用驅(qū)動表的結(jié)果集作為外表到內(nèi)表中查找每一條記錄，如果有索引，就會走索引掃描，沒有索引就會全表掃。
nl join并不能適用所有場景，例如兩個表都是很大的表的等值連接，這種場景是hash join所擅長的，而且是生產(chǎn)環(huán)境中最常見的場景。mysql在這個時候就顯得力不從心，所以在使用mysql時我們可能會制定如下規(guī)范：禁止使用大表連接。這也是mysql永遠的痛。不過據(jù)說8.0版本已經(jīng)將hash join作為一個需求納入了，我們拭目以待吧。
相比起來，postgresql的優(yōu)化器十分的強勁。支持了hash join、nest loop、sort merge join，掃描算法支持seq scan、index scan、index only scan，同時還支持堆內(nèi)元組技術(shù)（HOT）。在postgresql11版本中還加入了并行掃描，親測在兩張大表（一張1.6億一張256萬數(shù)據(jù)，均無索引）做join結(jié)果集300多萬，pg開啟并行大概20s以內(nèi)就跑出結(jié)果，強于其他數(shù)據(jù)庫。
上面討論了兩表join的算法，下面看看多表join時mysql和pg是如何處理的。多表join其實涉及到一個問題：如何找到代價最小的最優(yōu)路徑。為什么會有這個問題呢？因為在多表連接時，每兩個表之間連接具有一個代價值，優(yōu)化器會根據(jù)代價估算調(diào)整不同表join的順序，最后算出一個最優(yōu)或者近似最優(yōu)代價，使用這個代價生成執(zhí)行計劃，這樣就涉及到圖論中的最短路徑問題，不同的連接順序組合代表了圖的遍歷，最優(yōu)代價其實就是求無源圖的最短路徑問題。我們知道兩種主流的最短路徑算法是迪杰斯特拉（Dijkstra）算法和弗洛伊德（floyd）算法，這兩種算法也是動態(tài)規(guī)劃中的經(jīng)典算法。
在mysql中計算最優(yōu)代價使用貪心算法，而pg使用的是動態(tài)規(guī)劃。
Mysql：
Mysql連接使用貪心算法，下面這個圖表明了貪心算法的過程：
貪心算法的前提是確定源點，算法思想也和名字很像，只找當前步驟的最優(yōu)解，是一種深度優(yōu)先的解法，算法復(fù)雜度是O（n²）找到后繼續(xù)深入下一層，直至達到終點。比如上圖從A到G，使用貪心算法的路徑是A->B->D->G算法，代價是1+2+6=9，很明顯這并不是最優(yōu)解，最優(yōu)解我們?nèi)庋劭梢钥闯鰜硎茿->C->F->G，代價是2+3+1=6。所以我們看貪心算法并不是全局最優(yōu)的，但是優(yōu)點是算法復(fù)雜度低，mysql可能也是基于這種考慮而使用貪心算法，不想將時間都浪費在計算代價上了，因為如果關(guān)聯(lián)的表特別多，那么代價的計算是指數(shù)級增長，所以貪心算法雖然不是最優(yōu)解，但是在連接表的數(shù)量很大的情況下具有一定優(yōu)勢。
Postgresql：
再來看看pg使用的動態(tài)規(guī)劃，動態(tài)規(guī)劃解決的是無源最短路徑問題，我們想象一下其實多表連接本身就是一個無源最短路徑問題，只是mysql在進行連接的時候隨機選了一個作為起點而已。
動態(tài)規(guī)劃的思想是將問題分解為子問題，將問題遞推為子問題進行解決。以floyd算法為例。算法使用鄰接矩陣來表示每個點之間的距離，如果沒有連線，則代表無窮大。比如下面這個圖：
弗洛伊德算法使用矩陣記錄節(jié)點直接距離，它的強大之處在于它經(jīng)過若干次計算后得到任意兩個節(jié)點直接的最短距離，是真正意義上的無源最短路徑算法，但是它的算法復(fù)雜度也比較高，是O（n³）。下面介紹一下該算法，算法的核心思想是如果a[ij]>a[ik]+a[kj]，那么a[ij]=a[ik]+a[kj]，對于每兩個節(jié)點ab之間的距離，如果存在第三個中間節(jié)點c使得acb的距離更短，那么ab的距離使用acb代替，并更新到矩陣。這樣的遍歷過程我們大致就理解了需要三層循環(huán)，里面的兩層循環(huán)是對于ab、ac、ad...de總共（n-1）*（n-1）種選擇（自己對自己的距離不用計算）計算每個中間節(jié)點（最外層循環(huán)）的距離是否更小。矩陣計算過程如下：
對于第一行，依次計算ab，ac，ad，ae的距離是否有第三個節(jié)點進行替換，對于ab計算發(fā)現(xiàn)，ab<ac+cb&&ab<ad+db&&ab<ae+eb，所以ab不用更新，同理ac也不用更新，對于ad，計算得到ab+bd=6，ac+cd=∞，ae+ed=∞，于是更新ad=6，同理計算更新ae=8；然后依次計算下面幾行。全部遍歷完，經(jīng)歷了三層循環(huán)，算法復(fù)雜度是O（n³）。pg使用該算法能夠得到最優(yōu)執(zhí)行計劃，但是在表的個數(shù)很多時計算代價所付出的代價也很大。
綜上，mysql使用貪心算法只能得到局部最優(yōu)執(zhí)行計劃，但是計算最優(yōu)解所消耗的代價較小，而pg使用動態(tài)規(guī)劃能夠得到最優(yōu)執(zhí)行計劃，但是計算最優(yōu)解算法復(fù)雜度較高，代價較大。但是總體上mysql的優(yōu)化器相比pg還是有很大差距，pg的優(yōu)化器甚至引入了基因算法，有很多比較學(xué)術(shù)的考量，當?shù)闷饘W(xué)術(shù)派數(shù)據(jù)庫的稱號，也希望mysql能夠越來越好吧。
