ITPub博客

首页 > Linux操作系统 > Linux操作系统 > ORACLE Hash Join

ORACLE Hash Join

原创 Linux操作系统 作者:tthero00boo 时间:2013-07-08 00:24:55 0 删除 编辑
ORACLE Hash Join

引自:Oracle中hashjoin研究 2012年第27期 SCIENCE&TECHNOLOGYINFORMATION
http://hwhuang.iteye.com/blog/1479076
http://www.360doc.com/content/11/0625/17/2660674_129507672.shtml

tom大师视频,hj.swf :http://asktom.oracle.com/pls/apex/f?p=100:8:0::NO

1. hash join原理概述

哈希连接是一种基于equi-join的技术。Oracle是从7.3版本开始引入哈希连接,来替代sort-merge和nested-loopjoin方式,目的是为了oracle提高效率。当哈希连接时,将大量消耗CPU(在内存中创建临时的hash表,并进行hash计算)资源,反观mergejoin,其主要消耗盘IO(扫描表或索引)资源上。hashjoin在并行系统中对CPU的消耗非常明显。所以在系统CPU资源紧张时,最好的办法是限制使用hash join

引入哈希连接,主要目的是为了解决嵌套循环连接中大量随机读取的问题,同时又要解决排序合并连接中排序代价过大的问题。在不需要排序的情况下,哈希函数就能够把连接对象集中在一起。可以哈希函数并不直接负责连接任务,而是负责把将要连接的对象提前集中在特定的位置。将具有相同哈希值的数据行集中存储在相同的空间上,该空间被称之为“分区”。一般把必须要进行连接的两个分区称之为为“分区对”。

哈希连接过程
当在内存中哈希表构建完成后,进行下面的处理。哈希连接过程是,首先进行扫描第二个大表;当大表不能完全cache到可用内存的时候,大表继续被分成很多分区;大表的第一个分区装入到cache内存;对大表第一个分区的数据进行扫描,并与哈希表进行比较,这时如果有匹配的纪录,添加到结果集里面;其它的分区处理同第一个分区操作步骤一样;所有的分区处理完后,ORACLE对产生的结果集进行归并、汇总,产生最终的结果。
内部机制
执行散列连接时会获得一个数据集,利用一个内部的散列函数作用于连接列上以产生散列键,我们可以将该数据集转换为一个存储器内单表散列簇(single-tablehashcluster)的等价形式(假设有足够的内存)。然后我们开始获取第二个表的数据,当读取每一行时,在连接列上应用同样的散列函数,并查看是否在存储器内散列簇中定位到一个匹配的行。

(a)限制条件(等值连接或notexists)
因为在连接列上使用了散列函数以使散列簇中的数据随机分布,因而只有当连接条件是等值条件的时候散列连接才能正常执行。notexists也是可以的,它是等值条件的反向使用而已。
(b)表命名
构建表(用它来“构建”存储器中的散列簇)。探查表(用它来“探查”存储器中的散列簇)。
(c)适用情况
散列连接适用于小结果集连接到大结果集(注意不是小表和大表,而是结果集)

生成“伪查询”
优化器执行散列连接,首先将sql分解为完全分离的两个部分
伪查询中的列是选取连接列和所有引用的列。
估算两个数据集的行数和行大小(选择依据)
行大小bytes是根据user_tab_columns的avg_col_len列得到的。这两个参数直接影响到数据集的大小进而会影响构建表的选择。优化器会选择较小的数据集作为构建表。需要注意的是,行大小并不是所有字段的长度和,而是伪查询中的字段长度和。其中伪查询涉及的字段除了最终显示的字段外,还包括连接的字段。这些字段都是需要被读取的,因此也要计算在内

当表连接中的小表能够完全cache到可用内存的时候,哈希连接的效果最佳。哈希连接的成本只是两个表从硬盘读入到内存的成本。但是,如果哈希表过大而不能全部cache到可用内存时,优化器将会把哈希表分成多个分区,再将分区逐一cache到内存中。当表的分区超过了可用内存时,分区的部分数据就会临时地写到磁盘上的临时表空间上

适用原则:
当连接的两个表是用等值连接并且表的数据量比较大时,优化器才可能采用哈希连接。
哈希连接适用于连接两个大的结果集或者一大一小两个结果集。哈希连接的优点在于返回所有其他记录,尤其当hashtable能够适合memory,其性能极其优越

哈希连接优缺点(对比其他连接方式):
(a)优点
在缺少有用的索引时,哈希连接比嵌套循环连接更加有效。哈希连接可能比嵌套循环连接快,因为处理内存中的哈希表比检索B树更加迅速。
哈希连接可能比排序合并连接更快,因为这种情况下,只有一张源表需要排序。在排序合并连接中,两张表的数据都需要先做排序,然后做MERGE操作,因此效率相对最差。
哈希连接的效率最高,因为只要对两张表扫描一次。在绝大多数情况下,哈希连接效率比其他JOIN方式效率更高。
(b)缺点(限制条件)
和排序合并连接、群集连接一样,哈希连接只能用于等价连接。和排序合并连接一样,哈希连接使用内存资源,并且当用于排序内存不足时,会增加临时表空间的IO(这将使这种连接方法速度变的极慢)。
哈希连接返回第一条结果会慢,因为一个数据源必须要hash到内存中或者内存和磁盘中。当请求快速返回记录集时,Oracle倾向于使用NL

--形象的来说
假设我们有两个数据集合A和B,当我们对两个数据集做hash join,我们首先挑选一个数据集,比如是A,把A转变成为内存中的一个hash table,这个hash table和我们前面介绍过的single hash cluster table是很类似的,只不过single hash cluster table是在磁盘上,hash join的hash table是放在内存里。在这里,我们使用的是oracle内部的hash函数,hash函数的hash key就是A和B做join的那个列。

然后我们开始从第二个结果集B里面获取数据,对于B里的每一条数据使用相同的hash函数找到对应的A里数据在hash table里面的位置,在这个位置上检查能不能找到匹配的数据。

在这里,我们把数据集A称为build table 构建表(也就是A被build到内存中建立hash table),数据集合B叫做probe table 探查表(也就是说我们用B去probe hash table)。

其实hash join就有点像outer table是普通表,inner table是一个single hash cluster table的nested loops,都是使用一张表上的数据,通过hash函数到另一个hash table里面寻找匹配的数据。不过不同的是hash join里面的hash table是放在用户使用的专有内存,即UGA里(10g以后hash join和sort使用的内存被分配到PGA里),而single hash cluster table最多只能cache到buffer cache里,而对buffer cache的过多访问会产生大量latch,这个问题在hash join里就不存在。

hash join会选择比较小的表做build table,这个小是看那个表上得到的结果集比较小,就把哪个表作为build table。
根据小的row sources (称作build input,我们记较小的表为S,较大的表为B)  建立一个可以存在于hash area内存中的hash table,然后用大的row sources(称作probe input) 来探测前面所建的hash table。如果hash area内存不够大,hash table就无法完全存放在hash area内存中。针对这种情况,Oracle在连接键利用一个hash函数将build input和probe input分割成多个不相连的分区(分别记作Si和Bi),这个阶段叫做分区阶段;然后各自相应的分区,即Si和Bi再做Hash join,这个阶段叫做join阶段。 

引用链接2中的例子
select
bu.build_vc,
pb.probe_vc,
pb.probe_padding
from
build_tab bu,
probe_tab pb
where
bu.id between 1 and 500
and pb.id = bu.id_probe
;
把这个SQL拆分成2部分:
select
bu.id
bu.build_vc,
bu.id_probe
from
build_tab bu
where
bu.id between 1 and 500
;
select
pb.probe_vc,
pb.probe_padding,
pb.id
from
probe_tab pb
;
oracle会根据这两个虚拟的查询的返回结果决定到底哪个表的返回结果集表较小,而这个结果集的大小则是 = 结果集的行数 * user_tab_columns.sum(avg_col_len)计算得出的。

查询user_tab_columns
SQL> select column_name, avg_col_len from user_tab_columns where table_name='PROBE_TAB';

COLUMN_NAME AVG_COL_LEN
-------------------- -----------
ID 5
N1 4
PROBE_VC 21
PROBE_PADDING 501

4 rows selected.

SQL> select column_name, avg_col_len from user_tab_columns where table_name='BUILD_TAB';

COLUMN_NAME AVG_COL_LEN
-------------------- -----------
ID 4
ID_PROBE 5
BUILD_VC 21
BUILD_PADDING 501

4 rows selected.

我们看到probe_tab的结果集是(5+21+521)*5000=2635000,
build_tab的结果集是(4+5+21)*500=15000,
所以把build_tab作为build table。

2. hash join工作模式
hash join有三种工作模式,分别是optimal模式,onepass模式和multipass模式

optimal:当驱动结果集生成的hash表全部可以放入PGA的hash area时,称为optimal,大致过程如下: 
1.先根据驱动表,得到驱动结果集 
2.在hash area生成hash bulket,(这里的hash bucket总是2的n次方,比如1024或4096),并将若干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物理读的次数会显著增加

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/28859270/viewspace-765698/,如需转载,请注明出处,否则将追究法律责任。

下一篇: Oracle中Hint随记
请登录后发表评论 登录
全部评论

注册时间:2013-06-30

  • 博文量
    31
  • 访问量
    142178