8.2.1.7 嵌套连接优化_MySQL 5.7 参考手册

MySQL 8.0 参考手册 / 第8章优化 / 8.2 优化SQL语句 / 8.2.1 优化 SELECT 语句 / 8.2.1.7 嵌套连接优化

8.2.1.7 嵌套连接优化

表达连接的语法允许嵌套连接。以下讨论涉及第 13.2.9.2 节“JOIN 子句”中描述的连接语法。

与 SQL 标准相比，语法得到了table_factor扩展。后者只接受table_reference，而不是一对括号内的列表。table_reference如果我们将项目列表中的每个逗号视为等同于内部联接，则这是一个保守的扩展。例如：

SELECT * FROM t1 LEFT JOIN (t2, t3, t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

相当于：

SELECT * FROM t1 LEFT JOIN (t2 CROSS JOIN t3 CROSS JOIN t4)
                 ON (t2.a=t1.a AND t3.b=t1.b AND t4.c=t1.c)

在 MySQL 中，CROSS JOIN语法上等同于INNER JOIN; 他们可以互相替代。在标准 SQL 中，它们是不等价的。 INNER JOIN与 ON从句一起使用；CROSS JOIN否则使用。

通常，在仅包含内部连接操作的连接表达式中可以忽略括号。考虑这个连接表达式：

t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)
   ON t1.a=t2.a

删除括号并向左分组操作后，该连接表达式转换为以下表达式：

(t1 LEFT JOIN t2 ON t1.a=t2.a) LEFT JOIN t3
    ON t2.b=t3.b OR t2.b IS NULL

然而，这两个表达并不等同。要查看这一点，假设表t1、 t2和t3具有以下状态：

表t1包含行 (1)，(2)
表t2包含行 (1,101)
表t3包含行 (101)

在这种情况下，第一个表达式返回包含行(1,1,101,101), 的结果集(2,NULL,NULL,NULL)，而第二个表达式返回行(1,1,101,101), (2,NULL,NULL,101)：

mysql> SELECT *
       FROM t1
            LEFT JOIN
            (t2 LEFT JOIN t3 ON t2.b=t3.b OR t2.b IS NULL)
            ON t1.a=t2.a;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL | NULL |
+------+------+------+------+

mysql> SELECT *
       FROM (t1 LEFT JOIN t2 ON t1.a=t2.a)
            LEFT JOIN t3
            ON t2.b=t3.b OR t2.b IS NULL;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL |  101 |
+------+------+------+------+

在以下示例中，外连接操作与内连接操作一起使用：

t1 LEFT JOIN (t2, t3) ON t1.a=t2.a

该表达式不能转换为以下表达式：

t1 LEFT JOIN t2 ON t1.a=t2.a, t3

对于给定的表状态，两个表达式返回不同的行集：

mysql> SELECT *
       FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL | NULL |
+------+------+------+------+

mysql> SELECT *
       FROM t1 LEFT JOIN t2 ON t1.a=t2.a, t3;
+------+------+------+------+
| a    | a    | b    | b    |
+------+------+------+------+
|    1 |    1 |  101 |  101 |
|    2 | NULL | NULL |  101 |
+------+------+------+------+

因此，如果我们在带有外连接运算符的连接表达式中省略括号，我们可能会更改原始表达式的结果集。

更确切地说，我们不能忽略左外连接操作的右操作数和右连接操作的左操作数中的括号。也就是说，对于外连接操作的内表表达式，我们不能忽略括号。其他操作数（外表的操作数）的括号可以忽略。

以下表达式：

(t1,t2) LEFT JOIN t3 ON P(t2.b,t3.b)

对于任何表和属性和上的t1,t2,t3任何条件，都等同于此表达式： Pt2.bt3.b

t1, t2 LEFT JOIN t3 ON P(t2.b,t3.b)

只要连接表达式 ( ) 中连接操作的执行顺序joined_table不是从左到右，我们就会谈论嵌套连接。考虑以下查询：

SELECT * FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a
  WHERE t1.a > 1

SELECT * FROM t1 LEFT JOIN (t2, t3) ON t1.a=t2.a
  WHERE (t2.b=t3.b OR t2.b IS NULL) AND t1.a > 1

这些查询被认为包含这些嵌套连接：

t2 LEFT JOIN t3 ON t2.b=t3.b
t2, t3

在第一个查询中，嵌套连接是通过左连接操作形成的。在第二个查询中，它由内部连接操作组成。

在第一个查询中，括号可以省略：连接表达式的语法结构决定了连接操作的相同执行顺序。对于第二个查询，括号不能省略，尽管这里的连接表达式可以在没有它们的情况下被明确解释。在我们的扩展语法中，第二个查询的括号 in(t2, t3)是必需的，尽管理论上可以在没有它们的情况下解析查询：我们仍然会有明确的查询语法结构，因为LEFT JOIN和ON 扮演表达式左右分隔符的角色(t2,t3)。

前面的例子证明了这些要点：

对于仅涉及内连接（而不是外连接）的连接表达式，可以删除括号并从左到右评估连接。事实上，表可以按任何顺序求值。
通常，对于外部连接或混合了内部连接的外部连接，情况并非如此。删除括号可能会改变结果。

具有嵌套外部连接的查询以与具有内部连接的查询相同的管道方式执行。更确切地说，利用了嵌套循环连接算法的变体。回忆一下嵌套循环连接执行查询所使用的算法（参见第 8.2.1.6 节，“嵌套循环连接算法”）。假设对 3 个表的连接查询T1,T2,T3具有以下形式：

SELECT * FROM T1 INNER JOIN T2 ON P1(T1,T2)
                 INNER JOIN T3 ON P2(T2,T3)
  WHERE P(T1,T2,T3)

这里，P1(T1,T2)和 P2(T3,T3)是一些连接条件（关于表达式），而是P(T1,T2,T3)对表列的条件T1,T2,T3。

嵌套循环连接算法将按以下方式执行此查询：

FOR each row t1 in T1 {
  FOR each row t2 in T2 such that P1(t1,t2) {
    FOR each row t3 in T3 such that P2(t2,t3) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

该表示法表示通过连接行、和 t1||t2||t3的列构造的行。在下面的一些示例中，表名出现的位置表示其中一行用于该表的每一列。例如，表示通过连接行和的列构造的行，并且对于每一列。这样的行被称为 -complemented。 t1t2t3NULLNULLt1||t2||NULLt1t2NULLt3NULL

现在考虑一个带有嵌套外部连接的查询：

SELECT * FROM T1 LEFT JOIN
              (T2 LEFT JOIN T3 ON P2(T2,T3))
              ON P1(T1,T2)
  WHERE P(T1,T2,T3)

对于此查询，修改嵌套循环模式以获得：

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t2 in T2 such that P1(t1,t2) {
    BOOL f2:=FALSE;
    FOR each row t3 in T3 such that P2(t2,t3) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f2=TRUE;
      f1=TRUE;
    }
    IF (!f2) {
      IF P(t1,t2,NULL) {
        t:=t1||t2||NULL; OUTPUT t;
      }
      f1=TRUE;
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

通常，对于外连接操作中第一个内表的任何嵌套循环，都会引入一个标志，该标志在循环之前关闭并在循环之后检查。当从外部表的当前行找到表示内部操作数的表中的匹配项时，该标志将打开。如果在循环周期结束时标志仍然关闭，则没有找到与外表的当前行匹配的结果。NULL在这种情况下，该行由内表的列值补充。结果行被传递到输出的最终检查或进入下一个嵌套循环，但前提是该行满足所有嵌入式外部连接的连接条件。

在示例中，嵌入了由以下表达式表示的外连接表：

(T2 LEFT JOIN T3 ON P2(T2,T3))

对于带有内连接的查询，优化器可以选择不同顺序的嵌套循环，例如：

FOR each row t3 in T3 {
  FOR each row t2 in T2 such that P2(t2,t3) {
    FOR each row t1 in T1 such that P1(t1,t2) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

对于具有外部连接的查询，优化器只能选择外部表循环先于内部表循环的顺序。因此，对于我们的外连接查询，只有一种嵌套顺序是可能的。对于以下查询，优化器评估两个不同的嵌套。在两个嵌套中， T1必须在外循环中处理，因为它用于外连接。T2和 T3用于内部连接，因此连接必须在内循环中处理。但是，由于连接是内部连接，T2因此 T3可以按任意顺序处理。

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)
  WHERE P(T1,T2,T3)

一个嵌套评估T2，然后 T3：

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t2 in T2 such that P1(t1,t2) {
    FOR each row t3 in T3 such that P2(t1,t3) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f1:=TRUE
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

另一个嵌套评估T3，然后 T2：

FOR each row t1 in T1 {
  BOOL f1:=FALSE;
  FOR each row t3 in T3 such that P2(t1,t3) {
    FOR each row t2 in T2 such that P1(t1,t2) {
      IF P(t1,t2,t3) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f1:=TRUE
    }
  }
  IF (!f1) {
    IF P(t1,NULL,NULL) {
      t:=t1||NULL||NULL; OUTPUT t;
    }
  }
}

在讨论内连接的嵌套循环算法时，我们省略了一些对查询执行性能影响可能很大的细节。我们没有提到所谓的 “下推”条件。假设我们的 WHERE条件 P(T1,T2,T3)可以用一个合取公式来表示：

P(T1,T2,T2) = C1(T1) AND C2(T2) AND C3(T3).

在这种情况下，MySQL 实际上使用以下嵌套循环算法来执行带有内连接的查询：

FOR each row t1 in T1 such that C1(t1) {
  FOR each row t2 in T2 such that P1(t1,t2) AND C2(t2)  {
    FOR each row t3 in T3 such that P2(t2,t3) AND C3(t3) {
      IF P(t1,t2,t3) {
         t:=t1||t2||t3; OUTPUT t;
      }
    }
  }
}

您会看到每个连词C1(T1), C2(T2),C3(T3)都从最内层循环推出到最外层循环，在那里可以对其进行评估。如果C1(T1)是一个非常严格的条件，这个条件下推可能会大大减少从表T1 传递到内部循环的行数。因此，查询的执行时间可能会大大缩短。

For a query with outer joins, the WHERE condition is to be checked only after it has been found that the current row from the outer table has a match in the inner tables. Thus, the optimization of pushing conditions out of the inner nested loops cannot be applied directly to queries with outer joins. Here we must introduce conditional pushed-down predicates guarded by the flags that are turned on when a match has been encountered.

Recall this example with outer joins:

P(T1,T2,T3)=C1(T1) AND C(T2) AND C3(T3)

For that example, the nested-loop algorithm using guarded pushed-down conditions looks like this:

FOR each row t1 in T1 such that C1(t1) {
  BOOL f1:=FALSE;
  FOR each row t2 in T2
      such that P1(t1,t2) AND (f1?C2(t2):TRUE) {
    BOOL f2:=FALSE;
    FOR each row t3 in T3
        such that P2(t2,t3) AND (f1&&f2?C3(t3):TRUE) {
      IF (f1&&f2?TRUE:(C2(t2) AND C3(t3))) {
        t:=t1||t2||t3; OUTPUT t;
      }
      f2=TRUE;
      f1=TRUE;
    }
    IF (!f2) {
      IF (f1?TRUE:C2(t2) && P(t1,t2,NULL)) {
        t:=t1||t2||NULL; OUTPUT t;
      }
      f1=TRUE;
    }
  }
  IF (!f1 && P(t1,NULL,NULL)) {
      t:=t1||NULL||NULL; OUTPUT t;
  }
}

通常，下推谓词可以从连接条件中提取，例如P1(T1,T2)and P(T2,T3)。在这种情况下，下推谓词也由一个标志保护，该标志防止检查NULL由相应的外连接操作生成的 -complemented 行的谓词。

如果由WHERE条件中的谓词引发，则禁止在同一嵌套连接中通过键从一个内表访问另一个内表。