踩坑CBO，解决那些坑爹的SQL优化问题_PART8

接PART7：

2.7 HASH碰撞问题

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

  一般格式如下：

HASH JOIN

  build table

  probe table

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

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

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

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

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


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

  可以看到存储100行+的bucket有61个，而且最多的一个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展开了。