CirroData三种Join算法简介

2022-01-10 00:00:00 数据执行算法排序球员

SQL Join用于根据两个或多个表中的列之间的关系，从这些表中查询数据。常见的类型有SQL Inner Join、SQL Left Join、SQL Right Join、SQL Full Join 。那么，实现上述Join类型的算法都有哪些呢？本文重点介绍CirroData的nested loop join, sort-merge join，hash join三种Join算法。

Join场景举例

假设我们准备建立一个提供NBA比赛信息网站，用来提供对球队、球员、场馆、比赛等信息的查询，网站后台数据库中现有team和player两张表。Team表记录球队的信息，包括球队编号（key）、球队名称（name）、主场所在地（homefield）。Player表记录球员信息，包括球员编号（key）、姓名（name）、薪资（salary）、所属球队Id（teamId）。两张表数据信息如下。

现要查询薪资大于等于7200球员的球队名称、球员名称、球员薪资，SQL语句如下：

select team.name, player.name，player.salary

from player join team

on player.teamid = team.key and player.salary >= 7200

数据库中该语句大致执行流程如下：

该查询语句由上而下进行抽取、分为4个执行单元。先执行team-scan, player-scan两个执行单元，然后执行team-join-player单元，后是执行select-output单元。

team-scan表示将team表的数据表从硬盘读取到内存中来。
player-scan表示将player表的数据表从硬盘中读取到内存中来。
team-join-player会将内存中的team表和内存中的player表按照SQL中on连接条件进行JOIN匹配操作。
select-output会将team-join-player送来的结果按照select后要求的格式进行运算和输出。

三种Join算法介绍

为了便于描述算法、我们假设运行环境内存足够、不考虑分布式特殊处理。将team表和player表数据读取到内存以后，就可以开始join运算了。常见的Join算法有三种：nested loop join， sort-merge join， hash join。这三种join都可以等效的完成上面查询球员薪资的SQL语句的运算。

Nested loop join算法

Nested loop join算法简述：

两层for循环，依次取出player表的每行数据，和team表逐行比较。如果满足join的连接条件，就输出；如果不满足，本轮不做处理并取下一行进行比较。

Nested loop join算法伪代码：

Nested loop join的算法优点：

算法简单、同时他对于join的连接条件没有特殊要求（特殊要求参见后续hash算法）、对于左表，右表的数据没有特殊要求（特殊要求参见sort-merge join算法）。

Nested loop join的算法缺点：时间复杂度是O（N*M）(其中N和M是两个表中数据的行数）。如果表比较大的话，判断匹配时的比较次数会很多，所以执行会比较慢。

Sort-merge join算法

Sort-merge join算法简述：

Sort-merge join的算法是一种特殊的nested loop join算法。该算法前提条件是将参与join的两个表按照join key进行排序。

Sort-merge join算法执行步骤：

对team表和player表按照join key进行排序，排序字段分别为team.key和player.teamId。

将team表和player表排序完以后。我们执行如下步骤：

Step0:我们首先取出player表中teamId为0的行。如下记为player-team0，

接下来把player-team0当作一个表和team表做nestloop操作。然后将nestloop的结果输出即可。

Step1:然后我们继续取出player表中teamId为1的行，如下记为player-team1,接下来将player-team1当作一个表和team表做nested loop join操作。然后将nested loop的结果输出即可。

Stepn:同理，后提取player表中teamId=5的行，如下记为player-teamN，将player-teamN和team表做nested loop join。然后将nested loop join的结果输出即可。以上步骤执行完毕，sort-merge join也就执行完了。

上述操作是将player表切割成几个小表，然后和team整个表做nested loop join。这是一个特殊的nested loop join。因为player表和team表做过排序，我们可以对执行过程做优化。

Sort-merge join优化方法：

在step0步骤的nested loop的实现中，我们可以记住team表中team.key=1的位置。同时由于team表已经排序。当player-team0和team表的nested loop join操作执行到team.key=1的行时，我们可以肯定：team表的后续行都不会满足player.teamId=team.Key。所以我们可以提前结束这个Nested loop join的执行。因此，此处的player-team0和team做Nested loop join的时间复杂度不再是N*M。其时间复杂度是小于等于N*M的 (其中Nplayer-team0的行数，M为team表的行数）

同样我们在step1的执行过程中，可以记录team表team.key=2的位置。方便我们在step3的步骤实现中跳过team表的一些不必要的行的比较。依此类推,我们可以看到，由于player表和team表排序。计算过程中的每个nestloop的时间复杂度都降低了。

Sort-merge join算法的优点：

Sort-merge join算法，要求参与join的两张表是排序表。并且排序的列，是连接条件中包含的列。在有些情况下，sort-merge join的执行效率要比hash join要高（比如内存有限，team表又比较大，不能将team表中的数据一次性放入hash表中，需要反复建立hash表，这个操作就比较耗时。

对于事务型数据库，如果join的连接键上建有索引。Team-scan和player-scan执行模块获取排序数据比较方便，可以考虑使用sort-merge join。对于分析型数据库，可以在向team表，player表insert数据的时候，先按照join的键值排序，然后insert存储在数据库中。这样在join查询的时候可以考虑使用sort-merge join。

Sort-merge join算法的限制条件：

如果join的on连接条件仅仅包含“不等”（!=）或者like条件。通常不走sort-merge join。

Hash join算法

Hash join算法简述：

顾名思义，我们需要先建立一个hash表，本文中我们使用team表来建立hash表，然后扫描另外一张表player表、查找hash表，比较具有相同哈希码的元组的相等联接是否相等。

Hash join算法执行步骤：

1.建立team表的hash表

现在我们建立一个hash表（TeamHashTable)，根据hash(team.key)指示的桶号（bucketId），依次将指向team表中各行数据的指针ptrTeam，存入TeamHashTable相应的bucket（桶）中。

2.遍历player表、查找hash表

当指向Team表各行数据的指针都存储在TeamHashTable中以后。依次取出player表中的每行数据，根据hash(ptrPlayer->teamId)生成的hash值（bucketId，即桶号）到TeamHashTable找到对应bucket（桶），从中找到先前存储在其中的指向team表某行的指针ptrTeam。比较两者的等值连接条件，如果相等将两个指针指向的数据拼在一起就可以作为join的结果输出了。例如：Output.push_back(*ptrPlayer, *ptrTeam);

这是hash join算法的核心部分。针对我们上文中的SQL，我们画出hash join的计算流程示意图：

Hash join算法伪代码

Hash join算法的优点：

执行player.teamId = team.key的时间复杂度是O（1），所以hash join的执行效率会比较高。

Hash join算法的限制条件：

Join的on条件中必须有“等值连接条件“。

总结

为了便于介绍基本算法，文中并未考虑服务器的内存限制因素。本文简单介绍了CirroData数据库的nested loop join, sort-merge join，hash join三种算法。在SQL具体的执行过程中，选择哪种Join算法更优，通常由执行计划来决定。三种算法在各自领域性能指标优异。

来源：https://mp.weixin.qq.com/s/AlxLOn_nrz3W0sShSFoqJw

相关文章