# 4.6 嵌套连接接优化

表达联接的语法允许嵌套联接。

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

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

等效于：

```sql
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`否则使用。

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

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

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

```sql
(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)`：

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

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

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

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

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

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

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

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

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

下面的表达式：

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

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

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

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

```sql
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
```

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

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

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

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

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

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

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

```sql
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)`在table的列上的条件`T1,T2,T3`。

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

```clike
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`互补的。

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

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

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

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

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

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

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

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

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

一个嵌套计算`T2`，然后 `T3`：

```clike
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`：

```clike
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)`可以用一个联合公式表示：

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

在这种情况下，MySQL实际上使用以下嵌套循环算法通过内部联接执行查询：

```clike
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` 仅在发现外部表的当前行在内部表中具有匹配项之后，才检查条件。因此，将条件从内部嵌套循环中推出的优化不能直接应用于具有外部联接的查询。在这里，我们必须引入条件下推谓词，该条件下推谓词由遇到匹配时打开的标志保护。

回想一下带有外部联接的示例：

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

对于该示例，使用受保护的下推条件的嵌套循环算法如下所示：

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