TiDB 源碼閱讀系列文章（七）基於規則的優化

在 TiDB 裡面，SQL 優化的過程可以分為邏輯優化和物理優化兩個部分。邏輯優化主要是基於規則的優化，簡稱 RBO（rule based optimization）。物理優化會為邏輯查詢計劃中的運算元選擇某個具體的實現，需要用到一些統計信息，決定哪一種方式代價最低，所以是基於代價的優化 CBO（cost based optimization）。

本篇將主要關注邏輯優化。先介紹 TiDB 中的邏輯運算元，然後介紹 TiDB 的邏輯優化規則，包括列裁剪、最大最小消除、投影消除、謂詞下推、TopN 下推等等。

邏輯運算元介紹

在寫具體的優化規則之前，先簡單介紹查詢計劃裡面的一些邏輯運算元。

• DataSource 這個就是數據源，也就是表，select * from t 裡面的 t
• Selection 選擇，例如 select xxx from t where xx = 5 裡面的 where 過濾條件
• Projection 投影， select c from t 裡面的取 c 列是投影操作
• Join 連接， select xx from t1, t2 where t1.c = t2.c 就是把 t1 t2 兩個表做 Join

選擇，投影，連接（簡稱 SPJ） 是最基本的運算元。其中 Join 有內連接，左外右外連接等多種連接方式。

select b from t1, t2 where t1.c = t2.c and t1.a > 5

變成邏輯查詢計劃之後，t1 t2 對應的 DataSource，負責將數據撈上來。上面接個 Join 運算元，將兩個表的結果按 t1.c = t2.c 連接，再按 t1.a > 5 做一個 Selection 過濾，最後將 b 列投影。下圖是未經優化的表示：

• Sort 就是 select xx from xx order by 裡面的 order by 。
• Aggregation，在 select sum(xx) from xx group by yy 中的 group by 操作，按某些列分組。分組之後，可能帶一些聚合函數，比如 Max/Min/Sum/Count/Average 等，這個例子裡面是一個 sum。
• Apply 這個是用來做子查詢的。

列裁剪

列裁剪的思想是這樣的：對於用不上的列，沒有必要讀取它們的數據，無謂的浪費 IO 資源。比如說表 t 裡面有 a b c d 四列。

select a from t where b > 5

這個查詢裡面明顯只有 a b 兩列被用到了，所以 c d 的數據是不需要讀取的。在查詢計劃裡面，Selection 運算元用到 b 列，下面接一個 DataSource 用到了 a b 兩列，剩下 c 和 d 都可以裁剪掉，DataSource 讀數據時不需要將它們讀進來。

列裁剪的演算法實現是自頂向下地把運算元過一遍。某個結點需要用到的列，等於它自己需要用到的列，加上它的父親結點需要用到的列。可以發現，由上往下的結點，需要用到的列將越來越多。代碼是在 plan/column_pruning.go 文件裡面。

列裁剪主要影響的運算元是 Projection，DataSource，Aggregation，因為它們跟列直接相關。Projection 裡面會裁掉用不上的列，DataSource 裡面也會裁剪掉不需要使用的列。

Aggregation 運算元會涉及哪些列？group by 用到的列，以及聚合函數裡面引用到的列。比如 select avg(a), sum(b) from t group by c d，這裡面 group by 用到的 c 和 d 列，聚合函數用到的 a 和 b 列。所以這個 Aggregation 使用到的就是 a b c d 四列。

Selection 做列裁剪時，要看它父親要哪些列，然後它自己的條件裡面要用到哪些列。Sort 就看 order by 裡面用到了哪些列。Join 則要把連接條件中用到的各種列都算進去。具體的代碼裡面，各個運算元都是實現 PruneColumns 介面：

func (p *LogicalPlan) PruneColumns(parentUsedCols []*expression.Column)

通過列裁剪這一步操作之後，查詢計劃裡面各個運算元，只會記錄下它實際需要用到的那些列。

最大最小消除

最大最小消除，會對 Min/Max 語句進行改寫。

select min(id) from t

我們用另一種寫法，可以做到類似的效果：

select id from t order by id desc limit 1

這個寫法有什麼好處呢？前一個語句，生成的執行計劃，是一個 TableScan 上面接一個 Aggregation，也就是說這是一個全表掃描的操作。後一個語句，生成執行計劃是 TableScan + Sort + Limit。

在某些情況，比如 id 是主鍵或者是存在索引，數據本身有序， Sort 就可以消除，最終變成 TableScan 或者 IndexLookUp 接一個 Limit，這樣子就不需要全表掃了，只需要讀到第一條數據就得到結果！全表掃操作跟只查一條數據，性能上可是天壤之別。

最大最小消除，做的事情就是由 SQL 優化器「自動」地做這個變換。

select max(id) from t

生成的查詢樹會被轉換成下面這種：

select max(id) from (select id from t order by id desc limit 1 where id is not null) t

這個變換複雜一些是要處理 NULL 的情況。經過這步變換之後，還會執行其它變換。所以中間生成的額外的運算元，可能在其它變換裡面被繼續修改掉。

min 也是類似的語句替換。相應的代碼是在 max_min_eliminate.go 文件裡面。實現是一個純粹的 AST 結構的修改。

投影消除

投影消除可以把不必要的 Projection 運算元消除掉。那麼，什麼情況下，投影運算元是可消除的呢？

首先，如果 Projection 運算元要投影的列，跟它的孩子結點的輸出列，是一模一樣的，那麼投影步驟就是一個無用操作，可以消除。比如 select a,b from t 在表 t 裡面就正好就是 a b 兩列，那就沒必要 TableScan 上面再做一次 Projection。

然後，投影運算元下面的孩子結點，又是另一個投影運算元，那麼孩子結點的投影操作就沒有意義，可以消除。比如 Projection(A) -> Projection(A,B,C) 只需要保留 Projection(A) 就夠了。

類似的，在投影消除規則裡面，Aggregation 跟 Projection 操作很類似。因為從 Aggregation 結點出來的都是具體的列，所以 Aggregation(A) -> Projection(A,B,C) 中，這個 Projection 也可以消除。

代碼是在 eliminate_projection.go 裡面。

func eliminate(p Plan, canEliminate bool) { 對 p 的每個孩子，遞歸地調用 eliminate 如果 p 是 Project 如果 canEliminate 為真 消除 p 如果 p 的孩子的輸出列，跟 p 的輸出列相同，消除 p }

注意 canEliminate 參數，它是代表是否處於一個可被消除的「上下文」裡面。比如 Projection(A) -> Projection(A, B, C) 或者 Aggregation -> Projection 遞歸調用到孩子結點 Projection 時，該 Projection 就處理一個 canEliminate 的上下文。

簡單解釋就是，一個 Projection 結點是否可消除：

• 一方面由它父結點告訴它，它是否是一個冗餘的 Projection 操作。
• 另一方面由它自己和孩子結點的輸入列做比較，輸出相同則可消除。

謂詞下推

謂詞下推是非常重要的一個優化。比如

select * from t1, t2 where t1.a > 3 and t2.b > 5

假設 t1 和 t2 都是 100 條數據。如果把 t1 和 t2 兩個表做笛卡爾集了再過濾，我們要處理 10000 條數據，而如果能先做過濾條件，那麼數據量就會大量減少。謂詞下推會盡量把過濾條件，推到靠近葉子節點，從而減少數據訪問，節省計算開銷。這就是謂詞下推的作用。

謂詞下推的介面函數類似是這樣子的：

func (p *baseLogicalPlan) PredicatePushDown(predicates []expression.Expression) ([]expression.Expression, LogicalPlan)

PredicatePushDown 函數處理當前的查詢計劃 p，參數 predicates 表示要添加的過濾條件。函數返回值是無法下推的條件，以及生成的新 plan。

這個函數會把能推的條件盡量往下推，推不下去的條件，做到一個 Selection 運算元裡面，然後連接在節點 p 上面，形成新的 plan。比如說現在有條件 a > 3 AND b = 5 AND c < d，其中 a > 3 和 b = 5 都推下去了，那剩下就接一個 c < d 的 Selection。

我們看一下 Join 運算元是如何做謂詞下推的。代碼是在 plan/predicate_push_down.go 文件。

首先會做一個簡化，將左外連接和右外連接轉化為內連接。

什麼情況下外連接可以轉內連接？左向外連接的結果集包括左表的所有行，而不僅僅是連接列所匹配的行。如果左表的某行在右表中沒有匹配的行，則在結果集右邊補 NULL。做謂詞下推時，如果我們知道接下來的的謂詞條件一定會把包含 NULL 的行全部都過濾掉，那麼做外連接就沒意義了，可以直接改寫成內連接。

什麼情況會過濾掉 NULL 呢？比如，某個謂詞的表達式用 NULL 計算後會得到 false；或者謂詞裡面用 OR 條件連接，其中一個會過濾 NULL；又或者用 AND 條件連接，其中每個都是過濾 NULL 的。術語裡面 OR 條件連接叫做析取範式 DNF (disjunctive normal form)。對應的還有合取範式 CNF (conjunctive normal form)。TiDB 的代碼裡面用到這種縮寫。

接下來，把所有條件全收集起來，然後區分哪些是 Join 的等值條件，哪些是 Join 需要用到的條件，哪些全部來自於左孩子，哪些全部來自於右孩子。

區分之後，對於內連接，可以把左條件，和右條件，分別向左右孩子下推。等值條件和其它條件保留在當前的 Join 運算元中，剩下的返回。

謂詞下推不能推過 MaxOneRow 和 Limit 節點。因為先 Limit N 行，然後再做 Selection 操作，跟先做 Selection 操作，再 Limit N 行得到的結果是不一樣的。比如數據是 1 到 100，先 Limit 10 再 Select 大於 5，得到的是 5 到 10，而先做 Selection 再做 Limit 得到的是 5 到 15。MaxOneRow 也是同理，跟 Limit 1 效果一樣。

DataSource 運算元很簡單，會直接把過濾條件加入到 CopTask 裡面。最後會被通過 coprocessor 推給 TiKV 去做。

構建節點屬性

在 build_key_info.go 文件裡面，會構建 unique key 和 MaxOneRow 屬性。這一步不是在做優化，但它是在構建優化過程需要用到的一些信息。

build_key_info 是在收集關於唯一索引的信息。我們知道某些列是主鍵或者唯一索引列，這種情況該列不會在多個相同的值。只有葉子節點知道這個信息。`build_key_info` 就是要將這個信息，從葉子節點，傳遞到 LogicalPlan 樹上的所有節點，讓每個節點都知道這些屬性。

對於 DataSource，對於主鍵列，和唯一索引列，都是 unique key。注意處理 NULL，需要列是帶有 NotNull 標記的，以及考慮聯合索引。

對於 Projection，它的孩子中的唯一索引列信息，跟它的投影表達式的列取交集。比如 a b c 列都是唯一索引，投影其中的 b 列，輸入的 b 列仍然具有值唯一的屬性。

如果一個節點輸出肯定只有一行，這個節點會設置一個 MaxOneRow 屬性。哪些情況節點輸出只有一行呢？

• 如果一個運算元的孩子是 MaxOneRow 運算元。
• 如果是 Limit 1，可以設置 MaxOneRow。
• 如果是 Selection，並且過濾條件是一個唯一索引列等於某常量。
• Join 運算元，如果它的左右孩子都是 MaxOneRow 屬性。

總結

這是基於規則優化（RBO）的上篇。介紹了邏輯查詢計劃裡面基本的運算元，以及一部分的優化規則。後續我們還將介紹更多的優化規則，以及基於代價的優化（CBO）。

作者：毛康力

推薦閱讀：