十分鐘成為 Contributor 系列 | 助力 TiDB 表達式計算性能提升 10 倍

• 2019 年 10 月 4 日
• 筆記

最近我們擴展了 TiDB 表達式計算框架，增加了向量化計算介面，初期的性能測試顯示，多數表達式計算性能可大幅提升，部分甚至可提升 1~2 個數量級。為了讓所有的表達式都能受益，我們需要為所有內建函數實現向量化計算。

TiDB 的向量化計算是在經典 Volcano 模型上的進行改進，儘可能利用 CPU Cache，SIMD Instructions，Pipeline，Branch Predicatation 等硬體特性提升計算性能，同時降低執行框架的迭代開銷，這裡提供一些參考文獻，供感興趣的同學閱讀和研究：

1. MonetDB/X100: Hyper-Pipelining Query Execution
2. Balancing Vectorized Query Execution with Bandwidth-Optimized Storage
3. The Design and Implementation of Modern Column-Oriented Database Systems

在這篇文章中，我們將描述：

1. 如何在計算框架下實現某個函數的向量化計算；
2. 如何在測試框架下做正確性和性能測試；
3. 如何參與進來成為 TiDB Contributor。

表達式向量化

1. 如何訪問和修改一個向量

在 TiDB 中，數據按列在記憶體中連續存在 Column 內，Column 詳細介紹請看：TiDB 源碼閱讀系列文章（十）Chunk 和執行框架簡介。本文所指的向量，其數據正是存儲在 Column 中。

我們把數據類型分為兩種：

1. 定長類型：Int64、Uint64、Float32、Float64、Decimal、Time、Duration；
2. 變長類型：String、Bytes、JSON、Set、Enum。

定長類型和變長類型數據在 Column 中有不同的組織方式，這使得他們有如下的特點：

1. 定長類型的 Column 可以隨機讀寫任意元素；
2. 變長類型的 Column 可以隨機讀，但更改中間某元素後，可能需要移動該元素後續所有元素，導致隨機寫性能很差。

對於定長類型（如 int64），我們在計算時會將其轉成 Golang Slice（如 []int64），然後直接讀寫這個 Slice。相比於調用 Column 的介面，需要的 CPU 指令更少，性能更好。同時，轉換後的 Slice 仍然引用著 Column 中的記憶體，修改後不用將數據從 Slice 拷貝到 Column 中，開銷降到了最低。

對於變長類型，元素長度不固定，且為了保證元素在記憶體中連續存放，所以不能直接用 Slice 的方式隨機讀寫。我們規定變長類型數據以追加寫（append）的方式更新，用 Column 的 Get() 介面進行讀取。

總的來說，變長和定長類型的讀寫方式如下：

1. 定長類型（以 int64 為例)

a. `ResizeInt64s(size, isNull)`：預分配 size 個元素的空間，並把所有位置的 `null` 標記都設置為 `isNull`；

b.  `Int64s()`：返回一個 `[]int64` 的 Slice，用於直接讀寫數據；

c.  `SetNull(rowID, isNull)`：標記第 `rowID` 行為 `isNull`。

1. 變長類型（以 string 為例）

a. `ReserveString(size)`：預估 size 個元素的空間，並預先分配記憶體；

b. `AppendString(string)`: 追加一個 string 到向量末尾；

c.  `AppendNull()`：追加一個 `null` 到向量末尾；

d.  `GetString(rowID)`：讀取下標為 `rowID` 的 string 數據。

當然還有些其他的方法如 IsNull(rowID)，MergeNulls(cols) 等，就交給大家自己去探索了，後面會有這些方法的使用例子。

2. 表達式向量化計算框架

向量化的計算介面大概如下（完整的定義在這裡）：

vectorized() bool  vecEvalXType(input *Chunk, result *Column) error

• XType 可能表示 Int, String 等，不同的函數需要實現不同的介面；
• input 表示輸入數據，類型為 *Chunk；
• result 用來存放結果數據。

外部執行運算元（如 Projection，Selection 等運算元），在調用表達式介面進行計算前，會通過 vectorized() 來判斷此表達式是否支援向量化計算，如果支援，則調用向量化介面，否則就走行式介面。

對於任意表達式，只有當其中所有函數都支援向量化後，才認為這個表達式是支援向量化的。

比如 (2+6)*3，只有當 MultiplyInt 和 PlusInt 函數都向量化後，它才能被向量化執行。

為函數實現向量化介面

要實現函數向量化，還需要為其實現 vecEvalXType() 和 vectorized() 介面。

• 在 vectorized() 介面中返回 true ，表示該函數已經實現向量化計算；
• 在 vecEvalXType() 實現此函數的計算邏輯。

尚未向量化的函數在 issue/12058 中，歡迎感興趣的同學加入我們一起完成這項宏大的工程。

向量化程式碼需放到以 _vec.go 結尾的文件中，如果還沒有這樣的文件，歡迎新建一個，注意在文件頭部加上 licence 說明。

這裡是一個簡單的例子 PR/12012，以 builtinLog10Sig 為例：

1. 這個函數在 expression/builtin_math.go 文件中，則向量化實現需放到文件 expression/builtin_math_vec.go 中；
2. builtinLog10Sig 原始的非向量化計算介面為 evalReal()，那麼我們需要為其實現對應的向量化介面為 vecEvalReal()；
3. 實現完成後請根據後續的說明添加測試。

下面為大家介紹在實現向量化計算過程中需要注意的問題。

1. 如何獲取和釋放中間結果向量

存儲表達式計算中間結果的向量可通過表達式內部對象 bufAllocator 的 get() 和 put() 來獲取和釋放，參考 PR/12014，以 builtinRepeatSig 的向量化實現為例：

buf2, err := b.bufAllocator.get(types.ETInt, n)  if err != nil {      return err  }  defer b.bufAllocator.put(buf2) // 注意釋放之前申請的記憶體

2. 如何更新定長類型的結果

如前文所說，我們需要使用 ResizeXType() 和 XTypes() 來初始化和獲取用於存儲定長類型數據的 Golang Slice，直接讀寫這個 Slice 來完成數據操作，另外也可以使用 SetNull() 來設置某個元素為 NULL。程式碼參考 PR/12012，以 builtinLog10Sig 的向量化實現為例：

f64s := result.Float64s()  for i := 0; i < n; i++ {      if isNull {          result.SetNull(i, true)      } else {          f64s[i] = math.Log10(f64s[i])      }  }

3. 如何更新變長類型的結果

如前文所說，我們需要使用 ReserveXType() 來為變長類型預分配一段記憶體（降低 Golang runtime.growslice() 的開銷），使用 AppendXType() 來追加一個變長類型的元素，使用 GetXType() 來讀取一個變長類型的元素。程式碼參考 PR/12014，以 builtinRepeatSig 的向量化實現為例：

result.ReserveString(n)  ...  for i := 0; i < n; i++ {      str := buf.GetString(i)      if isNull {          result.AppendNull()      } else {      result.AppendString(strings.Repeat(str, int(num)))      }  }

4. 如何處理 Error

所有受 SQL Mode 控制的 Error，都利用對應的錯誤處理函數在函數內就地處理。部分 Error 可能會被轉換成 Warn 而不需要立即拋出。

這個比較雜，需要查看對應的非向量化介面了解具體行為。程式碼參考 PR/12042，以 builtinCastIntAsDurationSig 的向量化實現為例：

for i := 0; i < n; i++ {      ...      dur, err := types.NumberToDuration(i64s[i], int8(b.tp.Decimal))      if err != nil {         if types.ErrOverflow.Equal(err) {            err = b.ctx.GetSessionVars().StmtCtx.HandleOverflow(err, err) // 就地利用對應處理函數處理錯誤         }         if err != nil { // 如果處理不掉就拋出            return err         }         result.SetNull(i, true)         continue      }      ...  }

5. 如何添加測試

我們做了一個簡易的測試框架，可避免大家測試時做一些重複工作。

該測試框架的程式碼在 expression/bench_test.go 文件中，被實現在 testVectorizedBuiltinFunc 和 benchmarkVectorizedBuiltinFunc 兩個函數中。

我們為每一個 builtin_XX_vec.go 文件增加了 builtin_XX_vec_test.go 測試文件。當我們為一個函數實現向量化後，需要在對應測試文件內的 vecBuiltinXXCases 變數中，增加一個或多個測試 case。下面我們為 log10 添加一個測試 case：

var vecBuiltinMathCases = map[string][]vecExprBenchCase {      ast.Log10: {          {types.ETReal, []types.EvalType{types.ETReal}, nil},      },  }

具體來說，上面結構體中的三個欄位分別表示:

1. 該函數的返回值類型；
2. 該函數所有參數的類型；
3. 是否使用自定義的數據生成方法（dataGener），nil 表示使用默認的隨機生成方法。

對於某些複雜的函數，你可自己實現 dataGener 來生成數據。目前我們已經實現了幾個簡單的 dataGener，程式碼在 expression/bench_test.go 中，可直接使用。

添加好 case 後，在 expression 目錄下運行測試指令：

# 功能測試  GO111MODULE=on go test -check.f TestVectorizedBuiltinMathFunc    # 性能測試  go test -v -benchmem -bench=BenchmarkVectorizedBuiltinMathFunc -run=BenchmarkVectorizedBuiltinMathFunc

在你的 PR Description 中，請把性能測試結果附上。不同配置的機器，性能測試結果可能不同，我們對機器配置無任何要求，你只需在 PR 中帶上你本地機器的測試結果，讓我們對向量化前後的性能有一個對比即可。

如何成為 Contributor

為了推進表達式向量化計算，我們正式成立 Vectorized Expression Working Group，其具體的目標和制度詳見這裡。與此對應，我們在 TiDB Community Slack 中創建了 wg-vec-expr channel 供大家交流討論，不設門檻，歡迎感興趣的同學加入。

如何成為 Contributor：

1. 在此 issue 內選擇感興趣的函數並告訴大家你會完成它；
2. 為該函數實現 vecEvalXType() 和 vectorized() 的方法；
3. 在向量化測試框架內添加對該函數的測試；
4. 運行 make dev，保證所有 test 都能通過；
5. 發起 Pull Request 並完成 merge 到主分支。

如果貢獻突出，可能被提名為 reviewer，reviewer 的介紹請看 這裡。

如果你有任何疑問，也歡迎到 wg-vec-expr channel 中提問和討論。

原文閱讀：https://pingcap.com/blog-cn/10mins-become-contributor-of-tidb-20190916/