一、概述這篇文章是數據庫性能調優技術系列的第四篇。上一篇文章講解了深入理解嵌套循環連接執行計劃。
上一篇文章中提到兩張表的連接有三種執行方式：1）嵌套循環連接；2）散列連接；3）歸並連接。散列連接是很重要的連接方式，包含比較多的內容，這篇文章中講解為什麼需要散列連接？如何理解散列連接？
和前三篇文章一樣，本文講解的是些比較抽象的內容，不拘泥於具體的數據。所以本文中使用的代價評估模型也是抽象的，假設了數據庫緩沖區大小只有一個頁，新頁的讀取必然導致舊頁的釋放。讀完本文之後應該能夠讀懂達夢數據庫、Oracle數據庫、sqlserver數據庫的執行計劃。
二、深入理解嵌套循環執行計劃為什麼要引入散列連接呢？假設兩張表t1(c1 int,c2 int),t2(d1 int,d2 int)，查詢語句為select c1,d1 from t1 inner join t2 on c1=d1。如果數據庫沒有實現散列連接、合並連接的話，只能選擇使用嵌套循環。
從上篇文章中我們可以得到，對於t1的每一條記錄，都需要遍歷t2的每一條記錄。因此，當t1的記錄數數為m,t2的記錄數為n，那麼該查詢語句訪問的記錄次數為m*n。當m=10000、n=10000時，那麼m*n=100000000（1億）。這是比較誇張的浪費時間。如果m是100萬，n是100萬，那麼m*n就是1萬億次，讀一萬億次記錄，這是不能忍受的。
這裡需要提到的一點是：我們不以讀取記錄的多少作為評價標准，在實際代價評估中，采用數據頁（也可稱為數據塊，I/O的基本單位）。
但是兩者之間又是有聯系的，假設每個頁存放100個數據，那麼t1的數據頁為100頁(10000/100)，t2的數據頁為100頁，那麼對於t1中的每一條記錄，需要遍歷t2的100頁，加上該記錄在t1中也屬於一個數據頁。因此，對於t1中的每一個記錄，需要訪問101個數據頁。那麼該查詢的I/O量為：10000*（100+1）=1010000頁。如果考慮到數據頁的緩沖，情況會更加復雜。代價評估是個很復雜的課題，可能需要單獨寫個系列來闡述數據庫查詢優化系統的代價評估模型。這裡我們不考慮數據頁緩沖，也就相當於假設數據庫緩沖區的大小僅僅為1個頁。
好了，繼續前面的話題。
如果t1(c1)上建立有唯一索引iut1c1（非唯一索引也是一樣），那麼可以將t2作為外表，對於t2的每一條記錄，使用d1的值去命中索引iut1c1對應的B樹。假設該B樹的高度為3層，那麼對於t2的每一條記錄，需要訪問t1表索引iut1c1中三個頁（B樹的高度），加上本身在t2中屬於一個頁。所以，在這種情況下，查詢代價為：10000*(3+1)=40000頁。
我們來對比一下，沒有索引與有索引，兩者之間的代價對比約等於25:1（比值1010000：20%">40000）。也可以這麼認為，假設沒有索引的時候執行需要25s，那麼有索引的情況下只需要1s。
這裡我們把話題再延展下，如果m,n都為1000000，占用的塊都為10000頁（1000000/100）。沒有索引的情況的I/O量為：1000000*(10000+1)=10001000000頁。在t1(c1)有索引，該索引的高度對應的高度為4的情況下，假設I/O量為：100000*(4+1)=5000000。對比一下，沒有索引與有索引，兩者之間的代價比約等於2000:1。相等於，假設沒有索引的情況下執行需要2000s，那麼有索引的情況下只需要1s。
從上面的對比當中，我們可以發現索引的重要性，在實際應用當中，80%</span>的查詢性能問題來源於沒有創建索引或者沒有創建合適的索引。
索引，真是個好東西。如果用戶沒有創建索引，數據庫內核也拿用戶沒辦法，只能自己想辦法。這裡提出兩種解決方法：1）建立臨時索引；2）使用散列連接。
1）數據庫內核使用建立臨時索引的方法大家可能聽到過一個這樣的概念：“在sqlserver系統中，如果用戶沒有創建索引，執行查詢時，sqlserver會自動創建該索引。”
這裡我們先撇開sqlserver到底是使用臨時索引還是散列連接，我們只是對這句話加以理解。
對於上文提到的查詢語句，執行過程描述如下：
1) create index itemp on t1(c1);
2) 執行查詢語句select c1,d1 from t1 inner join t2 on c1=d1；
3) drop index itemp;
我們來評估下代價。如上文鎖描述，假設m,n都為IGHT: 120%">1000000，占用的塊都為10000頁。
首先是計算構造索引的代價：對t1的數據進行全掃描，對於每一條記錄要插入到B樹中，假設插入操作平均需要使用3個頁。（因為起始時，B樹只有一層，插入只需要訪問1頁，B樹兩層使需要訪問2頁，等等）。該步驟的代價為：1000000*（3+1）=4000000頁。
然後計算查詢的代價，前面已經計算過：100000*(4+1)=5000000頁。
所以，整個代價為4000000+5000000=9000000頁。
進行對比：10000:9:5(比值10001000000:9000000:5000000)。不使用索引的代價為10000，使用臨時索引的代價為9，使用用戶創建的索引代價為5。
所以，我們發現使用臨時索引還是個不錯的選擇。
2）數據庫內核使用散列連接的方法 首先我們講下散列連接的原理：
1）對t1表（稱為構建表）進行全掃描，對於每一個記錄，對c1值進行使用內部散列函數，然後將該數據存放到相應的散列桶。
2）開始讀t2表（稱為探查散列表），對於t2的每一個記錄，對d1值使用同樣的散列函數，得到相應的散列值，查看該桶中是否有行。
如果相應的桶中沒有行，則會丟失t2中這一行記錄。如果散列桶中如果有一些行呢，則會精通的檢查散列連接判斷是否存在合適的匹配。因為不同的值可以產生同樣的散列值。找到精確匹配的值，組合成記錄放入結果集中。
我們來評估下代價。
1）首先我們先看構建散列的代價，對於t1的每一個記錄，一般只需要訪問一個散列桶。所以該步驟的代價為：1000000*(1+1)=2000000頁。
2）對於t2的每一個記錄，一般只需要訪問一個散列桶。所以該步驟的代價為：1000000*(1+1)=2000000頁。
所以，整個代價為2000000+2000000=4000000頁。
進行對比：10000:4:5(比值10001000000:4000000:5000000)，不使用索引的代價為10000，使用散列連接的代價為4，使用用戶創建的索引代價為5。
是不是覺得不可思議？散列連接的代價竟然比使用索引的連接還小。我們通過一個例子來驗證一下：
SQL> create table t1(c1 int,c2 int);
Table created.
SQL> begin
2 for colval in 1..10000
HEIGHT: 120%"> 3 loop
4 insert into t1 values(colval,colval);
5 end loop;
6 end;
7 /
PL/SQL procedure successfully completed.
SQL> create table t2(d1 int,d2 int);
Table created.
SQL> begin
2 for colval in 1..10000
3 loop
4 insert into t2 values(colval,colval);
5 end loop;
6 end;
7 /
PL/SQL procedure successfully completed.
SQL> create index it1c1 on t1(c1);
Index created.
SQL>
查詢語句“select c1,d1 from t1 inner join t2 on c1=d1;”對應的執行計劃為：
Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=ALL_ROWS (Cost=13 Card=10000 Byte
s=260000)
1 0 HASH JOIN (Cost=13 Card=10000 Bytes=260000)
2 1 TABLE Access (FULL) OF 'T1' (TABLE) (Cost=6 Card=10000 B
ytes=130000)
3 1 TABLE Access (FULL) OF 'T2' (TABLE) (Cost=6 Card=10000 B
ytes=130000)
從執行計劃中，我們看出盡管t1(c1)建立了索引，數據庫還是采用了散列連接。我們也許會經常疑惑：“為什麼我創建了索引，數據庫沒使用該索引。”
各位可以驗證一下，當你覺得應該可以使用索引，而數據庫沒有使用索引的情況一般會是：數據庫使用散列連接代替了嵌套循環連接。千萬不要將該結論進行延伸，從而得出：“我們不需要建立索引，數據庫不使用索引”。數據庫會根據查詢代價進行合理的選擇。哪種代價小，就會使用哪種執行計劃進行執行。
我們再看該執行計劃，“TABLE ACCESS (FULL) OF 'T1' (TABLE)”就是構建散列表，散列表構建之後就會執行“TABLE Access (FULL) OF 'T2' (TABLE)”。比如對於t2的記錄(1,1)，
使用散列函數得出hashvalue1，找到hashvalue1對應的桶，裡面可能有幾個值，這要看使用什麼樣的散列函數。假設散列函數是mod 10001，那麼該桶裡只會有一個記錄(1,1)。如果散列函數是mod 9000。裡面就會有記錄(1,1)與(9001,9001)。這種情況下，我們要進行對比，對於記錄(1,1)（對應(c1,c2)）,因為滿足c1=d1，所以構造處記錄(1,1)（對應查詢項(c1,d1)）放入結果集，對於記錄(9001,9001)不滿足c1=d1，所以該記錄不符合。如果t1表中有重復記錄(1,1)，那麼這裡就會產生兩條記錄插入到結果集中，因為：對於每個精確匹配c1=d1
HEIGHT: 120%">的記錄都會組合成結果記錄放入到結果集中。
