【ACDU翻译】8.2.1.8嵌套联接优化

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

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

等效于：

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

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

在除去括号并在左侧进行分组操作之后，该join表达式将转换为该表达式：

但是，这两种表达方式并不相同。看到这一点，假设表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)：

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

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

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

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

更确切地说，我们不能忽略左外部联接操作的右操作数和右联接操作的左操作数中的括号。换句话说，我们不能忽略外部联接操作的内部表表达式的括号。另一个操作数（外部表的操作数）的括号可以忽略。

下面的表达式：

对于任何表t1,t2,t3和P属性t2.b 以及条件而言 ，此表达式均等效于此表达式 t3.b：

每当连接表达式（joined_table）中的连接操作执行顺序不是从左到右时，我们都在谈论嵌套连接。考虑以下查询：

这些查询被认为包含以下嵌套联接：

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

在第一个查询中，可以省略括号：join表达式的语法结构规定了join操作的相同执行顺序。对于第二个查询，尽管可以在没有括号的情况下明确地解释此处的联接表达式，但是不能省略括号。在扩展语法中，(t2, t3)需要第二个查询的括号，尽管从理论上讲可以在没有括号的情况下对其进行解析：由于查询LEFT JOIN并ON 在表达式的左右定界符中扮演着角色，因此查询仍然具有明确的句法结构(t2,t3)。

前面的示例演示了以下几点：

• 对于仅涉及内部联接（而不涉及外部联接）的联接表达式，可以删除括号并以从左到右的方式评估联接。实际上，可以按任何顺序评估表。


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

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

在这里，P1(T1,T2)and P2(T3,T3)是一些联接条件（在表达式上），而P(T1,T2,T3)条件是在table的列上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表示通过连接的行的列构成的行 t1，t2和 t3。在以下某些示例中， NULL出现表名的地方表示该表NULL的每一列都使用一行。例如，t1||t2||NULL 表示通过将行t1和的列t2以及 NULL的每一列 串联而构造的行t3。据说这样的行是 NULL互补的。

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

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

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内部表的列的值补充 。结果行将传递到输出的最终检查项或下一个嵌套循环，但前提是该行满足所有嵌入式外部联接的联接条件。

在该示例中，嵌入了以下表达式表示的外部联接表：

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

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可以按任何顺序进行处理。

一个嵌套计算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条件谓词引起的，则禁止通过一个键在同一个嵌套联接中从一个内部表访问另一个内部表。