作者：姚珂男

在 TiDB 源碼閱讀系列文章（七）基于規(guī)則的優(yōu)化 一文中，我們介紹了幾種 TiDB 中的邏輯優(yōu)化規(guī)則，包括列剪裁，最大最小消除，投影消除，謂詞下推和構(gòu)建節(jié)點(diǎn)屬性，本篇將繼續(xù)介紹更多的優(yōu)化規(guī)則：聚合消除、外連接消除和子查詢優(yōu)化。

聚合消除會(huì)檢查 SQL 查詢中 Group By 語句所使用的列是否具有唯一性屬性，如果滿足，則會(huì)將執(zhí)行計(jì)劃中相應(yīng)的 LogicalAggregation 算子替換為 LogicalProjection 算子。這里的邏輯是當(dāng)聚合函數(shù)按照具有唯一性屬性的一列或多列分組時(shí)，下層算子輸出的每一行都是一個(gè)多帶帶的分組，這時(shí)就可以將聚合函數(shù)展開成具體的參數(shù)列或者包含參數(shù)列的普通函數(shù)表達(dá)式，具體的代碼實(shí)現(xiàn)在 rule_aggregation_elimination.go 文件中。下面舉一些具體的例子。

例一：

下面這個(gè) Query 可以將聚合函數(shù)展開成列的查詢：

select max(a) from t group by t.pk;

被等價(jià)地改寫成：

select a from t;

例二：

下面這個(gè) Query 可以將聚合函數(shù)展開為包含參數(shù)列的內(nèi)置函數(shù)的查詢：

select count(a) from t group by t.pk;

被等價(jià)地改寫成：

select if(isnull(a), 0, 1) from t;

這里其實(shí)還可以做進(jìn)一步的優(yōu)化：如果列 a 具有 Not Null 的屬性，那么可以將 if(isnull(a), 0, 1) 直接替換為常量 1（目前 TiDB 還沒做這個(gè)優(yōu)化，感興趣的同學(xué)可以來貢獻(xiàn)一個(gè) PR）。

另外提一點(diǎn)，對(duì)于大部分聚合函數(shù)，參數(shù)的類型和返回結(jié)果的類型一般是不同的，所以在展開聚合函數(shù)的時(shí)候一般會(huì)在參數(shù)列上構(gòu)造 cast 函數(shù)做類型轉(zhuǎn)換，展開后的表達(dá)式會(huì)保存在作為替換 LogicalAggregation 算子的 LogicalProjection 算子中。

這個(gè)優(yōu)化過程中，有一點(diǎn)非常關(guān)鍵，就是如何知道 Group By 使用的列是否滿足唯一性屬性，尤其是當(dāng)聚合算子的下層節(jié)點(diǎn)不是 DataSource 的時(shí)候？我們?cè)?（七）基于規(guī)則的優(yōu)化 一文中的“構(gòu)建節(jié)點(diǎn)屬性”章節(jié)提到過，執(zhí)行計(jì)劃中每個(gè)算子節(jié)點(diǎn)會(huì)維護(hù)這樣一個(gè)信息：當(dāng)前算子的輸出會(huì)按照哪一列或者哪幾列滿足唯一性屬性。因此，在聚合消除中，我們可以通過查看下層算子保存的這個(gè)信息，再結(jié)合 Group By 用到的列判斷當(dāng)前聚合算子是否可以被消除。

不同于 （七）基于規(guī)則的優(yōu)化 一文中“謂詞下推”章節(jié)提到的將外連接轉(zhuǎn)換為內(nèi)連接，這里外連接消除指的是將整個(gè)連接操作從查詢中移除。

外連接消除需要滿足一定條件：

條件 1 : LogicalJoin 的父親算子只會(huì)用到 LogicalJoin 的 outer plan 所輸出的列

條件 2 :

條件 2.1 : LogicalJoin 中的 join key 在 inner plan 的輸出結(jié)果中滿足唯一性屬性

條件 2.2 : LogicalJoin 的父親算子會(huì)對(duì)輸入的記錄去重

條件 1 和條件 2 必須同時(shí)滿足，但條件 2.1 和條件 2.2 只需滿足一條即可。

滿足條件 1 和 條件 2.1 的一個(gè)例子：

select t1.a from t1 left join t2 on t1.b = t2.pk;

可以被改寫成：

select t1.a from t1;

滿足條件 1 和條件 2.2 的一個(gè)例子：

select distinct(t1.a) from t1 left join t2 on t1.b = t2.b;

可以被改寫成：

select distinct(t1.a) from t1;

具體的原理是，對(duì)于外連接，outer plan 的每一行記錄肯定會(huì)在連接的結(jié)果集里出現(xiàn)一次或多次，當(dāng) outer plan 的行不能找到匹配時(shí)，或者只能找到一行匹配時(shí)，這行 outer plan 的記錄在連接結(jié)果中只出現(xiàn)一次；當(dāng) outer plan 的行能找到多行匹配時(shí)，它會(huì)在連接結(jié)果中出現(xiàn)多次；那么如果 inner plan 在 join key 上滿足唯一性屬性，就不可能存在 outer plan 的行能夠找到多行匹配，所以這時(shí) outer plan 的每一行都會(huì)且僅會(huì)在連接結(jié)果中出現(xiàn)一次。同時(shí)，上層算子只需要 outer plan 的數(shù)據(jù)，那么外連接可以直接從查詢中被去除掉。同理就可以很容易理解當(dāng)上層算子只需要 outer plan 的去重后結(jié)果時(shí)，外連接也可以被消除。

這部分優(yōu)化的具體代碼實(shí)現(xiàn)在 rule_join_elimination.go 文件中。

子查詢分為非相關(guān)子查詢和相關(guān)子查詢，例如：

-- 非相關(guān)子查詢
select * from t1 where t1.a > (select t2.a from t2 limit 1);
-- 相關(guān)子查詢
select * from t1 where t1.a > (select t2.a from t2 where t2.b > t1.b limit 1);

對(duì)于非相關(guān)子查詢， TiDB 會(huì)在 expressionRewriter 的邏輯中做兩類操作：

子查詢展開

即直接執(zhí)行子查詢獲得結(jié)果，再利用這個(gè)結(jié)果改寫原本包含子查詢的表達(dá)式；比如上述的非相關(guān)子查詢，如果其返回的結(jié)果為一行記錄 “1” ，那么整個(gè)查詢會(huì)被改寫為：

select * from t1 where t1.a > 1;

詳細(xì)的代碼邏輯可以參考 expression_rewriter.go 中的 handleScalarSubquery 和 handleExistSubquery 函數(shù)。

子查詢轉(zhuǎn)為 Join

對(duì)于包含 IN (subquery) 的查詢，比如：

select * from t1 where t1.a in (select t2.a from t2);

會(huì)被改寫成：

select t1.* from t1 inner join (select distinct(t2.a) as a from t2) as sub on t1.a = sub.a;

如果 t2.a 滿足唯一性屬性，根據(jù)上面介紹的聚合消除規(guī)則，查詢會(huì)被進(jìn)一步改寫成：

select t1.* from t1 inner join t2 on t1.a = t2.a;

這里選擇將子查詢轉(zhuǎn)化為 inner join 的 inner plan 而不是執(zhí)行子查詢的原因是：以上述查詢?yōu)槔硬樵兊慕Y(jié)果集可能會(huì)很大，展開子查詢需要一次性將 t2 的全部數(shù)據(jù)從 TiKV 返回到 TiDB 中緩存，并作為 t1 掃描的過濾條件；如果將子查詢轉(zhuǎn)化為 inner join 的 inner plan ，我們可以更靈活地對(duì) t2 選擇訪問方式，比如我們可以對(duì) join 選擇 IndexLookUpJoin 實(shí)現(xiàn)方式，那么對(duì)于拿到的每一條 t1 表數(shù)據(jù)，我們只需拿 t1.a 作為 range 對(duì) t2 做一次索引掃描，如果 t1 表很小，相比于展開子查詢返回 t2 全部數(shù)據(jù)，我們可能總共只需要從 t2 返回很少的幾條數(shù)據(jù)。

注意這個(gè)轉(zhuǎn)換的結(jié)果不一定會(huì)比展開子查詢更好，其具體情況會(huì)受 t1 表和 t2 表數(shù)據(jù)的影響，如果在上述查詢中， t1 表很大而 t2 表很小，那么展開子查詢?cè)賹?duì) t1 選擇索引掃描可能才是最好的方案，所以現(xiàn)在有參數(shù)控制這個(gè)轉(zhuǎn)化是否打開，詳細(xì)的代碼可以參考 expression_rewriter.go 中的 handleInSubquery 函數(shù)。

對(duì)于相關(guān)子查詢，TiDB 會(huì)在 expressionRewriter 中將整個(gè)包含相關(guān)子查詢的表達(dá)式轉(zhuǎn)化為 LogicalApply 算子。LogicalApply 算子是一類特殊的 LogicalJoin ，特殊之處體現(xiàn)在執(zhí)行邏輯上：對(duì)于 outer plan 返回的每一行記錄，取出相關(guān)列的具體值傳遞給子查詢，再執(zhí)行根據(jù)子查詢生成的 inner plan ，即 LogicalApply 在執(zhí)行時(shí)只能選擇類似循環(huán)嵌套連接的方式，而普通的 LogicalJoin 則可以在物理優(yōu)化階段根據(jù)代價(jià)模型選擇最合適的執(zhí)行方式，包括 HashJoin，MergeJoin 和 IndexLookUpJoin，理論上后者生成的物理執(zhí)行計(jì)劃一定會(huì)比前者更優(yōu)，所以在邏輯優(yōu)化階段我們會(huì)檢查是否可以應(yīng)用“去相關(guān)”這一優(yōu)化規(guī)則，試圖將 LogicalApply 轉(zhuǎn)化為等價(jià)的 LogicalJoin 。其核心思想是將 LogicalApply 的 inner plan 中包含相關(guān)列的那些算子提升到 LogicalApply 之中或之上，在算子提升后如果 inner plan 中不再包含任何的相關(guān)列，即不再引用任何 outer plan 中的列，那么 LogicalApply 就會(huì)被轉(zhuǎn)換為普通的 LogicalJoin ，這部分代碼邏輯實(shí)現(xiàn)在 rule_decorrelate.go 文件中。

具體的算子提升方式分為以下幾種情況：

inner plan 的根節(jié)點(diǎn)是 LogicalSelection

則將其過濾條件添加到 LogicalApply 的 join condition 中，然后將該 LogicalSelection 從 inner plan 中刪除，再遞歸地對(duì) inner plan 提升算子。

以如下查詢?yōu)槔?/p>

select * from t1 where t1.a in (select t2.a from t2 where t2.b = t1.b);

其生成的最初執(zhí)行計(jì)劃片段會(huì)是：

LogicalSelection 提升后會(huì)變成如下片段：

到此 inner plan 中不再包含相關(guān)列，于是 LogicalApply 會(huì)被轉(zhuǎn)換為如下 LogicalJoin ：

inner plan 的根節(jié)點(diǎn)是 LogicalMaxOneRow

即要求子查詢最多輸出一行記錄，比如這個(gè)例子：

select *, (select t2.a from t2 where t2.pk = t1.a) from t1;

因?yàn)樽硬樵兂霈F(xiàn)在整個(gè)查詢的投影項(xiàng)里，所以 expressionRewriter 在處理子查詢時(shí)會(huì)對(duì)其生成的執(zhí)行計(jì)劃在根節(jié)點(diǎn)上加一個(gè) LogicalMaxOneRow 限制最多產(chǎn)生一行記錄，如果在執(zhí)行時(shí)發(fā)現(xiàn)下層輸出多于一行記錄，則會(huì)報(bào)錯(cuò)。在這個(gè)例子中，子查詢的過濾條件是?t2 表的主鍵上的等值條件，所以子查詢肯定最多只會(huì)輸出一行記錄，而這個(gè)信息在“構(gòu)建節(jié)點(diǎn)屬性”這一步時(shí)會(huì)被發(fā)掘出來并記錄在算子節(jié)點(diǎn)的 MaxOneRow 屬性中，所以這里的 LogicalMaxOneRow 節(jié)點(diǎn)實(shí)際上是冗余的，于是我們可以將其從 inner plan 中移除，然后再遞歸地對(duì) inner plan 做算子提升。

inner plan 的根節(jié)點(diǎn)是 LogicalProjection

則首先將這個(gè)投影算子從 inner plan 中移除，再根據(jù) LogicalApply 的連接類型判斷是否需要在 LogicalApply 之上再加上一個(gè) LogicalProjection ，具體來說是：對(duì)于非 semi-join 這一類的連接（包括 inner join 和 left join ），inner plan 的輸出列會(huì)保留在 LogicalApply 的結(jié)果中，所以這個(gè)投影操作需要保留，反之則不需要。最后，再遞歸地對(duì)刪除投影后的 inner plan 提升下層算子。

inner plan 的根節(jié)點(diǎn)是 LogicalAggregation

首先我們會(huì)檢查這個(gè)聚合算子是否可以被提升到 LogicalApply 之上再執(zhí)行。以如下查詢?yōu)槔?/p>

select *, (select sum(t2.b) from t2 where t2.a = t1.pk) from t1;

其最初生成的執(zhí)行計(jì)劃片段會(huì)是：

將聚合提升到 LogicalApply 后的執(zhí)行計(jì)劃片段會(huì)是：

即先對(duì) t1 和 t2 做連接，再在連接結(jié)果上按照 t1.pk 分組后做聚合。這里有兩個(gè)關(guān)鍵變化：第一是不管提升前 LogicalApply 的連接類型是 inner join 還是 left join ，提升后必須被改為 left join ；第二是提升后的聚合新增了 Group By 的列，即要按照 outer plan 傳進(jìn) inner plan 中的相關(guān)列做分組。這兩個(gè)變化背后的原因都會(huì)在后面進(jìn)行闡述。因?yàn)樘嵘?inner plan 不再包含相關(guān)列，去相關(guān)后最終生成的執(zhí)行計(jì)劃片段會(huì)是：

聚合提升有很多限定條件：

LogicalApply 的連接類型必須是 inner join 或者 left join 。 LogicalApply 是根據(jù)相關(guān)子查詢生成的，只可能有 3 類連接類型，除了 inner join 和 left join 外，第三類是 semi join （包括 SemiJoin，LeftOuterSemiJoin，AntiSemiJoin，AntiLeftOuterSemiJoin），具體可以參考 expression_rewriter.go 中的代碼，限于篇幅在這里就不對(duì)此做展開了。對(duì)于 semi join 類型的 LogicalApply ，因?yàn)?inner plan 的輸出列不會(huì)出現(xiàn)在連接的結(jié)果中，所以很容易理解我們無法將聚合算子提升到 LogicalApply 之上。

LogicalApply 本身不能包含 join condition 。以上面給出的查詢?yōu)槔梢钥吹骄酆咸嵘髸?huì)將子查詢中包含相關(guān)列的過濾條件 (t2.a = t1.pk) 添加到 LogicalApply 的 join condition 中，如果 LogicalApply 本身存在 join condition ，那么聚合提升后聚合算子的輸入（連接算子的輸出）就會(huì)和在子查詢中時(shí)聚合算子的輸入不同，導(dǎo)致聚合算子結(jié)果不正確。

子查詢中用到的相關(guān)列在 outer plan 輸出里具有唯一性屬性。以上面查詢?yōu)槔?，如?t1.pk 不滿足唯一性，假設(shè) t1 有兩條記錄滿足 t1.pk = 1，t2 只有一條記錄 { (t2.a: 1, t2.b: 2) } ，那么該查詢會(huì)輸出兩行結(jié)果 { (sum(t2.b): 2), (sum(t2.b): 2) } ；但對(duì)于聚合提升后的執(zhí)行計(jì)劃，則會(huì)生成錯(cuò)誤的一行結(jié)果 { (sum(t2.b): 4) } 。當(dāng) t1.pk 滿足唯一性后，每一行 outer plan 的記錄都對(duì)應(yīng)連接結(jié)果中的一個(gè)分組，所以其聚合結(jié)果會(huì)和在子查詢中的聚合結(jié)果一致，這也解釋了為什么聚合提升后需要按照 t1.pk 做分組。

聚合函數(shù)必須滿足當(dāng)輸入為 null 時(shí)輸出結(jié)果也一定是 null 。這是為了在子查詢中沒有匹配的特殊情況下保證結(jié)果的正確性，以上面查詢?yōu)槔?，?dāng) t2 表沒有任何記錄滿足 t2.a = t1.pk 時(shí)，子查詢中不管是什么聚合函數(shù)都會(huì)返回 null 結(jié)果，為了保留這種特殊情況，在聚合提升的同時(shí)， LogicalApply 的連接類型會(huì)被強(qiáng)制改為 left join（改之前可能是 inner join ），所以在這種沒有匹配的情況下，LogicalApply 輸出結(jié)果中 inner plan 部分會(huì)是 null ，而這個(gè) null 會(huì)作為新添加的聚合算子的輸入，為了和提升前結(jié)果一致，其結(jié)果也必須是 null 。

對(duì)于根據(jù)上述條件判定不能提升的聚合算子，我們?cè)贆z查這個(gè)聚合算子的子節(jié)點(diǎn)是否為 LogicalSelection ，如果是，則將其從 inner plan 中移除并將過濾條件添加到 LogicalApply 的 join condition 中。這種情況下 LogicalAggregation 依然會(huì)被保留在 inner plan 中，但會(huì)將 LogicalSelection 過濾條件中涉及的 inner 表的列添加到聚合算子的 Group By 中。比如對(duì)于查詢：

select *, (select count(*) from t2 where t2.a = t1.a) from t1;

其生成的最初的執(zhí)行計(jì)劃片段會(huì)是：

因?yàn)榫酆虾瘮?shù)是 count(*) ，不滿足當(dāng)輸入為 null 時(shí)輸出也為 null 的條件，所以它不能被提升到 LogicalApply 之上，但它可以被改寫成：

注意 LogicalAggregation 的 Group By 新加了 t2.a ，這一步將原本的先做過濾再做聚合轉(zhuǎn)換為了先按照 t2.a 分組做聚合，再將聚合結(jié)果與 t1 做連接。 LogicalSelection 提升后 inner plan 已經(jīng)不再依賴 outer plan 的結(jié)果了，整個(gè)查詢?nèi)ハ嚓P(guān)后將會(huì)變?yōu)椋?/p>

這是基于規(guī)則優(yōu)化的第二篇文章，后續(xù)我們還將介紹更多邏輯優(yōu)化規(guī)則：聚合下推，TopN 下推和 Join Reorder 。