06 hash join (Oracle裡的哈希連接配接原理)

hash join (Oracle裡的哈希連接配接原理) 2015年09月25日 17:00:28 閱讀數：2188

哈希連接配接（HASH JOIN）是一種兩個表在做表連接配接時主要依靠哈希運算來得到連接配接結果集的表連接配接方法。

在Oracle 7.3之前，Oracle資料庫中的常用表連接配接方法就隻有排序合并連接配接和嵌套循環連接配接這兩種，但這兩種表連接配接方法都有其明顯缺陷。對于排序合并連接配接，如果兩個表在施加了目标SQL中指定的謂詞條件（如果有的話）後得到的結果集很大且需要排序的話，則這種情況下的排序合并連接配接的執行效率一定是很差的；而對于嵌套循環連接配接，如果驅動表所對應的驅動結果集的記錄數很大，即便在被驅動表的連接配接列上存在索引，此時使用嵌套循環連接配接的執行效率也同樣會很差。

為了解決排序合并連接配接和嵌套循環連接配接在上述情形下執行效率不高的問題，同時也為了給優化器提供一種新的選擇，Oracle在Oracle 7.3中引入了哈希連接配接。從理論上來說，哈希連接配接的執行效率會比排序合并連接配接和嵌套循環連接配接的執行效率要高，當然，實際情況并不總是這樣。

在Oracle 10g及其以後的Oracle資料庫版本中，優化器（實際上是CBO，因為哈希連接配接僅适用于CBO）在解析目标SQL時是否考慮哈希連接配接是受限于隐含參數_HASH_JOIN_ENABLED，而在Oracle 10g以前的Oracle資料庫版本中，CBO在解析目标SQL時是否考慮哈希連接配接是受限于參數HASH_JOIN_ENABLED。

_HASH_JOIN_ENABLED的預設值是TRUE，表示允許CBO在解析目标SQL時考慮哈希連接配接。當然，即使你将該參數的值改成了FALSE，我們使用USE_HASH Hint依然可以讓CBO在解析目标SQL時考慮哈希連接配接，這說明USE_HASH Hint的優先級高于參數_HASH_JOIN_ENABLED。

如果兩個表（這裡将它們分别命名為表T1和表T2）在做表連接配接時使用的是哈希連接配接，則Oracle在做哈希連接配接時會依次順序執行如下步驟：

1、  首先Oracle會根據參數HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值來決定Hash Partition的數量（Hash Partition是一個邏輯上的概念，所有Hash Partition的集合就被稱之為Hash Table，即一個Hash Table是由多個Hash Partition所組成，而一個Hash Partition又是由多個Hash Bucket所組成）；

2、  表T1和T2在施加了目标SQL中指定的謂詞條件（如果有的話）後得到的結果集中資料量較小的那個結果集會被Oracle選為哈希連接配接的驅動結果集，這裡我們假設T1所對應的結果集的資料量相對較小，我們記為S；T2所對應的結果集的資料量相對較大，我們記為B；顯然這裡S是驅動結果集，B是被驅動結果集；

3、  接着Oracle會周遊S，讀取S中的每一條記錄，并對S中的每一條記錄按照該記錄在表T1中的連接配接列做哈希運算，這個哈希運算會使用兩個内置哈希函數，這兩個哈希函數會同時對該連接配接列計算哈希值，我們把這兩個内置哈希函數分别記為hash_func_1和hash_func_2，它們所計算出來的哈希值分别記為hash_value_1和hash_value_2；

4、  然後Oracle會按照hash_value_1的值把相應的S中的對應記錄存儲在不同Hash Partition的不同Hash Bucket裡，同時和該記錄存儲在一起的還有該記錄用hash_func_2計算出來的hash_value_2的值。注意，存儲在Hash Bucket裡的記錄并不是目标表的完整行記錄，而是隻需要存儲位于目标SQL中的跟目标表相關的查詢列和連接配接列就足夠了；我們把S所對應的每一個Hash Partition記為Si；

5、  在建構Si的同時，Oracle會建構一個位圖（BITMAP），這個位圖用來标記Si所包含的每一個Hash Bucket是否有記錄（即記錄數是否大于0）；

6、  如果S的資料量很大，那麼在建構S所對應的Hash Table時，就可能會出現PGA的工作區（WORK AREA）被填滿的情況，這時候Oracle會把工作區中現有的Hash Partition中包含記錄數最多的Hash Partition寫到磁盤上（TEMP表空間）；接着Oracle會繼續建構S所對應的Hash Table，在繼續建構的過程中，如果工作區又滿了，則Oracle會繼續重複上述挑選包含記錄數最多的Hash Partition并寫回到磁盤上的動作；如果要建構的記錄所對應的Hash Partition已經事先被Oracle寫回到了磁盤上，則此時Oracle就會去磁盤上更新該Hash Partition，即會把該條記錄和hash_value_2直接加到這個已經位于磁盤上的Hash Partition的相應Hash Bucket中；注意，極端情況下可能會出現隻有某個Hash Partition的部分記錄還在記憶體中，該Hash Partition的剩餘部分和餘下的所有Hash Partition都已經被寫回到磁盤上；

7、  上述建構S所對應的Hash Table的過程會一直持續下去，直到周遊完S中的所有記錄為止；

8、  接着，Oracle會對所有的Si按照它們所包含的記錄數來排序，然後Oracle會把這些已經排好序的Hash Partition按順序依次、并且盡可能的全部放到記憶體中（PGA的工作區），當然，如果實在放不下的話，放不下的那部分Hash Partition還是會位于磁盤上。我認為這個按照Si的記錄數來排序的動作不是必須要做的，因為這個排序動作的根本目的就是為了盡可能多的把那些記錄數較小的Hash Partition保留在記憶體中，而将那些已經被寫回到磁盤上、記錄數較大且現有記憶體已經放不下的Hash Partition保留在磁盤上，顯然，如果所有的Si本來就都在記憶體中，也沒發生過将Si寫回到磁盤的操作，那這裡根本就不需要排序了。

9、     至此Oracle已經處理完S，現在可以來開始處理B了；

10、 Oracle會周遊B，讀取B中的每一條記錄，并對B中的每一條記錄按照該記錄在表T2中的連接配接列做哈希運算，這個哈希運算和步驟3中的哈希運算是一模一樣的，即這個哈希運算還是會用步驟3中的hash_func_1和hash_func_2，并且也會計算出兩個哈希值hash_value_1和hash_value_2；接着Oracle會按照該記錄所對應的哈希值hash_value_1去Si裡找比對的Hash Bucket；如果能找到比對的Hash Bucket，則Oracle還會周遊該Hash Bucket中的每一條記錄，并會校驗存儲于該Hash Bucket中的每一條記錄的連接配接列，看是否是真的比對（即這裡要校驗S和B中的比對記錄所對應的連接配接列是否真的相等，因為對于Hash運算而言，不同的值經過哈希運算後的結果可能是一樣的），如果是真的比對，則上述hash_value_1所對應B中的記錄的位于目标SQL中的查詢列和該Hash Bucket中的比對記錄便會組合起來，一起作為滿足目标SQL連接配接條件的記錄傳回；如果找不到比對的Hash Bucket，則Oracle就會去通路步驟5中建構的位圖，如果位圖顯示該Hash Bucket在Si中對應的記錄數大于0，則說明該Hash Bucket雖然不在記憶體中，但它已經被寫回到了磁盤上，則此時Oracle就會按照上述hash_value_1的值把相應B中的對應記錄也以Hash Partition的方式寫回到磁盤上，同時和該記錄存儲在一起的還有該記錄用hash_func_2計算出來的hash_value_2的值；如果位圖顯示該Hash Bucket在Si中對應的記錄數等于0，則Oracle就不用把上述hash_value_1所對應B中的記錄寫回到磁盤上了，因為這條記錄必然不滿足目标SQL的連接配接條件；這個根據位圖來決定是否将上述hash_value_1所對應B中的記錄寫回到磁盤的動作就是所謂的“位圖過濾”；我們把B所對應的每一個Hash Partition記為Bj；

11、 上述去Si中查找比對Hash Bucket和建構Bj的過程會一直持續下去，直到周遊完B中的所有記錄為止；

12、 至此Oracle已經處理完所有位于記憶體中的Si和對應的Bj，現在隻剩下位于磁盤上的Si和Bj還未處理；

13、 因為在建構Si和Bj時用的是同樣的哈希函數hash_func_1和hash_func_2，是以Oracle在處理位于磁盤上的Si和Bj的時候可以放心的配對處理，即隻有對應Hash Partition Number值相同的Si和Bj才可能會産生滿足連接配接條件的記錄；這裡我們用Sn和Bn來表示位于磁盤上且對應Hash Partition Number值相同的Si和Bj；

14、 對于每一對兒Sn和Bn，它們之中記錄數較少的會被當作驅動結果集，然後Oracle會用這個驅動結果集的Hash Bucket裡記錄的hash_value_2來建構新的Hash Table，另外一個記錄數較大的會被當作被驅動結果集，然後Oracle會用這個被驅動結果集的Hash Bucket裡記錄的hash_value_2去上述建構的新Hash Table中找比對記錄；注意，對每一對兒Sn和Bn而言，Oracle始終會選擇它們中記錄數較少的來作為驅動結果集，是以每一對兒Sn和Bn的驅動結果集都可能會發生變化，這就是所謂的“動态角色互換”；

15、 步驟14中如果存在比對記錄，則該比對記錄也會作為滿足目标SQL連接配接條件的記錄傳回；

16、 上述處理Sn和Bn的過程會一直持續下去，直到周遊完所有的Sn和Bn為止。

對于哈希連接配接的優缺點及适用場景，我們有如下總結：

Ÿ     哈希連接配接不一定會排序，或者說大多數情況下都不需要排序；

Ÿ     哈希連接配接的驅動表所對應的連接配接列的可選擇性應盡可能的好，因為這個可選擇性會影響對應Hash Bucket中的記錄數，而Hash Bucket中的記錄數又會直接影響從該Hash Bucket中查找比對記錄的效率；如果一個Hash Bucket裡所包含的記錄數過多，則可能會嚴重降低所對應哈希連接配接的執行效率，此時典型的表現就是該哈希連接配接執行了很長時間都沒有結束，資料庫所在database server上的CPU占用率很高，但目标SQL所消耗的邏輯讀卻很低，因為此時大部分時間都耗費在了周遊上述Hash Bucket裡的所有記錄上，而周遊Hash Bucket裡記錄這個動作是發生在PGA的工作區裡，是以不耗費邏輯讀；

Ÿ     哈希連接配接隻适用于CBO、它也隻能用于等值連接配接條件（即使是哈希反連接配接，Oracle實際上也是将其轉換成了等價的等值連接配接）；

Ÿ     哈希連接配接很适合于一個小表和大表之間的表連接配接，特别是在小表的連接配接列的可選擇性非常好的情況下，這時候哈希連接配接的執行時間就可以近似看作是和全表掃描那個大表所耗費的時間相當；

Ÿ     當兩個表做哈希連接配接時，如果這兩個表在施加了目标SQL中指定的謂詞條件（如果有的話）後得到的結果集中資料量較小的那個結果集所對應的Hash Table能夠完全被容納在記憶體中時（PGA的工作區），則此時的哈希連接配接的執行效率會非常高。

轉載于:https://www.cnblogs.com/jason01/p/9182757.html