TiDB 原始碼閱讀系列文章(八)基於代價的優化

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

概述

本文是 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) 的比較,具體也是通過統計資訊就算出代價,選取最優解。

(圖中黑色字型運算元為邏輯運算元,藍色字型為物理運算元,黃色箭頭為已經計算過代價的運算元,會獲取已經快取在雜湊表中的結果,紅色虛線箭頭為不符合 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

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 函式處理。

作者:李霞

相關文章

資料庫 最新文章