子查詢

http://note.youdao.com/yws/public/redirect/share?id=50f2c387a5d6c9bc816c4b5282cf410e&type=false 1

一概述

MySQL子查詢優化的技術或優化政策，包括三種，分别為：

1 semi-join：半連接配接優化技術，本質上是把子查詢上拉到父查詢中，與父查詢的表做join/semi-join的操作。關鍵詞是“上拉”。

2 Materialization：物化子查詢，子查詢的結果通常緩存在記憶體或臨時表中

3 EXISTS strategy：把半連接配接轉換為EXISTS操作。本質上是把父表的條件下推到子查詢中關鍵詞是“下推”。

子查詢格式	可選的優化政策
IN/=ANY	semi-join， Materialization，EXISTS strategy
NOT IN/<>ALL	Materialization， EXISTS strategy

二 semi join

1 什麼是半連接配接？

semi join，半連接配接操作，是關系代數規定的擴充操作符之一。對于“R semi-join S”其語義為：連接配接後的結果中，隻包括R與S在公共屬性上的交集所限定的R中的部分元組。

anti join，反半連接配接，語義與半連接配接相反。即“R semi-join S”相當于“S anti-join R”。

2 為什麼要用半連接配接優化子查詢？

對于子查詢，其子查詢部分相對于父表的每個符合條件的元組，都要把子查詢執行一輪。效率低下。用半連接配接操作優化子查詢，是把子查詢上拉到父查詢中，這樣子查詢的表和父查詢中的表是并列關系，父表的每個符合條件的元組，隻需要在子表中找符合條件的元組即可，不需要“父表的每個符合條件的元組，都要把子查詢執行一輪”，是以效率提高。

這種優化方式，稱為“上拉/扁平化”。

3 半連接配接的優化政策

MySQL提供5種優化政策，來進一步優化半連接配接操作，分别是：

3.1 DUPS_WEEDOUT/重複剔除：執行普通的兩表内連接配接操作，用臨時表緩存結果，在臨時表中在所查詢的列上（a in subquery，MySQL自動在臨時表的a列上建立主鍵）通過主鍵去除重複的元組。在執行計劃中，可以看到“Start temporary/End temporary”。

參考資料：

https://mariadb.com/kb/en/mariadb/documentation/optimization-and-tuning/query-optimizations/optimization-strategies/duplicateweedout-strategy/

3.2 LOOSE_SCAN/松散掃描：在執行連接配接的時候，半連接配接的表S（R semi-join S）其元組需要有序（a in select b from t，b上存在索引，其元組的順序按照b成分組狀，則使用b上可用的索引讀取元組的時候，可以按序引序把相同的值的元組有序讀到），此時，根據索引拿出每組重複元組中的第一個元組（其他重複元組被讀到後跳過，是以要求S的元組有序），與R表進行連接配接。

https://mariadb.com/kb/en/mariadb/documentation/optimization-and-tuning/query-optimizations/optimization-strategies/loosescan-strategy/

3.3 FIRST_MATCH/首次比對：兩表做普通的内連接配接，連接配接後的結果，存于臨時表，在每次儲存到臨時表前，在臨時表中檢查是否有相同值的元組存在，不存在則儲存。

https://mariadb.com/kb/en/mariadb/documentation/optimization-and-tuning/query-optimizations/optimization-strategies/firstmatch-strategy/

3.4 MATERIALIZE_LOOKUP/索引式物化：把子查詢的結果物化到臨時表，執行連接配接的時候，可以用臨時表的索引（MySQL自動為臨時表建立索引）完成連接配接操作。這種情況下，完成連接配接的時候，通常被物化後的子查詢的結果是連接配接操作的内表，這樣才便于使用索引快速定位内表的元組。

3.5 MATERIALIZE_SCAN/掃描式物化：類似上一個。隻是臨時表的索引不能輔助加快連接配接，隻能通過全表掃描的方式，掃描臨時表中的元組，來完成半連接配接操作。這種情況下，完成連接配接的時候，通常被物化後的子查詢的結果是連接配接操作的外表，是以需要全表掃描。注意，兩種物化方式要求子查詢是“非相關的子查詢”，這樣其結果才穩定不變可被物化（記憶體化/緩存化）。

https://mariadb.com/kb/en/mariadb/documentation/optimization-and-tuning/query-optimizations/optimization-strategies/semi-join-materialization-strategy/

這5種政策的選擇，是通過代價估算的方式，來挑出其中最優的政策。

需要注意的是：

3.6半連接配接操作對于表達“半”含義的表，具有“存在即可”的含義，如果有多個元組符合連接配接條件，則不能讓每個符合條件的元組都與外表進行連接配接，是以，對于半連接配接的表即一個内表來說，就需要把滿足條件的重複元組去掉或使用索引等方式進行“隻選擇一個”式的操作。

3.7 如果需要更進一步學習，可以參考代碼中相關函數：

advance_sj_state()

semijoin_firstmatch_loosescan_access_paths()

semijoin_loosescan_fill_driving_table_position()

setup_semijoin_dups_elimination()

等等。

3.8 注意：半連接配接的這5種子優化政策，需要通過代價估算完成最優選擇。

4 MySQL對什麼樣的子查詢支援使用半連接配接進行優化？

子查詢語句必須滿足：

子查詢語句必須同時滿足（如果其中有一個不滿足，則采用EXISTS政策優化子查詢--這一點，就是SEMI-JOIN政策和EXISTS政策之間的差別。即據此知道對于子查詢，MySQL是如何決定使用哪種優化政策的）：

4.1 謂詞必須是：IN/=ANY（不可以是NOT IN）

4.2 子查詢必須是一個簡單子查詢，不能包括：UNION/GROUP BY/HAVING/聚集函數。如果包含有ORDER BY則不可以帶有LIMIT子句。

4.3 表的總數（外表和内表之和）不能超過61（MySQL支援的最多可連接配接的表的個數）。

4.4 子查詢位于WHERE/JOIN-ON子句中，且首層不存在OR/NOT操作（即首層的條件子句中隻能是AND操作符連接配接的表達式。如果與OR操作在同層的子查詢不可以被半連接配接優化，但可以被“物化政策”優化）。

4.5 查詢塊中不可以包括：STRAIGHT_JOIN（與子查詢同層的連接配接子句中不可以包括STRAIGHT_JOIN）。

4.6 半連接配接參數必須打開(set optimizer_switch='semijoin=on';)，否則采用EXISTS政策優化子查詢。

4.7 不是UPDATE/DELETE指令（在UPDATE/DELETE指令子查詢不被半連接配接優化）。

4.8 子查詢語句不能是無表子句（如子查詢形如“select 1”是不能被半連接配接優化的）。父查詢語句也不能是無表子句。

其他：

4.9 子查詢是相關子查詢或不相關子查詢均可。

4.10 可以帶有DISTINCT/LIMIT子句，但LIMIT不可以和ORDER BY合用。

5 半連接配接進一步優化為内連接配接

MySQL支援把子查詢優化為半連接配接, 還支援把優化後的半連接配接進一步優化為内連接配接。優化的條件，是子查詢的目标列，使用了主鍵或唯一鍵。例如，子查詢中的目标列是K2表的主鍵列：

CREATE TABLE K1 (pk1 INT PRIMARY KEY, a1 INT);

CREATE TABLE K2 (pk2 INT PRIMARY KEY, a2 INT);

INSERT INTO K1 VALUES (1,1), (2,2), (3,null);

INSERT INTO K2 VALUES (1,1), (2,2), (3,null);

SELECT * FROM K1 WHERE a1 IN (SELECT pk2 FROM K2);

mysql> EXPLAIN SELECT * FROM K1 WHERE a1 IN (SELECT pk2 FROM K2);

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

| 1 | SIMPLE | K1 | NULL | ALL | NULL | NULL | NULL | NULL | 3 | 100.00 | Using where |

| 1 | SIMPLE | K2 | NULL | eq_ref | PRIMARY | PRIMARY | 4 | m.K1.a1 | 1 | 100.00 | Using index |

2 rows in set, 1 warning (0.00 sec)

mysql> show warnings;

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

| Level | Code | Message|

| Note | 1003 | /* select#1 */ select `m`.`k1`.`pk1` AS `pk1`,`m`.`k1`.`a1` AS `a1` from `m`.`k2` join `m`.`k1` where (`m`.`k2`.`pk2` = `m`.`k1`.`a1`) |

1 row in set (0.00 sec)

這個示例中，MySQL首先把子查詢優化為半連接配接（semi join），然後，調用pull_out_semijoin_tables()函數把半連接配接優化為内連接配接。其支援的形式為：

... WHERE oe IN (SELECT it1.primary_key WHERE p(it1, it2) ... )

謂詞p，隻能是内連接配接。

http://note.youdao.com/yws/public/redirect/share?id=a2cfee0ef4ad16f67e3d390fe7cf7029&type=false 2

三 物化政策

1 什麼是物化政策？

如果子查詢執行一次即可以得到結果,即子查詢的結果是穩定的,則這樣的子查詢可以被緩存起來，多次使用。緩存即是物化。緩存到記憶體中，如果記憶體中放不下，則會寫外存。在MySQL中，這個緩存對應的是臨時表（即：物化利用了臨時表的機制）。

相關子查詢依賴于父查詢，結果不确定，是以能被物化的，一定是“非相關子查詢”。

2 物化政策與半連接配接中的物化子政策有什麼不同嗎？

物化政策，outside-in materialization，取個名字叫“外化”。此政策隻用于“非相關子查詢”。這相當于把子查詢執行一次，然後緩存結果供多次使用。

而半連接配接中的物化子政策，盡管也是隻可以用于“非相關子查詢”，但優化後，查詢語句執行的是實實在在的内連接配接或半連接配接操作（如果子查詢的目标列存在唯一索引，則可以進一步把半連接配接優化為内連接配接操作，如前所述）。

如果子查詢不能被優化為半連接配接，則形如下式的（子查詢位于OR操作中），可以使用物化政策優化（主要在于OR操作，但非OR的IN子查詢，也可能被物化，但屬于半連接配接操作的物化）。

SELECT ... FROM ... WHERE (expr1, ..., exprN) [NOT] IN (SELECT ... ) OR expr;



四 EXISTS政策

1 什麼是EXISTS政策？

EXISTS政策，首先對應于SEMI-JOIN政策。其主要表述的，是下推的含義。下推什麼呢？下推父查詢的條件部分到子查詢的條件部分。其形式如下：

初始格式：

outer_expr IN (SELECT inner_expr FROM ... WHERE subquery_where)

下推後的格式：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

這樣做的好處，是起到當子查詢不可消除的時候、用父查詢的條件在子查詢中起到限制子查詢元組個數的作用。



2 EXISTS政策的限制？

并不是所有的子查詢，都可以使用EXISTS政策，因為下推條件會帶來一些問題。這個問題就是對NULL值的處理。

滿足如下條件的，可以用下推來優化子查詢：

2.1 outer_expr和inner_expr都不可以有NULL值，且

2.2 SQL語句的語義，并不需要從子查詢的傳回結果（下推後的子查詢的傳回值，隻能是FALSE或TRUE）為FALSE的情況下區分NULL值。



如果不能全部滿足上述2個條件，MySQL會“下推”父查詢的條件到子查詢，但下推後的格式變化為：

情況一： outer_expr不可為NULL

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND

(outer_expr=inner_expr OR inner_expr IS NULL))

情況二：outer_expr可為NULL，不可以下推。

http://note.youdao.com/yws/public/redirect/share?id=0dd0f5b1bbd96d65ee4d5d93c732dfa6&type=false 3

五進一步挖掘

1 MySQL僅僅是用半連接配接/物化/EXISTS政策來優化子查詢的嗎？

Convert the subquery to a join, or use table pullout and run the query as an inner join between subquery tables and outer tables. Table pullout pulls a table out from the subquery to the outer query.

這表明MySQL是可以把子查詢優化為連接配接操作的（這是一種特例：把半連接配接進一步優化為連接配接，需要子查詢的目标列為唯一鍵，如outer_expr IN (SELECT field_primary_key...)）。

2 三種優化政策之間的關系

2.1 預設使用半連接配接進行優化，可以使用“set optimizer_switch='semijoin=off';”指令關閉半連接配接政策。

2.2 如果半連接配接參數關閉,則可以使用物化政策或EXISTS政策,使用哪種,由decide_subquery_strategy()函數決定，此函數調用compare_costs_of_subquery_strategies()函數進行兩種政策的代價計算，決定選用代價小的優化政策。可以使用“set optimizer_switch='materialization=off'; ”指令關閉物化政策，進而訓示MySQL優化器使用EXISTS政策。

3 如何區分是使用了哪種優化政策？

政策名稱	查詢執行計劃顯示項	值	說明
半連接配接政策	SHOW WARNINGS指令顯示内容	semi join	（子查詢的select列為主鍵或者唯一索引）
物化政策	select_type	SUBQUERY/SIMPLE	（子查詢的select列有空值）
	<materialize>(query fragment)	非半連接配接的物化，即物化政策中的物化
	MATERIALIZED	被物化政策物化的子查詢（子查詢的select列沒有空值）
EXISTS政策		DEPENDENT SUBQUERY	DEPENDENT說明了依賴的關系，EXISTS政策把子查詢變為了相關子查詢

五 進一步挖掘

五進一步挖掘