共计 3219 个字符，预计需要花费 9 分钟才能阅读完成。
Join 是 SQL 中的罕用操作。在理论的数据库利用中，咱们常常须要从多个数据表中读取数据，这时咱们就能够应用 SQL 语句中的连贯（join），在两个或多个数据表中查问数据。
罕用 Join 算法
罕用的多表连贯算法次要有三类，别离是 Nested-Loop Join、Hash Join 和 Sort Merge Join。
Nested-Loop Join
Simple Nested-Loop Join 是最简略粗犷的 Join 算法，即通过双层循环比拟数据来取得后果，然而这种算法显然太过于粗鲁，如果每个表有 1 万条数据，那么对数据比拟的次数 = 1 万 * 1 万 = 1 亿次，很显然这种查问效率会十分慢。
在 Simple Nested-Loop Join 算法的根底上，延申出了 Index Nested-Loop Join 和 block Nested-Loop Join。前者通过缩小内层表数据的匹配次数优化查问效率；后者则是通过一次性缓存外层表的多条数据，以此来缩小内层表的扫表次数，从而达到晋升性能的目标。
Batched Key Access Join (BKA Join) 能够看作是一个性能优化版的 Index Nested-Loop Join。之所以称为 Batched，是因为它的实现应用了存储引擎提供的 MRR（Multi-Range Read）接口批量进行索引查问，并通过 PK 排序的办法，将随机索引回表转化为程序回表，肯定水平上减速了查索引的磁盘 IO。
Hash Join
两个表若是元组数目过多，一一遍历开销就很大，Hash Join（哈希连贯）是一种进步连贯效率的办法。哈希连贯次要分为两个阶段：建设阶段（build phase)和探测阶段（probe phase)。
在建设阶段，首先抉择一个表（个别状况下是较小的那个表，以缩小建设哈希表的工夫和空间），对其中每个元组上的连贯属性（join attribute)采纳哈希函数失去哈希值，从而建设一个哈希表。
在探测阶段，对另一个表，扫描它的每一行并计算连贯属性的哈希值，与 bulid phase 建设的哈希表比照，若有落在同一个 bucket 的，如果满足连贯谓词（predicate)则连接成新的表。
在内存足够大的状况下，建设哈希表的整个过程都在内存中实现，实现连贯操作后才放到磁盘里。因而这个过程也会带来很多的内存耗费。
Merge Join
Merge join 第一个步骤是确保两个关联表都是依照关联的字段进行排序。如果关联字段有可用的索引，并且排序统一，则能够间接进行 merge join 操作；否则须要先对关联的表依照关联字段进行一次排序（就是说在 merge join 前的两个输出上，可能都须要执行一个排序操作，再进行 merge join）。
两个表都依照关联字段排序好之后，merge join 操作从每个表取一条记录开始匹配，如果合乎关联条件，则放入后果集中；否则，将关联字段值较小的记录摈弃，从这条记录对应的表中取下一条记录持续进行匹配，直到整个循环完结。
Merge join 操作自身是十分快的，然而 merge join 前进行的排序可能会带来较大的性能损耗。
云溪数据库采纳的分布式 join 算子
云溪数据库是由浪潮开源的一款分布式 NewSQL 数据库，其采纳的 Join 算法包含 Merge join、Hash join 和 Lookup join。
Merge join
在两个表索引排序雷同的状况下，Merge joins 比 Hash joins 在计算和内存方面更高效，性能更好。Merge joins 要求在相等列上索引两个表，并且索引必须具备雷同的程序。如果不满足这些条件，云溪数据库才会转向较慢的 Hash joins。
Merge joins 在两个表的索引列上执行，如下所示：
云溪数据库查看相等列上的索引，并且它们的排序形式雷同（即 ASC 或 DESC）。
云溪数据库从每个表中取一行并进行比拟。
对于内连贯：
如果行相等，则云溪数据库返回行。
如果有多个匹配项，则返回匹配项的笛卡尔积。
如果行不相等，云溪数据库将抛弃较低值的行并应用下一行反复该过程，直到解决完所有行。
对于外连贯：
如果行相等，则云溪数据库返回行。
如果有多个匹配项，则返回匹配项的笛卡尔积。
如果行不相等，则云溪数据库 将返回 NULL 非匹配列，并应用下一行反复该过程，直到解决完所有行。
HashJoin
如果无奈应用一个 Merge join，云溪数据库将应用一个 Hash join。Hash joins 的计算量很大，须要额定的内存。
Hash joins 在两个表上执行，如下所示：
云溪数据库读取两个表并尝试抉择较小的表。
云溪数据库在较小的表上创立内存中的哈希表。如果哈希表太大，它将溢出到磁盘存储（这可能会影响性能）。
而后，云溪数据库扫描大表，查找哈希表中的每一行。
Lookup Join
对于一般的 join 算法，咱们留神到，没有必要对于 Outer 表中每行数据，都对 Inner 表进行一次全表扫操作，很多时候能够通过索引缩小数据读取的代价，这就用到了 Lookup join。
Lookup join 的适配前提是，在 join 的两个表中，Outer 表上的对应索引列存在索引。在执行过程中，首先读取小表的数据，而后去大表的索引中找到大略的 scan 范畴，拿大表的数据与小表的数据比拟，推动大表最初就能够得出后果。其执行过程简述如下：
从 Inner 表中取一批数据；
通过 join key 以及这一批数据结构在 outer 表的取值范畴，只读取对应范畴内的数据
对从 inner 表取出的每一行数据，都与 2 中取出的对应范畴内的每一条数据执行 join 操作并输入后果交给下层解决
反复步骤 1.2.3 直到遍历完 Outer 表为止。
Lookup Join 在执行时会一直变更状态，在不同阶段进入不同的状态做 join 解决：
阶段一： jrReadingInput 阶段
这个阶段读取小表的一块块数据，并对每一行数据开始构建对于大表的 index scan 的范畴(命名为 span)，构建实现后进入下一个阶段。当小表的这一块数据被读完后会回到这个状态持续读取，反复直到小表被读完。
阶段二： jrPerformingLookup 阶段
这个阶段通过阶段一失去的 span，将这个 span 中的数据取出放在一个容器中，让小表读出的一块数据每一行去这个容器中的每一行数据做 lookup 查找，执行 join 操作并将后果存储在容器中。当数据匹配实现后进入下一阶段。
阶段三： jrEmittingRows 阶段
从阶段二中的容器中取出 join 后果输入到下层。
分布式 join 计算和数据重散布
与传统数据库相比，分布式数据库的架构有很大的不同。以云溪数据库为例，数据库架构能够分为 SQL 层和存储层，SQL 层的计算节点须要计算数据所在的分片，而后从多个存储节点拉取所需的数据。
目前云溪数据库采纳两种方法实现分布式计算时表的关联：
重散布
将两表按 join 的列，按 hash 特色从新散布到每个节点上。执行分布式的 join 时，如果各个执行节点的数据没有依照 join 列的特色进行散布，这个时候就会将数据进行 hash 重散布，具体操作如下：
1)选取一个 hash 函数对该行数据进行 join 列的 hash 值计算
2)对参加计算的节点数取余
依据取余后果将特定行数据散发至对应计算节点进行 join 计算。
播送
将数据量较小的表进行播送。
相干的代价计算为：
M + N > min(M,N) * L：播送；
M + N <= min(M,N) * L：重散布。
M 和 N 别离为左右表的行数，L 为参加计算的节点个数。
总结
本文介绍了罕用的多表连贯 Join 算法，以及分布式数据库云溪数据库采纳的 Join 算法和分布式 Join 策略。对相干技术或产品有任何问题欢送提 issue 或在社区中留言探讨。同时欢送宽广对分布式数据库感兴趣的开发者独特参加云溪数据库我的项目的建设。
对于云溪数据库的更多详情能够查看：
官网代码仓库：https://gitee.com/ZNBase/zn-kvs
官网：http://www.znbase.com/
分割邮箱：haojingyi@inspur.com
