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(左連接配接和右連接配接的優化)