我们在做SQL查询的时候，经常会用到各种相关查询。对于不同的连接，效率还是不一样的。我们应该使用哪一个？虽然数据库可以做一些查询优化，但是理解其中的原理可以帮助我们直奔核心。让我们开始加入吧。我们分析了三种常见的join：Mergejoin、Hashjoin和NestedLoopJoin。在此之前，我们先介绍几个关键词：内在关系和外在关系。关系可以是：表索引先前操作的中间结果当您连接两个关系时，连接算法处理内部和外部关系的方式是不同的。外层关系是左数据集，内层关系是右数据集。比如AJOINB，此时A是外层关系，B是内层关系。而且一般AJOINB和BJOINA的用法不同。稍后我们假设外部关系有N个元素，内部关系有M个元素。然而，在实际的优化器中，可以从统计信息中得到准确的值。Nestedloopjoin嵌套关联是最简单的一种。过程大致是：遍历外层关系的每一行，然后找出内层关系的每一行是否匹配。伪代码写法如下：nested_loop_join(arrayouter,arrayinner)foreachrowainouterforeachrowbininnerif(match_join_condition(a,b))write_result_in_output(a,b)endifendforendfor因为两次重新遍历，所以复杂度为O(N*M)。对应磁盘I/O，在外层关系中，每N行需要从内层关系中循环读取M行数据。所以这个算法需要从磁盘读取N+N*M行数据。但是，如果内部关系小到可以放入内存，则只需要读取M+N次。虽然时间复杂度没有变化，但是这种方法在磁盘I/O上还是不错的。因此，可以用索引代替内在关系，对磁盘I/O也更有好处。HashjoinHashjoin比较复杂，但很多情况下也比loopnestedjoin便宜hashjoin的原理是：从内在关系中获取所有元素，并将哈希表保存到磁盘中在内存中创建一个哈希表读取一个1取外关系的所有元素（使用哈希表的哈希函数）计算每个元素的哈希值，找到与内关系关联的哈希桶，检查外关系的元素是否匹配哈希桶。在时间复杂度上，我们需要做一些假设来简化问题：内在关系分为X个哈希桶。哈希函数将数据的哈希值几乎均匀地分布在各个关系中，相当于说哈希桶的大小是一致的。.外关系的元素与哈希桶中的所有元素匹配，成本为哈希桶中元素的个数。时间复杂度为(M/X)*N+cost_to_create_hash_table(M)+cost_of_hash_function*N。如果哈希函数创建足够小的桶，则复杂度为O(M+N)。还有一个散列连接版本，它对内存更友好，但对磁盘I/O不太有利。情况如下：计算外关系和内关系的哈希表，将哈希表保存到磁盘，然后将两个关系的哈希桶一一比较（一个关系读入内存，另一个是逐行读取）MergejoinJOIN是唯一产生排序的连接算法。注意：这种简化的合并连接不区分内部表或外部表；两个表扮演相同的角色。但是实际的实现是不同的，例如在处理重复值时。（可选）有序连接操作：两个输入源均按连接键排序。Mergejoin操作：将排序后的输入源合并在一起。(1)排序我们已经提到归并排序了，这里归并排序是一个非常好的算法。有时数据集是排序的，例如：如果表是内部排序的，例如连接条件中的索引组织表如果连接条件中的关系是索引如果连接应用于排序查询的中间结果(2)Mergejoin这部分和我们说的mergesort中的merge操作很相似。唯一的区别是我们不从两个关系中选择所有元素，只选择相同的元素。一般原则是：在两个关系中，当比较当前元素（当前等号第一次出现）相同时，将两个元素都放入结果中，然后比较两个关系中的下一个元素different如果是，则去与最小元素的关系中寻找下一个元素，重复步骤1、2、3，直到其中一个关系的最后一个元素。这种方法很有效，因为两种关系都已排序，您不再需要“回头看”。该算法是简化版，不处理同一数据在两组数据中多次出现的情况。哪种连接算法最好？如果有最好的，就没必要弄那么多种类。由于需要考虑许多因素，因此不会有一个简单的答案，例如：可用内存大小：如果没有足够的内存，请与强大的散列连接说再见，至少是完全内存中的散列连接再见。两个数据集的大小：如果大表join小表，nestedloopjoin比hashjoin快，因为后者有创建hash的成本；如果两个表都非常大，那么嵌套循环连接循环连接的CPU成本非常高。是否有索引：有两个B+树索引，mergejoin似乎是比较明智??的选择。结果集是否需要排序：即使你使用的是无序数据集，你也可能希望使用更昂贵的mergejoin（带排序），因为最终结果是排序的，你可以将它与另一个结果组合set由合并连接连接（查询使用的ORDERBY/GROUPBY/DISTINCT等运算符也可能隐式或显式需要排序结果）。关系是否排序：此时Mergejoin是最好的选择。联接类型：是等值联接（例如tableA.col1=tableB.col2）还是内部联接？外连接？笛卡尔积？还是自己加入？有些连接在某些情况下不起作用。数据分布：如果join条件的数据是倾斜的（比如按姓氏join人，会有很多同姓的人），使用hashjoin会是一场灾难，因为hash函数会产生一个很分布不均的哈希桶。如果您希望连接操作使用多线程或多处理。【本文为专栏作家“侯书城”原创稿件，转载请通过作者微信公众号“Tomcat物语”获得授权】点此查看本作者更多好文
