昆明做网站推,平顶山车祸最新新闻事件,首页调用网站栏目id,wordpress 文章列表模板我们知道数据库里面两表关联主要有三种常见的关联方式#xff0c;即
nested loop joinhash joinmerge join
nested loop join在OLTP交易场景占比是最多的#xff0c;常用于关联字段为主键或索引字段的情况#xff0c;通过主键或索引以及loop的方式#xff0c;A表可以快速…我们知道数据库里面两表关联主要有三种常见的关联方式即
nested loop joinhash joinmerge join
nested loop join在OLTP交易场景占比是最多的常用于关联字段为主键或索引字段的情况通过主键或索引以及loop的方式A表可以快速查找到匹配的B表中的数据。
merge join又称为sort merge可想而知如果被关联的两个数据集正好是有序的那么采用这种方式是最高效的。
hash join则是把一个表通常为小表放在hash内存中进行匹配关联。
虽然知道这点简单的理解不过当别人问起来hash join具体怎么实现的时候发现并不能说出个一二看来还是应该我去熟悉一下底层的原理。参考网上关于hash join原理的一二之后也用本篇文章稍作记录作为一个学习的过程吧~
背景概念
所谓连接join是通过把多个表之间某列相等的元组提取出来组成新的表。两个表如果元数目过多逐个遍历开销就很大这里说的其实就是nested join哈希连接hash join就是一种提高连接效率的方法。
自Oracle 7.3以来就实现了hash join的技术MySQL则是在最新的8.0版本中实现了hash join。Hash join只能用于相等连接相对于nested loop joinhash join更适合处理大型结果集。Hash join不需要在驱动表上存在索引。
基本概述
Hash join算法的基本思想是根据小表记为S表建立一个可以存在于hash area内存中的hash table然后用大小记为B表来探测前面的hash table。
如果hash area内存不够大hash table就无法完全存放在hash area内存中。针对这种情况Oracle在连接键上利用一个hash函数将S表和B表分割成多个不相连的分区分别记为Si和Bi这个阶段叫做分区阶段然后各自相应的分区即Si和Bi再做Hash join这个阶段叫做join阶段。
如果分区后针对某个分区所建的hash table还是太大的话Oracle采用nested-loops hash join就是对部分Si建立hash table然后读取所有的Bi与所建的hash table做连接然后再对剩余的Si建立hash table再将所有的Bi与所建的hash table做连接直到所有Si都连接完。
Hash join算法有一个限制它假设两表在连接键上是均匀的不过实际情况是数据可能不均匀为了应对这个问题Oracle引进几种技术包括位图向量过滤、角色互换、柱状图等。
主要过程
从上面描述可以发现Hash join主要分为两个阶段建立阶段build phase和探测阶段probe phase
Build Phase
选择一个表通常是较小的那个表以减少建立哈希表的时间和空间。然后对其中每个元组上的连接属性采用哈希函数得到哈希值从而建立一个哈希表。
Probe Phase
对另一个表扫描它的每一行并计算连接属性的哈希值与Build Phase建立的哈希表对比如果落在同一个bucket的如果满足连接谓词则连接成新的表。
在内存足够大的情况下建立哈希表的过程时整个表都在内存中完成连接操作后才放在磁盘里面。但这个过程会带来很多的IO操作。
另一种哈希连接Grace hash join适用于内存不足的情况也就是前面提到的先分区再join的过程。
基本原理
参考https://www.cnblogs.com/qlee/archive/2011/04/11/2012572.html 使用一个例子来解释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第一步是判定小表S表是否能完全存放在hash area内存中如果能完全存放在内存中则在内存中建立hash table这是最简单的Hash join。
如果不能全部放在内存中则将S表进行分区分区的个数叫做fan-out。
Oracle采用内部一个hash函数作用于连接键上将S和B分割成多个分区假设产生10个分区如下表。 经过以上分区之后只需要相应的分区之间做join即可如果有分区为NULL的话则相应的分区Join即可忽略。
