嵌套连接优化

表示连接的语法允许嵌套连接。

与 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和任何基于属性t2.b和t3.b的条件P，都等价于以下表达式：

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

在第一个查询中，嵌套连接是使用左外连接操作形成的。在第二个查询中，它是使用内连接操作形成的。

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

上述示例展示了以下几点：

• 对于只涉及内连接（而不涉及外连接）的连接表达式，可以删除括号，并按从左到右的顺序执行连接操作。实际上，表可以以任何顺序进行评估。

• 对于外连接或混合使用内连接和外连接的情况，这个规则通常不成立。删除括号可能会改变结果。

具有嵌套外连接的查询以与具有内连接的查询相同的管道方式执行。更准确地说，利用了嵌套循环连接算法的变体。回想一下，嵌套循环连接如何执行查询的算法。假设在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(T2,T3)是一些连接条件（ON表达式），而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表示通过连接行t1、t2和t3的列构造的行。在以下示例中，出现表名的地方为NULL表示在该表的每个列中使用NULL的行。例如，t1||t2||NULL表示通过连接行t1和t2的列，并在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必须在外部循环中处理，因为它在外连接中使用。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传递到内部循环的行数。结果，查询的执行时间可能会显著提高。

对于具有外连接的查询，只有在确认当前外部表的行在内部表中有匹配项后，才需要检查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条件的谓词引发了从一个内部表到另一个内部表的关键访问，则是禁止的。