Heim  >  Artikel  >  Datenbank  >  深入理解Oracle表(5):三大表连接方式详解之Hash Join的定义,原

深入理解Oracle表(5):三大表连接方式详解之Hash Join的定义,原

WBOY
WBOYOriginal
2016-06-07 15:37:261315Durchsuche

Hash Join只能用于相等连接,且只能在CBO优化器模式下。相对于nested loop join,hash join更适合处理大型结果集 Hash Join的执行计划第1个是hash表(build table),第2个探查表(probe table),一般不叫内外表,nested loop才有内外表 Hash表也就是所谓的内表

 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的过程:

      深入理解Oracle表(5):三大表连接方式详解之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] view plaincopyprint?

  1. sys@ORCL> ed  
  2. Wrote file afiedt.buf  
  3.   
  4.   1  select a.ksppinm name,b.ksppstvl value,a.ksppdesc description  
  5.   2  from x$ksppi a,x$ksppcv b  
  6.   3  where a.indx = b.indx  
  7.   4* and a.ksppinm like '%hash_multiblock_io_count%'  
  8. sys@ORCL> /  
  9.   
  10. NAME                           VALUE DESCRIPTION  
  11. ------------------------------ ----- ------------------------------------------------------------  
  12. _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)
          这样产生十个分区,如下表:

          深入理解Oracle表(5):三大表连接方式详解之Hash Join的定义,原

          经过这样的分区之后,只需要相应的分区之间做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
                      其中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适合于小表与大表连接、返回大型结果集的连接.

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn