摘要：概述本文是源碼閱讀系列文章的第八篇。圖中黑色字體算子為邏輯算子，藍色字體為物理算子，黃色箭頭為已經計算過代價的算子，會獲取已經緩存在哈希表中的結果，紅色虛線箭頭為不符合的算子。

本文是 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，接下來會對其中幾個典型的邏輯算子對應的物理算子進行一個簡單介紹，如下表：

基于代價優化的的主要思路是計算所有可能的執行計劃的代價，并挑選代價最小的執行計劃的路徑。那么可以倒推出，首先得到需要采集對應表的統計信息，那么就可以用來計算出每個算子的執行代價，最后將得到每條路徑上算子的代價按路徑各自累加獲取代價最小的路徑。具體的代碼實現在 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) 的比較，具體也是通過統計信息就算出代價，選取最優解。

（圖中黑色字體算子為邏輯算子，藍色字體為物理算子，黃色箭頭為已經計算過代價的算子，會獲取已經緩存在哈希表中的結果，紅色虛線箭頭為不符合 prop 的算子。）

代價評估的調用邏輯在 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 plan"s 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 表示整個 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 分為三種類型，分別是 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 中。

引入預處理 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 函數處理。

作者：李霞