共計 2006 個字符，預計需要花費 6 分鐘才能閱讀完成。
這篇文章主要介紹 MySQL 和 PostgreSQL 在多表連接算法上的差異有哪些，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
我們知道 mysql 沒有 hash join，也沒有 merge join，所以在連接的時候只有一種算法 nest loop join，nl join 使用驅動表的結果集作為外表到內表中查找每一條記錄，如果有索引，就會走索引掃描，沒有索引就會全表掃。
nl join 并不能適用所有場景，例如兩個表都是很大的表的等值連接，這種場景是 hash join 所擅長的，而且是生產環境中最常見的場景。mysql 在這個時候就顯得力不從心，所以在使用 mysql 時我們可能會制定如下規范：禁止使用大表連接。這也是 mysql 永遠的痛。不過據說 8.0 版本已經將 hash join 作為一個需求納入了，我們拭目以待吧。
相比起來，postgresql 的優化器十分的強勁。支持了 hash join、nest loop、sort merge join，掃描算法支持 seq scan、index scan、index only scan，同時還支持堆內元組技術（HOT）。在 postgresql11 版本中還加入了并行掃描，親測在兩張大表（一張 1.6 億一張 256 萬數據，均無索引）做 join 結果集 300 多萬，pg 開啟并行大概 20s 以內就跑出結果，強于其他數據庫。
上面討論了兩表 join 的算法，下面看看多表 join 時 mysql 和 pg 是如何處理的。多表 join 其實涉及到一個問題：如何找到代價最小的最優路徑。為什么會有這個問題呢？因為在多表連接時，每兩個表之間連接具有一個代價值，優化器會根據代價估算調整不同表 join 的順序，最后算出一個最優或者近似最優代價，使用這個代價生成執行計劃，這樣就涉及到圖論中的最短路徑問題，不同的連接順序組合代表了圖的遍歷，最優代價其實就是求無源圖的最短路徑問題。我們知道兩種主流的最短路徑算法是迪杰斯特拉（Dijkstra）算法和弗洛伊德（floyd）算法，這兩種算法也是動態規劃中的經典算法。
在 mysql 中計算最優代價使用貪心算法，而 pg 使用的是動態規劃。
Mysql：
Mysql 連接使用貪心算法，下面這個圖表明了貪心算法的過程：
貪心算法的前提是確定源點，算法思想也和名字很像，只找當前步驟的最優解，是一種深度優先的解法，算法復雜度是 O（n2）找到后繼續深入下一層，直至達到終點。比如上圖從 A 到 G，使用貪心算法的路徑是 A - B- D- G 算法，代價是 1 +2+6=9，很明顯這并不是最優解，最優解我們肉眼可以看出來是 A - C- F- G，代價是 2 +3+1=6。所以我們看貪心算法并不是全局最優的，但是優點是算法復雜度低，mysql 可能也是基于這種考慮而使用貪心算法，不想將時間都浪費在計算代價上了，因為如果關聯的表特別多，那么代價的計算是指數級增長，所以貪心算法雖然不是最優解，但是在連接表的數量很大的情況下具有一定優勢。
Postgresql：
再來看看 pg 使用的動態規劃，動態規劃解決的是無源最短路徑問題，我們想象一下其實多表連接本身就是一個無源最短路徑問題，只是 mysql 在進行連接的時候隨機選了一個作為起點而已。
動態規劃的思想是將問題分解為子問題，將問題遞推為子問題進行解決。以 floyd 算法為例。算法使用鄰接矩陣來表示每個點之間的距離，如果沒有連線，則代表無窮大。比如下面這個圖：
弗洛伊德算法使用矩陣記錄節點直接距離，它的強大之處在于它經過若干次計算后得到任意兩個節點直接的最短距離，是真正意義上的無源最短路徑算法，但是它的算法復雜度也比較高，是 O（n3）。下面介紹一下該算法，算法的核心思想是如果 a[ij] a[ik]+a[kj]，那么 a[ij]=a[ik]+a[kj]，對于每兩個節點 ab 之間的距離，如果存在第三個中間節點 c 使得 acb 的距離更短，那么 ab 的距離使用 acb 代替，并更新到矩陣。這樣的遍歷過程我們大致就理解了需要三層循環，里面的兩層循環是對于 ab、ac、ad…de 總共（n-1）*（n-1）種選擇（自己對自己的距離不用計算）計算每個中間節點（最外層循環）的距離是否更小。矩陣計算過程如下：
對于第一行，依次計算 ab，ac，ad，ae 的距離是否有第三個節點進行替換，對于 ab 計算發現，ab ac+cb ab ad+db ab ae+eb，所以 ab 不用更新，同理 ac 也不用更新，對于 ad，計算得到 ab+bd=6，ac+cd=∞，ae+ed=∞，于是更新 ad=6，同理計算更新 ae=8；然后依次計算下面幾行。全部遍歷完，經歷了三層循環，算法復雜度是 O（n3）。pg 使用該算法能夠得到最優執行計劃，但是在表的個數很多時計算代價所付出的代價也很大。
以上是“MySQL 和 PostgreSQL 在多表連接算法上的差異有哪些”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注丸趣 TV 行業資訊頻道！
