8.2.1.7 嵌套联接优化

table 达联接的语法允许嵌套联接。以下讨论引用了第 13.2.9.2 节“ JOIN 子句”中描述的连接语法。

  • table_factor 的语法与 SQL 标准相比有所扩展。后者仅接受 table_reference ,而不接受一对括号内的列 table。如果我们将 table_reference *项目列 table 中的每个逗号都视为等效于内部联接,则这是一个保守的扩展。例如:
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 JOINON子句一起使用;否则使用CROSS JOIN

通常,在仅包含内部联接操作的联接 table 达式中可以忽略括号。考虑以下联接 table 达式:

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

在除去括号和左侧的分组操作之后,该 jointable 达式将转换为该 table 达式:

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

但是,这两种 table 达方式并不相等。要看到这一点,假设 tablet1t2t3具有以下状态:

  • tablet1包含第(1)(2)

  • tablet2包含第(1,101)

  • tablet3包含第(101)

在这种情况下,第一个 table 达式返回包含行(1,1,101,101)(2,NULL,NULL,NULL)的结果集,而第二个 table 达式返回行(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

该 table 达式不能转换为以下 table 达式:

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

对于给定的 table 状态,两个 table 达式返回不同的行集:

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 |
+------+------+------+------+

因此,如果我们在使用外部联接运算符的联接 table 达式中省略括号,则可能会更改原始 table 达式的结果集。

更确切地说,我们不能忽略左外部联接操作的右操作数和右联接操作的左操作数的括号。换句话说,我们不能忽略外部联接操作的内部 tabletable 达式的括号。另一个操作数(外部 table 的操作数)的括号可以忽略。

下面的 table 达式:

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

对于属性t2.bt3.b上的任何 tablet1,t2,t3和任何条件P,此 table 达式等效:

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

每当联接 table 达式(* joined_table *)中的联接操作执行 Sequences 不是从左到右时,我们都在谈论嵌套联接。考虑以下查询:

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

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

在第一个查询中,可以省略括号:联接 table 达式的语法结构将规定联接操作的执行 Sequences。对于第二个查询,尽管可以在没有括号的情况下明确地解释此处的联接 table 达式,但是不能省略括号。在我们的扩展语法中,第二个查询的(t2, t3)括号是必需的,尽管从理论上讲可以在没有括号的情况下对其进行解析:由于LEFT JOINON充当了左定界符和右定界符的作用,因此查询仍然具有明确的语法结构 table 达式(t2,t3)

前面的示例说明了以下几点:

  • 对于仅涉及内部联接(而不涉及外部联接)的联接 table 达式,可以删除括号并从左到右评估联接。实际上,可以按任何 Sequences 评估 table。

  • 通常,对于外部联接或与内部联接混合的外部联接,情况并非如此。删除括号可能会改变结果。

具有嵌套外部联接的查询的执行方式与具有内部联接的查询的执行方式相同。更确切地说,利用了嵌套循环联接算法的一种变体。调用嵌套循环联接执行查询的算法(请参见第 8.2.1.6 节“嵌套循环加入算法”)。假设 3 个 tableT1,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)是一些 table 达式(在 table 达式上),而P(T1,T2,T3)是 tableT1,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||t3table 示通过串联行t1t2t3的列而构造的行。在以下某些示例中,出现 table 名的NULLtable 示该 table 的每一列都使用NULL的行。例如,t1||t2||NULLtable 示通过将行t1t2以及NULL的列对t3的每一列进行级联而构造的行。这样的行被称为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;
    }
  }
}

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

在该示例中,嵌入了以下 table 达式 table 示的外部联接 table:

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

对于具有内部联接的查询,优化器可以选择不同 Sequences 的嵌套循环,例如:

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;
      }
    }
  }
}

对于具有外部联接的查询,优化器只能选择以下 Sequences:外部 table 的循环优先于内部 table 的循环。因此,对于带有外部联接的查询,只能使用一个嵌套 Sequences。对于以下查询,优化器将评估两个不同的嵌套。在两个嵌套中,T1必须在外部循环中处理,因为它在外部联接中使用。 T2T3用于内部联接中,因此必须在内部循环中处理联接。但是,由于联接是内部联接,因此可以按任一 Sequences 处理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)可以用一个联合公式 table 示:

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)是非常严格的条件,则此条件下推可能会大大减少 tableT1传递给内部循环的行数。结果,查询的执行时间可以大大改善。

对于具有外部联接的查询,只有在发现外部 table 中的当前行在内部 table 中具有匹配项之后,才检查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条件的谓词引起的,则禁止从一个内部 table 到同一嵌套联接中的另一个内部 table 的键访问。