mysql5.7官网直译SQL语句优化--嵌套连接的优化

1.7Nested Join Optimization(嵌套连接的优化)

允许嵌套连接的表达式语法。下面的描述引用在13.2.9.2的连接语法。

table_factor的语法是对标准sql比较的扩展。后者只接受table_reference,而不是一个括号内的list集合。如果我们考虑每一个在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则在其他条件下使用。

一般情况下，圆括号可以被省略的，如果连接表达式中只有inner 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 |

+------+------+------+------+

在下面的例子中，一个外连接(outer join)操作和一个内连接(inner join)操作结合；

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和任何覆盖P条件属性t2.b和t3.b；

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和在(t2,t3)左右两边分隔符中on条件扮演的角色作用。

之前的例子说明了这几点：

>对于只有内连接的连接表达式(没有外连接),括号能够被去除，并且连接从左到右取值。事实上，表的顺序可以随意排列。

>相同不是一直成立的，一般来说，对于外部连接或者是混合了内部连接的外部连接。去掉括号有可能会改变结果值。

嵌套了外部连接的查询会以与内部连接查询相同的管道方式执行。更具体的说，作为一种嵌套循环的变体被执行。算法被调用，当一个嵌套循环连接在查询中被执行。具体看8.2.1.6的嵌套循环连接算法。

假设一个查询覆盖了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)是一些连接条件，而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;

    }

  }

}

当讨论内连接的嵌套循环算法时，我们忽略了一些可能会对查询产生巨大影响的细节。我们没有注意可能用到"pushed-down"的条件。假设我们的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) and P(T2,T3).在这种情况下，一个压入断言被控制通过一个标记。该标记阻止检查通过外部连接生成的null补充行数据。

不允许来自内部表中的key访问到另一个相同嵌套连接中涉及到的表中去，如果它是由where条件引出的key的话。

到此嵌套连接优化就结束了，接下来我们将介绍：1.8Left Join and Right Join Optimization(左连接和右连接的优化)