三类关联算法

常见的关联算法有三大类，分别是嵌套循环（Nested Loop Join）、排序归并（SortMerge Join）和哈希（Hash Join）。

嵌套循环连接算法

所有的嵌套循环算法都由内外两个循环构成，分别从两张表中顺序取数据。其中，外层循

环表称为外表（Outer 表），内层循环表则称为内表（Inner 表）。因为这个算法的过程是

由遍历 Outer 表开始，所以 Outer 表也称为驱动表。在最终得到的结果集中，记录的排列

顺序与 Outer 表的记录顺序是一致的。

根据在处理环节上的不同，嵌套循环算法又可以细分为三种，分别是 Simple NestedLoop Join（SNLJ）、Block Nested-Loop Join（BNJ）和 Index Lookup Join（ILJ）。

Simple Nested Loop Join

每次为了匹配 Outer 表的一条记录，都要对 Inner 表做一次全表扫描操作。而全表扫描的磁盘I/O 开销很大，所以 SNLJ 的成本很高。 并且每次取outer都要做一次IO。

Block Nested-Loop Join

一次取多条记录去匹配，减少取数IO次数，与 SNLJ 相比，BNJ 虽然在时间复杂度都是 O(m*n)（m 和 n 分别是 Outer 表和Inner 表的记录行数），但磁盘 I/O 的开销却明显降低了，所以效果优于 SNLJ。

Index Lookup Join

匹配通过索引匹配而不需要全表查提高速度。

排序归并连接算法

1.第一阶段是排序，就是对 Outer 表和 Inner 表进行排序，排序的依据就是每条记录在连

接键上的数值。

2.第二阶段就是归并，因为两张表已经按照同样的顺序排列，所以 Outer 表和 Inner 表各

一次循环遍历就能完成比对工作了。

简单来说，SMJ 就是先要把两个数据集合变成两个数据序列，也就是有序的数据单元，然

后再做循环比对。这样算下来，它的计算成本是两次排序再加两次循环。你可能会觉得奇

怪，这成本是不是比 NLJ 还要高呀？

是的。所以选择 SMJ 是有前提的，而这个前提就是表的记录本身就是有序的，否则就不划

算了。我们知道，索引是天然有序的，如果表的连接键刚好是索引列，那么 SMJ 就是三种嵌套循环算法中成本最低的，它的时间复杂度只有 O(m+n)。

哈希连接算法

Simple Hash Join

1.建立阶段

选择一张表作为 Inner 表，对其中每条记录上的连接属性（Join Attribute）使用哈希函数

得到哈希值，从而建立一个哈希表。在计算逻辑允许的情况下，建立阶段选择数据量较小

的表作为 Inner 表，以减少生成哈希表的时间和空间开销。

2.探测阶段

另一个表作为 Outer 表，扫描它的每一行并计算连接属性的哈希值，与建立阶段生成的哈

希表进行对比。当然，哈希值相等不代表连接属性相等，还要再做一次判断，返回最终满

足条件的记录。

通过 Simple Hash Join 这个命名，我们就能知道它也是一个简单的算法。这里的简单是

说，它做了非常理想化的假设，也就是 Inner 表形成的哈希表小到能够放入内存中。可实

际上，即使对于单体数据库来说，这个哈希表也是有可能超过内存容量的。

Grace Hash Join

GHJ 算法与 SHJ 的不同之处在于，GHJ 正视了哈希表大于内存这个问题，将哈希表分块缓

存在磁盘上。