连接（Join）是关系数据库重要特性，它和事务常被作为数据库与文件系统的两个重要区别项。程序员江湖一直流传着某某baba的神秘开发宝典，其中数据库部分有重要一条避免过多表的Join，奈何Join特性实在是好用，广大程序员们无视着宝典的谆谆教诲，依旧每天乐此不疲的使用这Join特性。那数据库有哪些连接算法呢？它们的实现方式是怎样呢？它们之间又有什么区别呢？为什么需要这么多不同的连接算法呢？如果你也好奇这些问题，那么请继续往下阅读，本文将逐一回答上述问题。
程序员必备的数据库知识2：Join算法关联算法简介关系型数据库主要有三种Join算法：NestedLoopJoin，HashJoin、MergeJoin，像Oracle、SqlServer、DB2这几位数据库中的老炮均支持三种Join方式；MySQL长久以来只支持NLJ或其变种，直到8.0.18版本后才有限的支持HashJoin。在「程序员必备的数据库知识：数据存储结构」一文中介绍了数据库几种常见的数据存储结构，存储引擎之上是计算引擎。以MySQL数据库为例，计算引擎层通常包括SQL接口、解析器、查询优化器、缓存等组件，数据库Join实现就在计算引擎的查询优化器中。
以MySQL数据库为例，计算引擎层然而数据库具体选择哪种连接算法，是由本身决定的，主要根据当前的优化器模式、表大小、连接列是否有索引和排序等因素决定。
多表连接方式又分为：内连接（等值连接）、外连接和交叉连接，外连接又分为：左外连接、右外连接和全外连接。对于不同方式的连接查询，使用相同的Join算法也会有不同的成本产生，这和实现方式紧密相关的。本文不涉及同一个Join算法在不同连接方式的情况。
NestedLoopJoinNLJ是MySQL最重要的连接方式，也是MySQL长期唯一支持的连接方式，直到8.0.18版本MySQL才有限的支持HashJoin。那什么是NLJ呢？从概念上讲，NLJ相当于两个嵌套循环，用第一张表做OutterLoop，第二张表做InnerLoop，OutterLoop的每一条记录跟InnerLoop的记录作比较，最终符合条件的就将该数据记录。
可以用以下伪代码表示：
NLJ可以用伪代码表示如果忽略内存和CPU的时间，它的成本是：
Cost(NLJ)=Read(M)+M*Read(N)（其中M和N表示需要读两个关联表中的数据行数）
NLJ的算法比较简单，并且对Join的连接条件没有特殊要求（HashJoin通常只支持等值，MergeJoin一般不支持不等和like），在有索引过滤性较好的OLTP场景下，它的查询效率很高。缺点也同样明显，由于它的成本是：Read(M)+M*Read(N)。在OLAP需要大表间Join场景下，它的查询效率变得比较差。在MySQL中NLJ还有两个变种：IndexNestedLoopJoin（INLJ）、BlockNestedLoopJoin（BNLJ），本文不涉及这方面的扩展，有兴趣的同学可以深入研究。
HashJoinHashJoin是Oracle、SQLServer、PostgreSQL中重要的关联算法，当两个表关联时，选择一张表按照join条件给的列构建hash表，然后将第二张表的每行记录去探测hash表中的数据，如果符合连接条件就输出该数据。前一张表我们叫做build表，后一张表我们的叫做probe表。为了减少内存使用量，通常选择小表作为hash表，大表作为probe表。
HashJoin经典HashJoin主要有两个步骤：选择hash表，扫描该表并创建hash表；将另一个作为probe表，扫描每一行数据，然后在hash表中找寻对应的满足条件的记录。忽略内存和CPU时间，它的成本是：
Cost(HJ)=Read(M)+Read(N)HashJoin需要把表放到内存中，如果内存不够怎么办？为了处理这种情况，又诞生一些HashJoin的变种，比如GraceHashJoin。简单说是通过分区方式实现，根据关联字段将两个表的数据分区，然后对同一分区的数据再进行原生Hashjoin的build与probe过程，最后将所有分区的数据合并成最后的结果集。当然在实际中会更复杂，比如在大数据量的情况下，有概率出现不同数据的HASH值却是相同的问题。
总的来说，HashJoin是处理大表间Join的不错选择。MySQL在8.0.18前一直没有Hashjoin的实现，甚至在5.5以前只有最原始的NLJ，5.5后才有NLJ优化变种的B（Block）NLJ。但Oracle早在7.3版本之后就引入了Hashjoin算法，在OLAP领域中Hashjoin更是绝对的标配，Greenplum和SparkSQL就充分利用了它。但是它也有缺点，比如只能使用等值查询、需要更多的内存资源等。
MergeJoinMergeJoin，准确地说它叫SortMergeJoin，在合并关联查询时要先确保两个关联表是按关联字段相同排序的。如果关联字段有可用的索引（配合聚集索引服用效果更佳）并且排序一致，则可以直接进行Merge操作，否则要先对关联表按照关联字段进行一次排序。排好序后，再从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。因此它的成本是这样的：
COST(MJ)=Read(M)+Sort(M)+Read(N)+Sort(N)显然，MergeJoin适合在关联列上有索引的表，最好在关联列还有相同的排序方式，在这种情况下它的关联查询效率是最高的。但是关联字段如果没有排序，那么它的排序阶段则比较耗时。
总结通过前文的分析，我们基本可以回答文章最开头的几个问题了，更多信息可以看下表格。另外，除了上述常见的三种数据库Join方式外，还有Hive支持MapJoin和ReduceJoin。
常见Join算法的优势对比总览作者司马辽太杰是NineData工程师。NineData向企业和个人提供高效、安全的数据库SQL开发、数据库备份、数据复制/迁移/集成、数据对比等功能，是一个SaaS服务开箱即用，可以快速提升企业SQL开发效率，保障企业数据安全。NineData