通往性能優化的JOIN方法說明

看到很多朋友對資料庫的了解、認識還是沒有突破一個瓶頸，而這個瓶頸往往隻是一層窗紙，越過了你将看到一個新世界。

04、05年做項目的時候，用SQL Server 2000，核心表（大部分使用頻繁的關鍵功能每次都要用到）達到了800萬資料量，很早以前查過一些相關表，有的達到了3000多萬，磁盤使用的光纖盤，100G空間，每周必須備份轉移資料，否則100G空間一周會滿掉，這個系統幾年來，目前仍然保持非常良好的性能。還聽說過朋友的SQL Server 2000資料庫工作在幾十TB的環境下，高并發量，對這種級别的駕馭能力我還是差的很遙遠。

想當年，也是一提SQL Server，就覺得它的性能沒法跟Oracle相比，一提到大資料處理就想到Oracle。自己一路走來，在本地blog上記錄了很多優化方面的post，對的錯的都有，沒有時間系列的整理出來，這篇文章将join方法的概念稍微整理在一起，給大家個參考。通過查資料了解裡面提到的各種概念，在實際中不斷驗證總結，完全可以對資料庫一步步深入了解下去的。

我隻對SQL Server 2000比較了解，但這并不阻礙我在Oracle、MySql進行SQL調優、産品架構，因為在資料庫理論原理上，各大資料庫基本出入不大，對資料庫的深入了解，也不會影響你架構設計思想變壞，相反給你帶來的是更深層次的思考。

​關于執行計劃的說明​

在SQL Server查詢分析器的Query菜單中選擇Show Execution Plan，運作SQL查詢語句，在結果視窗中有Grid、Execution Plan、Messages三個Tab。看圖形形式的執行計劃，順序是從右到左，這也是執行的順序。執行計劃中的每一個圖示表示一個操作，每一個操作都會有一個或多個輸入，也會有一個或多個輸出。輸入和輸出，有可能是一個實體資料表、索引資料結構，或者是執行過程中的一些中間結果集/資料結構。滑鼠移動到圖示上，會顯示這個操作的具體資訊，例如邏輯和實體操作名稱、記錄的數量和大小、I/O成本、CPU成本、操作的具體表達式（參數Argument）。滑鼠移動到連接配接箭頭上，會顯示箭頭起始端的操作輸出結果集的記錄數、記錄的大小，一般情況下可以将這個輸出結果集了解為箭頭結束端的輸入。

另外關于執行計劃的一些補充說明：1. 執行計劃中顯示的資訊，都是一個“評估”的結果，不是100%準确的資訊，例如記錄數量是取自統計資訊，I/O成本、CPU成本來自執行計劃生成過程中基于統計資訊等得出的評估結果。2. 執行計劃不一定準确，一方面受SQL Server維護的統計資訊準确性的影響，另一方面SQL語句編譯時刻與執行時刻的環境（記憶體使用狀況、CPU狀況等）可能會不一樣。

關于統計資訊、I/O成本和CPU成本的評估、SQL語句的編譯和執行過程，這裡不再深入。另外盡管執行計劃不一定準确，但它仍是SQL語句分析最重要的依據，因為你可以了解為，絕大部分情況下，SQL Server是以這種方式來執行的。

​JOIN方法說明​

資料庫中，象tableA inner join tableB、tableA left out join tableB這樣的SQL語句是如何執行join操作的？就是說SQL Server使用什麼算法實作兩個表資料的join操作？

SQL Server 2000有三種方式：nested loop、merge、hash。Oracle也是使用這三種方式，不過Oracle選擇使用nested loop的條件跟SQL Server有點差别，記憶體管理機制跟SQL Server不一樣，是以檢視執行計劃，Oracle中nested loop運用非常多，而merge和hash方式相對較少，SQL Server中，merge跟hash方式則是非常普遍。

以SQL Server 2000為例對這三種方式進行說明，穿插在裡面講解執行計劃的一些初級使用。

​1. nested loop join​

​1.1 示例SQL​

select ... from tableA inner join tableB on tableA.col1=tableB.col1 where tableA.col2=? and tableB.col2=?tableA中沒有建立任何索引，tableB中在col1上有建立一個主鍵（聚集索引）。

​1.2 算法僞代碼描述​

foreach rowA in tableA where tableA.col2=? { search rowsB from tableB where tableB.col1=rowA.col1 and tableB.col2=? ; if(rowsB.Count<=0) discard rowA ; else output rowA and rowsB ; }

join操作有兩個輸入，上面例子中tableA是outer input，用于外層循環；tableB是inner input，用于循環内部。下面針對執行計劃描述一下SQL Server完成這個操作的具體步驟。

​1.3 檢視執行計劃方法​

移到文章最前面。

​1.4 執行步驟​

下面是示例SQL的執行計劃圖。nested loop操作的右邊，位于上面的是outer input，位于下面的是inner input。你不能夠根據join中哪個表出現在前面來确定outer input和inner input關系，而必須從執行計劃中來确定，因為SQL Server會自動選擇哪個作為inner input。

圖1

a) 對tableA執行Table Scan操作。這個操作的輸入是tableA表中的資料，這些資料位于磁盤上，操作過程中被加載到記憶體；輸出是符合條件的記錄集，将作為b)的outer input。在這個操作中，tableA.col1=?的條件會被使用。

b) 執行上面僞代碼描述的nested loop操作。對a)中的每個輸出記錄，執行步驟c)。

c) 對tableB執行Clustered Index Seek操作。這個操作是在nested loop循環裡面執行的，輸入是tableB表的聚集索引資料。它使用tableB.col1=rowA.col1和tableB.col2=?這兩個條件，從tableB的聚集索引中選擇符合條件的結果。

d) 構造傳回結果集。從nested loop的輸出中，整理出select中指定的字段，構造最終輸出結果集。

​1.5 進階說明​

上面例子對inner input使用的是聚集索引，下面看一下非聚集索引的情況，加強對執行計劃的了解、分析能力。

把tableB col1上的主鍵修改為非聚集方式，示例的SQL語句執行計劃如下：

圖2

前面三個執行步驟a)、b)、c)跟1.4中一樣，有一點需要注意的是，步驟c)是執行Index Seek操作，它跟Clustered Index Seek有差別。聚集索引的根節點是每一條實際資料記錄，而非聚集索引的根節點是對聚集索引根結點鍵值的引用（如果表存在聚集索引），或者是對實際資料記錄rowid的引用（指沒有聚集索引的表，這種表稱為heap表）。Clustered Index Seek執行之後，實際的實體資料記錄已經被加載到記憶體中，而Index Seek操作之後，并沒有加載實際的實體資料記錄，而隻是非聚集索引的根結點資料，其中隻包含了索引字段資料以及引用的聚集索引鍵值或者rowid。SQL Server在這個步驟中使用非聚集索引根結點資料中的索引字段值，與outer input中的記錄（rowA）關聯字段進行比對，判斷是否是符合條件的結果，如果是，則将非聚集索引根結點資料結構儲存到nested loop操作的輸出資料結構中，并且會建立一個書簽（Bookmark），訓示在必要的時候需要根據這個書簽去擷取引用的資料。

d) 執行Bookmark Lookup操作。nested loop操作的輸出是一個記憶體資料結構，在從這個記憶體資料結構中整理出整個查詢語句的輸出結果集之前，需要處理前面的書簽引用問題，Bookmark Lookup操作就是根據書簽中引用的聚集索引鍵值或者rowid擷取具體記錄資料。

e) Filter過濾操作。回顧前面幾個操作，在執行nested loop時隻是使用非聚集索引的索引字段（tableB.col1）跟outer input的關聯字段進行比對，到目前為止還沒有使用tableB.col2=?這個條件，這個操作就是使用tableB.col2=?對Bookmark Lookup的輸出進行過濾。

看的仔細的人到這裡後可能會有幾個疑問，1. tableA.col2=?怎麼沒有一個Filter操作？2. 在1.4中為什麼沒有出現Filter操作？解釋如下：1. 在tableA上面執行的是Table Scan操作，是直接對每條實際資料進行掃描，在這個掃描過程中可以使用tableA.col2=?這個條件進行過濾，避免一個額外的Filter操作。滑鼠移動到Table Scan操作上，從提示資訊的參數（Argument）裡面可以看到tableA.col2=?的條件已經被運用上了。2. 前面說過，聚集索引的根節點是實際資料記錄，執行Clustered Index Seek的時候，最終也是掃描到了實際資料記錄，在這個過程中運用tableB.col2=?這個條件，同樣避免一個額外的Filter操作。這就是1.4中沒有Filter操作的原因。

f) 構造傳回結果集。跟1.4步驟d)一樣。

​1.6 nested loop使用條件​

任何一個join操作，如果滿足nested loop使用條件，查詢優化過程中SQL Server就會對nested loop的成本（I/O成本、CPU成本等）進行評估，基于評估結果确定是否使用這種join方式。

使用nested loop方式的條件是：a) outer input的記錄數不大，最好是在1000-2000以下，一般超過3000就很難說了，基本不大會選擇nested loop。b) 作為inner input的表中，有可用于這個查詢的索引。

這是因為outer input記錄數不大，意味着外層循環次數比較小；inner input上有可用的索引，意味着在循環裡面搜尋inner input表中是否存在比對的記錄時，效率會很高，哪怕inner input表實際記錄數有幾百萬。基于這兩個條件，nested loop的執行效率非常高，在三種join方式裡面，是記憶體和CPU消耗最少的一種（不合理的強制指定nested loop方式除外）。

關于使用條件另外的說明：outer input的記錄數，并不是指outer input表中實際記錄數，例如示例SQL中，如果tableA在col2上有維護統計資訊（存在col2的索引或者是單獨維護的統計資訊），并且tableA.col2=?的條件值符合SARG（可搜尋參數）形式，那麼查詢編譯時刻SQL Server就能夠利用統計資訊和條件值評估出符合條件的記錄數，查詢執行時刻符合條件tableA.col2=?的記錄才被用于外層循環。inner input表中有可用的索引，是指inner input表中用于和outer input表關聯的字段（一個或多個字段）能夠命中某個索引（這些字段的部分或者全部出現在某個索引字段的前面）。

符合上面的條件，也不是說SQL Server 100%就會選擇nested loop。因為SQL Server的查詢優化器是基于成本評估的，如果其它方案評估出的成本勝過這個，SQL Server會選擇其它的join方式。舉個例子，如果inner input上符合條件的索引是非聚集索引，這樣SQL Server可能需要一個額外的Bookmark Lookup操作擷取實際記錄資料，如果inner input表資料量非常大，索引碎片程度很高等情況，可能導緻Bookmark Lookup成本非常高，SQL Server會嘗試其它join方案的評估選擇。

​1.7 強制指定nested loop方式​

使用loop關鍵字實作，例如tableA inner loop join tableB，将強制SQL Server使用nested loop方式執行這個join操作。或者使用option選項，例如tableA inner join tableB option(loop join)　nested loop算法有它适用的範圍，在這個範圍之内效率是最高的，超出這個範圍效率反而很差，除非你有十分的把握，不要随意強制指定join方式。

接下來就不再象上面這樣詳細的講述了。

​2. merge join​

merge join第一個步驟是確定兩個關聯表都是按照關聯的字段進行排序。如果關聯字段有可用的索引，并且排序一緻，則可以直接進行merge join操作；否則，SQL Server需要先對關聯的表按照關聯字段進行一次排序（就是說在merge join前的兩個輸入上，可能都需要執行一個Sort操作，再進行merge join）。

兩個表都按照關聯字段排序好之後，merge join操作從每個表取一條記錄開始比對，如果符合關聯條件，則放入結果集中；否則，将關聯字段值較小的記錄抛棄，從這條記錄對應的表中取下一條記錄繼續進行比對，直到整個循環結束。 

在多對多的關聯表上執行merge join時，通常需要使用臨時表進行操作。例如A join B使用merge join時，如果對于關聯字段的某一組值，在A和B中都存在多條記錄A1、A2...An、B1、B2...Bn，則為A中每一條記錄A1、A2...An，都必須在B中對所有相等的記錄B1、B2...Bn進行一次比對。這樣，指針需要多次從B1移動到Bn，每一次都需要讀取相應的B1...Bn記錄。将B1...Bn的記錄預先讀出來放入記憶體臨時表中，比從原資料頁或磁盤讀取要快。

merge join操作本身是非常快的，但是merge join前進行的排序可能會相當耗時（SQL Server最消耗記憶體和CPU的操作，一個是大資料排序，一個是大資料的hash運算，這都是指查詢計劃裡面的Sort以及Hash相關的操作，例如hash join、使用hash算法實作的Distinct操作等，而不是指你的SQL中order by關鍵字），尤其是對資料量非常大的記錄集，是以導緻使用merge join的查詢成本變得非常高。對于資料量非常大的表，如果merge join的關聯字段可以使用聚集索引，merge join是最快的Join方法之一。是以優化方案是在表結構設計層面良好的設計關聯關系和表的索引結構，SQL語句充分利用索引，盡可能減少merge join前的排序操作，減少Bookmark Lookup操作。

一般情況下，如果無法滿足nested loop條件，會考慮對merge join方法的評估。merge join的選擇，主要是考慮兩個輸入的資料量，以及分别對應于關聯字段是否能夠命中索引。例如tableA join tableB，關聯字段在兩個表中都能命中索引，資料量超過了nested loop的選擇範圍，則會考慮使用merge join方法。當然，如果tableA和tableB的資料量過大導緻評估出來的成本過高，則會放棄merge join而評估hash join了。

使用inner merge join或者option(merge join)強制使用merge join方法。

​3. hash join​

hash join有兩個輸入：build input（也叫做outer input）和probe input（也叫做inner input），不僅用于inner/left/right join等，象union/group by等也會使用hash join進行操作，在group by中build input和probe input都是同一個記錄集。

同nested loop，在執行計劃中build input位于上方，probe input位于下方。

hash join操作分兩個階段完成：build（構造）階段和probe（探測）階段。

​Build階段​

這個階段主要構造hash table。在inner/left/right join等操作中，表的關聯字段作為hash key；在group by操作中，group by的字段作為hash key；在union或其它一些去除重複記錄的操作中，hash key包括所有的select字段。

Build操作從build input輸入中取出每一行記錄，将該行記錄關聯字段的值使用hash函數生成hash值，這個hash值對應到hash table中的hash buckets（哈希表目）。如果一個hash值對應到多個hash buckts，則這些hash buckets使用連結清單資料結構連接配接起來。當整個build input的table處理完畢後，build input中的所有記錄都被hash table中的hash buckets引用/關聯了。

​Probe階段​

在這個階段，SQL Server從probe input輸入中取出每一行記錄，同樣将該行記錄關聯字段的值，使用build階段中相同的hash函數生成hash值，根據這個hash值，從build階段構造的hash table中搜尋對應的hash bucket。hash算法中為了解決沖突，hash bucket可能會連結到其它的hash bucket，probe動作會搜尋整個沖突鍊上的hash bucket，以查找比對的記錄。 

關于hash算法的細節，可以檢視資料結構的一些資料。hash算法主要是用于大資料量的搜尋，為了避免每次都象merge join一樣在全部的資料中進行搜尋比對，通過合适的 hash函數，先給要搜尋的資料根據hash key建立hash值作為索引，在搜尋時，先通過hash值定位到一個較小的搜尋範圍，然後在這個範圍中搜尋比對符合條件的結果，以提高效率。 

SQL Server将資料量較小的表作為build input，盡量使根據build input構造的hash table能夠完全放在記憶體中，這樣probe階段的比對操作就完全是在記憶體中進行，這樣的hash join叫做In-Memory Hash Join。

如果build input記錄數非常大，建構的hash table無法在記憶體中容納時，SQL Server分别将build input和probe input切分成多個分區部分（partition），每個partition都包括一個獨立的、成對比對的build input和probe input，這樣就将一個大的hash join切分成多個獨立、互相不影響的hash join，每一個分區的hash join都能夠在記憶體中完成。SQL Server将切分後的partition檔案儲存在磁盤上，每次裝載一個分區的build input和probe input到記憶體中，進行一次hash join。這種hash join叫做Grace Hash Join，使用的Grace Hash Join算法。

伴随着大資料的hash join運算，還會有standard external merge sorts、multiple merge levels、multiple partitioning steps、multiple partitioning levels，SQL Server還可能會使用Recursive Hash Join等算法或其它的優化手段。

hash join一般都用于大資料量的操作，例如join中某個表的資料達到一定程度或者無法一次加載到記憶體，另外如果你的關聯字段在兩個join表中都不能夠命中索引，也是使用hash join來處理。是以一般情況下，hahs join處理代價非常高，是資料庫伺服器記憶體和CPU的頭号殺手之一，尤其是涉及到分區（資料量太大導緻記憶體不夠的情況，或者并發通路很高導緻目前處理線程無法獲得足夠的記憶體，那麼資料量不是特大的情況下也可能需要進行分區），為了盡快的完成所有的分區步驟，将使用大量異步的I/O操作，是以期間單一一個線程就可能導緻多個磁盤驅動器出于忙碌狀态，這很有可能阻塞其它線程的執行。

使用inner hash join或者option (hash join)強制使用hash join方法。

​建議​

三種join方法，都是擁有兩個輸入。優化的基本原則：1. 避免大資料的hash join，盡量将其轉化為高效的merge join、nested loop join。可能使用的手段有表結構設計、索引調整設計、SQL優化，以及業務設計優化。例如備援字段的運用，将統計分析結果用service定期跑到靜态表中，适當的備援表，使用AOP或類似機制同步更新等。2. 盡量減少join兩個輸入端的資料量。這一點比較常犯的毛病是，條件不符合SARG（光這一點就有很多高超的技巧可以發揮），在子查詢内部條件給的不充分（SQL過于複雜情況下SQL Server查詢優化器經常犯傻，寫在子查詢外部的條件不會被用在子查詢内部，影響子查詢内部的效率或者是跟子查詢再join時候的效率）。另外也是設計、業務端盡量限制這兩個輸入的資料量了。

關于業務設計方面的優化，參考以前寫的一篇post：系統分析設計 一個JOIN問題解決方案的感想 重視業務分析設計。

​補充：關于SQL Server 2005​

大緻看了下SQL Server 2005，執行計劃的顯示确實有一些不一樣，但主要部分或者說原理上是差不多的，不會有多少偏差。上面的示例SQL，在tableB上面使用非聚集索引時，SQL Server 2005的執行計劃圖如下：

圖3

一個主要的不同點是SQL Server 2000下面Bookmark Lookup操作，在2005下面顯示成一個RID Lookup操作 + 一個Nested Loops操作實作，其實這也是很好了解的，可以說這樣顯示執行計劃更合理一點，讓你一看到這個操作，就知道它是通過一個循環機制到tableB中擷取實際資料。