前言
连贯（Join）是关系数据库重要个性，它和事务常被作为数据库与文件系统的两个重要区别项。程序员江湖始终流传着某某 baba 的神秘开发宝典，其中数据库局部有重要一条防止过多表的 Join，奈何 Join 个性切实是好用，宽广程序员们忽视着宝典的谆谆教诲，仍旧每天乐此不疲的应用这 Join 个性。那数据库有哪些连贯算法呢？它们的实现形式是怎么呢？它们之间又有什么区别呢？为什么须要这么多不同的连贯算法呢？如果你也好奇这些问题，那么请持续往下浏览，本文将逐个答复上述问题。
关联算法简介
关系型数据库次要有三种 Join 算法：Nested Loop Join，Hash Join、Merge Join，像 Oracle、SqlServer、DB2 这几位数据库中的老炮均反对三种 Join 形式；MySQL 长久以来只反对 NLJ 或其变种，直到 8.0.18 版本后才无限的反对 Hash Join。在「程序员必备的数据库常识：数据存储构造」一文中介绍了数据库几种常见的数据存储构造，存储引擎之上是计算引擎。以 MySQL 数据库为例，计算引擎层通常包含 SQL 接口、解析器、查问优化器、缓存等组件，数据库 Join 实现就在计算引擎的查问优化器中。
然而数据库具体抉择哪种连贯算法，是由自身决定的，次要依据以后的优化器模式、表大小、连贯列是否有索引和排序等因素决定。
多表连贯形式又分为：内连贯（等值连贯）、外连贯和穿插连贯，外连贯又分为：左外连贯、右外连贯和全外连贯。对于不同形式的连贯查问，应用雷同的 Join 算法也会有不同的老本产生，这和实现形式严密相干的。本文不波及同一个 Join 算法在不同连贯形式的状况。
Nested Loop Join
NLJ 是 MySQL 最重要的连贯形式，也是 MySQL 长期惟一反对的连贯形式，直到 8.0.18 版本 MySQL 才无限的反对 Hash Join。那什么是 NLJ 呢？从概念上讲，NLJ 相当于两个嵌套循环，用第一张表做 Outter Loop，第二张表做 Inner Loop，Outter Loop 的每一条记录跟 Inner Loop 的记录作比拟，最终符合条件的就将该数据记录。
能够用以下伪代码示意：
如果疏忽内存和 CPU 的工夫，它的老本是：
Cost(NLJ) = Read(M) + M * Read(N)（其中 M 和 N 示意须要读两个关联表中的数据行数）
NLJ 的算法比较简单，并且对 Join 的连贯条件没有特殊要求（Hash Join 通常只反对等值，Merge Join 个别不反对不等和 like），在有索引过滤性较好的 OLTP 场景下，它的查问效率很高。毛病也同样显著，因为它的老本是：Read(M) + M * Read(N)。在 OLAP 须要大表间 Join 场景下，它的查问效率变得比拟差。在 MySQL 中 NLJ 还有两个变种：Index Nested Loop Join（INLJ）、Block Nested Loop Join（BNLJ），本文不波及这方面的扩大，有趣味的同学能够深入研究。
Hash Join
Hash Join 是 Oracle、SQLServer、PostgreSQL 中重要的关联算法，当两个表关联时，抉择一张表依照 join 条件给的列构建 hash 表，而后将第二张表的每行记录去探测 hash 表中的数据，如果合乎连贯条件就输入该数据。前一张表咱们叫做 build 表，后一张表咱们的叫做 probe 表。为了缩小内存使用量，通常抉择小表作为 hash 表，大表作为 probe 表。
经典 Hash Join 次要有两个步骤：抉择 hash 表，扫描该表并创立 hash 表；将另一个作为 probe 表，扫描每一行数据，而后在 hash 表中找寻对应的满足条件的记录。疏忽内存和 CPU 工夫，它的老本是：
Cost(HJ) = Read(M) + Read(N)
Hash Join 须要把表放到内存中，如果内存不够怎么办？为了解决这种状况，又诞生一些 Hash Join 的变种，比方 Grace Hash Join。简略说是通过分区形式实现，依据关联字段将两个表的数据分区，而后对同一分区的数据再进行原生 Hash join 的 build 与 probe 过程，最初将所有分区的数据合并成最初的后果集。当然在理论中会更简单，比方在大数据量的状况下，有概率呈现不同数据的 HASH 值却是雷同的问题。
总的来说，Hash Join 是解决大表间 Join 的不错抉择。MySQL 在 8.0.18 前始终没有 Hash join 的实现，甚至在 5.5 以前只有最原始的 NLJ，5.5 后才有 NLJ 优化变种的 B（Block）NLJ。但 Oracle 早在 7.3 版本之后就引入了 Hash join 算法，在 OLAP 畛域中 Hash join 更是相对的标配，Greenplum 和 Spark SQL 就充分利用了它。然而它也有毛病，比方只能应用等值查问、须要更多的内存资源等。
Merge Join
Merge Join，精确地说它叫 Sort Merge Join，在合并关联查问时要先确保两个关联表是按关联字段雷同排序的。如果关联字段有可用的索引（配合汇集索引服用成果更佳）并且排序统一，则能够间接进行 Merge 操作，否则要先对关联表依照关联字段进行一次排序。排好序后，再从每个表取一条记录开始匹配，如果合乎关联条件，则放入后果集中；否则将关联字段值较小的记录摈弃，从这条记录对应的表中取下一条记录持续进行匹配，直到整个循环完结。因而它的老本是这样的：
COST(MJ) = Read(M) + Sort(M) + Read(N) + Sort(N)
显然，Merge Join 适宜在关联列上有索引的表，最好在关联列还有雷同的排序形式，在这种状况下它的关联查问效率是最高的。然而关联字段如果没有排序，那么它的排序阶段则比拟耗时。
总结
通过前文的剖析，咱们根本能够答复文章最结尾的几个问题了，更多信息能够看下表格。另外，除了上述常见的三种数据库 Join 形式外，还有 Hive 反对 Map Join 和 Reduce Join。
作者
司马辽太杰是 NineData 工程师。NineData 向企业和集体提供高效、平安的数据库 SQL 开发、数据库备份、数据复制 / 迁徙 / 集成、数据比照等性能，是一个 SaaS 服务开箱即用，能够疾速晋升企业 SQL 开发效率，保障企业数据安全。NineData 地址：https://www.ninedata.cloud/