MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)

如需转载请标明出处：http://blog.csdn.net/itas109
QQ技术交流群：129518033

环境：
MySQL版本：5.5.15
操作系统：windows

本文讨论Join嵌套优化(Nested Join Optimization)。

与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，NULL），（2，NULL）
• 表t2包含行（1，101）
• 表t3包含行（NULL，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)

每当连接表达式（join_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（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表示通过连接行t1，t2和t3的列而构成的行。 在下面的一些示例中，出现表名的NULL意味着该表的每列使用NULL的行。 例如，t1 || t2 || NULL表示通过连接行t1和t2的列构造的行，以及t3的每列的NULL。 这样的行被认为是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值补充。 结果行被传递到输出的最终检查或下一个嵌套循环，但只有当该行满足所有嵌入的外连接的连接条件时才行。

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

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

Reference：
https://dev.mysql.com/doc/refman/5.5/en/nested-join-optimization.html

觉得文章对你有帮助，可以用微信扫描二维码捐赠给博主，谢谢！

如需转载请标明出处：http://blog.csdn.net/itas109
QQ技术交流群：129518033

最后

以上就是内向海燕为你收集整理的MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)的全部内容，希望文章能够帮你解决MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。