Documentation Home
MySQL 8.4 Reference Manual
Related Documentation Download this Manual
PDF (US Ltr) - 39.8Mb
PDF (A4) - 39.9Mb
Man Pages (TGZ) - 257.9Kb
Man Pages (Zip) - 364.9Kb
Info (Gzip) - 4.0Mb
Info (Zip) - 4.0Mb


10.2.1.8 Nested Join 优化

表达连接的语法允许嵌套连接。以下讨论参考了在第15.2.13.2节,“JOIN子句”中描述的连接语法。

table_factor 的语法与 SQL 标准相比有所扩展。后者仅接受 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

然而,这两个表达式并不等价。要看到这一点,假设表 t1t2t3 有以下状态:

  • 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 和任何条件 P,该条件涉及属性 t2.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

在第一个查询中,嵌套连接是由左连接操作形成的。在第二个查询中,它是由内连接操作形成的。

在第一个查询中,可以省略括号:连接表达式的语法结构 dictate 了相同的执行顺序。对于第二个查询,括号不能省略,尽管连接表达式在没有它们的情况下可以被解释为无歧义的。我们的扩展语法要求 (t2, t3) 中的括号,在第二个查询中是必需的,尽管理论上这个查询可以不带它们被解析:我们仍然将有明确的语法结构对查询进行解释,因为 LEFT JOINON 扮演了左边和右边分隔符的角色,对于表达式 (t2,t3)

前面的例子说明了这些点:

  • 对于仅包含内连接(以及不包括外连接)的连接表达式,括号可以被移除,并且连接可以按从左到右的顺序进行评估。实际上,表可以以任何顺序进行评估。

  • 同样,不是总是对的,对于外连接或混合了内连接和外连接的查询。在省略括号时可能会改变结果集。

包含嵌套外连接的查询与仅包含内连接的查询一样在管道中执行。更准确地说,嵌套循环连接算法被利用。回想一下由嵌套循环连接执行的查询(见第10.2.1.7节,“嵌套循环连接算法”)。假设一个连接查询,涉及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 中,表示通过将表 t1t2t3 的列拼接而构造的行。在以下一些例子中,NULL 表示在某些表名出现的地方表示使用 NULL 作为该表的每一列。例如,t1||t2||NULL 表示将 t1t2 的列拼接,并对 t3 的每一列使用 NULL。这样的行被称为 NULL-补全的。

现在考虑一个包含嵌套外连接的查询。

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 必须在外部循环中处理,因为它用于外连接。T2T3 用于内连接,因此该连接必须在内部循环中处理。然而,由于这是一个内连接,T2T3 可以按任意顺序处理。

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 传递给内部循环的行数。因此,对于查询执行时间可能会有巨大的改进。

对于包含外连接的查询,WHERE 条件只在确定当前行从外部表中找到匹配后才进行检查。因此,对于包含外连接的查询,推下条件到内部嵌套循环中的优化不能直接应用。在这种情况下,我们必须引入带有标志的条件推下谓词,这些标志在遇到匹配时打开。

回想一下这个例子,其中包含外连接:

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

对于该示例,使用带有条件推下谓词的嵌套循环算法如下:

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)P(T2,T3) 中提取推下谓词。在这种情况下,推下谓词由一个标志保护,该标志防止对应于外连接操作的 NULL-补全行进行谓词检查。

从一张内表到另一张内表在同一嵌套连接中通过键访问是禁止的,如果它由 WHERE 条件中的谓词引起。