MySQL查询优化之六-Join嵌套优化（NestedJoinOptimization）MySQL查询优化之六-Join嵌套优化(Nested Join Optimization)
环境：
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补充的。
现在考虑⼀个嵌套的外连接的查询：
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值补充。 结果⾏被传递到输出的最终检查或下⼀个嵌套循环，但只有当该⾏满⾜所有嵌⼊的外连接的连接条件时才⾏。
在该⽰例中，嵌⼊由以下表达式表⽰的外部联接表：
join和in哪个查询更快(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 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条件仅在发现外表中的当前⾏与内表中的匹配之后才被检查。 因此，从内部嵌套循环中推出条件的优化不能直接应⽤于具有外部连接的查询。 在这⾥，我们必须介绍在遇到匹配时打开的标志保护的条件下推谓词。
回想⼀下外部连接的例⼦：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。