標籤:

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 技術內幕 —— 談調度

TAG:TiDB | SQL | NewSQL |