第2步：决定fan-out数
(Number of Partitions) * C<= Favm *M
其中C为Cluster size，其值为DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT
Favm为hash area内存可以使用的百分比，一般为0.8左右
M为Hash_area_size的大小
第3步：读取部分小表S，采用内部hash函数(这里称为hash_fun_1)
将连接键值映射至某个分区，同时采用hash_fun_2函数对连接键值产生另外一个hash值
这个hash值用于创建hash table用，并且与连接键值存放在一起
第4步：对build input建立位图向量
第5步：如果内存中没有空间了，则将分区写至磁盘上
第6步：读取小表S的剩余部分，重复第三步，直至小表S全部读完
第7步：将分区按大小排序，选取几个分区建立hash table(这里选取分区的原则是使选取的数量最多)
第8步：根据前面用hash_fun_2函数计算好的hash值，建立hash table
第9步：读取表B，采用位图向量进行位图向量过滤
第10步：对通过过滤的数据采用hash_fun_1函数将数据映射到相应的分区中去，并计算hash_fun_2的hash值
第11步：如果所落的分区在内存中，则将前面通过hash_fun_2函数计算所得的hash值与内存中已存在的hash table做连接
将结果写致磁盘上。如果所落的分区不在内存中，则将相应的值与表S相应的分区放在一起
第12步：继续读取表B，重复第9步，直至表B读取完毕
第13步：读取相应的(Si,Bi)做hash连接。在这里会发生动态角色互换
第14步：如果分区过后，最小的分区也比内存大，则发生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
根据上述的步骤描述，我们可以看出：
Cost(HJ)=Cost(HJ1)+Cost(HJ2)
其中Cost(HJ1)的成本就是扫描S,B表，并将无法放在内存上的部分写回磁盘，对应前面第2步至第12步
Cost(HJ2)即为做nested-loop hash join的成本，对应前面的第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需要循环的次数：n=(S/F)/M
一般情况下，如果n大于10的话，hash join的性能将大大下降
从n的计算公式可以看出，n与Fan-out成反比例，提高fan-out，可以降低n
当hash_area_size是固定时，可以降低cluster size来提高fan-out
从这里我们可以看出，提高hash_multiblock_io_count参数的值并不一定提高hash join的性能
㈤ Hash Join的过程
一次完整的hash join如下：
1 计算小表的分区（bucket）数--Hash分桶
决定hash join的一个重要因素是小表的分区（bucket）数
这个数字由hash_area_size、hash_multiblock_io_count和db_block_size参数共同决定
Oracle会保留hash area的20%来存储分区的头信息、hash位图信息和hash表
因此，这个数字的计算公式是：
Bucket数=0.8*hash_area_size/(hash_multiblock_io_count*db_block_size)
2 Hash计算
读取小表数据（简称为R），并对每一条数据根据hash算法进行计算
Oracle采用两种hash算法进行计算，计算出能达到最快速度的hash值（第一hash值和第二hash值）
而关于这些分区的全部hash值（第一hash值）就成为hash表
3 存放数据到hash内存中
将经过hash算法计算的数据，根据各个bucket的hash值（第一hash值）分别放入相应的bucket中
第二hash值就存放在各条记录中
4 创建hash位图
与此同时，也创建了一个关于这两个hash值映射关系的hash位图
5 超出内存大小部分被移到磁盘
如果hash area被占满，那最大一个分区就会被写到磁盘（临时表空间）上去
任何需要写入到磁盘分区上的记录都会导致磁盘分区被更新
这样的话，就会严重影响性能，因此一定要尽量避免这种情况
2-5一直持续到整个表的数据读取完毕
6 对分区排序
为了能充分利用内存，尽量存储更多的分区，Oracle会按照各个分区的大小将他们在内存中排序
7 读取大表数据，进行hash匹配
接下来就开始读取大表（简称S）中的数据
按顺序每读取一条记录，计算它的hash值，并检查是否与内存中的分区的hash值一致
如果是，返回join数据
如果内存中的分区没有符合的，就将S中的数据写入到一个新的分区中，这个分区也采用与计算R一样的算法计算出hash值
也就是说这些S中的数据产生的新的分区数应该和R的分区集的分区数一样。这些新的分区被存储在磁盘（临时表空间）上
8 完全大表全部数据的读取
一直按照7进行，直到大表中的所有数据的读取完毕
9 处理没有join的数据
这个时候就产生了一大堆join好的数据和从R和S中计算存储在磁盘上的分区
10 二次hash计算
从R和S的分区集中抽取出最小的一个分区，使用第二种hash函数计算出并在内存中创建hash表
采用第二种hash函数的原因是为了使数据分布性更好
11 二次hash匹配
在从另一个数据源（与hash在内存的那个分区所属数据源不同的）中读取分区数据，与内存中的新hash表进行匹配。返回join数据
12 完成全部hash join
继续按照9-11处理剩余分区，直到全部处理完毕
㈥ Hash Join的模式
Oracle中，Hash Join也有三种模式：optimal，one-pass，multi-pass
⑴ optimal
当驱动结果集生成的hash表全部可以放入PGA的hash area时，称为optimal，大致过程如下：
① 先根据驱动表，得到驱动结果集
② 在hash area生成hash bulket，并将若干bulket分成一组，成为一个partition，还会生成一个bitmap的列表，每个bulke