联接查问

联接查问是一种常见的数据库操作，即在两张表（或更多表）中进行行匹配的操作。个别称之为程度操作，这是因为对几张表进行联接操作所产生的后果集能够蕴含这几张表中所有的列。

CROSS JOIN

CROSS JOIN对两个表执行笛卡儿积，返回两个表中所有列的组合。若左表有m行数据，右表有n行数据，则CROSS JOIN将返回m*n行的表。

CROSS JOIN的一个用途是疾速生成反复测试数据，因为通过它能够很快地结构m*n*o行的数据。

CROSS JOIN的另一个用途是能够作为返回后果集的行号，例如：

SELECT emp_no, dept_no, @a:=@a+1 AS row_num FROM dept_emp, (SELECT @a:=0 ) t;
INNER JOIN

通过INNER JOIN用户能够依据一些过滤条件来匹配表之间的数据。在逻辑查问的前三个解决阶段中，INNER JOIN利用前两个阶段，即首先产生笛卡儿积的虚构表，再依照ON过滤条件来进行数据的匹配操作。

INNER关键字可省略。因为不会增加内部行，INNER JOIN中WHERE的过滤条件能够写在ON子句中。在MySQL数据库中，如果INNER JOIN后不跟ON子句，这时INNER JOIN等于CROSS JOIN。此外，如果ON子句中的列具备雷同的名称，能够应用USING子句来进行简化。

OUTER JOIN

通过OUTER JOIN用户能够依照一些过滤条件来匹配表之间的数据。与INNER JOIN不同的是，在通过OUTER JOIN增加的保留表中存在未找到的匹配数据。

NATURAL JOIN

ANSI SQL还反对NATURAL JOIN，即天然联接。NATURAL JOIN等同于INNTER JOIN与USING的组合，它隐含的作用是将两个表中具备雷同名称的列进行匹配。

NONEQUI JOIN

NONEQUI JOIN的联接条件蕴含“等于”运算符之外的运算符。例如，有一张部门经理表dept_manager，要生成表中所有两个不同经理的组合。这里先假如以后表中仅蕴含员工号A、B、C，执行CROSS JOIN后将生成上面九对：（A，A）、（A，B）、（A，C）、（B，A）、（B，B）、（B，C）、（C，A）、（C，B）、（C，C）。

显然，（A，A）、（B，B）和（C，C）蕴含雷同的员工号，不是无效的员工组合。而（A， B）、（B，A）又示意同样的组合。要解决这个问题，能够指定一个右边值小于左边值的联接条件，这样能够移除上述两种状况。该问题的解决方案为：

SELECT a.emp_no,b.emp_no FROM dept_manager a INNER JOIN dept_manager b ON a.emp_no < b.emp_no;

联接算法

联接算法是MySQL数据库用于解决联接的物理策略。旧版本的MySQL数据库仅反对Nested-Loops Join算法，自8.0.18版本开始反对Hash Join算法。

当联接的表上有索引时，Nested-Loops Join是十分高效的算法。依据B+树的个性，其联接的工夫复杂度为O（N），若没有索引，则可视为最坏的状况，工夫复杂度为O（N2）。MySQL数据库依据不同的应用场合，反对两种Nested-Loops Join算法，一种是Simple Nested-LoopsJoin（NLJ）算法，另一种是Block Nested-Loops Join（BNL）算法。

Simple Nested-Loops Join算法（简略嵌套循环算法）

Simple Nested-Loops Join从第一张表中每次读取一条记录，而后将记录与嵌套表中的记录进行比拟。

假如在两张表R和S上进行联接的列都不含有索引。这个算法的扫描次数为：Rn+Rn*Sn，扫描老本为O（Rn*Sn）。Rn和Sn别离代表R表和S表中别离含有的记录数。

对于联接的列含有索引的状况，内部表的每条记录不再须要扫描整张外部表，只须要扫描外部表上的索引即可失去联接的判断后果。如果外部表联接列的索引高度为SBH，那么上述算法的扫描次数为Rn+SBH*Rn，扫描老本为O（Rn）。而个别B+树的高度为3～4层，因而在有索引的状况下，Simple Nested-Loops Join算法的执行速度是比拟快的。

优化器在个别状况下总是抉择将联接列含有索引的表作为外部表。如果两张表R和S在联接的列上都有索引，并且索引的高度雷同，那么优化器会抉择将记录数起码的表作为内部表，这是因为外部表的扫描次数总是索引的高度，与记录的数量无关。

Block Nested-Loops Join算法（块嵌套循环算法）

Block Nested-Loops Join算法是针对没有索引的联接状况设计的，其应用Join Buffer（联接缓冲）来缩小外部循环读取表的次数。

例如，Block Nested-Loops Join算法先把对Outer Loop表（内部表）每次读取的10行记录（精确地说是10行须要进行联接的列）放入Join Buffer中，而后在Inner Loop表（外部表）中间接匹配这10行数据。因而，对Inner Loop表的扫描缩小了1/10。

MySQL数据库应用Join Buffer的准则如下：

  • 零碎变量join_buffer_size决定了Join Buffer的大小。
  • Join Buffer可被用于联接是ALL、index和range的类型。
  • 每次联接应用一个Join Buffer，因而多表的联接能够应用多个Join Buffer。
  • Join Buffer在联接产生之前进行调配，在SQL语句执行完后进行开释。
  • Join Buffer只存储须要进行查问操作的相干列数据，而不是整行的记录。

在MySQL 5.5以及之前的版本中，Join Buffer只能在INNER JOIN中应用，在OUTER JOIN中则不能应用，即Block Nested-Loops Join算法不反对OUTER JOIN。

Batched Key Access Join算法（批量键值拜访联接算法）

MySQL 5.6（MariaDB 5.3）开始反对BatchedKey Access Join算法（简称BKA），该算法的思维为联合索引和group这两种办法（SimpleNested-Loops Join和Block Nested-Loops Join只能应用一种）来进步search-for-match的操作，以此放慢联接的执行效率。咱们能够把这种算法了解为group-index-lookup（组索引查问）。

为什么应用group-index-lookup能进步search-for-match的操作呢？因为这样能够进步数据库整体资源的Cache命中率，从CPU Cache、PageCache到Disk的拜访，效率都变得更高。如果内部表扫描的是主键，那么表中的记录拜访都是比拟有序的，然而如果联接的列是非主键索引，那么对于表中记录的拜访可能就是十分离散的。因而对于非主键索引的联接，Batched Key Access Join算法将能极大进步SQL的执行效率。

为什么应用group-index-lookup能进步search-for-match的操作呢？因为这样能够进步数据库整体资源的Cache命中率，从CPU Cache、PageCache到Disk的拜访，效率都变得更高。如果内部表扫描的是主键，那么表中的记录拜访都是比拟有序的，然而如果联接的列是非主键索引，那么对于表中记录的拜访可能就是十分离散的。因而对于非主键索引的联接，Batched Key Access Join算法将能极大进步SQL的执行效率。

Batched Key Access Join算法的工作步骤如下：

  1. 将内部表中相干的列放入Join Buffer中。
  2. 批量地将Key（索引键值）发送到Multi-Range Read（MRR）接口。
  3. Multi-Range Read（MRR）通过收到的Key，依据其对应的ROWID进行排序，而后再进行数据的读取操作。
  4. 返回后果集给客户端。

举个例子，当初有这样一条SQL语句：

SELECT MAX(l_extendedprice) FROM orders, lineitem WHERE o_orderdate BETWEEN '1995-01-01' AND '1995-01-31' AND l_orderkey=o_orderkey;

在上述SQL语句中，lineitem的主键为（l_orderkey，l_linenumber）的联结索引，l_orderkey、o_orderdate和o_orderkey上都有索引。l_extendedprice是表lineitem中的列，不在索引l_orderkey中。因而当通过l_orderkey索引来进行search-for-match操作之后，还须要依据ROWID来查找l_extendedprice的值，而这个查找是离散的，故应用Batched Key Access Join算法能进步SQL语句执行的效率。

在MySQL 5.5下，数据库外部表的search-for-match操作抉择了PRIMARY这个索引，也就是主键索引，而没有应用曾经存在于列l_orderkey上的i_l_orderkey索引。产生这个后果的起因还是优化器认为利用辅助索引失去联接判断后，还要再次读取主键上的列l_ extendedprice，这是离散读取，因而要远远慢于间接的主键拜访，并且主键索引的最左列也是l_orderkey。

在MySQL 5.6下，能够应用下列语句启用BatchedKey Access Join算法。

SET optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

因为Batched Key Access Join算法的实质是通过Multi-Range Read接口将非主键索引对于记录的拜访，转化为依据ROWID排序的较为有序的记录获取，所以要想通过Batched Key Access Join算法来进步性能，岂但须要确保联接的列参加match的操作，还要有对非主键列的search操作。如果联接不波及针对主键进一步获取数据，外部表只参加联接判断，那么就不会启用Batched Key Access Join算法，因为没有必要去调用Multi-Range Read接口。

Batched Key Access Join算法从实质上来说还是Simple Nested-Loops Join算法，其产生的条件为外部表上有索引，并且该索引为非主键的，并且联接须要拜访外部表主键上的索引。这时Batched Key Access Join算法调用Multi-RangeRead接口，批量地进行索引键的匹配和主键索引上获取数据的操作，以此来进步联接的执行效率。

Classic Hash Join算法（经典哈希联接算法）

Batched Key Access Join算法尽管解决了一些问题，然而还存在一些问题。一方面，不是每个联接语句都是有索引的，对于没有索引的状况，MySQL数据库目前只能应用Block Nested-LoopsJoin算法。这样尽管缩小了外部表的扫描次数，然而没有缩小执行search-for-match的次数。另一方面，即便有索引，然而当失去的数据占据表中大部分时，间接应用主键索引扫描更有效率，应用Multi-Range Read反而显得没有什么必要。

对于上述的两方面问题，能够通过另外一种联接算法来解决，即Hash Join，是一种广泛应用于数据仓库和OLAP利用的经典联接算法。

Classic Hash Join算法同样应用Join Buffer，先将内部表中数据放入Join Buffer中，而后依据键值产生一张散列表，这是第一个阶段，称为build阶段。随后读取外部表中的一条记录，对其利用散列函数，将其和散列表中的数据进行比拟，这是第二个阶段，称为probe阶段。

如果将Hash查找利用于Simple Nested-LoopsJoin中，则执行打算的Extra列会显示BNLH。如果将Hash查找利用于Batched Key Access Join中，则执行打算的Extra列会显示BKAH。

假使Join Buffer可能齐全寄存下内部表的数据，那么Classic Hash Join算法只须要扫描一次外部表。反之，Classic Hash Join须要扫描屡次外部表。为了使Classic Hash Join更有效率，应该更好地布局Join Buffer的大小。

注：Hash Join只能利用于等值的联接操作中，因为已通过散列函数生成新的联接值，不能将Hash Join用于非等值的联接操作中。