ITPub博客

首页 > Linux操作系统 > Linux操作系统 > Hash join算法原理

Hash join算法原理

原创 Linux操作系统 作者:star_guan2008 时间:2008-04-10 18:51:41 0 删除 编辑

自从oracke 7.3以来,oracle提供了一种新的join技术,就是hash joinHash Join只能用于相等连接,且只能在CBO优化器模式下。相对于nested loop joinhash join更适合处理大型结果集。Hash join不需要在驱动表上存在索引。

 

一.       Hash Join概述

Hash join算法的一个基本思想就是根据小的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 inputprobe input分割成多个不相连的分区(分别记作SiBi),这个阶段叫做分区阶段;然后各自相应的分区,即SiBi再做Hash join,这个阶段叫做join阶段。

如果在分区后,针对某个分区所建的hash table还是太大的话,oracle就采用nested-loops hash join。所谓的nested-loops hash join就是对部分Si建立hash table,然后读取所有的Bi与所建的hash table做连接,然后再对剩余的Si建立hash table,再将所有的Bi与所建的hash table做连接,直至所有的Si都连接完了。

Hash Join算法有一个限制,就是它是在假设两张表在连接键上是均匀的,也就是说每个分区拥有差不多的数据。但是实际当中数据都是不均匀的,为了很好地解决这个问题,oracle引进了几种技术,位图向量过滤、角色互换、柱状图,这些术语的具体意义会在后面详细介绍。

一般的线性表、树中,记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系,在结构中查找记录时需进行一系列和关键字的比较。这一类查找 方法建立在“比较”的基础上,查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录,因此必须在记录的存储位置和它的关键字之间建立一确定的 对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。因而查找时,只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等 的记录,则必定在f(K)的存储位置上,由此不需要进行比较便可直接取得所查记录。在此,称这个对应关系f为哈希函数,按这个思想建立的表为哈希表(又称 为杂凑法或散列法)。

select  /*+ USE_HASH(b a) */  a.jsjdm, a.rkje
  from sbdb.sb_jl_sbjkzb a, djdb.dj_jl_jbsj b
 where a.jsjdm=b.jsjdm
  and 
  b.kydjrq >= to_date('20080101', 'yyyymmdd')



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

请登录后发表评论 登录
全部评论

注册时间:2008-02-19

  • 博文量
    82
  • 访问量
    108893