子查詢定義

在一個完整的查詢語句中包含的子查詢塊被稱為子查詢。通常情況下，我們可以将出現在SELECT、WHERE和HAVING文法中的子查詢塊稱為嵌套子查詢，出現在FROM文法後的子查詢塊稱為内聯視圖或派生表。

本篇文章将會結合源碼介紹在MySQL中針對子查詢的幾種優化政策。

子查詢在執行計劃中的表示

Semijoin/Antijoin

對于表示是否存在語義的查詢語句，在文法上表示為IN/=ANY/EXISTS，優化器會嘗試轉換為semijoin/antijoin進行優化。與普通join會将左表和右表的記錄連接配接在一起不同，semijoin/antijoin僅關心右表中是否存在可以與左表記錄連接配接的記錄，而傳回左表記錄。

在prepare階段，優化器會首先檢查目前查詢是否可以轉換為semijoin/antijoin的條件（由于antijoin是semijoin的相反，在代碼層面也是一塊處理的，是以之後的論述以semijoin為主），這部分代碼在

SELECT_LEX::resolve_subquery

中，具體的條件總結如下：

子查詢必須是謂詞IN/=ANY/EXISTS的一部分，并且出現在WHERE或ON文法的最高層，可以被包含在AND表達式中。

必須是單個查詢塊，不帶有UNION。
不包含HAVING文法。
不包含任何聚合函數。
不包含LIMIT文法。
外查詢語句沒有使用STRAIGHT_JOIN文法。

如果滿足條件，将會把目前謂詞加入到外查詢的

SELECT_LEX::sj_candidates

中作為semijon的備選。

由于優化器對查詢塊的處理是一種遞歸的方式，在完成對子查詢的判斷之後，在外層查詢的prepare階段，會調用

SELECT_LEX::flatten_subqueries

函數完成子查詢到semijoin的最終轉換，這個過程在整個查詢的生命周期隻會發生一次，且不可逆。在SQL文法上等價為：

從一個帶有備選semijoin子查詢判斷條件的查詢塊：
    SELECT ...
    FROM ot, ...
    WHERE oe IN (SELECT ie FROM it1 ... itN WHERE subq_where) AND outer_where
轉換為：
    SELECT ...
    FROM ot SEMI JOIN (it1 ... itN), ...
    WHERE outer_where AND subq_where AND oe=ie

為了實作上述過程，需要進行以下步驟：

建立 SEMI JOIN (it1 ... itN) 語以部分，并加入到外層查詢塊的執行計劃中。
将子查詢的WHERE條件以及JOIN條件，加入到父查詢的WHERE條件中。
将子查詢謂詞從父查詢的判斷謂詞中消除。

具體的僞代碼如下：

SELECT_LEX::flatten_subqueries()
     /* Semijoin flattening is bottom-up. Indeed, we have this execution flow,
        for SELECT#1 WHERE X IN (SELECT #2 WHERE Y IN (SELECT#3)) :

        SELECT_LEX::prepare() (select#1)
           -> fix_fields() on IN condition
               -> SELECT_LEX::prepare() on subquery (select#2)
                   -> fix_fields() on IN condition
                        -> SELECT_LEX::prepare() on subquery (select#3)
                        <- SELECT_LEX::prepare()
                   <- fix_fields()
                   -> flatten_subqueries: merge #3 in #2
                   <- flatten_subqueries
               <- SELECT_LEX::prepare()
           <- fix_fields()
           -> flatten_subqueries: merge #2 in #1

        Note that flattening of #(N) is done by its parent JOIN#(N-1), because
        there are cases where flattening is not possible and only the parent can
        know.*/
   |--子查詢層層嵌套中采用bottom-up的方式去展開。在fix_fields()的過程中依次從裡往外。僅支援IN和EXISTS的子查詢，且内層的sj_candidates為空。
   |--由于在WHERE條件同一層可能存在多個可以展開的子查詢判斷，首先會計算優先級來決定semijoin展開順序：
      1. 依賴外層查詢的子查詢優先于不相關子查詢。
      2. 有着更多表的子查詢優先于更少表的子查詢。
      3. 順序上先計算的子查詢優先于後計算的。
   |--semijoin子查詢不能和antijoin子查詢互相嵌套。
   |--判斷子查詢的WHERE條件是否為常量。
      如果判斷條件永遠為FALSE，那麼子查詢結果永遠為空。該情況下，可以将子查詢直接清除，不用轉換成semijoin。
   |--替換外層查詢的WHERE條件中子查詢判斷的條件
      1. 子查詢内條件并不永遠為FALSE，或者永遠為FALSE的情況下，需要改寫為antijoin（antijoin情況下，子查詢結果永遠為空，外層查詢條件永遠通過）。
         此時将條件改為永遠為True。
      2. 子查詢永遠為FALSE，且不是antijoin。那麼将外層查詢中的條件改成永遠為False。
      /* 子查詢判斷條件可能為IN/=ANY/EXISTS，或者對應的否定。參數為Item_exists_subselect *。
         The following transformations are performed:

         1. IN/=ANY predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE (oe1, ... oeM) IN (SELECT ie1, ..., ieM
                                  FROM it1 ... itK
                                 [WHERE inner-cond])
          [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) SJ (it1 ... itK)
                           ON (oe1, ... oeM) = (ie1, ..., ieM)
                              [AND inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         Notice that the inner-cond may contain correlated and non-correlated
         expressions. Further transformations will analyze and break up such
         expressions.

         2. EXISTS predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE EXISTS (SELECT expressions
                       FROM it1 ... itK
                       [WHERE inner-cond])
          [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) SJ (it1 ... itK)
                            [ON inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]
         
         3. Negated EXISTS predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE NOT EXISTS (SELECT expressions
                       FROM it1 ... itK
                       [WHERE inner-cond])
          [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) AJ (it1 ... itK)
                            [ON inner-cond]
         [WHERE outer-cond AND is-null-cond(it1)]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         where AJ means "antijoin" and is like a LEFT JOIN; and is-null-cond is
         false if the row of it1 is "found" and "not_null_compl" (i.e. matches
         inner-cond).
         
         4. Negated IN predicates on the form:

         SELECT ...
         FROM ot1 ... otN
         WHERE (oe1, ... oeM) NOT IN (SELECT ie1, ..., ieM
                                  FROM it1 ... itK
                                  [WHERE inner-cond])
         [AND outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         are transformed into:

         SELECT ...
         FROM (ot1 ... otN) AJ (it1 ... itK)
                            ON (oe1, ... oeM) = (ie1, ..., ieM)
                            [AND inner-cond]
         [WHERE outer-cond]
         [GROUP BY ...] [HAVING ...] [ORDER BY ...]

         5. The cases 1/2 (respectively 3/4) above also apply when the predicate is
         decorated with IS TRUE or IS NOT FALSE (respectively IS NOT TRUE or IS FALSE).*/
   |--SELECT_LEX::convert_subquery_to_semijoin() // 将目前查詢塊中包含的子查詢判斷轉換成TABLE_LIST中的semijoin嵌套，antijoin也在裡面完成。
     |--生成一個新的semijoin嵌套的TABLE_LIST表
     |--TABLE_LIST::merge_underlying_tables() // 将子查詢中潛在的表合并到上述join表中
     |--将子查詢的葉子表插入到目前查詢塊的葉子表後面，重新設定子查詢的葉子表的序号和依賴的外表。将子查詢的葉子表重置。
     |--如果是outer join的話，在join連結清單中傳遞可空性。
     |--SELECT_LEX::decorrelate_condition()
       |--将内層子查詢中的關聯條件去關聯化，這些條件被加入到semijoin的清單裡。這些條件必須是确定的，僅支援簡單判斷條件或者由簡單判斷條件組成的AND條件。
       |--decorrelate_equality()
         |--判斷左右條件是否僅依賴于内外層表，将其表達式分别加入到semijoin内外表的表達式清單中。
     |--decorrelate_join_conds() // 解關聯内層查詢的join條件
     |--Item_cond_and::fix_after_pullout() // 将子查詢的WHERE條件上拉，更新使用表的資訊
     |--SELECT_LEX::build_sj_cond() // 根據semijoin的條件清單建立AND條件，如果有條件為常量True，則去除該條件；如果常量為False，則整個條件都去除。
     |--将建立出來的semijoin條件加入到外層查詢的WHERE條件中

物化執行 or 疊代式循環執行

對于不能采用semijoin/antijoin執行的存在式語義的子查詢，在MySQL源碼的表示含義下，會做IN->EXISTS的轉換，其實本質是在物化執行和疊代式循環執行中做選擇。IN文法代表非相關子查詢僅執行一次，将查詢結果物化成臨時表，之後需要結果時候就去物化表中查找；EXISTS代表對于外表的每一條記錄，子查詢都會執行一次，是疊代式循環執行。

MySQL會在prepare階段嘗試做IN->EXISTS的轉換，然後在optimize階段，比較IN or EXISTS執行的代價，最後根據代價決定采用哪種執行政策完成最終轉換。

在prepare階段IN->EXISTS的轉換主要是将IN文法的左表達式與右表達式中子查詢的輸出列對應組合，加入到子查詢的WHERE或者HAVING條件中，在SQL語義上表示為：

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)
轉換為：
EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

這一過程主要發生在

Item_in_subselect::single_value_in_to_exists_transformer

中，詳細過程為：

/* 通過判斷條件注入将IN文法轉換為EXISTS文法
   向子查詢中注入額外的判斷條件，并将子查詢标記為關聯子查詢。*/
|--Item_in_subselect::single_value_in_to_exists_transformer()
  |--如果子查詢包含聚合函數、視窗函數、GROUP文法、HAVING文法，将判斷條件加入到HAVING文法中。
  |--如果我們想區分NULL和False的結果的話，将這個條件封裝到觸發器中。
     SELECT ie FROM ... HAVING subq_having AND
               trigcond(oe $cmp$ ref_or_null_helper<ie>)
  |--建立指向子查詢唯一列的Item_ref_null_helper對象，與之前注入的左表達式Item_ref共同建立比較表達式
  |--如果子查詢的第一個列為包含聚合列的表達式，那麼WHERE和HAVING文法中可能通過不同的Item_ref引用到這個Item，存入到Item_sum::ref_by數組中
  |--and_items() // 加入到HAVING條件中
|--如果不包含聚合函數、視窗函數、GROUP文法、HAVING文法，将判斷條件加入WHERE語句中
  |--如果不需要區分NULL與False的結果：
     SELECT 1 FROM ... WHERE (oe $cmp$ ie) AND subq_where
  |--如果需要區分上述結果的差别，使用觸發器
     SELECT 1 FROM ...
     WHERE subq_where AND trigcond((oe $cmp$ ie) OR (ie IS NULL))
           HAVING trigcond(@<is_not_null_test@>(ie))
  |--其他，單個查詢塊，沒有表及上述文法，直接用條件表達式在外查詢中替代

總結

以上就是MySQL中針對子查詢所做的大部分優化和轉換的工作，代碼分析基于MySQL 8.0.19版本。

參考：

https://dev.mysql.com/doc/refman/8.0/en/subquery-optimization.html

MySQL 子查詢優化源碼分析子查詢定義子查詢在執行計劃中的表示Semijoin/Antijoin物化執行 or 疊代式循環執行總結

子查詢定義

子查詢在執行計劃中的表示

Semijoin/Antijoin

物化執行 or 疊代式循環執行

總結

繼續閱讀

SQL優化SQL語句優化的目的

資料遷移方法資料遷移原則資料遷移之雙寫方案資料遷移之級聯同步方案

redis叢集資料一緻性_RedisRaft為Redis叢集帶來強大的資料一緻性

JAVA高效程式設計指南

寶塔面闆mysql恢複2018.1.8更新

Centos7 MySQL 5.7 安裝MySQL 5.7 安裝

查找入職員工時間排名倒數第三的員工所有資訊

Hibernate使用Hibernate的“3個準備，7個步驟”Hibernate API簡介操作實體對象對象識别

雲計算面試題——mysql/存儲引擎/備份

關于SQL語言

SQL語言基礎：常用的資料查詢語句

Ubuntu16.04安裝Apache+MySQL+PHP1. 安裝Apache2. 安裝MySQL3. 安裝PHP4. 安裝phpMyAdmin

MySQL的4種隔離級别？出現問題

neo4j之cypher使用文檔

mysql使用source指令導入.sql檔案

sqlServer根據經緯查距離