第7章:优化 / 7.2. 优化SELECT语句和其它查询 / 7.2.10. MySQL如何优化嵌套Join

表示联接的语法允许嵌套联接。下面的讨论引用了13.2.7.1节,“JOIN语法”中描述的联接语法。

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

但是这两个表达式不等效。要说明这点,假定表t1t2t3有下面的状态:

·         t1包含行{1}{2}

·         t2包含行{1,101}

·         t3包含行{101}

在这种情况下,第1个表达式返回包括行{1,1,101,101}{2,NULL,NULL,NULL}的结果,第2个表达式返回行{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 (t2t3) ON t1.a=t2.a

该表达式不能转换为下面的表达式:

t1 LEFT JOIN t2 ON t1.a=t2.at3.

对于给定的表状态,第1个表达式返回行{1,1,101,101}{2,NULL,NULL,NULL},第2个表达式返回行{1,1,101,101}{2,NULL,NULL,101}

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

因此,如果我们忽略联接表达式中的括号连同外面的联接操作符,我们会改变原表达式的结果。

更确切地说,我们不能忽视左外联接操作的右操作数和右联接操作的左操作数中的括号。换句话说,我们不能忽视外联接操作中的内表达式中的括号。可以忽视其它操作数中的括号(外部表的操作数)

对于任何表t1t2t3和属性t2.bt3.b的任何条件P,下面的表达式:

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

等价于表达式

t1t2 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

认为是嵌套的。第1个查询结合左联接操作则形成嵌套的联接,而在第二个查询中结合内联接操作形成嵌套联接。

在第1个查询中,括号可以忽略:联接表达式的语法结构与联接操作的执行顺序相同。但对于第2个查询,括号不能省略,尽管如果没有括号,这里的联接表达式解释不清楚。(在外部扩展语法中,需要第2个查询的(t2t3)的括号,尽管从理论上对查询分析时不需要括号:这些查询的语法结构将仍然不清楚,因为LEFT JOINON将充当表达式(t2,t3)的左、右界定符的角色)

前面的例子说明了这些点:

·         对于只包含内联接(而非外联接)的联接表达式,可以删除括号。你可以移除括号并从左到右评估(或实际上,你可以按任何顺序评估表)

·         总的来说,对外联接却不是这样。去除括号可能会更改结果。

·         总的来说,对外联接和内联接的结合,也不是这样。去除括号可能会更改结果。

含嵌套外联接的查询按含内联接的查询的相同的管道方式执行。更确切地说,利用了嵌套环联接算法。让我们回忆嵌套环联接执行查询时采用什么算法。

假定我们有一个如下形式的表T1T2T3的联接查询:

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)是表T1T2T3的列的一个条件。

嵌套环联接算法将按下面的方式执行该查询:

 

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表示“连接行t1t2t3的列组成的行”。在下面的一些例子中,出现行名的NULL表示NULL用于行的每个列。例如,t1||t2||NULL表示“连接行t1t2的列以及t3的每个列的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;
      }
    }
  }
}

对于有外联接的查询,优化器可以只选择这样的顺序:外表的环优先于内表的环。这样,对于有外联接的查询,只可能有一种嵌套顺序。在下面的查询中,优化器将评估两个不同的嵌套:

SELECT * T1 LEFT JOIN (T2,T3) ON P1(T1,T2) AND P2(T1,T3)
  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) {
    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;
    }
  }
}

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;
    }
  }
}

在两个嵌套中,必须在外环中处理T1,因为它用于外联接中。T2T3用于内联接中,因此联接必须在内环中处理。但是,因为该联接是一个内联接,T2T3可以以任何顺序处理。

当讨论内联接嵌套环的算法时,我们忽略了部分详情,可能对查询执行的性能的影响会很大。我们没有提及所谓的“下推”条件。假定可以用连接公式表示我们的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条件推导出,根据从一个内表到相同嵌套联接的另一个表的关键字进行的访问被禁止。(在这种情况下,我们可以使用有条件关键字访问,但是该技术还未用于MySQL 5.1中)