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)。
作者:毛康力
推薦閱讀:
※TiSpark (Beta) 用戶指南
※TiDB 在游族網路平台部的深度應用
※為 TiDB 重構 built-in 函數
※TiDB 幫助萬達網路科技集團實現高性能高質量的實時風控平台
※三篇文章了解 TiDB 技術內幕 —— 談調度