|
崔華，網(wǎng)名 dbsnake Oracle ACE Director，ACOUG 核心專(zhuān)家 編輯手記：感謝崔華授權(quán)我們獨(dú)家轉(zhuǎn)載其精品文章，也歡迎大家向“Oracle”社區(qū)投稿。 哈希連接（HASH JOIN）是一種兩個(gè)表在做表連接時(shí)主要依靠哈希運(yùn)算來(lái)得到連接結(jié)果集的表連接方法。 在 Oracle 7.3之前，Oracle 數(shù)據(jù)庫(kù)中的常用表連接方法就只有排序合并連接和嵌套循環(huán)連接這兩種，但這兩種表連接方法都有其明顯缺陷： 對(duì)于排序合并連接，如果兩個(gè)表在施加了目標(biāo) SQL 中指定的謂詞條件（如果有的話）后得到的結(jié)果集很大且需要排序的話，則這種情況下的排序合并連接的執(zhí)行效率一定是很差的； 而對(duì)于嵌套循環(huán)連接，如果驅(qū)動(dòng)表所對(duì)應(yīng)的驅(qū)動(dòng)結(jié)果集的記錄數(shù)很大，即便在被驅(qū)動(dòng)表的連接列上存在索引，此時(shí)使用嵌套循環(huán)連接的執(zhí)行效率也同樣會(huì)很差。
為了解決排序合并連接和嵌套循環(huán)連接在上述情形下執(zhí)行效率不高的問(wèn)題，同時(shí)也為了給優(yōu)化器提供一種新的選擇，Oracle 在 Oracle 7.3 中引入了哈希連接。從理論上來(lái)說(shuō)，哈希連接的執(zhí)行效率會(huì)比排序合并連接和嵌套循環(huán)連接的執(zhí)行效率要高，當(dāng)然，實(shí)際情況并不總是這樣。 在 Oracle 10g 及其以后的 Oracle 數(shù)據(jù)庫(kù)版本中，優(yōu)化器（實(shí)際上是 CBO，因?yàn)?strong>哈希連接僅適用于 CBO）在解析目標(biāo) SQL 時(shí)是否考慮哈希連接是受限于隱含參數(shù) _HASH_JOIN_ENABLED，而在 Oracle 10g 以前的 Oracle 數(shù)據(jù)庫(kù)版本中，CBO 在解析目標(biāo) SQL 時(shí)是否考慮哈希連接是受限于參數(shù) HASH_JOIN_ENABLED。 _HASH_JOIN_ENABLED 的默認(rèn)值是 TRUE，表示允許 CBO 在解析目標(biāo) SQL時(shí)考慮哈希連接。當(dāng)然，即使你將該參數(shù)的值改成了 FALSE，我們使用 USE_HASH Hint 依然可以讓 CBO 在解析目標(biāo) SQL 時(shí)考慮哈希連接，這說(shuō)明 USE_HASH Hint 的優(yōu)先級(jí)高于參數(shù) _HASH_JOIN_ENABLED。 如果兩個(gè)表（這里將它們分別命名為表 T1 和表 T2）在做表連接時(shí)使用的是哈希連接，則 Oracle 在做哈希連接時(shí)會(huì)依次順序執(zhí)行如下步驟： 首先 Oracle 會(huì)根據(jù)參數(shù) HASH_AREA_SIZE、DB_BLOCK_SIZE 和_HASH_MULTIBLOCK_IO_COUNT 的值來(lái)決定 Hash Partition 的數(shù)量（Hash Partition 是一個(gè)邏輯上的概念，所有 Hash Partition 的集合就被稱(chēng)之為 Hash Table，即一個(gè) Hash Table 是由多個(gè) Hash Partition 所組成，而一個(gè) Hash Partition 又是由多個(gè) Hash Bucket 所組成）； 表T1和T2在施加了目標(biāo) SQL 中指定的謂詞條件（如果有的話）后，得到的結(jié)果集中數(shù)據(jù)量較小的會(huì)被 Oracle 選為哈希連接的驅(qū)動(dòng)結(jié)果集，這里我們假設(shè) T1 所對(duì)應(yīng)的結(jié)果集的數(shù)據(jù)量相對(duì)較小，記為 S；T2 所對(duì)應(yīng)的結(jié)果集的數(shù)據(jù)量相對(duì)較大，記為 B；顯然這里 S 是驅(qū)動(dòng)結(jié)果集，B 是被驅(qū)動(dòng)結(jié)果集； 遍歷 S，讀取 S 中的每一條記錄，并對(duì) S 中的每一條記錄按照該記錄在表 T1 中的連接列做哈希運(yùn)算，這個(gè)哈希運(yùn)算會(huì)使用兩個(gè)內(nèi)置哈希函數(shù)，這兩個(gè)哈希函數(shù)會(huì)同時(shí)對(duì)該連接列計(jì)算哈希值，把這兩個(gè)內(nèi)置哈希函數(shù)分別記為 hash_func_1 和 hash_func_2，計(jì)算的哈希值分別記為 hash_value_1 和 hash_value_2； 按照 hash_value_1 的值把相應(yīng)的 S 中的對(duì)應(yīng)記錄存儲(chǔ)在不同 Hash Partition 的不同 Hash Bucket 里，同時(shí)和該記錄存儲(chǔ)在一起的還有該記錄用 hash_func_2 計(jì)算出來(lái)的 hash_value_2 的值。注意，存儲(chǔ)在 Hash Bucket 里的記錄并不是目標(biāo)表的完整行記錄，而是只需要存儲(chǔ)位于目標(biāo) SQL 中的跟目標(biāo)表相關(guān)的查詢(xún)列和連接列就足夠了；把 S 所對(duì)應(yīng)的每一個(gè) Hash Partition 記為 Si； 在構(gòu)建 Si 的同時(shí)，Oracle 會(huì)構(gòu)建一個(gè)位圖（BITMAP），這個(gè)位圖用來(lái)標(biāo)記 Si 所包含的每一個(gè) Hash Bucket 是否有記錄（即記錄數(shù)是否大于0）； 如果 S 的數(shù)據(jù)量很大，那么在構(gòu)建 S 所對(duì)應(yīng)的 Hash Table 時(shí)，就可能會(huì)出現(xiàn) PGA 的工作區(qū)（WORK AREA）被填滿的情況，這時(shí)候 Oracle 會(huì)把工作區(qū)中現(xiàn)有的 Hash Partition 中包含記錄數(shù)最多的 Hash Partition 寫(xiě)到磁盤(pán)上（TEMP 表空間）；接著 Oracle 會(huì)繼續(xù)構(gòu)建 S 所對(duì)應(yīng)的 Hash Table，在繼續(xù)構(gòu)建的過(guò)程中，如果工作區(qū)又滿了，則 Oracle 會(huì)繼續(xù)重復(fù)上述挑選包含記錄數(shù)最多的 Hash Partition 并寫(xiě)回到磁盤(pán)上的動(dòng)作；如果要構(gòu)建的記錄所對(duì)應(yīng)的 Hash Partition 已經(jīng)事先被 Oracle 寫(xiě)回到了磁盤(pán)上，則此時(shí) Oracle 就會(huì)去磁盤(pán)上更新該 Hash Partition，即會(huì)把該條記錄和 hash_value_2 直接加到這個(gè)已經(jīng)位于磁盤(pán)上的 Hash Partition 的相應(yīng) Hash Bucket 中；注意，極端情況下可能會(huì)出現(xiàn)只有某個(gè) Hash Partition 的部分記錄還在內(nèi)存中，該 Hash Partition 的剩余部分和余下的所有 Hash Partition 都已經(jīng)被寫(xiě)回到磁盤(pán)上； 上述構(gòu)建 S 所對(duì)應(yīng)的 Hash Table 的過(guò)程會(huì)一直持續(xù)下去，直到遍歷完 S 中的所有記錄為止； 接著，Oracle 會(huì)對(duì)所有的 Si 按照它們所包含的記錄數(shù)來(lái)排序，然后 Oracle 會(huì)把這些已經(jīng)排好序的 Hash Partition 按順序依次、并且盡可能的全部放到內(nèi)存中（PGA 的工作區(qū)），當(dāng)然，如果實(shí)在放不下的話，放不下的那部分 Hash Partition 還是會(huì)位于磁盤(pán)上。我認(rèn)為這個(gè)按照 Si 的記錄數(shù)來(lái)排序的動(dòng)作不是必須要做的，因?yàn)檫@個(gè)排序動(dòng)作的根本目的就是為了盡可能多的把那些記錄數(shù)較小的 Hash Partition 保留在內(nèi)存中，而將那些已經(jīng)被寫(xiě)回到磁盤(pán)上、記錄數(shù)較大且現(xiàn)有內(nèi)存已經(jīng)放不下的 Hash Partition 保留在磁盤(pán)上，顯然，如果所有的 Si 本來(lái)就都在內(nèi)存中，也沒(méi)發(fā)生過(guò)將 Si 寫(xiě)回到磁盤(pán)的操作，那這里根本就不需要排序了。 至此 Oracle 已經(jīng)處理完 S，現(xiàn)在可以來(lái)開(kāi)始處理 B 了； Oracle 會(huì)遍歷 B，讀取 B 中的每一條記錄，并對(duì) B 中的每一條記錄按照該記錄在表 T2 中的連接列做哈希運(yùn)算，這個(gè)哈希運(yùn)算和步驟3中的哈希運(yùn)算是一模一樣的，即這個(gè)哈希運(yùn)算還是會(huì)用步驟3中的 hash_func_1 和 hash_func_2，并且也會(huì)計(jì)算出兩個(gè)哈希值 hash_value_1 和hash_value_2；接著 Oracle 會(huì)按照該記錄所對(duì)應(yīng)的哈希值 hash_value_1 去 Si 里找匹配的 Hash Bucket；如果能找到匹配的 Hash Bucket，則 Oracle 還會(huì)遍歷該 Hash Bucket 中的每一條記錄，并會(huì)校驗(yàn)存儲(chǔ)于該 Hash Bucket 中的每一條記錄的連接列，看是否是真的匹配（即這里要校驗(yàn) S 和 B 中的匹配記錄所對(duì)應(yīng)的連接列是否真的相等，因?yàn)閷?duì)于 Hash 運(yùn)算而言，不同的值經(jīng)過(guò)哈希運(yùn)算后的結(jié)果可能是一樣的），如果是真的匹配，則上述 hash_value_1 所對(duì)應(yīng) B 中的記錄的位于目標(biāo) SQL 中的查詢(xún)列和該 Hash Bucket 中的匹配記錄便會(huì)組合起來(lái)，一起作為滿足目標(biāo) SQL 連接條件的記錄返回；如果找不到匹配的 Hash Bucket，則 Oracle 就會(huì)去訪問(wèn)步驟5中構(gòu)建的位圖，如果位圖顯示該 Hash Bucket 在 Si 中對(duì)應(yīng)的記錄數(shù)大于0，則說(shuō)明該 Hash Bucket 雖然不在內(nèi)存中，但它已經(jīng)被寫(xiě)回到了磁盤(pán)上，則此時(shí) Oracle就會(huì)按照上述 hash_value_1 的值把相應(yīng) B 中的對(duì)應(yīng)記錄也以 Hash Partition 的方式寫(xiě)回到磁盤(pán)上，同時(shí)和該記錄存儲(chǔ)在一起的還有該記錄用 hash_func_2 計(jì)算出來(lái)的 hash_value_2 的值；如果位圖顯示該 Hash Bucket 在 Si 中對(duì)應(yīng)的記錄數(shù)等于0，則 Oracle 就不用把上述 hash_value_1所對(duì)應(yīng) B 中的記錄寫(xiě)回到磁盤(pán)上了，因?yàn)檫@條記錄必然不滿足目標(biāo) SQL 的連接條件；這個(gè)根據(jù)位圖來(lái)決定是否將上述 hash_value_1 所對(duì)應(yīng)B中的記錄寫(xiě)回到磁盤(pán)的動(dòng)作就是所謂的“位圖過(guò)濾”；我們把B所對(duì)應(yīng)的每一個(gè) Hash Partition 記為 Bj; 上述去 Si 中查找匹配 Hash Bucket 和構(gòu)建 Bj 的過(guò)程會(huì)一直持續(xù)下去，直到遍歷完 B 中的所有記錄為止； 至此 Oracle 已經(jīng)處理完所有位于內(nèi)存中的 Si 和對(duì)應(yīng)的 Bj，現(xiàn)在只剩下位于磁盤(pán)上的 Si 和 Bj 還未處理； 因?yàn)樵跇?gòu)建 Si 和 Bj 時(shí)用的是同樣的哈希函數(shù) hash_func_1 和hash_func_2，所以 Oracle 在處理位于磁盤(pán)上的 Si 和 Bj 的時(shí)候可以放心的配對(duì)處理，即只有對(duì)應(yīng) Hash Partition Number 值相同的 Si 和 Bj 才可能會(huì)產(chǎn)生滿足連接條件的記錄；這里我們用 Sn 和 Bn 來(lái)表示位于磁盤(pán)上且對(duì)應(yīng) Hash Partition Number 值相同的 Si 和 Bj； 對(duì)于每一對(duì)兒 Sn 和 Bn，它們之中記錄數(shù)較少的會(huì)被當(dāng)作驅(qū)動(dòng)結(jié)果集，然后 Oracle 會(huì)用這個(gè)驅(qū)動(dòng)結(jié)果集的 Hash Bucket 里記錄的 hash_value_2 來(lái)構(gòu)建新的 Hash Table，另外一個(gè)記錄數(shù)較大的會(huì)被當(dāng)作被驅(qū)動(dòng)結(jié)果集，然后 Oracle會(huì)用這個(gè)被驅(qū)動(dòng)結(jié)果集的 Hash Bucket 里記錄的 hash_value_2 去上述構(gòu)建的新 Hash Table 中找匹配記錄；注意，對(duì)每一對(duì)兒 Sn 和 Bn 而言，Oracle 始終會(huì)選擇它們中記錄數(shù)較少的來(lái)作為驅(qū)動(dòng)結(jié)果集，所以每一對(duì)兒 Sn 和 Bn 的驅(qū)動(dòng)結(jié)果集都可能會(huì)發(fā)生變化，這就是所謂的“動(dòng)態(tài)角色互換”； 步驟14中如果存在匹配記錄，則該匹配記錄也會(huì)作為滿足目標(biāo) SQL 連接條件的記錄返回； 上述處理 Sn 和 Bn 的過(guò)程會(huì)一直持續(xù)下去，直到遍歷完所有的 Sn 和 Bn 為止。
對(duì)于哈希連接的優(yōu)缺點(diǎn)及適用場(chǎng)景，我們有如下總結(jié)：
哈希連接不一定會(huì)排序，或者說(shuō)大多數(shù)情況下都不需要排序； 哈希連接的驅(qū)動(dòng)表所對(duì)應(yīng)的連接列的可選擇性應(yīng)盡可能的好，因?yàn)檫@個(gè)可選擇性會(huì)影響對(duì)應(yīng) Hash Bucket 中的記錄數(shù)，而 Hash Bucket 中的記錄數(shù)又會(huì)直接影響從該 Hash Bucket 中查找匹配記錄的效率；如果一個(gè) Hash Bucket 里所包含的記錄數(shù)過(guò)多，則可能會(huì)嚴(yán)重降低所對(duì)應(yīng)哈希連接的執(zhí)行效率，此時(shí)典型的表現(xiàn)就是該哈希連接執(zhí)行了很長(zhǎng)時(shí)間都沒(méi)有結(jié)束，數(shù)據(jù)庫(kù)所在 database server 上的 CPU 占用率很高，但目標(biāo) SQL 所消耗的邏輯讀卻很低，因?yàn)榇藭r(shí)大部分時(shí)間都耗費(fèi)在了遍歷上述 Hash Bucket 里的所有記錄上，而遍歷 Hash Bucket 里記錄這個(gè)動(dòng)作是發(fā)生在 PGA 的工作區(qū)里，所以不耗費(fèi)邏輯讀； 哈希連接只適用于 CBO、它也只能用于等值連接條件（即使是哈希反連接，Oracle 實(shí)際上也是將其轉(zhuǎn)換成了等價(jià)的等值連接）； 哈希連接很適合于一個(gè)小表和大表之間的表連接，特別是在小表的連接列的可選擇性非常好的情況下，這時(shí)候哈希連接的執(zhí)行時(shí)間就可以近似看作是和全表掃描那個(gè)大表所耗費(fèi)的時(shí)間相當(dāng)； 當(dāng)兩個(gè)表做哈希連接時(shí)，如果這兩個(gè)表在施加了目標(biāo) SQL 中指定的謂詞條件（如果有的話）后得到的結(jié)果集中數(shù)據(jù)量較小的那個(gè)結(jié)果集所對(duì)應(yīng)的 Hash Table 能夠完全被容納在內(nèi)存中時(shí)（PGA 的工作區(qū)），則此時(shí)的哈希連接的執(zhí)行效率會(huì)非常高。
可以借助于10104事件所產(chǎn)生的 trace 文件來(lái)觀察目標(biāo) SQL 在做哈希連接時(shí)的大致過(guò)程和一些統(tǒng)計(jì)信息（比如用了多少個(gè) Hash Partition、多個(gè)少 Hash Bucket 以及各個(gè) Hash Bucket 都分別有多少條記錄等），10104 事件在我們實(shí)際診斷哈希連接的性能問(wèn)題時(shí)非常有用。
使用 10104 事件觀察目標(biāo) SQL 做哈希連接的具體過(guò)程為： oradebug setmypid oradebug event 10104 trace name context forever, level 1 set autotrace traceonly 實(shí)際執(zhí)行目標(biāo) SQL（必須要實(shí)際執(zhí)行該 SQL，不能用 explain plan for） oradebug tracefile_name 一個(gè)典型的 10104 事件所產(chǎn)生的 trace 文件內(nèi)容為如下所示： kxhfInit(): enter kxhfInit(): exit *** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) *** Join Type: INNER join Original hash-area size: 3642760 Memory for slot table: 2826240 Calculated overhead for partitions and row/slot managers: 816520 Hash-join fanout: 8 Number of partitions: 8 Number of slots: 23 Multiblock IO: 15 Block size(KB): 8 Cluster (slot) size(KB): 120 Minimum number of bytes per block: 8160 Bit vector memory allocation(KB): 128 Per partition bit vector length(KB): 16 ……省略顯示部分內(nèi)容 Slot table resized: old=23 wanted=12 got=12 unload=0 *** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) *** Total number of partitions: 8 Number of partitions which could fit in memory: 8 Number of partitions left in memory: 8 Total number of slots in in-memory partitions: 8 kxhfResize(enter): resize to 14 slots (numAlloc=8, max=12) kxhfResize(exit): resized to 14 slots (numAlloc=8, max=14) set work area size to: 2215K (14 slots) *** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) *** Total number of partitions: 8 Number of partitions left in memory: 8 Total number of rows in in-memory partitions: 1000 (used as preliminary number of buckets in hash table) Estimated max # of build rows that can fit in avail memory: 79800 ### Partition Distribution ### Partition:0 rows:120 clusters:1 slots:1 kept=1 Partition:1 rows:122 clusters:1 slots:1 kept=1 ……省略顯示部分內(nèi)容 Partition:6 rows:118 clusters:1 slots:1 kept=1 Partition:7 rows:137 clusters:1 slots:1 kept=1 *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) *** Revised number of hash buckets (after flushing): 1000 Allocating new hash table. *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) *** Requested size of hash table: 256 Actual size of hash table: 256 Number of buckets: 2048 Match bit vector allocated: FALSE *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) *** Total number of rows (may have changed): 1000 Number of in-memory partitions (may have changed): 8 Final number of hash buckets: 2048 Size (in bytes) of hash table: 8192 qerhjBuildHashTable(): done hash-table on partition=7, index=0 last_slot#=3 rows=137 total_rows=137 qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=4 rows=118 total_rows=255 ……省略顯示部分內(nèi)容 qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=2 rows=122 total_rows=880 qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=5 rows=120 total_rows=1000 kxhfIterate(end_iterate): numAlloc=8, maxSlots=14 *** (continued) HASH JOIN BUILD HASH TABLE (PHASE 1) *** ### Hash table ### # NOTE: The calculated number of rows in non-empty buckets may be smaller # than the true number. Number of buckets with 0 rows: 1249 Number of buckets with 1 rows: 626 Number of buckets with 2 rows: 149 Number of buckets with 3 rows: 21 Number of buckets with 4 rows: 3 Number of buckets with 5 rows: 0 ……省略顯示部分內(nèi)容 Number of buckets with between 90 and 99 rows: 0 Number of buckets with 100 or more rows: 0 ### Hash table overall statistics ### Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799 Total number of rows: 1000 Maximum number of rows in a bucket: 4 Average number of rows in non-empty buckets: 1.251564 Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000 qerhjFetch: max probe row length (mpl=0) *** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory kxhfRemoveChunk: remove chunk 0 from slot table 注意到上述顯示內(nèi)容中我粗體標(biāo)出的部分，如 “Number of in-memory partitions (may have changed):8”、 “Final number of hash buckets: 2048”、 “Total buckets: 2048 Empty buckets: 1249 Non-empty buckets: 799”、 “Total number of rows: 1000”、 “Maximum number of rows in a bucket:4”、 “Disabled bitmap filtering: filtered rows=0 minimum required=50 out of=1000”
等，這說(shuō)明上述哈希連接驅(qū)動(dòng)結(jié)果集的記錄數(shù)為1000，共有8個(gè) Hash Partition、2048個(gè) Hash Bucket，這2048個(gè) Hash Bucket 中有1249個(gè)是空的（即沒(méi)有記錄）、799個(gè)有記錄，包含記錄數(shù)最多的一個(gè) Hash Bucket 所含記錄的數(shù)量為4以及上述哈希連接并沒(méi)有啟用位圖過(guò)濾。 本文內(nèi)容收入崔華出版著作《基于Oracle的SQL優(yōu)化》一書(shū)。
|
