你的位置:首页 > 数据库

[数据库]Oracle 哈希连接原理


《基于Oracle的sql优化》里关于哈希连接的原理介绍如下:

哈希连接(HASH JOIN)是一种两个表在做表连接时主要依靠哈希运算来得到连接结果集的表连接方法。

在Oracle 7.3之前,Oracle数据库中的常用表连接方法就只有排序合并连接和嵌套循环连接这两种,但这两种表连接方法都有其明显缺陷。对于排序合并连接,如果两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集很大且需要排序的话,则这种情况下的排序合并连接的执行效率一定是很差的;而对于嵌套循环连接,如果驱动表所对应的驱动结果集的记录数很大,即便在被驱动表的连接列上存在索引,此时使用嵌套循环连接的执行效率也同样会很差。

为了解决排序合并连接和嵌套循环连接在上述情形下执行效率不高的问题,同时也为了给优化器提供一种新的选择,Oracle在Oracle 7.3中引入了哈希连接。从理论上来说,哈希连接的执行效率会比排序合并连接和嵌套循环连接的执行效率要高,当然,实际情况并不总是这样。

在Oracle 10g及其以后的Oracle数据库版本中,优化器(实际上是CBO,因为哈希连接仅适用于CBO)在解析目标SQL时是否考虑哈希连接是受限于隐含参数_HASH_JOIN_ENABLED,而在Oracle10g以前的Oracle数据库版本中,CBO在解析目标SQL时是否考虑哈希连接是受限于参数HASH_JOIN_ENABLED。

_HASH_JOIN_ENABLED的默认值是TRUE,表示允许CBO在解析目标SQL时考虑哈希连接。当然,即使你将该参数的值改成了FALSE,我们使用USE_HASH Hint依然可以让CBO在解析目标SQL时考虑哈希连接,这说明USE_HASH Hint的优先级高于参数_HASH_JOIN_ENABLED。

    

如果两个表(这里将它们分别命名为表T1和表T2)在做表连接时使用的是哈希连接,则Oracle在做哈希连接时会依次顺序执行如下步骤:

1、  首先Oracle会根据参数HASH_AREA_SIZE、DB_BLOCK_SIZE和_HASH_MULTIBLOCK_IO_COUNT的值来决定Hash Partition的数量(Hash Partition是一个逻辑上的概念,所有Hash Partition的集合就被称之为Hash Table,即一个Hash Table是由多个Hash Partition所组成,而一个Hash Partition又是由多个Hash Bucket所组成);

2、  表T1和T2在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集会被Oracle选为哈希连接的驱动结果集,这里我们假设T1所对应的结果集的数据量相对较小,我们记为S;T2所对应的结果集的数据量相对较大,我们记为B;显然这里S是驱动结果集,B是被驱动结果集;

3、  接着Oracle会遍历S,读取S中的每一条记录,并对S中的每一条记录按照该记录在表T1中的连接列做哈希运算,这个哈希运算会使用两个内置哈希函数,这两个哈希函数会同时对该连接列计算哈希值,我们把这两个内置哈希函数分别记为hash_func_1和hash_func_2,它们所计算出来的哈希值分别记为hash_value_1和hash_value_2;

4、  然后Oracle会按照hash_value_1的值把相应的S中的对应记录存储在不同Hash Partition的不同Hash Bucket里,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值。注意,存储在Hash Bucket里的记录并不是目标表的完整行记录,而是只需要存储位于目标SQL中的跟目标表相关的查询列和连接列就足够了;我们把S所对应的每一个Hash Partition记为Si;

5、  在构建Si的同时,Oracle会构建一个位图(BITMAP),这个位图用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0

6、  如果S的数据量很大,那么在构建S所对应的Hash Table时,就可能会出现PGA的工作区(WORK AREA)被填满的情况,这时候Oracle会把工作区中现有的Hash Partition中包含记录数最多的Hash Partition写到磁盘上(TEMP表空间);接着Oracle会继续构建S所对应的Hash Table,在继续构建的过程中,如果工作区又满了,则Oracle会继续重复上述挑选包含记录数最多的Hash Partition并写回到磁盘上的动作;如果要构建的记录所对应的Hash Partition已经事先被Oracle写回到了磁盘上,则此时Oracle就会去磁盘上更新该Hash Partition,即会把该条记录和hash_value_2直接加到这个已经位于磁盘上的Hash Partition的相应Hash Bucket中;注意,极端情况下可能会出现只有某个Hash Partition的部分记录还在内存中,该Hash Partition的剩余部分和余下的所有Hash Partition都已经被写回到磁盘上

7、  上述构建S所对应的Hash Table的过程会一直持续下去,直到遍历完S中的所有记录为止;

8、  接着,Oracle会对所有的Si按照它们所包含的记录数来排序,然后Oracle会把这些已经排好序的Hash Partition按顺序依次、并且尽可能的全部放到内存中(PGA的工作区),当然,如果实在放不下的话,放不下的那部分Hash Partition还是会位于磁盘上。我认为这个按照Si的记录数来排序的动作不是必须要做的,因为这个排序动作的根本目的就是为了尽可能多的把那些记录数较小的Hash Partition保留在内存中,而将那些已经被写回到磁盘上、记录数较大且现有内存已经放不下的Hash Partition保留在磁盘上,显然,如果所有的Si本来就都在内存中,也没发生过将Si写回到磁盘的操作,那这里根本就不需要排序了

9、     至此Oracle已经处理完S,现在可以来开始处理B了;

10、 Oracle会遍历B,读取B中的每一条记录,并对B中的每一条记录按照该记录在表T2中的连接列做哈希运算,这个哈希运算和步骤3中的哈希运算是一模一样的,即这个哈希运算还是会用步骤3中的hash_func_1和hash_func_2,并且也会计算出两个哈希值hash_value_1和hash_value_2;接着Oracle会按照该记录所对应的哈希值hash_value_1去Si里找匹配的Hash Bucket;如果能找到匹配的Hash Bucket,则Oracle还会遍历该Hash Bucket中的每一条记录,并会校验存储于该Hash Bucket中的每一条记录的连接列,看是否是真的匹配(即这里要校验S和B中的匹配记录所对应的连接列是否真的相等,因为对于Hash运算而言,不同的值经过哈希运算后的结果可能是一样的),如果是真的匹配,则上述hash_value_1所对应B中的记录的位于目标SQL中的查询列和该Hash Bucket中的匹配记录便会组合起来,一起作为满足目标SQL连接条件的记录返回;如果找不到匹配的Hash Bucket,则Oracle就会去访问步骤5中构建的位图,如果位图显示该Hash Bucket在Si中对应的记录数大于0,则说明该Hash Bucket虽然不在内存中,但它已经被写回到了磁盘上,则此时Oracle就会按照上述hash_value_1的值把相应B中的对应记录也以Hash Partition的方式写回到磁盘上,同时和该记录存储在一起的还有该记录用hash_func_2计算出来的hash_value_2的值;如果位图显示该Hash Bucket在Si中对应的记录数等于0,则Oracle就不用把上述hash_value_1所对应B中的记录写回到磁盘上了,因为这条记录必然不满足目标SQL的连接条件;这个根据位图来决定是否将上述hash_value_1所对应B中的记录写回到磁盘的动作就是所谓的"位图过滤"我们把B所对应的每一个Hash Partition记为Bj

11、 上述去Si中查找匹配Hash Bucket和构建Bj的过程会一直持续下去,直到遍历完B中的所有记录为止;

12、 至此Oracle已经处理完所有位于内存中的Si和对应的Bj,现在只剩下位于磁盘上的Si和Bj还未处理;

13、 因为在构建Si和Bj时用的是同样的哈希函数hash_func_1和hash_func_2,所以Oracle在处理位于磁盘上的Si和Bj的时候可以放心的配对处理,即只有对应Hash Partition Number值相同的Si和Bj才可能会产生满足连接条件的记录;这里我们用Sn和Bn来表示位于磁盘上且对应Hash Partition Number值相同的Si和Bj

14、 对于每一对儿Sn和Bn,它们之中记录数较少的会被当作驱动结果集,然后Oracle会用这个驱动结果集的Hash Bucket里记录的hash_value_2来构建新的Hash Table,另外一个记录数较大的会被当作被驱动结果集,然后Oracle会用这个被驱动结果集的Hash Bucket里记录的hash_value_2去上述构建的新Hash Table中找匹配记录;注意,对每一对儿Sn和Bn而言,Oracle始终会选择它们中记录数较少的来作为驱动结果集,所以每一对儿Sn和Bn的驱动结果集都可能会发生变化,这就是所谓的"动态角色互换"

15、 步骤14中如果存在匹配记录,则该匹配记录也会作为满足目标SQL连接条件的记录返回;

16、 上述处理Sn和Bn的过程会一直持续下去,直到遍历完所有的Sn和Bn为止。

  

对于哈希连接的优缺点及适用场景,我们有如下总结:

     哈希连接不一定会排序,或者说大多数情况下都不需要排序;

     哈希连接的驱动表所对应的连接列的可选择性应尽可能的好,因为这个可选择性会影响对应Hash Bucket中的记录数,而Hash Bucket中的记录数又会直接影响从该Hash Bucket中查找匹配记录的效率;如果一个Hash Bucket里所包含的记录数过多,则可能会严重降低所对应哈希连接的执行效率,此时典型的表现就是该哈希连接执行了很长时间都没有结束,数据库所在database server上的CPU占用率很高,但目标SQL所消耗的逻辑读却很低,因为此时大部分时间都耗费在了遍历上述Hash Bucket里的所有记录上,而遍历Hash Bucket里记录这个动作是发生在PGA的工作区里,所以不耗费逻辑读

     哈希连接只适用于CBO、它也只能用于等值连接条件(即使是哈希反连接,Oracle实际上也是将其转换成了等价的等值连接)

     哈希连接很适合于一个小表和大表之间的表连接,特别是在小表的连接列的可选择性非常好的情况下,这时候哈希连接的执行时间就可以近似看作是和全表扫描那个大表所耗费的时间相当

     当两个表做哈希连接时,如果这两个表在施加了目标SQL中指定的谓词条件(如果有的话)后得到的结果集中数据量较小的那个结果集所对应的Hash Table能够完全被容纳在内存中时(PGA的工作区),则此时的哈希连接的执行效率会非常高。

 

对于以上的说明有两点不明:

  1. 对于第四步,计算的hash value存储在不同Hash Partition的不同Hash Bucket里,如果计算的值和以前重复,是不是会覆盖掉以前Hash Bucket里的记录呢 ?如果是这样,是不是也解释了hash连接非常适合小表连接列可选择性好的情况呢?如果不是,怎么理解可选择性好这句话呢?
  2. 位图向量里面记录的到底是什么呢?如果仅仅"用来标记Si所包含的每一个Hash Bucket是否有记录(即记录数是否大于0)",怎么"显示该Hash Bucket在Si中对应的记录数等于0"呢?
  3. Hash计算的两个函数作用是什么呢?

第一个疑问已在作者博客里询问,第三个问题作者在他博客下面回答了读者的疑问,"之所以用两个hash函数是为了使各个hash bucket里的值分布的更加均匀",另一个函数就是计算hash值了。

对于第二个问题,在另外一个作者的一篇博客中找到,"在将S表读入内存分区时,oracle即记录连接键的唯一值,构建成所谓的位图向量",可见位图向量记录的是小表S的唯一键值:

引自:http://blog.163.com/chunlei_cl/blog/static/81843020146253596868/

原文:

深入理解Oracle表:三大表连接方式详解之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以后就不再使用了

[sql] 

sys@ORCL> ed 
Wrote file afiedt.buf 
 
 1 select a.ksppinm name,b.ksppstvl value,a.ksppdesc description 
 2 from x$ksppi a,x$ksppcv b 
 3 where a.indx = b.indx 
 4* and a.ksppinm like '%hash_multiblock_io_count%' 
sys@ORCL> / 
 
NAME VALUE DESCRIPTION 
------------------------------ ----- ------------------------------------------------------------ 
_hash_multiblock_io_count 0 number of blocks hash join will read/write at once 


  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的计算公式可以看出,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的列表,每个bulket在上面占一位
 ③ 对结果集的join键做hash运算,将数据分散到相应partition的bulket中
  当运算完成后,如果键值唯一性较高的话,bulket里的数据会比较均匀,也有可能有的桶里面数据会是空的
  这样bitmap上对应的标志位就是0,有数据的桶,标志位会是1  
 ④ 开始扫描第二张表,对jion键做hash运算,确定应该到某个partition的某个bulket去探测
  探测之前,会看这个bulket的bitmap是否会1,如果为0,表示没数据,这行就直接丢弃掉
 ⑤ 如果bitmap为1,则在桶内做精确匹配,判断OK后,返回数据
  这个是最优的hash join,他的成本基本是两张表的full table scan,在加微量的hash运算
  博客开篇的那幅图描述的也就是这种情况

 ⑵ one-pass
  如果进程的pga很小,或者驱动表结果集很大,超过了hash area的大小,会怎么办?
  当然会用到临时表空间,此时oracle的处理方式稍微复杂点需奥注意上面提到的有个partition的概念
  可以这么理解,数据是经过两次hash运算的,先确定你的partition,再确定你的bulket
  假设hash area小于整个hash table,但至少大于一个partition的size,这个时候走的就是one-pass
  当我们生成好hash表后,状况是部分partition留在内存中,其他的partition留在磁盘临时表空间中
  当然也有可能某个partition一半在内存,一半在磁盘,剩下的步骤大致如下:
 ① 扫描第二张表,对join键做hash运算,确定好对应的partition和bulket
 ② 查看bitmap,确定bulket是否有数据,没有则直接丢弃
 ③ 如果有数据,并且这个partition是在内存中的,就进入对应的桶去精确匹配,能匹配上,就返回这行数据,否则丢弃
 ④ 如果partition是在磁盘上的,则将这行数据放入磁盘中暂存起来,保存的形式也是partition,bulket的方式
 ⑤ 当第二张表被扫描完后,剩下的是驱动表和探测表生成的一大堆partition,保留在磁盘上
 ⑥ 由于两边的数据都按照相同的hash算法做了partition和bulket,现在只要成对的比较两边partition数据即可
 并且在比较的时候,oracle也做了优化处理,没有严格的驱动与被驱动关系
 他会在partition对中选较小的一个作为驱动来进行,直到磁盘上所有的partition对都join完
 可以发现,相比optimal,他多出的成本是对于无法放入内存的partition,重新读取了一次,所以称为one-pass
 只要你的内存保证能装下一个partition,oracle都会腾挪空间,每个磁盘partition做到one-pass
 
 ⑶ multi-pass
  这是最复杂,最糟糕的hash join
  此时hash area小到连一个partition也容纳不下,当扫描好驱动表后
  可能只有半个partition留在hash area中,另半个加其他的partition全在磁盘上
  剩下的步骤和one-pass比价类似,不同的是针对partition的处理
  由于驱动表只有半个partition在内存中,探测表对应的partition数据做探测时
  如果匹配不上,这行还不能直接丢弃,需要继续保留到磁盘,和驱动表剩下的半个partition再做join
  这里举例的是内存可以装下半个partition,如果装的更少的话,反复join的次数将更多
  当发生multi-pass时,partition物理读的次数会显著增加

 ㈦ Hash Join的位图
 这个位图包含了每个hash分区是否有有值的信息。它记录了有数据的分区的hash值
 这个位图的最大作用就是,如果probe input中的数据没有与内存中的hash表匹配上
 先查看这个位图,以决定是否将没有匹配的数据写入磁盘
 那些不可能匹配到的数据(即位图上对应的分区没有数据)就不再写入磁盘
 
 ㈧ 小结
  ① 确认小表是驱动表
  ② 确认涉及到的表和连接键分析过了
  ③ 如果在连接键上数据不均匀的话,建议做柱状图
  ④ 如果可以,调大hash_area_size的大小或pga_aggregate_target的值
  ⑤ Hash Join适合于小表与大表连接、返回大型结果集的连接