TiDB 源碼閱讀系列文章（八）基於代價的優化

概述

本文是 TiDB 源碼閱讀系列文章的第八篇。內文會先簡單介紹制定查詢計劃以及優化的過程，然後用較大篇幅詳述在得到邏輯計劃後，如何基於統計信息和不同的屬性選擇等生成各種不同代價的物理計劃，通過比較物理計劃的代價，最後選擇一個代價最小的物理計劃，即 Cost-Based Optimization（CBO）的過程。

優化器框架

一般優化器分兩個階段進行優化，即基於規則的優化（Rule-Based-Opimization，簡稱 RBO）和基於代價的優化（CBO）。

TiDB 主要分為兩個模塊對計划進行優化：

• 邏輯優化，主要依據關係代數的等價交換規則做一些邏輯變換。
• 物理優化，主要通過對查詢的數據讀取、表連接方式、表連接順序、排序等技術進行優化。

相比 RBO，CBO 依賴於統計信息的準確性與及時性，執行計劃會及時的根據數據變換做對應的調整。

優化器流程

TiDB 一個查詢語句的簡單流程：一個語句經過 parser 後會得到一個抽象語法樹（AST），首先用經過合法性檢查後的 AST 生成一個邏輯計劃，接著會進行去關聯化、謂詞下推、聚合下推等規則化優化，然後通過統計數據計算代價選擇最優的物理計劃，最後執行。流程如下圖 1。

物理運算元簡介

通過之前介紹物理層優化的方式，我們可以知道同一個邏輯運算元可能因為它的數據讀取、計算方式等不同會生成多個不同的物理運算元，例如邏輯上的 Join 運算元轉換成物理運算元可以選擇 HashJoin、SortMergeJoin、IndexLookupJoin。

這裡會簡單介紹一些邏輯運算元可選擇的物理運算元。例如語句：select sum(*) from t join s on t.c = s.c group by a。此語句中邏輯運算元有 DataSource、Aggregation、Join 和 Projection，接下來會對其中幾個典型的邏輯運算元對應的物理運算元進行一個簡單介紹，如下表：

CBO 流程

基於代價優化的的主要思路是計算所有可能的執行計劃的代價，並挑選代價最小的執行計劃的路徑。那麼可以倒推出，首先得到需要採集對應表的統計信息，那麼就可以用來計算出每個運算元的執行代價，最後將得到每條路徑上運算元的代價按路徑各自累加獲取代價最小的路徑。具體的代碼實現在 plan/optimizer.go 中 dagPhysicalOptimize 函數，本文介紹的流程基本上也都由此函數完成，代碼如下：

func dagPhysicalOptimize(logic LogicalPlan) (PhysicalPlan, error) { logic.preparePossibleProperties() logic.deriveStats() t, err := logic.convert2PhysicalPlan(&requiredProp{taskTp: rootTaskType, expectedCnt: math.MaxFloat64}) if err != nil { return nil, errors.Trace(err) } p := t.plan() p.ResolveIndices() return p, nil}

出於易讀性的考慮，接下來不會按代碼調用順序介紹，下面的段落與上面代碼的函數對應情況如下：

• prune prop 對應的函數 preparePossibleProperties。
• 統計信息對應的獲取函數 deriveStats。
• 其餘章節會介紹函數 convert2PhysicalPlan。

整體流程

這裡會先描述整個 CBO 的流程。這部分邏輯的主體框架在文件plan/physical_plan_builder.go ，具體處理的函數是 convert2PhysicalPlan。

例子

為了便於理解 CBO 的整個流程，這裡會由一個例子展開。

在展開前，先引入 required property，這個概念很重要。required property 是對運算元返回值數據的要求，比如希望有些運算元是按某些列有序的方式返回數據，那麼會傳對應的列信息，有些運算元是沒有要求的那麼可以傳空的 property。

那麼，現在我們舉個例子，SQL 如下：

select sum(s.a),count(t.b) from s join t on s.a = t.a and s.c < 100 and t.c > 10 group bys.a（其中 a 是索引，b 也是索引）

此語句就是基於此語句的 on 條件對錶 s 和表 t 做 join，然後對 join 結果做聚合。將其用圖表示如圖 2（此處為了與圖 3 對比，此處省略 Projection 運算元）。

得到了邏輯運算元之後，我們怎麼選擇最優的物理運算元呢？

TiDB 是用記憶化搜索來處理的。由下往上和由上往下搜索的區別不大，考慮到後者的理解性更好，且按 parent 要求的 prop 傳給 children，能減少一些可能性（這個後面會具體介紹）。我們選擇了由上往下的方式。

接下來我們來具體介紹一下這個例子中的運算元生成及選取流程。一開始的 prop 是空的，不會對 Agg 這個運算元有要求。接下來就根據當前邏輯運算元所有可能的 prop 構建對應的物理運算元，Agg 則可以生成 Stream Agg 和 Hash Agg（此邏輯在如下面代碼段的 genPhysPlansByReqProp 實現）。前者要求按 group bykey 有序，即按 a 列有序，所以他孩子的 prop 裡面會帶有 a 列。後者沒有要求，則 prop 為空。此邏輯代碼段在 plan/physical_plan_builder.go 中的：

for _, pp := range p.self.genPhysPlansByReqProp(prop) { t, err = p.getBestTask(t, pp) if err != nil { return nil, errors.Trace(err) }}

那麼 Stream Agg 的 child 是 Join，Join 對應 3 種 物理運算元，SortMerge Join（SMJ）、Hash Join（HJ）和 Index Join（IdxJ）。SMJ 運算元要求按 join key 有序，所以構建 DS（DataSource）時，需要表 s 按 s.a 有序，表 t 按 t.a 有序。所以將 DS 構建成物理運算元的時候雖然有 IdxScan（a），IdxScan（b）和 TableScan（TS），但是這些運算元中滿足 prop（s.a）只有 IdxScan（a）。這個例子中，只有 IdxScan（a）滿足要求，返回給 SMJ，如果有另外的 運算元滿足的話，就會通過代價來選取，這部分內容會在「代價評估」具體介紹。

使用記憶化搜索，將每個運算元的 prop 計算 hash 值並存儲到哈希表，所以在 HJ 算 DS（s）（帶黃色箭頭的路徑）時會發現 SMJ 下面的 DS（s）計算過了，那麼就會直接取值不做多餘計算。

篇幅有限這裡只對左側的路徑做了描述。這個例子最後一層比較是 HA + HJ + idx(c) 和 SA + MJ + idx(a) 的比較，具體也是通過統計信息就算出代價，選取最優解。

代價評估

代價評估的調用邏輯在 plan/physical_plan_builder.go 中，代碼如下：

func (p *baseLogicalPlan) getBestTask(bestTask task, pp PhysicalPlan) (task, error) { tasks := make([]task, 0, len(p.children)) for i, child := range p.children { childTask, err := child.convert2PhysicalPlan(pp.getChildReqProps(i)) if err != nil { return nil, errors.Trace(err) } tasks = append(tasks, childTask) } resultTask := pp.attach2Task(tasks...) if resultTask.cost() < bestTask.cost() { bestTask = resultTask } return bestTask, nil}

統計信息

這裡會詳細描述一下在 CBO 流程中統計信息的使用。具體採集統計信息的方法和過程，本文不具體展開，後續我們會有文章具體介紹。

一個 statesInfo 的結構有兩個欄位：

// statsInfo stores the basic information of statistics for the plans output. It is used for cost estimation.type statsInfo struct { count float64 cardinality []float64}

其中 count 欄位表示這個表的數據行數，每個表有一個值。cardinality 欄位是用於表示每一列 distinct 數據行數，每個 column 一個。cardinality 一般通過統計數據得到，也就是統計信息中對應表上對應列的 DNV（the number of distinct value）的值。此數據具體的獲取方式有兩種：

• 方式一，使用真實的統計數據，具體公式如下：

statsTable.count/ histogram.count * hist.NDV

（statsTable.count 會根據 stats lease 定期更新，histogram.count 只有用戶手動 analyze 才更新）

• 方式二，使用一個估計值，由於統計數據在某些情況下還沒有收集完成，此時沒有統計數據，具體公式如下：

statsTable.count* distinctFactor

那麼接下來我們舉兩個例子介紹通過統計數據獲取運算元的 statsInfo。

• DataSource，首先通過前面介紹的兩種公式獲取 count 和 cardinality，接著用可下推的表達式計算 selectivity 的值，selectivity = row count after filter / row count before filter，最後用計算的 selectivity 來調整原來的 count 和 cardinality 的值。
• LogicalJoin（inner join），此運算元的 count 獲取的公式：N(join(s,t)) = N(s) * N(t) / (V(s.key) * V(t.key)) *Min(V(s.key), V(t.key)) （其中 N 為表的行數，V 為 key 的 cardinality 值）

可以理解為表 s 與表 t 中不重複值的平均行數的乘積乘上小表的不重複值行數。

這裡介紹的邏輯在 stats.go 文件裡面的 plan/deriveStats 函數。

expected count

expected count 表示整個 SQL 結束前此運算元期望讀取的行數。例如 SQL：select* from swhere s.c1 < 5 order by id limit 3 (其中 c1 是索引列，id 是主鍵列)。我們可以簡單認為得到兩類可能的計劃路徑圖，如圖 4。

• 前者在 PhysicalLimit 時選擇 id 有序，那麼它的 expected count 為 3。因為有 c1 < 5 的過濾條件，所以在 TableScan 時 expected count 的值為 min(n(s)，3 / f (σ(c1<5) )) 。
• 後者在 TopN 的時候雖然知道它需要讀取 3 行，但是它是按 id 列有序，所以它的 expected count 為 Max，在 IndexScan 的時候 expected count 是 count * f (σ(c1<5)。

Task

在代價評估時將物理運算元關聯到 task 這個對象結構。task 分為三種類型，分別是 cop single, cop double 和 root。前兩種類型都可以下推到 coprocessor 執行。將其區分類型有兩個原因：一個是它可以區分對應的運算元是在 TiDB 處理還是被下推到 TiKV 的 coprocessor 處理；另外一個比較重要的原因是為了評估代價時更加準確。

這裡我們舉個例子，SQL 如下：

select *from t where c < 1 and b < 1 and a = 1 (其中 (a,b) 是索引, (b,a,c) 是索引，表 t 有 a、b 和 c 三列)

那麼可以得到如下兩種路徑：

• doubleread（即 IndexLookUpReader ）：IndexScan( a = 1 and b < 1 ) -> TableScan-> Selection(c < 1)
• singleread（即 IndexReader）：IndexScan( b < 1 ) -> Selection( a = 1 and c < 1 )

不區分 cop single 和 cop double 的時候，去搜索最底層，這會導致情況二被提前捨棄。但是實際上這兩種路徑，在第一種路徑考慮向 TiKV 讀兩次數據的情況後，其代價很有可能超過第二種路徑。所以我們會區分 copsingle 和 cop double，不在 IndexScan 的時候比較，而是在 Selection 結束的時候再比較開銷，那麼就很可能選第二種計劃路徑。這樣就比較符合實際情況。

我們通用的計算代價的公式：

Cost(p) = N(p)*FN+M(p)*FM+C(p)*FC （其中 N 表示網路開銷，M 表示內存開銷，C 表示 CPU 開銷，F 表示因子）

將 plan 與 task 關聯，並加上此 plan 的 cost。

task 處理的代碼主要在文件 plan/task.go 中。

prune properties

引入預處理 property 函數的原因是為了減少一些沒有必要考慮的 properties，從而儘可能早的裁減掉成物理計劃搜索路徑上的分支，例如：

select *from t join s on t.A = s.A and t.B = s.B

它的 property 可以是 {A, B}, {B, A}。

如果我們有 n 個等式條件，那麼我們會有 n! 種可能的 property。如果有了此操作，我們只能使用 t 表和 s 表本身擁有的 properties。

properties 是在 DataSource 這個 logical 運算元中獲取的，因為此運算元中可以得到對應的主鍵和索引信息。

此處邏輯由文件 plan/property_cols_prune.go 里的 preparePossibleProperties 函數處理。

作者：李霞

推薦閱讀：