Oracle Hash join 是一种非常高效的join 算法，主要以CPU(hash计算)和内存空间(创建hash table)为代价获得最大的效率。Hash join一般用于大表和小表之间的连接，我们将小表构建到内存中，称为Hash cluster，大表称为probe表。

当两个表做hash join时，oracle会选择一个表作为驱动表，先根据过滤条件排除不必要的数据，然后将结果集做成hash表，放入进程的hash area，接着扫描第二张表，将记录的join字段值做hash运算，到内存的hash表里面去探测，如果探测成功，就返回数据，否则这行就丢弃掉。

(miki西游 @mikixiyou 原文链接: http://mikixiyou.iteye.com/blog/1709321 )

Sql代码  

1. select /*+use_nl(a b)*/ a.*,b.*   
2. from dba_obj a,all_obj b  
3. where a.object_id=b.object_id  
4. and a.object_name like 'tt%'  
5.   
6.   
7.   
8. SELECT STATEMENT, GOAL = ALL_ROWS         
9.  NESTED LOOPS         
10.   TABLE ACCESS FULL SCOTT   DBA_OBJ  
11.   TABLE ACCESS BY INDEX ROWID   SCOTT   ALL_OBJ  
12.    INDEX UNIQUE SCAN    SCOTT   PK_ALL_OBJ  

执行计划解读

两个表使用了嵌套循环连接。首先访问dba_obj表，得到全部记录。然后按照此表记录依次去扫描all_obj表，扫描过程走索引快速得到all_obj的记录。

Sql代码  

1. select /*+use_hash(a b)*/ a.*,b.*   
2. from dba_obj a,all_obj b  
3. where a.object_id=b.object_id  
4. and a.object_name like 'tt%'  
5.   
6.   
7.   
8. SELECT STATEMENT, GOAL = ALL_ROWS         
9.  HASH JOIN        
10.   TABLE ACCESS FULL SCOTT   DBA_OBJ  
11.   TABLE ACCESS FULL SCOTT   ALL_OBJ  

执行计划解读

两个表使用了哈希连接。首先访问dba_obj表，得到全部记录，进行hash运算，放到内存hash area中形成hash table，也称为hash cluster。
然后，再腾出手来，全面扫描all_obj表，每扫描到一条记录时，将join字段进行hash运算，然后到hash area中去找与dba_obj表匹配的记录。
这个行为称为probe，中文称探测。此表也称为probe表。

hash table表是保存在hash area内存区域中，而这个区域在oracle中是分配在pga中。

PGA 包括 进程内存、UGA、sort area,bitmap merge area和hash area。UGA包含session状态信息和private sql area。

使用这个10104 event可以分析hash area的内存分配情况。

alter system set events '10104 trace name context forever,level 2';
 
select count(*)
  from (select /*+use_hash(i g) leading(i)*/
         i.*, g.*
          from tdividenddetail i, tproductinfo g
         where i.c_fundcode = g.fundcode
           and i.d_cdate > sysdate - 100);

使用use_hash提示强制让两个表采用hash join关联，然后使用leading提示强制让i表作为驱动表。

在hash area中，默认采用8个partition，每个partition保存若干个 hash table的记录。这些记录又以bucket逻辑结构存储。

分析trc文件内容如下所示：

Trc代码  

1. *** RowSrcId: 1 HASH JOIN STATISTICS (INITIALIZATION) ***  
2. Join Type: INNER join  
3. Original hash-area size: 3064559  
4. Memory for slot table: 2826240  
5. Calculated overhead for partitions and row/slot managers: 238319  
6. Hash-join fanout: 8  
7. Number of partitions: 8  
8. Number of slots: 23  
9. Multiblock IO: 15  
10. Block size(KB): 8  
11. Cluster (slot) size(KB): 120  
12. Minimum number of bytes per block: 8160  
13. Bit vector memory allocation(KB): 128  
14. Per partition bit vector length(KB): 16  
15. Maximum possible row length: 1708  
16. Estimated build size (KB): 0  
17. Estimated Build Row Length (includes overhead): 408  
18. # Immutable Flags:  
19.   Not BUFFER(execution) output of the join for PQ  
20.   Evaluate Left Input Row Vector  
21.   Evaluate Right Input Row Vector  
22. # Mutable Flags:  
23.   IO sync  
24. kxhfSetPhase: phase=BUILD  
25. kxhfAddChunk: add chunk 0 (sz=32) to slot table  
26. kxhfAddChunk: chunk 0 (lbs=0x2b4b26b47b20, slotTab=0x2b4b26b47ce8) successfuly added  
27. kxhfSetPhase: phase=PROBE_1  
28. qerhjFetch: max build row length (mbl=390)  
29. *** RowSrcId: 1 END OF BUILD (PHASE 1) ***  
30.   Revised row length: 370  
31.   Revised build size: 9KB  
32. kxhfResize(enter): resize to 12 slots (numAlloc=7, max=23)  
33. kxhfResize(exit): resized to 12 slots (numAlloc=7, max=12)  
34.   Slot table resized: old=23 wanted=12 got=12 unload=0  
35. *** RowSrcId: 1 HASH JOIN RESIZE BUILD (PHASE 1) ***  
36. Total number of partitions: 8  
37. Number of partitions which could fit in memory: 8  
38. Number of partitions left in memory: 8  
39. Total number of slots in in-memory partitions: 7  
40. kxhfResize(enter): resize to 13 slots (numAlloc=7, max=12)  
41. kxhfResize(exit): resized to 13 slots (numAlloc=7, max=13)  
42.   set work area size to: 1753K (13 slots)  
43. *** RowSrcId: 1 HASH JOIN BUILD HASH TABLE (PHASE 1) ***  
44. Total number of partitions: 8  
45. Number of partitions left in memory: 8  
46. Total number of rows in in-memory partitions: 27  
47.    (used as preliminary number of buckets in hash table)  
48. Estimated max # of build rows that can fit in avail memory: 8190  
49. ### Partition Distribution ###  
50. Partition:0    rows:3          clusters:1      slots:1      kept=1  
51. Partition:1    rows:5          clusters:1      slots:1      kept=1  
52. Partition:2    rows:3          clusters:1      slots:1      kept=1  
53. Partition:3    rows:4          clusters:1      slots:1      kept=1  
54. Partition:4    rows:6          clusters:1      slots:1      kept=1  
55. Partition:5    rows:3          clusters:1      slots:1      kept=1  
56. Partition:6    rows:3          clusters:1      slots:1      kept=1  
57. Partition:7    rows:0          clusters:0      slots:0      kept=1  
58.   
59. Revised number of hash buckets (after flushing): 27  
60. Allocating new hash table.  
61.   
62. Requested size of hash table: 8  
63. Actual size of hash table: 8  
64. Number of buckets: 64  
65. Match bit vector allocated: FALSE  
66.   
67. Total number of rows (may have changed): 27  
68. Number of in-memory partitions (may have changed): 8  
69. Final number of hash buckets: 64  
70. Size (in bytes) of hash table: 512  
71. qerhjBuildHashTable(): done hash-table on partition=6, index=1 last_slot#=5 rows=3 total_rows=3  
72. qerhjBuildHashTable(): done hash-table on partition=5, index=2 last_slot#=6 rows=3 total_rows=6  
73. qerhjBuildHashTable(): done hash-table on partition=4, index=3 last_slot#=0 rows=6 total_rows=12  
74. qerhjBuildHashTable(): done hash-table on partition=3, index=4 last_slot#=3 rows=4 total_rows=16  
75. qerhjBuildHashTable(): done hash-table on partition=2, index=5 last_slot#=1 rows=3 total_rows=19  
76. qerhjBuildHashTable(): done hash-table on partition=1, index=6 last_slot#=4 rows=5 total_rows=24  
77. qerhjBuildHashTable(): done hash-table on partition=0, index=7 last_slot#=2 rows=3 total_rows=27  
78. kxhfIterate(end_iterate): numAlloc=7, maxSlots=13  
79.   
80. ### Hash table ###  
81. # NOTE: The calculated number of rows in non-empty buckets may be smaller  
82. #       than the true number.  
83. Number of buckets with   0 rows:         42  
84. Number of buckets with   1 rows:         18  
85. Number of buckets with   2 rows:          4  
86. Number of buckets with   3 rows:          0  
87. Number of buckets with   4 rows:          0  
88. Number of buckets with   5 rows:          0  
89. Number of buckets with   6 rows:          0  
90. Number of buckets with   7 rows:          0  
91. Number of buckets with   8 rows:          0  
92. Number of buckets with   9 rows:          0  
93. Number of buckets with between  10 and  19 rows:          0  
94. Number of buckets with between  20 and  29 rows:          0  
95. Number of buckets with between  30 and  39 rows:          0  
96. Number of buckets with between  40 and  49 rows:          0  
97. Number of buckets with between  50 and  59 rows:          0  
98. Number of buckets with between  60 and  69 rows:          0  
99. Number of buckets with between  70 and  79 rows:          0  
100. Number of buckets with between  80 and  89 rows:          0  
101. Number of buckets with between  90 and  99 rows:          0  
102. Number of buckets with 100 or more rows:          0  
103. ### Hash table overall statistics ###  
104. Total buckets: 64 Empty buckets: 42 Non-empty buckets: 22  
105. Total number of rows: 27  
106. Maximum number of rows in a bucket: 2  
107. Average number of rows in non-empty buckets: 1.227273  
108. *** 2012-10-31 10:37:15.443  
109. qerhjFetch: max probe row length (mpl=0)  
110. *** RowSrcId: 1, qerhjFreeSpace(): free hash-join memory  
111. kxhfRemoveChunk: remove chunk 0 from slot table  

附加：Alibaba DBA Team 关于Oracle hash join 的文档

当做hash join时，oracle会选择一个表作为驱动表，先根据过滤条件排除不必要的数据，然后将结果集做成hash表，放入进程的hash area，接着扫描第二张表，将行的键值做hash运算，到内存的hash表里面去探测，如果探测成功，就返回数据，否则这行就丢弃掉这个是最基本的解释，实际情况中，考虑到单个进程PGA的大小，oracle不会让进程任意的消耗OS内存，hash area是有一定限制的，所以在oracle中，hash也有三种模式：
optimal，onepass，multipass

optimal:当驱动结果集生成的hash表全部可以放入PGA的hash area时，称为optimal，大致过程如下：
1.先根据驱动表，得到驱动结果集
2.在hash area生成hash bulket，并将若干bulket分成一组，成为一个partition，还会生成一个bitmap的列表，每个bulket在上面占一位
3.对结果集的join键做hash运算，将数据分散到相应partition的bulket中，当运算完成后，如果键值唯一性较高的话，bulket里的数据会比较均匀，也有可能有的桶里面数据会是空的，这样bitmap上对应的标志位就是0，有数据的桶，标志位会是1
4.开始扫描第二张表，对jion键做hash运算，确定应该到某个partition的某个bulket去探测，探测之前，会看这个bulket的bitmap是否会1，如果为0，表示没数据，这行就直接丢弃掉
5.如果bitmap为1，则在桶内做精确匹配，判断OK后，返回数据

这个是最优的hash join，他的成本基本是两张表的full table scan，在加微量的hash运算

onepass
如果进程的pga很小，或者驱动表结果集很大，超过了hash area的大小，会怎么办？当然会用到临时表空间，此时oracle的处理方式稍微复杂点需奥注意上面提到的有个partition的概念，可以这么理解，数据是经过两次hash运算的，先确定你的partition，再确定你的bulket，假设hash area小于整个hash table，但至少大于一个partition的size，这个时候走的就是onepass
当我们生成好hash表后，状况是部分partition留在内存中，其他的partition留在磁盘临时表空间中，当然也有可能某个partition一半在内存，一半在磁盘，剩下的步骤大致如下：
1.扫描第二张表，对join键做hash运算，确定好对应的partition和bulket
2.查看bitmap，确定bulket是否有数据，没有则直接丢弃
3.如果有数据，并且这个partition是在内存中的，就进入对应的桶去精确匹配，能匹配上，就返回这行数据，否则丢弃
4.如果partition是在磁盘上的，则将这行数据放入磁盘中暂存起来，保存的形式也是partition，bulket的方式
5.当第二张表被扫描完后，剩下的是驱动表和探测表生成的一大堆partition，保留在磁盘上
6.由于两边的数据都按照相同的hash算法做了partition和bulket，现在只要成对的比较两边partition数据即可，并且在比较的时候，oracle也做了优化处理，没有严格的驱动与被驱动关系，他会在partition对中选较小的一个作为驱动来进行，直到磁盘上所有的partition对都join完

可以发现，相比optimal，他多出的成本是对于无法放入内存的partition，重新读取了一次，所以称为onepass，只要你的内存保证能装下一个partition，oracle都会腾挪空间，每个磁盘partition做到onepass

multipass
这是最复杂，最糟糕的hash join，此时hash area小到连一个partition也容纳不下，当扫描好驱动表后，可能只有半个partition留在hash area中，另半个加其他的partition全在磁盘上,剩下的步骤和onepass比价类似，不同的是针对partition的处理
由于驱动表只有半个partition在内存中，探测表对应的partition数据做探测时，如果匹配不上，这行还不能直接丢弃，需要继续保留到磁盘，和驱动表剩下的半个partition再做join，这里举例的是内存可以装下半个partition，如果装的更少的话，反复join的次数将更多，当发生multipass时，partition物理读的次数会显著增加