關(guān)于oracle中的hash join詳解

一、? hash join概念? ? ? ? ? ? ? ? ??

hash join(HJ)是一種用于equi-join（而anti-join就是使用NOT IN時(shí)的join）的技術(shù)。在Oracle中，它是從7.3開始引入的，以代替sort-merge和nested-loop join方式，提高效率。在CBO（hash join只有在CBO才可能被使用到）模式下，優(yōu)化器計(jì)算代價(jià)時(shí)，首先會(huì)考慮hash join?？梢酝ㄟ^提示use_hash來強(qiáng)制使用hash join，也可以通過修改會(huì)話或數(shù)據(jù)庫(kù)參數(shù)HASH_JOIN_ENABLED=FALSE（默認(rèn)為TRUE）強(qiáng)制不使用hash join。 ? ? ? ? ? ????? Hash join的主要資源消耗在于CPU（在內(nèi)存中創(chuàng)建臨時(shí)的hash表，并進(jìn)行hash計(jì)算），而merge join的資源消耗主要在于磁盤IO（掃描表或索引）。在并行系統(tǒng)中，hash join對(duì)CPU的消耗更加明顯。所以在CPU緊張時(shí)，最好限制使用hash join。 ? ? ? ? ? ?

在絕大多數(shù)情況下，hash join效率比其他join方式效率更高： ? ? ? ? ? ??????

在Sort-Merge Join(SMJ)，兩張表的數(shù)據(jù)都需要先做排序，然后做merge。因此效率相對(duì)最差； ? ? ? ? ? ??????

Nested-Loop Join(NL)效率比SMJ更高。特別是當(dāng)驅(qū)動(dòng)表的數(shù)據(jù)量很大（集的勢(shì)高）時(shí)。這樣可以并行掃描內(nèi)表。 ? ? ? ? ? ??????

Hash join效率最高，因?yàn)橹灰獙?duì)兩張表掃描一次。? ? ? ? ? ? ??????

Hash join一般用于一張小表和一張大表進(jìn)行join時(shí)。Hash join的過程大致如下（下面所說的內(nèi)存就指sort area，關(guān)于過程，后面會(huì)作詳細(xì)討論）： ? ? ? ? ? ?

1．?一張小表被hash在內(nèi)存中。因?yàn)閿?shù)據(jù)量小，所以這張小表的大多數(shù)數(shù)據(jù)已經(jīng)駐入在內(nèi)存中，剩下的少量數(shù)據(jù)被放置在臨時(shí)表空間中； ? ? ? ? ? ?

2．?每讀取大表的一條記錄，就和小表中內(nèi)存中的數(shù)據(jù)進(jìn)行比較，如果符合，則立即輸出數(shù)據(jù)（也就是說沒有讀取臨時(shí)表空間中的小表的數(shù)據(jù)）。而如果大表的數(shù)據(jù)與小表中臨時(shí)表空間的數(shù)據(jù)相符合，則不直接輸出，而是也被存儲(chǔ)臨時(shí)表空間中。 ? ? ? ? ? ?

3．?當(dāng)大表的所有數(shù)據(jù)都讀取完畢，將臨時(shí)表空間中的數(shù)據(jù)以其輸出。 ? ? ? ? ? ???????

如果小表的數(shù)據(jù)量足夠小（小于hash area size），那所有數(shù)據(jù)就都在內(nèi)存中了，可以避免對(duì)臨時(shí)表空間的讀寫。 ? ? ? ? ? ?

如果是并行環(huán)境下，前面中的第2步就變成如下了：每讀取一條大表的記錄，和內(nèi)存中小表的數(shù)據(jù)比較，如果符合先做join，而不直接輸出，直到整張大表數(shù)據(jù)讀取完畢。如果內(nèi)存足夠，Join好的數(shù)據(jù)就保存在內(nèi)存中。否則，就保存在臨時(shí)表空間中。 ? ? ? ? ? ?

二、? Oracle中與hash join相關(guān)的參數(shù) ? ? ? ? ? ??????

首先，要注意的是，hash join只有在CBO方式下才會(huì)被激活。在oracle中與hash join相關(guān)的參數(shù)主要有以下幾個(gè)： ? ? ? ? ? ?

1.HASH_JOIN_ENABLED ? ? ? ? ? ??????

這個(gè)參數(shù)是控制查詢計(jì)劃是否采用hash join的“總開關(guān)”。它可以在會(huì)話級(jí)和實(shí)例級(jí)被修改。默認(rèn)為TRUE，既可以（不是一定，要看優(yōu)化器計(jì)算出來的代價(jià)）使用。如果設(shè)為FALSE，則禁止使用hash join。 ? ? ? ? ? ?

2.HASH_AREA_SIZE ? ? ? ? ? ??????

這個(gè)參數(shù)控制每個(gè)會(huì)話的hash內(nèi)存空間有多大。它也可以在會(huì)話級(jí)和實(shí)例級(jí)被修改。默認(rèn)（也是推薦）值是sort area空間大小的兩倍（2*SORT_AREA_SIZE）。要提高h(yuǎn)ash join的效率，就一定盡量保證sort area足夠大，能容納下整個(gè)小表的數(shù)據(jù)。但是因?yàn)槊總€(gè)會(huì)話都會(huì)開辟一個(gè)這么大的內(nèi)存空間作為hash內(nèi)存，所以不能過大（一般不建議超過2M）。在Oracle9i及以后版本中，Oracle不推薦在dedicated server中使用這個(gè)參數(shù)來設(shè)置hash內(nèi)存，而是推薦通過設(shè)置PGA_AGGRATE_TARGET參數(shù)來自動(dòng)管理PGA內(nèi)存。保留HASH_AREA_SIZE只是為了向后兼容。在dedicated server中，hash area是從PGA中分配的，而在MTS(Multi-Threaded Server)中，hash area是從UGA中分配的。 ? ? ? ? ? ??????

另外，還要注意的是，每個(gè)會(huì)話并不一定只打開一個(gè)hash area，因?yàn)橐粋€(gè)查詢中可能不止一個(gè)hash join，這是就會(huì)相應(yīng)同時(shí)打開多個(gè)hash area。 ? ? ? ? ? ?

3.HAHS_MULTIBLOCK_IO_COUNT ? ? ? ? ? ??????

這個(gè)參數(shù)決定每次讀入hash area的數(shù)據(jù)塊數(shù)量。因此它會(huì)對(duì)IO性能產(chǎn)生影響。他只能在init.ora或spfile中修改。在8.0及之前版本，它的默認(rèn)值是1，在8i及以后版本，默認(rèn)值是0。一般設(shè)置為1-(65536/DB_BLOCK_SIZE)。? ? ? ? 在9i中，這個(gè)參數(shù)是一個(gè)隱藏參數(shù)：_HASH_MULTIBLOCK_IO_COUNT，可以通過表x$ksppi查詢和修改。 ? ? ? ? ? ??????

另外，在MTS中，這個(gè)參數(shù)將不起作用（只會(huì)使用1）。 ? ? ? ? ? ??????

它的最大值受到OS的IO帶寬和DB_BLOCK_SIZE的影響。既不能大于MAX_IO_SIZE/DB_BLOCK_SIZE。 ? ? ? ? ? ??????

在8i及以后版本，如果這個(gè)值設(shè)置為0，則表示在每次查詢時(shí)，Oracle自己自動(dòng)計(jì)算這個(gè)值。這個(gè)值對(duì)IO性能影響非常大，因此，建議不要修改這個(gè)參數(shù)，使用默認(rèn)值0，讓Oracle自己去計(jì)算這個(gè)值。如果一定要設(shè)置這個(gè)值，要保證以下不等式能成立：R/M < Po2(M/C)其中，R表示小表的大小；M=HASH_AREA_SIZE*0.9；Po2(n)為n的2次方；C=HASH_MULTIBLOCK_IO_COUNT*DB_BLOCK_SIZE。 ? ? ? ? ? ?

三、? Hash join的過程 ? ? ? ? ? ??????

一次完整的hash join如下：? ? ? ? ? ??

1.計(jì)算小表的分區(qū)（bucket）數(shù) ? ? ? ? ? ?????

決定hash join的一個(gè)重要因素是小表的分區(qū)（bucket）數(shù)。這個(gè)數(shù)字由hash_area_size、hash_multiblock_io_count和db_block_size參數(shù)共同決定。Oracle會(huì)保留hash area的20%來存儲(chǔ)分區(qū)的頭信息、hash位圖信息和hash表。因此，這個(gè)數(shù)字的計(jì)算公式是： ? ? ? ? ? ??????

Bucket數(shù)=0.8*hash_area_size/(hash_multiblock_io_count*db_block_size) ? ? ? ? ? ?

2.Hash計(jì)算??? ? ? ? ? ? ??????

讀取小表數(shù)據(jù)（簡(jiǎn)稱為R），并對(duì)每一條數(shù)據(jù)根據(jù)hash算法進(jìn)行計(jì)算。Oracle采用兩種hash算法進(jìn)行計(jì)算，計(jì)算出能達(dá)到最快速度的hash值（第一hash值和第二hash值）。而關(guān)于這些分區(qū)的全部hash值（第一hash值）就成為hash表。 ? ? ? ? ? ?

3.存放數(shù)據(jù)到hash內(nèi)存中 ? ? ? ? ? ??????

將經(jīng)過hash算法計(jì)算的數(shù)據(jù)，根據(jù)各個(gè)bucket的hash值（第一hash值）分別放入相應(yīng)的bucket中。第二hash值就存放在各條記錄中。 ? ? ? ? ? ?

4.創(chuàng)建hash位圖 ? ? ? ? ? ??????

與此同時(shí)，也創(chuàng)建了一個(gè)關(guān)于這兩個(gè)hash值映射關(guān)系的hash位圖。 ? ? ? ? ? ?

5超出內(nèi)存大小部分被移到磁盤 ? ? ? ? ? ??????

如果hash area被占滿，那最大一個(gè)分區(qū)就會(huì)被寫到磁盤（臨時(shí)表空間）上去。任何需要寫入到磁盤分區(qū)上的記錄都會(huì)導(dǎo)致磁盤分區(qū)被更新。這樣的話，就會(huì)嚴(yán)重影響性能，因此一定要盡量避免這種情況。2-5一直持續(xù)到整個(gè)表的數(shù)據(jù)讀取完畢。 ? ? ? ? ? ?

6.對(duì)分區(qū)排序 ? ? ? ? ? ??????

為了能充分利用內(nèi)存，盡量存儲(chǔ)更多的分區(qū)，Oracle會(huì)按照各個(gè)分區(qū)的大小將他們?cè)趦?nèi)存中排序。 ? ? ? ? ? ?

7.讀取大表數(shù)據(jù)，進(jìn)行hash匹配 ? ? ? ? ? ??????

接下來就開始讀取大表（簡(jiǎn)稱S）中的數(shù)據(jù)。按順序每讀取一條記錄，計(jì)算它的hash值，并檢查是否與內(nèi)存中的分區(qū)的hash值一致。如果是，返回join數(shù)據(jù)。如果內(nèi)存中的分區(qū)沒有符合的，就將S中的數(shù)據(jù)寫入到一個(gè)新的分區(qū)中，這個(gè)分區(qū)也采用與計(jì)算R一樣的算法計(jì)算出hash值。也就是說這些S中的數(shù)據(jù)產(chǎn)生的新的分區(qū)數(shù)應(yīng)該和R的分區(qū)集的分區(qū)數(shù)一樣。這些新的分區(qū)被存儲(chǔ)在磁盤（臨時(shí)表空間）上。 ? ? ? ? ? ?

8.完全大表全部數(shù)據(jù)的讀取 ? ? ? ? ? ??????

一直按照7進(jìn)行，直到大表中的所有數(shù)據(jù)的讀取完畢。? ? ? ? ? ? ?

9.處理沒有join的數(shù)據(jù) ? ? ? ? ? ??????

這個(gè)時(shí)候就產(chǎn)生了一大堆join好的數(shù)據(jù)和從R和S中計(jì)算存儲(chǔ)在磁盤上的分區(qū)。 ? ? ? ? ? ?

10.二次hash計(jì)算 ? ? ? ? ? ??????

從R和S的分區(qū)集中抽取出最小的一個(gè)分區(qū)，使用第二種hash函數(shù)計(jì)算出并在內(nèi)存中創(chuàng)建hash表。采用第二種hash函數(shù)的原因是為了使數(shù)據(jù)分布性更好。 ? ? ? ? ? ?

11.二次hash匹配 ? ? ? ? ? ??????

在從另一個(gè)數(shù)據(jù)源（與hash在內(nèi)存的那個(gè)分區(qū)所屬數(shù)據(jù)源不同的）中讀取分區(qū)數(shù)據(jù)，與內(nèi)存中的新hash表進(jìn)行匹配。返回join數(shù)據(jù)。 ? ? ? ? ? ?

12.完成全部hash join ? ? ? ? ? ??????

繼續(xù)按照9-11處理剩余分區(qū)，直到全部處理完畢。? ? ? ? ? ? ??????

整個(gè)hash join就完成了。? ? ? ? ? ? ?

四、?關(guān)于唯一健值的hash位圖 ? ? ? ? ? ??????

這個(gè)位圖包含了每個(gè)hash分區(qū)是否有有值的信息。它記錄了有數(shù)據(jù)的分區(qū)的hash值。這個(gè)位圖的最大作用就是，如果S表中的數(shù)據(jù)沒有與內(nèi)存中的hash表匹配上，先查看這個(gè)位圖，已決定是否將沒有匹配的數(shù)據(jù)寫入磁盤。那些不可能匹配到的數(shù)據(jù)（即位圖上對(duì)應(yīng)的分區(qū)沒有數(shù)據(jù)）就不再寫入磁盤。