Chinaunix首页 | 论坛 | 博客
  • 博客访问: 653685
  • 博文数量: 94
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2939
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-30 13:00
个人简介

About me:optimistic,passionate and harmonious. Focus on oracle programming,peformance tuning,db design, j2ee,Linux/AIX,web2.0 tech,etc

文章分类

全部博文(94)

文章存档

2020年(57)

2014年(3)

2013年(32)

分类: Oracle

2020-06-18 16:21:00

接PART7:http://chinaunix.net/uid-7655508-id-5834675.html

2.7 HASH碰撞问题

  HASH JOIN是专门用来做大数据处理的高效算法,并且只能用于等值连接条件,针对表build tablehash table)和probe table构建HASH运算,查找满足条件的结果集。

  一般格式如下:

HASH JOIN

  build table

  probe table

  
这里的build table应该选择通过过滤条件过滤后,结果集尺寸较小的表(size不是rows),然后按照连接条件进行HASH函数运算,把需要的列和HASH函数运算结果存储到hash bucket中,hash bucket自身是链表结构。同样,对于probe table也需要进行hash函数运算,并根据运算结果到build tablehash bucket中去查询,查到满足,查不到丢弃。当然,ORACLE HASH JOIN内部构造还是很复杂的,具体可以参考Jonathan LewisCBO原理书。

  
HASH查找天生存在的问题:
  
一旦build table的连接条件列选择性不好(也就是重复值特别多),那么某些hash bucket上可能存储大量数据,由于hash bucket自身是链表结构,那么当查询这些hash bucket时,效率会急剧下降,此问题就是HASH运算的经典问题Hash CollisionHASH碰撞)

下面用一个小例子来分析下hash碰撞:



  其中a61w多条记录,b7w多条记录,此SQL结果返回8w多条记录,从执行计划来看,做HASH JOIN运算没有什么问题,但是实际此SQL执行10多分钟都没有执行完,效率非常低下,CPU使用率突增,远远大于访问两个表的时间。

  如果你了解HASH JOIN,这时候,你应当考虑是不是遇到hash collision了,如果很多bucket上存储大量数据,那么对于这样的hash bucket里的数据查找那就类似于nested loops了,必然效率大减。如下进一步分析:


  查找一下大于重复数据大于3000条的值,果然有很多,当然剩下数据也有很多比较大,探测HASH JOIN,可以使用EVENT 10104

  可以看到存储100+bucket61个,而且最多的一个bucket中存储了3782条,也就是和我们查询出来的一致。还是回到原始SQL

  ORACLE为什么选择substr(b.object_name,1,2)来构建HASH表呢,如果能将OR展开,原始SQL改为一个UNION ALL形式的,那么HASH表可以采用substr(b.object_name,1,2)b.object_id以及data_object_id来构建,那么必然唯一性很好,那应该可以解决hash collision问题,改写如下:

  现在的SQL执行时间从原来的10几分钟都没有结果,到4s执行完毕,再来看内部构建的HASH TABLE信息:

  最多的一个bucket中只存储6条数据,那肯定性能比前面好很多了。Hash碰撞的危害很大,实际应用中,可能比较复杂,如果遇到hash碰撞问题,最好的方式就是进行SQL重写,尽量从业务上分析,能不能增加其它选择性比较好的列进行JOIN

  回头来看看,既然我都知道改写成UNION ALL后,就采用2个组合列构建比较好的HASH表,那么ORACLE为什么不这样做呢?很简单,我这里只是举例刻意这么做的而已,用以说明HASH碰撞的问题,对于这种简单SQL,有选择性更好的列,收集下统计信息,ORACLE就可以将的SQL进行OR展开了。





阅读(3518) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~