数据库常见的join算法

大标 2022年3月9日18:44:48
评论
29
摘要

mysql支持的join算法• Nested Loop Join• Index Nested-Loop Join• Block Nested-Loop JoinIndex Nested-Loop Join 和 Block Nested-Loop Join是在Nested-Loop Join基础上做了优化。Nested Loop JoinNested-Loop Join的思想就是通过双层循环比较数据

mysql支持的join算法
• Nested Loop Join
• Index Nested-Loop Join
• Block Nested-Loop Join

Index Nested-Loop Join 和 Block Nested-Loop Join是在Nested-Loop Join基础上做了优化。

Nested Loop Join

Nested-Loop Join的思想就是通过双层循环比较数据来获得结果; 其中左表为外循环,右表为内循环,左表为驱动表。其实现逻辑简单粗暴,可以理解为两层for循环,小表在外环,大表在内环,数据比较的次数 = 小表记录数 * 大表记录数。
//select * from t1 inner join t2 on t1.a= t2.a;

List<结果> lists = new ArrayList<>();
for(t2 t2 : t2){ //外层循环
for(t1 t1 : t1){ //内循环
if(t2.a().equals(t1.a())){ //条件匹配
//存放结果到结果集
结果 = t1的字段 + t2的字段
lists.add(结果集);
}
}
}
索引嵌套循环连接 Index Nested-Loop Join

Index Nested-Loop Join

优化思路:内表为大表,可在join字段上建立索引,减少内表数据的扫描次数。

执行流程:

0.前置条件:外表 t2 已在连接用的 a 字段以建立索引;

1.从外表 t1 中读取一行数据 R;

2.使用 R 中的a 字段和内表 t2 的 a 字段进行索引关联查找;

3.根据索引到的记录取出表 t2 中满足条件的行,跟 R 组成一行,作为结果集的一部分;

4.重复执行步骤 1 到 3,直到表 t1 循环结束。

可见,通过索引的建立,避免了对大表进行全表扫描,加快了查询速度。

缓存块嵌套循环连接 Block Nested-Loop Join

Block Nested-Loop Join

优化思路:通过一次性缓存多条数据,减少外层表的循环次数。

t1为小表时的执行流程:

1.把t1 表查询的字段数据整个读入线程内存 join_buffer 中;

2.扫描表 t2,把表 t2 中的每一行取出来,跟 join_buffer 中的 数据做对比,满足 join 条件的,作为结果集的一部分返回。

Block Nested-Loop Join2

t1为大表时的执行流程:

1.扫描表 t1,顺序读取一定长度的数据行放入 join_buffer 中;

2.扫描表 t2,把 t2 中的每一行取出来,跟 join_buffer 中的数据做对比,满足 join 条件的,作为结果集的一部分返回;

3.清空 join_buffer;

4.顺序读取 t1表下一批次数据放入 join_buffer 中,重复步骤2

Oracle的join算法

• Nested Loop Join,嵌套循环

• Hash Join,将两个表中较小的一个在内存中构造一个 Hash 表(对JoinKey),扫描另一个表

• Sort Merge Join,将两个表排序,然后再进行join
DB2和SQL Server也使用这三种方式join算法。

Hash Join
Hash Join的使用场景:

• 适合于小表与大表连接、返回大型结果集的连接

• 只能用于等值连接,且只能在CBO优化器模式下
在inner/left/right join,以及union/group by等 都会使用hash join进行操作。

实现原理:

 

Hash Join

Hash Join中的小表称之为hash表,大表称为探查表,以小表作为驱动表。

• 两个输入:
– build input(也叫做outer input),小表
– probe input(也叫做inner input),大表

• 两个阶段:
– Build(构造)阶段,处理build input
– Probe(探测)阶段,探测probe input

build 阶段,主要是构造哈希表(hash table):
• 在inner/left/right join等操作中,表关联字段作为hash key
• 在group by操作中,group by的字段作为hash key;
• 在union或其它去重操作中,hash key包括所有的select字段。

一个hash值对应到hash table中的hash buckets。多个hash buckets可以使用链表数据结构连接起来。

Probe 阶段,从probe input中取出每一行记录,根据key值生成hash值,从build阶段构造的hash table中搜索对应的hash bucket。

• Grace Hash join

Hash Join

在内存足够大的情况下,建立的哈希表整体都放在内存中。
当小表数据量大到内存无法容纳时,会分别将build input和probe input切分成多个分区(partition),这样就将一个大的 Hash Join 切分成了多个独立且互相不影响的 Hash Join。

Hash Join的性能和资源消耗:

Hash join效率最高,因为只要对两张表扫描一次。

Hash join的主要资源消耗在于CPU。因其在内存中创建临时的hash表并进行hash计算时,都需要做大量的hash操作。

Merge Join

Merge join前需要确保两个关联表都是按照关联的字段进行排序;如果关联字段有索引并且排序一致,则可直接进行Merge Join操作。

通常用在数据没有索引但是已经排序的情况下,如果不需要排序操作,Merge Join本身的速度很快。

由于两表数据都要先做排序,再做merge,因此效率相对较差。

merge join的资源消耗主要在于磁盘I/O(扫描表或索引)。
Hive的join算法

• Reduce Join

hive-map-reduce

在Hive中也叫Common Join或Shuffle Join。

Shuffle阶段主要根据Key值hash分组,推送到不同的Reduce阶段。

• Map Join
如果一张大表一张小表,就可以将小表放到内存里,在map端做join
Map Join可以进行不等值的连接操作。

• SMB(Sort-Merge-Buket) Join
首先进行排序,继而合并,然后放到所对应的bucket中去。
bucket 就是按key进行hash,相同值的都放到一个bucket文件中去

SparkSQL的join算法
• shuffle hash join
• broadcast hash join
• sort merge join

前两者都属于hash join,只不过在hash join之前需要先shuffle还是先broadcast。

shuffler hash join 类似Grace Hash join,先根据join key进行分区,再hash join。

broadcast hash join 是将小表广播分发到大表所在的分区节点上,与分区记录进行hash join。

Sort-Merge Join:

sort-merge-join

shuffle阶段:将两张大表根据join key进行重新分区

sort阶段:对单个分区节点的两表数据,分别进行排序

merge阶段:对排好序的两张分区表数据执行join操作。

sort-merge-join

理论上数据经过shuffle之后是不需要sort的,可以直接merge。

sort merge join适合两张大表进行Join。

https://blog.csdn.net/m0_51698806/article/details/113757582

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
大标
  • 本文由 发表于 2022年3月9日18:44:48
  • 转载请务必保留本文链接:https://www.tanhuibiao.com/script/qita/1297.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: