关系性数据库JOIN的实现方式

程序猿读历史 2021-05-31

4674

一、原理

几乎所有的关系性数据库Join的实现方法只有三种，分别是：

Nested Loops Join：嵌套循环（NLJ）。
Sort Merge Join：排序循环（SMJ）
Hash Join：哈希（HJ）

在当前版本下的DB2、SQL Server、PostgreSQL和Oracle都是使用这三种方式（早期oracle版本也只有NLJ一种Join实现方法），但是很抱歉MySql（不包括MariaDB版本）在5.7及之前的版本只有NLJ和NLJ的变种，一个好消息是MySql8.0之后部分场景下支持了Hash Join。

本文主要介绍三种Join的实现方式，在以后文章详细介绍MySql5.7的join实现方式，MySql8.0的Hash Join的实现方式及应用场景。

二、Nested Loops Join原理

2.1 实现方式

Nested loops Join的实现方式是从一张表中读取数据(叫做驱动表outer table，驱动表结果集一般较小)，然后访问另一张表（叫做被驱动表inner table,通常有索引，被驱动表较大）。驱动表中的每一行与inner表中的相应记录JOIN。类似一个嵌套的循环。

在嵌套循环中，内表被外表驱动，外表返回的每一行都要在内表中找到与它匹配的行，所以整个查询返回的结果不能太大（大于1000不适合），要把返回子集较小表的作为外表，而且在内表的连接字段上一定要有索引。

适用情况：适用于驱动表的记录集比较小（<1000）而且inner表需要有有效的访问方法（Index），并且索引选择性较好的时候.JOIN的顺序很重要，驱动表的记录集一定要小，返回结果集的响应时间是最快的

伪代码如下：

select t1.*,t2.* from t1 join t2 on t1.col1=t2.col2;  


//驱动表 
for i in (select * from t1) loop       
    //被驱动表
    for j in (select * from t2 where col2=i.col1)         
    loop         
        ...;       
    end loop;         
end loop;

2.2 应用场景

驱动表的记录集比较小（<1000）而且inner表需要有有效的访问方法（Index）。
一般用在连接的表中有索引，并且索引选择性较好。

三、Sort Merge Join原理

3.1 实现方式

Sort Merge Join首先要保证两个关联表都是按照关联的字段进行排序。

如果关联字段有可用的索引而且排序一致，则可以直接进行Sort Merge Join操作；否则需要先对关联的表按照关联字段进行一次排序，所以在Sort Merge Join前的，需要进行一个Sort操作，再进行Merge Join。

两个表都按照关联字段排序好之后，Merge Join操作从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。在多对多的关联表上执行Merge Join时，通常需要使用临时表进行操作。

伪代码如下：

select t1.*,t2.* from t1  join t2 on t1.id=t2.id;          


步骤如下：
//这里的id代表连接字段    
访问t1，并order by t1_1.id，     
访问t2，并order by t2_1.id         
//依次交替 比对 归并，但无所谓驱动 
join t1_1.id = t2_1.id，

因为merge join需要做更多的排序，所以消耗的资源更多。通常来讲，能够使用merge join的地方，hash join都可以发挥更好的性能,即散列连接的效果都比排序合并连接要好。然而如果已经被排过序，在执行排序合并连接时不需要再排序了，这时排序合并连接的性能会优于散列连接。

3.2 应用场景

行源已经是有序的。
连接字段没有索引。
硬件资源较为短缺。
Join的表结果集都较大。

四、Hash Join原理

4.1 实现方式

数据库优化器使用两个表中较小的表，利用连接键（JOIN KEY）在内存中建立hash表，将列数据存储到hash列表中，然后扫描较大的表，同样对JOIN KEY进行HASH后探测散列表，找出与散列表匹配的行。

所以Hash Join做了：Build（构造）Hash表阶段和Probe（探测） Hash表阶段。

Build（构造）阶段

主要构造哈希表(hash table)。在inner/left/right join等操作中，表的关联字段作为hash key；在group by操作中，group by的字段作为hash key；在union或其它一些去除重复记录的操作中，hash key包括所有的select字段。

Build操作从build input输入中取出每一行记录，将该行记录关联字段的值使用hash函数生成hash值，这个hash值对应到hash table中的hash buckets。如果一个hash值对应到多个hash buckts，则这些hash buckets使用链表数据结构连接起来。当整个build input的table处理完毕后，build input中的所有记录都被hash table中的hash buckets引用/关联了。

Probe（探测）阶段

从probe input输入中取出每一行记录，同样将该行记录关联字段的值，使用build阶段中相同的hash函数生成hash值，根据这个hash值，从build阶段构造的hash table中搜索对应的hash bucket。hash算法中为了解决冲突，hash bucket可能会链接到其它的hash bucket，probe动作会搜索整个冲突链上的hash bucket，以查找匹配的记录。

如果build input记录数非常大，构建的hash table无法在内存中容纳时，将build input和probe input切分成多个分区部分（partition），每个partition都包括一个独立的、成对匹配的build input和probe input，这样就将一个大的hash join切分成多个独立、互相不影响的hash join，每一个分区的hash join都能够在内存中完成。将切分后的partition文件保存在磁盘上，每次装载一个分区的build input和probe input到内存中，进行一次hash join。

伪代码：

select t1.*,t2.* from t1  join t2 on t1.id=t2.id;  


for each row  R1 in the build table loop
      构建哈希表，将较小的表载入Hash 表中
     insert R1 into the appropriate hash bucket
 end loop;
 
for each row R2 in the probe table loop
    for each row R1 in the corresponding hash bucket loop
        /Hash中有记录与大表能Join条件匹配到的数据
        if R1 joins with R2
            //将hash表和匹配到的数据做Join操作，然后将结果输出 
            return (R1, R2)
    end loop;
 end loops

4.2 应用场景

两个表都相对较大。
两表是不按顺序的。
硬件资源充足，尤其内存。

五、总结

数据库选择什么join方式都是优化器选择的，一般情况中sql并不指明使用什么方式，如果一定要使用某一种join方式，可以通过hint的方式。
在绝大多数情况下，hash join效率比其他join方式效率更。
当数据时有序时，SMJ效率最高。
当驱动表的数据量很小时,NLJ效率很高。

数据库

文章转载自程序猿读历史，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

关系性数据库JOIN的实现方式

评论