《基于Oracle的sql優(yōu)化》里關(guān)于哈希連接的原理介紹如下：

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

在Oracle 7.3之前，Oracle數(shù)據(jù)庫中的常用表連接方法就只有排序合并連接和嵌套循環(huán)連接這兩種，但這兩種表連接方法都有其明顯缺陷。對于排序合并連接，如果兩個表在施加了目標(biāo)SQL中指定的謂詞條件（如果有的話）后得到的結(jié)果集很大且需要排序的話，則這種情況下的排序合并連接的執(zhí)行效率一定是很差的；而對于嵌套循環(huán)連接，如果驅(qū)動表所對應(yīng)的驅(qū)動結(jié)果集的記錄數(shù)很大，即便在被驅(qū)動表的連接列上存在索引，此時使用嵌套循環(huán)連接的執(zhí)行效率也同樣會很差。

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

在Oracle?10g及其以后的Oracle數(shù)據(jù)庫版本中，優(yōu)化器（實際上是CBO，因為哈希連接僅適用于CBO）在解析目標(biāo)SQL時是否考慮哈希連接是受限于隱含參數(shù)_HASH_JOIN_ENABLED，而在Oracle10g以前的Oracle數(shù)據(jù)庫版本中，CBO在解析目標(biāo)SQL時是否考慮哈希連接是受限于參數(shù)HASH_JOIN_ENABLED。

_HASH_JOIN_ENABLED的默認(rèn)值是TRUE，表示允許CBO在解析目標(biāo)SQL時考慮哈希連接。當(dāng)然，即使你將該參數(shù)的值改成了FALSE，我們使用USE_HASH Hint依然可以讓CBO在解析目標(biāo)SQL時考慮哈希連接，這說明USE_HASH Hint的優(yōu)先級高于參數(shù)_HASH_JOIN_ENABLED。

??? ?

如果兩個表（這里將它們分別命名為表T1和表T2）在做表連接時使用的是哈希連接，則Oracle在做哈希連接時會依次順序執(zhí)行如下步驟：

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

2、??表T1和T2在施加了目標(biāo)SQL中指定的謂詞條件（如果有的話）后得到的結(jié)果集中數(shù)據(jù)量較小的那個結(jié)果集會被Oracle選為哈希連接的驅(qū)動結(jié)果集，這里我們假設(shè)T1所對應(yīng)的結(jié)果集的數(shù)據(jù)量相對較小，我們記為S；T2所對應(yīng)的結(jié)果集的數(shù)據(jù)量相對較大，我們記為B；顯然這里S是驅(qū)動結(jié)果集，B是被驅(qū)動結(jié)果集；

3、??接著Oracle會遍歷S，讀取S中的每一條記錄，并對S中的每一條記錄按照該記錄在表T1中的連接列做哈希運算，這個哈希運算會使用兩個內(nèi)置哈希函數(shù)，這兩個哈希函數(shù)會同時對該連接列計算哈希值，我們把這兩個內(nèi)置哈希函數(shù)分別記為hash_func_1和hash_func_2，它們所計算出來的哈希值分別記為hash_value_1和hash_value_2；

4、??然后Oracle會按照hash_value_1的值把相應(yīng)的S中的對應(yīng)記錄存儲在不同Hash Partition的不同Hash Bucket里，同時和該記錄存儲在一起的還有該記錄用hash_func_2計算出來的hash_value_2的值。注意，存儲在Hash Bucket里的記錄并不是目標(biāo)表的完整行記錄，而是只需要存儲位于目標(biāo)SQL中的跟目標(biāo)表相關(guān)的查詢列和連接列就足夠了；我們把S所對應(yīng)的每一個Hash Partition記為Si；

5、??在構(gòu)建Si的同時，Oracle會構(gòu)建一個位圖（BITMAP），這個位圖用來標(biāo)記Si所包含的每一個Hash Bucket是否有記錄（即記錄數(shù)是否大于0）；

6、??如果S的數(shù)據(jù)量很大，那么在構(gòu)建S所對應(yīng)的Hash Table時，就可能會出現(xiàn)PGA的工作區(qū)（WORK AREA）被填滿的情況，這時候Oracle會把工作區(qū)中現(xiàn)有的Hash Partition中包含記錄數(shù)最多的Hash Partition寫到磁盤上（TEMP表空間）；接著Oracle會繼續(xù)構(gòu)建S所對應(yīng)的Hash Table，在繼續(xù)構(gòu)建的過程中，如果工作區(qū)又滿了，則Oracle會繼續(xù)重復(fù)上述挑選包含記錄數(shù)最多的Hash Partition并寫回到磁盤上的動作；如果要構(gòu)建的記錄所對應(yīng)的Hash Partition已經(jīng)事先被Oracle寫回到了磁盤上，則此時Oracle就會去磁盤上更新該Hash Partition，即會把該條記錄和hash_value_2直接加到這個已經(jīng)位于磁盤上的Hash Partition的相應(yīng)Hash Bucket中；注意，極端情況下可能會出現(xiàn)只有某個Hash Partition的部分記錄還在內(nèi)存中，該Hash Partition的剩余部分和余下的所有Hash Partition都已經(jīng)被寫回到磁盤上；

7、??上述構(gòu)建S所對應(yīng)的Hash Table的過程會一直持續(xù)下去，直到遍歷完S中的所有記錄為止；

8、??接著，Oracle會對所有的Si按照它們所包含的記錄數(shù)來排序，然后Oracle會把這些已經(jīng)排好序的Hash Partition按順序依次、并且盡可能的全部放到內(nèi)存中（PGA的工作區(qū)），當(dāng)然，如果實在放不下的話，放不下的那部分Hash Partition還是會位于磁盤上。我認(rèn)為這個按照Si的記錄數(shù)來排序的動作不是必須要做的，因為這個排序動作的根本目的就是為了盡可能多的把那些記錄數(shù)較小的Hash Partition保留在內(nèi)存中，而將那些已經(jīng)被寫回到磁盤上、記錄數(shù)較大且現(xiàn)有內(nèi)存已經(jīng)放不下的Hash Partition保留在磁盤上，顯然，如果所有的Si本來就都在內(nèi)存中，也沒發(fā)生過將Si寫回到磁盤的操作，那這里根本就不需要排序了。

9、?????至此Oracle已經(jīng)處理完S，現(xiàn)在可以來開始處理B了；

10、?Oracle會遍歷B，讀取B中的每一條記錄，并對B中的每一條記錄按照該記錄在表T2中的連接列做哈希運算，這個哈希運算和步驟3中的哈希運算是一模一樣的，即這個哈希運算還是會用步驟3中的hash_func_1和hash_func_2，并且也會計算出兩個哈希值hash_value_1和hash_value_2；接著Oracle會按照該記錄所對應(yīng)的哈希值hash_value_1去Si里找匹配的Hash Bucket；如果能找到匹配的Hash Bucket，則Oracle還會遍歷該Hash Bucket中的每一條記錄，并會校驗存儲于該Hash Bucket中的每一條記錄的連接列，看是否是真的匹配（即這里要校驗S和B中的匹配記錄所對應(yīng)的連接列是否真的相等，因為對于Hash運算而言，不同的值經(jīng)過哈希運算后的結(jié)果可能是一樣的），如果是真的匹配，則上述hash_value_1所對應(yīng)B中的記錄的位于目標(biāo)SQL中的查詢列和該Hash Bucket中的匹配記錄便會組合起來，一起作為滿足目標(biāo)SQL連接條件的記錄返回；如果找不到匹配的Hash Bucket，則Oracle就會去訪問步驟5中構(gòu)建的位圖，如果位圖顯示該Hash Bucket在Si中對應(yīng)的記錄數(shù)大于0，則說明該Hash Bucket雖然不在內(nèi)存中，但它已經(jīng)被寫回到了磁盤上，則此時Oracle就會按照上述hash_value_1的值把相應(yīng)B中的對應(yīng)記錄也以Hash Partition的方式寫回到磁盤上，同時和該記錄存儲在一起的還有該記錄用hash_func_2計算出來的hash_value_2的值；如果位圖顯示該Hash Bucket在Si中對應(yīng)的記錄數(shù)等于0，則Oracle就不用把上述hash_value_1所對應(yīng)B中的記錄寫回到磁盤上了，因為這條記錄必然不滿足目標(biāo)SQL的連接條件；這個根據(jù)位圖來決定是否將上述hash_value_1所對應(yīng)B中的記錄寫回到磁盤的動作就是所謂的"位圖過濾"；我們把B所對應(yīng)的每一個Hash Partition記為Bj；

11、?上述去Si中查找匹配Hash Bucket和構(gòu)建Bj的過程會一直持續(xù)下去，直到遍歷完B中的所有記錄為止；

12、?至此Oracle已經(jīng)處理完所有位于內(nèi)存中的Si和對應(yīng)的Bj，現(xiàn)在只剩下位于磁盤上的Si和Bj還未處理；

13、?因為在構(gòu)建Si和Bj時用的是同樣的哈希函數(shù)hash_func_1和hash_func_2，所以Oracle在處理位于磁盤上的Si和Bj的時候可以放心的配對處理，即只有對應(yīng)Hash Partition Number值相同的Si和Bj才可能會產(chǎn)生滿足連接條件的記錄；這里我們用Sn和Bn來表示位于磁盤上且對應(yīng)Hash Partition Number值相同的Si和Bj；

14、?對于每一對兒Sn和Bn，它們之中記錄數(shù)較少的會被當(dāng)作驅(qū)動結(jié)果集，然后Oracle會用這個驅(qū)動結(jié)果集的Hash Bucket里記錄的hash_value_2來構(gòu)建新的Hash Table，另外一個記錄數(shù)較大的會被當(dāng)作被驅(qū)動結(jié)果集，然后Oracle會用這個被驅(qū)動結(jié)果集的Hash Bucket里記錄的hash_value_2去上述構(gòu)建的新Hash Table中找匹配記錄；注意，對每一對兒Sn和Bn而言，Oracle始終會選擇它們中記錄數(shù)較少的來作為驅(qū)動結(jié)果集，所以每一對兒Sn和Bn的驅(qū)動結(jié)果集都可能會發(fā)生變化，這就是所謂的"動態(tài)角色互換"；

15、?步驟14中如果存在匹配記錄，則該匹配記錄也會作為滿足目標(biāo)SQL連接條件的記錄返回；

16、?上述處理Sn和Bn的過程會一直持續(xù)下去，直到遍歷完所有的Sn和Bn為止。

? ?

對于哈希連接的優(yōu)缺點及適用場景，我們有如下總結(jié)：

??????哈希連接不一定會排序，或者說大多數(shù)情況下都不需要排序；

??????哈希連接的驅(qū)動表所對應(yīng)的連接列的可選擇性應(yīng)盡可能的好，因為這個可選擇性會影響對應(yīng)Hash Bucket中的記錄數(shù)，而Hash Bucket中的記錄數(shù)又會直接影響從該Hash Bucket中查找匹配記錄的效率；如果一個Hash Bucket里所包含的記錄數(shù)過多，則可能會嚴(yán)重降低所對應(yīng)哈希連接的執(zhí)行效率，此時典型的表現(xiàn)就是該哈希連接執(zhí)行了很長時間都沒有結(jié)束，數(shù)據(jù)庫所在database server上的CPU占用率很高，但目標(biāo)SQL所消耗的邏輯讀卻很低，因為此時大部分時間都耗費在了遍歷上述Hash Bucket里的所有記錄上，而遍歷Hash Bucket里記錄這個動作是發(fā)生在PGA的工作區(qū)里，所以不耗費邏輯讀；

??????哈希連接只適用于CBO、它也只能用于等值連接條件（即使是哈希反連接，Oracle實際上也是將其轉(zhuǎn)換成了等價的等值連接）；

??????哈希連接很適合于一個小表和大表之間的表連接，特別是在小表的連接列的可選擇性非常好的情況下，這時候哈希連接的執(zhí)行時間就可以近似看作是和全表掃描那個大表所耗費的時間相當(dāng)；

??????當(dāng)兩個表做哈希連接時，如果這兩個表在施加了目標(biāo)SQL中指定的謂詞條件（如果有的話）后得到的結(jié)果集中數(shù)據(jù)量較小的那個結(jié)果集所對應(yīng)的Hash Table能夠完全被容納在內(nèi)存中時（PGA的工作區(qū)），則此時的哈希連接的執(zhí)行效率會非常高。

?

對于以上的說明有兩點不明：

對于第四步，計算的hash value存儲在不同Hash Partition的不同Hash Bucket里，如果計算的值和以前重復(fù)，是不是會覆蓋掉以前Hash Bucket里的記錄呢 ？如果是這樣，是不是也解釋了hash連接非常適合小表連接列可選擇性好的情況呢？如果不是，怎么理解可選擇性好這句話呢？

位圖向量里面記錄的到底是什么呢？如果僅僅"用來標(biāo)記Si所包含的每一個Hash Bucket是否有記錄（即記錄數(shù)是否大于0）"，怎么"顯示該Hash Bucket在Si中對應(yīng)的記錄數(shù)等于0"呢？

Hash計算的兩個函數(shù)作用是什么呢？

第一個疑問已在作者博客里詢問，第三個問題作者在他博客下面回答了讀者的疑問，"之所以用兩個hash函數(shù)是為了使各個hash bucket里的值分布的更加均勻"，另一個函數(shù)就是計算hash值了。

對于第二個問題，在另外一個作者的一篇博客中找到，"在將S表讀入內(nèi)存分區(qū)時，oracle即記錄連接鍵的唯一值，構(gòu)建成所謂的位圖向量"，可見位圖向量記錄的是小表S的唯一鍵值：

引自：http://blog.163.com/chunlei_cl/blog/static/81843020146253596868/

原文：

深入理解Oracle表：三大表連接方式詳解之Hash Join的定義，原理，算法，成本，模式和位圖

Hash Join只能用于相等連接，且只能在CBO優(yōu)化器模式下。相對于nested loop join，hash join更適合處理大型結(jié)果集
?Hash Join的執(zhí)行計劃第1個是hash表(build table)，第2個探查表(probe table)，一般不叫內(nèi)外表，nested loop才有內(nèi)外表
?Hash表也就是所謂的內(nèi)表，探查表所謂的外表
?兩者的執(zhí)行計劃形如：
?nested loop
?outer table ? --驅(qū)動表
?inner table
?
?hash join
? build table ?(inner table) --驅(qū)動表
? probe table ? (outer ?table)?
?先看一張圖片，大致了解Hash Join的過程：
???

? ?

??下面詳細(xì)了解一下Hash Join
?㈠?Hash join概念
?
?Hash join算法的一個基本思想就是根據(jù)小的row sources(稱作build input?也就是前文提到的build table，我們記較小的表為S，較大的表為B)
??建立一個可以存在于hash area內(nèi)存中的hash table
??然后用大的row sources(稱作probe input，也就是前文提到的probe table)?來探測前面所建的hash table
??如果hash area內(nèi)存不夠大，hash table就無法完全存放在hash area內(nèi)存中
??針對這種情況，Oracle在連接鍵利用一個hash函數(shù)將build input和probe input分割成多個不相連的分區(qū)
??分別記作Si和Bi，這個階段叫做分區(qū)階段；然后各自相應(yīng)的分區(qū)，即Si和Bi再做Hash join，這個階段叫做join階段?
??如果HASH表太大，無法一次構(gòu)造在內(nèi)存中，則分成若干個partition，寫入磁盤的temporary segment，則會多一個寫的代價，會降低效率
??至于小表的概念，對于?hash join?來說，能容納在?pga?中的?hash table?都可以叫小表，通常比如：
? pga_aggregate_target ? big integer ?1073741824
? hash ?area size?大體能使用到40多?M?，這樣的話通常可能容納?幾十萬的記錄
? hash area size缺省是2*sort_area_size,我們可以直接修改SORT_AREA_SIZE?的大小，HASH_AREA_SIZE也會跟著改變的
??如果你的workarea_size_policy=auto，那么我們只需設(shè)定pga_aggregate_target
??但請記住，這是一個session級別的參數(shù)，有時，我們更傾向于把hash_area_size的大小設(shè)成驅(qū)動表的1.6倍左右
??驅(qū)動表僅僅用于nested loop join?和?hash join，但Hash join不需要在驅(qū)動表上存在索引，而nested loop join則迫切需求
??一兩百萬記錄的表?join上??千萬記錄的表，hash join的通常表現(xiàn)非常好
??不過，多與少，大與小，很多時候很難量化，具體情況還得具體分析
??如果在分區(qū)后，針對某個分區(qū)所建的hash table還是太大的話，oracle就采用nested loop hash join
??所謂的nested-loops hash join就是對部分Si建立hash table，然后讀取所有的Bi與所建的hash table做連接
??然后再對剩余的Si建立hash table，再將所有的Bi與所建的hash table做連接，直至所有的Si都連接完了
?
?㈡?Hash Join原理
?
?考慮以下兩個數(shù)據(jù)集：
? S={1,1,1,3,3,4,4,4,4,5,8,8,8,8,10}
? B={0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11}
? Hash Join的第一步就是判定小表（即build input）是否能完全存放在hash area內(nèi)存中
??如果能完全存放在內(nèi)存中，則在內(nèi)存中建立hash table，這是最簡單的hash join
??如果不能全部存放在內(nèi)存中，則build input必須分區(qū)。分區(qū)的個數(shù)叫做fan-out
? Fan-out是由hash_area_size和cluster size來決定的。其中cluster size等于db_block_size * _hash_multiblock_io_count
? hash_multiblock_io_count是個隱藏參數(shù),在9.0.1以后就不再使用了

[sql]?

sys@ORCL>?ed?
Wrote?file?afiedt.buf?
?
?1?select?a.ksppinm?name,b.ksppstvl?value,a.ksppdesc?description?
?2?from?x$ksppi?a,x$ksppcv?b?
?3?where?a.indx?=?b.indx?
?4*?and?a.ksppinm?like?'%hash_multiblock_io_count%'?
sys@ORCL>?/?
?
NAME?VALUE?DESCRIPTION?
------------------------------?-----?------------------------------------------------------------?
_hash_multiblock_io_count?0?number?of?blocks?hash?join?will?read/write?at?once?

? Oracle采用內(nèi)部一個hash函數(shù)作用于連接鍵上，將S和B分割成多個分區(qū)
??在這里我們假設(shè)這個hash函數(shù)為求余函數(shù)，即Mod(join_column_value,10)
??這樣產(chǎn)生十個分區(qū)，如下表:
?

???經(jīng)過這樣的分區(qū)之后，只需要相應(yīng)的分區(qū)之間做join即可（也就是所謂的partition pairs）?
??如果有一個分區(qū)為NULL的話，則相應(yīng)的分區(qū)join即可忽略
??在將S表讀入內(nèi)存分區(qū)時，oracle即記錄連接鍵的唯一值，構(gòu)建成所謂的位圖向量
??它需要占hash area內(nèi)存的5%左右。在這里即為{1,3,4,5,8,10}
??當(dāng)對B表進(jìn)行分區(qū)時，將每一個連接鍵上的值與位圖向量相比較，如果不在其中，則將其記錄丟棄
??在我們這個例子中，B表中以下數(shù)據(jù)將被丟棄{0,0,2,2,2,2,2,2,9,9,9,9,9}
??這個過程就是位圖向量過濾
??當(dāng)S1,B1做完連接后，接著對Si,Bi進(jìn)行連接
??這里oracle將比較兩個分區(qū)，選取小的那個做build input，就是動態(tài)角色互換
??這個動態(tài)角色互換發(fā)生在除第一對分區(qū)以外的分區(qū)上面

?㈢?Hash Join算法
?
?第1步：判定小表是否能夠全部存放在hash area內(nèi)存中，如果可以，則做內(nèi)存hash join。如果不行，轉(zhuǎn)第二步
??第2步：決定fan-out數(shù)
?(Number of Partitions) * C<= Favm *M
??其中C為Cluster size，其值為DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT
? Favm為hash area內(nèi)存可以使用的百分比，一般為0.8左右
? M為Hash_area_size的大小
??第3步：讀取部分小表S，采用內(nèi)部hash函數(shù)(這里稱為hash_fun_1)
?將連接鍵值映射至某個分區(qū)，同時采用hash_fun_2函數(shù)對連接鍵值產(chǎn)生另外一個hash值
?這個hash值用于創(chuàng)建hash table用，并且與連接鍵值存放在一起
??第4步：對build input建立位圖向量
??第5步：如果內(nèi)存中沒有空間了，則將分區(qū)寫至磁盤上
??第6步：讀取小表S的剩余部分，重復(fù)第三步，直至小表S全部讀完
??第7步：將分區(qū)按大小排序，選取幾個分區(qū)建立hash table(這里選取分區(qū)的原則是使選取的數(shù)量最多)
??第8步：根據(jù)前面用hash_fun_2函數(shù)計算好的hash值，建立hash table
??第9步：讀取表B，采用位圖向量進(jìn)行位圖向量過濾
??第10步：對通過過濾的數(shù)據(jù)采用hash_fun_1函數(shù)將數(shù)據(jù)映射到相應(yīng)的分區(qū)中去，并計算hash_fun_2的hash值
??第11步：如果所落的分區(qū)在內(nèi)存中，則將前面通過hash_fun_2函數(shù)計算所得的hash值與內(nèi)存中已存在的hash table做連接
?將結(jié)果寫致磁盤上。如果所落的分區(qū)不在內(nèi)存中，則將相應(yīng)的值與表S相應(yīng)的分區(qū)放在一起
??第12步：繼續(xù)讀取表B，重復(fù)第9步，直至表B讀取完畢??
??第13步：讀取相應(yīng)的(Si,Bi)做hash連接。在這里會發(fā)生動態(tài)角色互換
??第14步：如果分區(qū)過后，最小的分區(qū)也比內(nèi)存大，則發(fā)生nested-loop hash join ?
?
?㈣?Hash Join的成本
?
??⑴?In-Memory Hash Join
? Cost(HJ)=Read(S)+ build hash table in memory(CPU)+Read(B) + Perform In memory Join(CPU)
??忽略cpu的時間，則：
? Cost(HJ)=Read(S)+Read(B)
?
??⑵?On-Disk Hash Join
??根據(jù)上述的步驟描述，我們可以看出：
? Cost(HJ)=Cost(HJ1)+Cost(HJ2)?
??其中Cost(HJ1)的成本就是掃描S,B表，并將無法放在內(nèi)存上的部分寫回磁盤，對應(yīng)前面第2步至第12步
?Cost(HJ2)即為做nested-loop hash join的成本，對應(yīng)前面的第13步至第14步
??其中Cost(HJ1)近似等于Read(S)+Read(B)+Write((S-M)+(B-B*M/S))
??因為在做nested-loop hash join時，對每一chunk的build input，都需要讀取整個probe input，因此
? Cost(HJ2)近似等于Read((S-M)+n*(B-B*M/S))，其中n是nested-loop hash join需要循環(huán)的次數(shù)：n=(S/F)/M
??一般情況下，如果n大于10的話，hash join的性能將大大下降
??從n的計算公式可以看出，n與Fan-out成反比例，提高fan-out，可以降低n
??當(dāng)hash_area_size是固定時，可以降低cluster size來提高fan-out
??從這里我們可以看出，提高h(yuǎn)ash_multiblock_io_count參數(shù)的值并不一定提高h(yuǎn)ash join的性能
?
?㈤?Hash Join的過程
?
?一次完整的hash join如下：
?1 ?計算小表的分區(qū)（bucket）數(shù)--Hash分桶
??決定hash join的一個重要因素是小表的分區(qū)（bucket）數(shù)
??這個數(shù)字由hash_area_size、hash_multiblock_io_count和db_block_size參數(shù)共同決定
? Oracle會保留hash area的20%來存儲分區(qū)的頭信息、hash位圖信息和hash表
??因此，這個數(shù)字的計算公式是：
? Bucket數(shù)=0.8*hash_area_size/(hash_multiblock_io_count*db_block_size)
?
?2 ?Hash計算
??讀取小表數(shù)據(jù)（簡稱為R），并對每一條數(shù)據(jù)根據(jù)hash算法進(jìn)行計算
? Oracle采用兩種hash算法進(jìn)行計算，計算出能達(dá)到最快速度的hash值（第一hash值和第二hash值）
??而關(guān)于這些分區(qū)的全部hash值（第一hash值）就成為hash表
?
?3 ?存放數(shù)據(jù)到hash內(nèi)存中
??將經(jīng)過hash算法計算的數(shù)據(jù)，根據(jù)各個bucket的hash值（第一hash值）分別放入相應(yīng)的bucket中
??第二hash值就存放在各條記錄中
?
?4 ?創(chuàng)建hash位圖
??與此同時，也創(chuàng)建了一個關(guān)于這兩個hash值映射關(guān)系的hash位圖
?
?5 ?超出內(nèi)存大小部分被移到磁盤
??如果hash area被占滿，那最大一個分區(qū)就會被寫到磁盤（臨時表空間）上去
??任何需要寫入到磁盤分區(qū)上的記錄都會導(dǎo)致磁盤分區(qū)被更新
??這樣的話，就會嚴(yán)重影響性能，因此一定要盡量避免這種情況
? 2-5一直持續(xù)到整個表的數(shù)據(jù)讀取完畢
?
?6 ?對分區(qū)排序
?為了能充分利用內(nèi)存，盡量存儲更多的分區(qū)，Oracle會按照各個分區(qū)的大小將他們在內(nèi)存中排序
?
?7 ?讀取大表數(shù)據(jù)，進(jìn)行hash匹配
??接下來就開始讀取大表（簡稱S）中的數(shù)據(jù)
??按順序每讀取一條記錄，計算它的hash值，并檢查是否與內(nèi)存中的分區(qū)的hash值一致
??如果是，返回join數(shù)據(jù)
??如果內(nèi)存中的分區(qū)沒有符合的，就將S中的數(shù)據(jù)寫入到一個新的分區(qū)中，這個分區(qū)也采用與計算R一樣的算法計算出hash值
??也就是說這些S中的數(shù)據(jù)產(chǎn)生的新的分區(qū)數(shù)應(yīng)該和R的分區(qū)集的分區(qū)數(shù)一樣。這些新的分區(qū)被存儲在磁盤（臨時表空間）上
?
?8 ?完全大表全部數(shù)據(jù)的讀取
??一直按照7進(jìn)行，直到大表中的所有數(shù)據(jù)的讀取完畢
?
?9 ?處理沒有join的數(shù)據(jù)
??這個時候就產(chǎn)生了一大堆join好的數(shù)據(jù)和從R和S中計算存儲在磁盤上的分區(qū)
?
?10 ?二次hash計算
??從R和S的分區(qū)集中抽取出最小的一個分區(qū)，使用第二種hash函數(shù)計算出并在內(nèi)存中創(chuàng)建hash表
??采用第二種hash函數(shù)的原因是為了使數(shù)據(jù)分布性更好
?
?11 ?二次hash匹配
??在從另一個數(shù)據(jù)源（與hash在內(nèi)存的那個分區(qū)所屬數(shù)據(jù)源不同的）中讀取分區(qū)數(shù)據(jù)，與內(nèi)存中的新hash表進(jìn)行匹配。返回join數(shù)據(jù)
?
?12 ?完成全部hash join
??繼續(xù)按照9-11處理剩余分區(qū)，直到全部處理完畢

?㈥?Hash Join的模式
?Oracle中，Hash Join也有三種模式：optimal，one-pass，multi-pass
?⑴?optimal
?當(dāng)驅(qū)動結(jié)果集生成的hash表全部可以放入PGA的hash area時，稱為optimal，大致過程如下：
?①?先根據(jù)驅(qū)動表，得到驅(qū)動結(jié)果集
?②?在hash area生成hash bulket，并將若干bulket分成一組，成為一個partition，還會生成一個bitmap的列表，每個bulket在上面占一位
?③?對結(jié)果集的join鍵做hash運算，將數(shù)據(jù)分散到相應(yīng)partition的bulket中
??當(dāng)運算完成后，如果鍵值唯一性較高的話，bulket里的數(shù)據(jù)會比較均勻，也有可能有的桶里面數(shù)據(jù)會是空的
??這樣bitmap上對應(yīng)的標(biāo)志位就是0，有數(shù)據(jù)的桶，標(biāo)志位會是1 ?
?④?開始掃描第二張表，對jion鍵做hash運算，確定應(yīng)該到某個partition的某個bulket去探測
??探測之前，會看這個bulket的bitmap是否會1，如果為0，表示沒數(shù)據(jù)，這行就直接丟棄掉
?⑤?如果bitmap為1，則在桶內(nèi)做精確匹配，判斷OK后，返回數(shù)據(jù)
??這個是最優(yōu)的hash join，他的成本基本是兩張表的full table scan，在加微量的hash運算
??博客開篇的那幅圖描述的也就是這種情況

?⑵?one-pass
??如果進(jìn)程的pga很小，或者驅(qū)動表結(jié)果集很大，超過了hash area的大小，會怎么辦？
??當(dāng)然會用到臨時表空間，此時oracle的處理方式稍微復(fù)雜點需奧注意上面提到的有個partition的概念
??可以這么理解，數(shù)據(jù)是經(jīng)過兩次hash運算的，先確定你的partition，再確定你的bulket
??假設(shè)hash area小于整個hash table，但至少大于一個partition的size，這個時候走的就是one-pass
??當(dāng)我們生成好hash表后，狀況是部分partition留在內(nèi)存中，其他的partition留在磁盤臨時表空間中
??當(dāng)然也有可能某個partition一半在內(nèi)存，一半在磁盤，剩下的步驟大致如下：
?①?掃描第二張表，對join鍵做hash運算，確定好對應(yīng)的partition和bulket
?②?查看bitmap，確定bulket是否有數(shù)據(jù)，沒有則直接丟棄
?③?如果有數(shù)據(jù)，并且這個partition是在內(nèi)存中的，就進(jìn)入對應(yīng)的桶去精確匹配，能匹配上，就返回這行數(shù)據(jù)，否則丟棄
?④?如果partition是在磁盤上的，則將這行數(shù)據(jù)放入磁盤中暫存起來，保存的形式也是partition，bulket的方式
?⑤?當(dāng)?shù)诙埍肀粧呙柰旰?#xff0c;剩下的是驅(qū)動表和探測表生成的一大堆partition，保留在磁盤上
?⑥?由于兩邊的數(shù)據(jù)都按照相同的hash算法做了partition和bulket，現(xiàn)在只要成對的比較兩邊partition數(shù)據(jù)即可
?并且在比較的時候，oracle也做了優(yōu)化處理，沒有嚴(yán)格的驅(qū)動與被驅(qū)動關(guān)系
?他會在partition對中選較小的一個作為驅(qū)動來進(jìn)行，直到磁盤上所有的partition對都join完
?可以發(fā)現(xiàn)，相比optimal，他多出的成本是對于無法放入內(nèi)存的partition，重新讀取了一次，所以稱為one-pass
?只要你的內(nèi)存保證能裝下一個partition，oracle都會騰挪空間，每個磁盤partition做到one-pass
?
?⑶?multi-pass
??這是最復(fù)雜，最糟糕的hash join
??此時hash area小到連一個partition也容納不下，當(dāng)掃描好驅(qū)動表后
??可能只有半個partition留在hash area中，另半個加其他的partition全在磁盤上
??剩下的步驟和one-pass比價類似，不同的是針對partition的處理
??由于驅(qū)動表只有半個partition在內(nèi)存中，探測表對應(yīng)的partition數(shù)據(jù)做探測時
??如果匹配不上，這行還不能直接丟棄，需要繼續(xù)保留到磁盤，和驅(qū)動表剩下的半個partition再做join
??這里舉例的是內(nèi)存可以裝下半個partition，如果裝的更少的話，反復(fù)join的次數(shù)將更多
??當(dāng)發(fā)生multi-pass時，partition物理讀的次數(shù)會顯著增加

?㈦?Hash Join的位圖
?這個位圖包含了每個hash分區(qū)是否有有值的信息。它記錄了有數(shù)據(jù)的分區(qū)的hash值
?這個位圖的最大作用就是，如果probe input中的數(shù)據(jù)沒有與內(nèi)存中的hash表匹配上
?先查看這個位圖，以決定是否將沒有匹配的數(shù)據(jù)寫入磁盤
?那些不可能匹配到的數(shù)據(jù)（即位圖上對應(yīng)的分區(qū)沒有數(shù)據(jù)）就不再寫入磁盤
?
?㈧?小結(jié)
??①?確認(rèn)小表是驅(qū)動表
??②?確認(rèn)涉及到的表和連接鍵分析過了
??③?如果在連接鍵上數(shù)據(jù)不均勻的話，建議做柱狀圖
??④?如果可以，調(diào)大hash_area_size的大小或pga_aggregate_target的值
??⑤?Hash Join適合于小表與大表連接、返回大型結(jié)果集的連接

轉(zhuǎn)載于:https://www.cnblogs.com/mellowsmile/p/4839902.html

總結(jié)

以上是生活随笔為你收集整理的Oracle 哈希连接原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。