MySQL Join 算法

MySQL中“关联(join)”一词所包含的意义比一般意义上理解的要更广泛。总的来说，MySQL认为任何一个查询都是一次“关联”——并不仅仅是一个查询需要到两个表匹配才叫关联，所以在MySQL中，每一个查询，每一个片段（包括子查询，甚至基于单表的SELECT）都可能是关联。

References:

https://dev.mysql.com/doc/refman/8.0/en/join.html MySQL JOIN Clause
https://dev.mysql.com/doc/refman/8.0/en/nested-loop-joins.html NLJ
https://dev.mysql.com/doc/refman/8.0/en/hash-joins.html MySQL Hash Join
https://dev.mysql.com/doc/refman/8.0/en/outer-join-optimization.html join 优化
https://mysqlserverteam.com/hash-join-in-mysql-8/ Hash Join原理
《高性能MySQL（第3版）》

MySQL在表之间执行联接使用嵌套循环算法或其变体。在8.0.18后新增了hash join。

嵌套循环联接（Nested-Loop Join, NLJ）

简单嵌套循环联接(NLJ)算法从循环中的第一个表中逐一读取记录，将每一条记录传递给处理联接中的下一个表的嵌套循环。有多少张表需要联接, 这个过程就重复多少次。

假设对三个表t1，t2和t3之间以如下类型联接：

Table   Join Type
t1      range
t2      ref
t3      ALL

如果使用简单NLJ算法，那么join的处理方式如下所示：

for each row in t1 matching range {
  for each row in t2 matching reference key {
    for each row in t3 {
      if row satisfies join conditions, send to client
    }
  }
}

由于NLJ算法从外循环一次次传递行到内循环中，它通常会多次读取内循环中处理的表。相信写代码的人都写过嵌套循环吧，如下图所示

块嵌套循环联接（Block Nested-Loop Join, BNL）

块嵌套循环（BNL）联接算法将外循环中读取行放在缓冲区来减少内循环中表必须被读取的次数。例如，如果将10条记录读入缓冲区，并将缓冲区传递给下一个内循环，那么内循环中读取的每条记录都可以与缓冲区中的所有10条记录进行比较。这就使内层循环的表必须被读取的次数减少了一个数量级。

在MySQL 8.0.18之前，这种算法适用于不能使用索引的等价联接（equi-joins）；在MySQL 8.0.18及以后的版本中，这种情况会采用哈希联接优化。从MySQL 8.0.20开始，MySQL不再使用块嵌套循环，在以前使用块嵌套循环的所有情况下都采用哈希联接（Hash Join）。

MySQL join buffer具有以下特征：

当联接的类型为ALL或index或range时可以使用join buffer。
永远不会给第一个非Constant Table分配join buffer，即使它的类型是ALL或index。
只有参与join的列存储在join buffer中，而不是整个行。
系统变量join_buffer_size决定了用于处理查询的每个缓冲区的大小。--调优
为每个可以缓冲的联接分配一个缓冲区，因此一个查询可以使用多个缓冲区来处理。
在执行联接（join）之前分配（allocate）缓冲区，并在查询完成后释放（free）缓冲区。

对于之前NLJ算法（无缓冲）的示例，使用缓冲将按如下方式进行联接：

for each row in t1 matching range {
  for each row in t2 matching reference key {
    store used columns from t1, t2 in join buffer
    if buffer is full {
      for each row in t3 {
        for each t1, t2 combination in join buffer {
          if row satisfies join conditions, send to client
        }
      }
      empty join buffer
    }
  }
}

if buffer is not empty {
  for each row in t3 {
    for each t1, t2 combination in join buffer {
      if row satisfies join conditions, send to client
    }
  }
}

如果S是join buffer中每个t1、t2组合的大小，C是buffer中组合的数量，那么表t3被扫描的次数是。

(S * C)/join_buffer_size + 1

t3扫描的次数随着join_buffer_size的增加而减少，直到join_buffer_size大到足以容纳所有的行组合时为止。继续增加则不会获得任何速度上的提升。

哈希联接（Hash Join）

从MySQL 8.0.18开始，MySQL对所有equi-join且联接条件没有索的查询都使用哈希联接，例如：

SELECT *
    FROM t1
    JOIN t2
        ON t1.c1=t2.c1;

和“块嵌套循环算法”相比，散列连接通常更快，并且不需要索引，所以正在用它取代“块嵌套循环算法”。从MySQL 8.0.20开始，取消了对块嵌套循环的支持，服务器在以前使用块嵌套循环的地方换成哈希连接。
简单介绍下Hash Join：

通常将Hash Join分为两个阶段。构建阶段（build phase）和探测阶段（probe phase）。
在构建阶段，从其中一个表输入（通常是两个中较小的一个）构建内存中的哈希表，服务器使用联接属性作为哈希表键。一旦所有行都存储在哈希表中，就完成了构建阶段。
在探测阶段，将第二个表的每一行计算联接键哈希，并检查它是否存在于在构建阶段创建的哈希表中。如果找到该哈希的匹配项，则它还需验证哈希表中的行与第二个表中的行之间的联接键是否真的匹配（由于存在哈希冲突）。

对于每个匹配项，将向客户端发送一个合并的行。最后，服务器仅扫描每个输入一次，使用恒定时间查找来查找两个输入之间的匹配行。如下图所示：

在刚才的例子中，假设三个表t1、t2和t3已经用以下语句创建。

CREATE TABLE t1 (c1 INT, c2 INT);
CREATE TABLE t2 (c1 INT, c2 INT);
CREATE TABLE t3 (c1 INT, c2 INT);

可以通过使用EXPLAIN看到正在使用hash join:

mysql> EXPLAIN
    -> SELECT * FROM t1
    ->     JOIN t2 ON t1.c1=t2.c1\G
*************************** 1. row ***************************
           id: 1
  select_type: SIMPLE
        table: t1
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: NULL
*************************** 2. row ***************************
           id: 1
  select_type: SIMPLE
        table: t2
   partitions: NULL
         type: ALL
possible_keys: NULL
          key: NULL
      key_len: NULL
          ref: NULL
         rows: 1
     filtered: 100.00
        Extra: Using where; Using join buffer (hash join)

（在MySQL 8.0.20之前，需要用FORMAT=TREE选项以查看是否使用了hash join。）

至此，三种物理Join方式，MySQL只差Merge Join了。
对于网上流传的一种优化：

用小表驱动大表
其实这些事MySQL优化器都做了工作，不用操心这些细节，除非偶尔有优化器不能正确工作的情况，那会才需要手动优化SQL, 而且现在还有了Hash Join。例如：

SELECT * FROM t1 LEFT JOIN t2 ON condition_1 WHERE condition_2 OR 0 = 1

优化器在准备过程中会看到0 = 1始终为false，这使得OR 0 = 1是多余的，会将其删除：

SELECT * FROM t1 LEFT JOIN t2 ON condition_1 where condition_2

现在，优化器可以将查询重写为内部联接

SELECT * FROM t1 JOIN t2 WHERE condition_1 AND condition_2

优化器会根据查询计划成本选择先使用表t2还是表t1。
需要关表join顺序的提示，可以使用optimizer hints; 也可以选择使用STRAIGHT_JOIN强制联接顺序, 但是STRAIGHT_JOIN可能会阻止索引的使用，因为它禁用了半连接的转换（semijoin transformations）。

添加新评论

文章目录

最近回复

分类

归档