SQL夯实基础(八):联接运算符算法归类

  今天主要介绍三个常用联接运算符算法:合并联接(Merge join),哈希联接(Hash Join)和嵌套循环联接(Nested Loop Join)。(mysql至8.0版本,都只支持Nested Loop Join,下一篇文章我会单独说下mysql对Nested Loop Join的使用)

一个关系可以是:

1 一个表

2 一个索引

3 上一个运算的中间结果(比如上一个联接运算的结果)

  当你联接两个关系时,联接算法对两个关系的处理是不同的。在本文剩余部分,我将假定:

外关系是左侧数据集(驱动表),内关系是右侧数据集(非驱动表、被驱动表)。

比如, A JOIN B 是 A 和 B 的联接,这里 A 是外关系,B 是内关系。多数情况下,A JOIN B 的成本跟 B JOIN A 的成本是不同的

在这一部分,我还将假定外关系有 N 个元素,内关系有 M 个元素。要记住,真实的优化器通过统计知道 N 和 M 的值

注:N 和 M 是关系的基数。【基数

驱动表与被驱动表

  这里我们叫他外关系和内关系(因为很多文章对这两个概念有不同的命名,很容易混乱):

  驱动表,即需要从驱动表中拿出来每条记录,去与被驱动表的所有记录进行匹配探测。

  理解驱动表和被驱动表的差异,最本质的问题,需要理解顺序读取和随机读取的差异,内存是适合随机读取的,但是硬盘就不是(固态随机读稍微好些,但是对比顺序读有差距),对于硬盘来说顺序读取的效率比较好。

1、驱动表,作为外层循环,若能只进行一次IO把所有数据拿出来最好,这就比较适合顺序读取,一次性批量的把数据读取出来,这里没考虑缓存等细节。

2、被驱动表,即里层循环,由于需要不断的拿外层循环传进来的每条记录去匹配,所以如果是适合随机读取的,那么效率就会比较高。如果表上有索引,实际上就意味着这个表是适合随机读取的。如果表的数据量较大,且没有索引,那么就不适合多次的随机读取,比较适合一次性的批量读取,就应该作为驱动表。

嵌套循环联接

嵌套循环联接是最简单的。

SQL夯实基础(八):联接运算符算法归类

道理如下:

1 针对外关系的每一行

2 查看内关系里的所有行来寻找匹配的行

下面是伪代码:

nested_loop_join(array outer, array inner)
for each row a in outer
for each row b in inner
if (match_join_condition(a,b))
write_result_in_output(a,b)
end if
end for
end for

由于这是个双迭代,时间复杂度是 O(N*M)

  在磁盘 I/O 方面, 针对 N 行外关系的每一行,内部循环需要从内关系读取 M 行。这个算法需要从磁盘读取 N+ N*M 行。但是,如果内关系足够小,你可以把它读入内存,那么就只剩下 M + N 次读取。这样修改之后,内关系必须是最小的,因为它有更大机会装入内存

在CPU成本方面没有什么区别,但是在磁盘 I/O 方面,最好的是每个关系只读取一次。

当然,内关系可以由索引代替,对磁盘 I/O 更有利

由于这个算法非常简单,下面这个版本在内关系太大无法装入内存时,对磁盘 I/O 更加有利。道理如下:

1 为了避免逐行读取两个关系,

2 你可以成簇读取,把(两个关系里读到的)两簇数据行保存在内存里,

3 比较两簇数据,保留匹配的,

4 然后从磁盘加载新的数据簇来继续比较

5 直到加载了所有数据。

可能的算法如下:

// improved version to reduce the disk I/O.

nested_loop_join_v2(file outer, file inner)

  for each bunch ba in outer

  // ba is now in memory

    for each bunch bb in inner

        // bb is now in memory

        for each row a in ba

          for each row b in bb

            if (match_join_condition(a,b))

              write_result_in_output(a,b)

            end if

          end for

       end for

    end for

   end for

使用这个版本,时间复杂度没有变化,但是磁盘访问降低了:

1 用前一个版本,算法需要 N + N*M 次访问(每次访问读取一行)。

2 用新版本,磁盘访问变为外关系的数据簇数量 + 外关系的数据簇数量 * 内关系的数据簇数量。

3 增加数据簇的尺寸,可以降低磁盘访问

哈希联接

哈希联接更复杂,不过在很多场合比嵌套循环联接成本低。

SQL夯实基础(八):联接运算符算法归类

哈希联接的道理是:

1) 读取内关系的所有元素

2) 在内存里建一个哈希表

3) 逐条读取外关系的所有元素

4) (用哈希表的哈希函数)计算每个元素的哈希值,来查找内关系里相关的哈希桶内

5) 是否与外关系的元素匹配。

  在时间复杂度方面我需要做些假设来简化问题:

1 内关系被划分成 X 个哈希桶

2 哈希函数几乎均匀地分布每个关系内数据的哈希值,就是说哈希桶大小一致。

3 外关系的元素与哈希桶内的所有元素的匹配,成本是哈希桶内元素的数量。

  时间复杂度是 (M/X) * N + 创建哈希表的成本(M) + 哈希函数的成本 * N。如果哈希函数创建了足够小规模的哈希桶,那么复杂度就是 O(M+N)。

  还有个哈希联接的版本,对内存有利但是对磁盘 I/O 不够有利。 这回是这样的:

1) 计算内关系和外关系双方的哈希表

2) 保存哈希表到磁盘

3) 然后逐个哈希桶比较(其中一个读入内存,另一个逐行读取)。

合并联接

合并联接是唯一产生排序的联接算法

注:这个简化的合并联接不区分内表或外表;两个表扮演同样的角色。但是真实的实现方式是不同的,比如当处理重复值时。

1.(可选)排序联接运算:两个输入源都按照联接关键字排序。

2.合并联接运算:排序后的输入源合并到一起。

  我们已经谈到过合并排序,在这里合并排序是个很好的算法(但是并非最好的,如果内存足够用的话,还是哈希联接更好)。

然而有时数据集已经排序了,比如:

1  如果表内部就是有序的,比如联接条件里一个索引组织表

2  如果关系是联接条件里的一个索引

3  如果联接应用在一个查询中已经排序的中间结果

  这部分与我们研究过的合并排序中的合并运算非常相似。不过这一次呢,我们不是从两个关系里挑选所有元素,而是只挑选相同的元素。道理如下:

1) 在两个关系中,比较当前元素(当前=头一次出现的第一个)

2) 如果相同,就把两个元素都放入结果,再比较两个关系里的下一个元素

3) 如果不同,就去带有最小元素的关系里找下一个元素(因为下一个元素可能会匹配)

4) 重复 1、2、3步骤直到其中一个关系的最后一个元素。

因为两个关系都是已排序的,你不需要『回头去找』,所以这个方法是有效的。

该算法是个简化版,因为它没有处理两个序列中相同数据出现多次的情况(即多重匹配)。真实版本『仅仅』针对本例就更加复杂,所以我才选择简化版。

1 如果两个关系都已经排序,时间复杂度是 O(N+M)

2 如果两个关系需要排序,时间复杂度是对两个关系排序的成本:O(N*Log(N) + M*Log(M))

哪个算法最好?

如果有最好的,就没必要弄那么多种类型了。这个问题很难,因为很多因素都要考虑,比如:

1 空闲内存:没有足够的内存的话就跟强大的哈希联接拜拜吧(至少是完全内存中哈希联接)。

2 两个数据集的大小。比如,如果一个大表联接一个很小的表,那么嵌套循环联接就比哈希联接快,因为后者有创建哈希的高昂成本;如果两个表都非常大,那么嵌套循环联接CPU成本就很高昂。

3 是否有索引:有两个 B+树索引的话,聪明的选择似乎是合并联接

4 结果是否需要排序:即使你用到的是未排序的数据集,你也可能想用成本较高的合并联接(带排序的),因为最终得到排序的结果后,你可以把它和另一个合并联接串起来(或者也许因为查询用 ORDER BY/GROUP BY/DISTINCT 等操作符隐式或显式地要求一个排序结果)。

5 关系是否已经排序:这时候合并联接是最好的候选项。

6 联接的类型:是等值联接(比如 tableA.col1 = tableB.col2 )? 还是内联接?外联接?笛卡尔乘积?或者自联接?有些联接在特定环境下是无法工作的。

7 数据的分布:如果联接条件的数据是倾斜的(比如根据姓氏来联接人,但是很多人同姓),用哈希联接将是个灾难,原因是哈希函数将产生分布极不均匀的哈希桶

8 如果你希望联接操作使用多线程或多进程。

上一篇:SVN环境搭建步骤


下一篇:RNN神经网络产生梯度消失和梯度爆炸的原因及解决方案