深入理解Oracle表(5)：三大表连接方式详解之Hash Join的定义，原理，算法，成本，模式和位图

  Hash Join只能用于相等连接，且只能在CBO优化器模式下。相对于nested loop join，hash join更适合处理大型结果集
 Hash Join的执行计划第1个是hash表(build table)，第2个探查表(probe table)，一般不叫内外表，nested loop才有内外表
 Hash表也就是所谓的内表，探查表所谓的外表
 两者的执行计划形如：
 nested loop
 outer table   --驱动表
 inner table
 
 hash join
  build table  (inner table) --驱动表
  probe table   (outer  table) 
 先看一张图片，大致了解Hash Join的过程：
 
 下面详细了解一下Hash Join
 ㈠ Hash join概念
 
 Hash join算法的一个基本思想就是根据小的row sources(称作build input 也就是前文提到的build table，我们记较小的表为S，较大的表为B)
  建立一个可以存在于hash area内存中的hash table
  然后用大的row sources(称作probe input，也就是前文提到的probe table) 来探测前面所建的hash table
  如果hash area内存不够大，hash table就无法完全存放在hash area内存中
  针对这种情况，Oracle在连接键利用一个hash函数将build input和probe input分割成多个不相连的分区
  分别记作Si和Bi，这个阶段叫做分区阶段；然后各自相应的分区，即Si和Bi再做Hash join，这个阶段叫做join阶段 
  如果HASH表太大，无法一次构造在内存中，则分成若干个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，那么我们只需设定pga_aggregate_target
  但请记住，这是一个session级别的参数，有时，我们更倾向于把hash_area_size的大小设成驱动表的1.6倍左右
  驱动表仅仅用于nested loop join 和 hash join，但Hash join不需要在驱动表上存在索引，而nested loop join则迫切需求
  一两百万记录的表 join上  千万记录的表，hash join的通常表现非常好
  不过，多与少，大与小，很多时候很难量化，具体情况还得具体分析
  如果在分区后，针对某个分区所建的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原理
 
 考虑以下两个数据集：
  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内存中
  如果能完全存放在内存中，则在内存中建立hash table，这是最简单的hash join
  如果不能全部存放在内存中，则build input必须分区。分区的个数叫做fan-out
  Fan-out是由hash_area_size和cluster size来决定的。其中cluster size等于db_block_size * _hash_multiblock_io_count
  hash_multiblock_io_count是个隐藏参数,在9.0.1以后就不再使用了

  Oracle采用内部一个hash函数作用于连接键上，将S和B分割成多个分区
  在这里我们假设这个hash函数为求余函数，即Mod(join_column_value,10)
  这样产生十个分区，如下表:
 
  经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partition pairs） 
  如果有一个分区为NULL的话，则相应的分区join即可忽略
  在将S表读入内存分区时，oracle即记录连接键的唯一值，构建成所谓的位图向量
  它需要占hash area内存的5%左右。在这里即为{1,3,4,5,8,10}
  当对B表进行分区时，将每一个连接键上的值与位图向量相比较，如果不在其中，则将其记录丢弃
  在我们这个例子中，B表中以下数据将被丢弃{0,0,2,2,2,2,2,2,9,9,9,9,9}
  这个过程就是位图向量过滤
  当S1,B1做完连接后，接着对Si,Bi进行连接
  这里oracle将比较两个分区，选取小的那个做build input，就是动态角色互换
  这个动态角色互换发生在除第一对分区以外的分区上面

 ㈢ Hash Join算法
 
 第1步：判定小表是否能够全部存放在hash area内存中，如果可以，则做内存hash join。如果不行，转第二步
  第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的计算公式可