7.深入TiDB：range 範圍計算優化
本文基於 TiDB release-5.1進行分析，需要用到 Go 1.16以後的版本
這篇文章首先會回顧一下整個 SQL 的執行過程，用來說明為什麼要範圍計算，最後從源碼的角度講解一下 析取範式 DNF (disjunctive normal form) 和 合取範式 CNF (conjunctive normal form) 是如何轉化為範圍區間。
優化過程解析
TiDB 在進行表掃描前會對查詢條件，也就是 Selection 算子的過濾條件化簡, 轉為區間掃描。可以儘早的將無關的數據過濾掉，提升整個 SQL 的執行效率。
例如：
CREATE TABLE test1 (a int primary key, b int, c int,index (b));
explain select * from test1 where b=5 or ( b>5 and (b>6 or b <8) and b<12) ;
在上面的查詢中，會對查詢條件進行優化，將索引搜索的返回縮小。對於上面的 where 條件中的表達式區間，最終會優化為：
b=5 or ( b>5 and (b>6 or b <8) and b<12)=> [5,12)
我們從 explain 中也可以看到優化結果：
+-------------------------+-------+---------+-----------------------+--------------------------------------------+
|id |estRows|task |access object |operator info |
+-------------------------+-------+---------+-----------------------+--------------------------------------------+
|IndexLookUp_10 |250.00 |root | | |
|├─IndexRangeScan_8(Build)|250.00 |cop[tikv]|table:test1, index:b(b)|range:[5,12), keep order:false, stats:pseudo|
|└─TableRowIDScan_9(Probe)|250.00 |cop[tikv]|table:test1 |keep order:false, stats:pseudo |
+-------------------------+-------+---------+-----------------------+--------------------------------------------+
在正式進入探究之前，我們先來看看 TiDB 的幾個優化步驟，讓不了的同學也能很好的掌握整個 SQL 優化過程。
對於上面我們的 SQL：
select * from test1 where b=5 or ( b>5 and (b>6 or b <8) and b<12) ;
首先會生成執行計劃：
在執行完 logicalOptimize 邏輯優化之後，執行計劃變為下面這樣：
Selection算子被下推到了 DataSource 算子中，在 DataSource 的 pushedDownConds 中保存着下推的過濾算子：
對於我們的 pushedDownConds 展開來是一個二叉樹結構：
因為索引底層是順序排列的，所以要將這顆樹轉為掃描區間。
然後在執行 physicalOptimize 然後進行物理優化的時候會遍歷 DataSource 算子的 possibleAccessPaths
...
for _, path := range ds.possibleAccessPaths {
if path.IsTablePath() {
continue
}
err := ds.fillIndexPath(path, ds.pushedDownConds)
if err != nil {
return nil, err
}
}
...
fillIndexPath 會調用 DetachCondAndBuildRangeForIndex 來生成掃描區間，這個函數會遞歸的調用如下 2 個函數：
detachDNFCondAndBuildRangeForIndex：展開 OR 條件連接也叫析取範式 DNF (disjunctive normal form)，生成掃描區間或合併掃描區間；
detachCNFCondAndBuildRangeForIndex：展開 AND 條件連接也叫合取範式 CNF (conjunctive normal form)，生成掃描區間或合併掃描區間；
整個執行過程如下：
上面的表達式樹最終生成了這樣的區間： [5,12)。
然後 physicalOptimize 會遞歸所有的算子調用 findBestTask 函數，最後調用到 DataSoure 算子使用 Skyline-Pruning 索引裁剪，它會從 possibleAccessPaths 獲取最優的執行計劃：
func (ds *DataSource) skylinePruning(prop *property.PhysicalProperty) []*candidatePath {
candidates := make([]*candidatePath, 0, 4)
for _, path := range ds.possibleAccessPaths {
var currentCandidate *candidatePath
...
pruned := false
for i := len(candidates) - 1; i >= 0; i-- {
// 比較索引代價，判斷是否進行裁剪
result := compareCandidates(candidates[i], currentCandidate)
if result == 1 {
pruned = true
break
} else if result == -1 {
candidates = append(candidates[:i], candidates[i+1:]...)
}
}
if !pruned {
candidates = append(candidates, currentCandidate)
}
}
...
return candidates
}
compareCandidates 函數會從下面三個方面進行判斷一個索引的優劣：
-
索引的列涵蓋了多少訪問條件。「訪問條件」指的是可以轉化為某列範圍的
where條件，如果某個索引的列集合涵蓋的訪問條件越多，那麼它在這個維度上更優。 -
選擇該索引讀表時，是否需要回表（即該索引生成的計劃是 IndexReader 還是 IndexLookupReader）。不用回表的索引在這個維度上優於需要回表的索引。如果均需要回表，則比較索引的列涵蓋了多少過濾條件。過濾條件指的是可以根據索引判斷的
where條件。如果某個索引的列集合涵蓋的訪問條件越多，則回表數量越少，那麼它在這個維度上越優。 -
選擇該索引是否能滿足一定的順序。因為索引的讀取可以保證某些列集合的順序，所以滿足查詢要求順序的索引在這個維度上優於不滿足的索引。
例如：如果索引 idx_a 在這三個維度上都不比 idx_b 差，且有一個維度比 idx_b 好，那麼 TiDB 會優先選擇 idx_a。
排除了不合適的索引之後，會根據下面的規則來選擇一個代價最低的索引進行讀表：
- 索引的每行數據在存儲層的平均長度。
- 索引生成的查詢範圍的行數量。
- 索引的回表代價。
- 索引查詢時的範圍數量。
最後生成的執行計劃為：PhysicalIndexLookUpReader。
範圍計算源碼分析
在上面中我也說到了 DetachCondAndBuildRangeForIndex 會根據 where 條件來生成掃描區間。
detachDNFCondAndBuildRangeForIndex 析取範式
func (d *rangeDetacher) detachDNFCondAndBuildRangeForIndex(condition *expression.ScalarFunction, newTpSlice []*types.FieldType) ([]*Range, []expression.Expression, bool, error) {
sc := d.sctx.GetSessionVars().StmtCtx
firstColumnChecker := &conditionChecker{
colUniqueID: d.cols[0].UniqueID,
shouldReserve: d.lengths[0] != types.UnspecifiedLength,
length: d.lengths[0],
}
rb := builder{sc: sc}
// 遞歸拉平 or 子項 Expression
dnfItems := expression.FlattenDNFConditions(condition)
newAccessItems := make([]expression.Expression, 0, len(dnfItems))
var totalRanges []*Range
hasResidual := false
for _, item := range dnfItems {
// 如果該子項 Expression 包含了 AND
if sf, ok := item.(*expression.ScalarFunction); ok && sf.FuncName.L == ast.LogicAnd {
// 遞歸拉平 and 子項 Expression
cnfItems := expression.FlattenCNFConditions(sf)
var accesses, filters []expression.Expression
res, err := d.detachCNFCondAndBuildRangeForIndex(cnfItems, newTpSlice, true)
if err != nil {
return nil, nil, false, nil
}
ranges := res.Ranges
accesses = res.AccessConds
filters = res.RemainedConds
if len(accesses) == 0 {
return FullRange(), nil, true, nil
}
if len(filters) > 0 {
hasResidual = true
}
totalRanges = append(totalRanges, ranges...)
newAccessItems = append(newAccessItems, expression.ComposeCNFCondition(d.sctx, accesses...))
} else if firstColumnChecker.check(item) {
if firstColumnChecker.shouldReserve {
hasResidual = true
firstColumnChecker.shouldReserve = d.lengths[0] != types.UnspecifiedLength
}
// 計算邏輯區間
points := rb.build(item)
// 將區間轉化為外暴露的 range 結構
ranges, err := points2Ranges(sc, points, newTpSlice[0])
if err != nil {
return nil, nil, false, errors.Trace(err)
}
totalRanges = append(totalRanges, ranges...)
newAccessItems = append(newAccessItems, item)
} else {
//生成 [null, +∞) 區間
return FullRange(), nil, true, nil
}
}
// 區間並
// 例如區間：[a, b], [c, d],表示的是a <= c. If b >= c
// 那麼這兩個區間可以合併為：[a, max(b, d)].
totalRanges, err := UnionRanges(sc, totalRanges, d.mergeConsecutive)
if err != nil {
return nil, nil, false, errors.Trace(err)
}
return totalRanges, []expression.Expression{expression.ComposeDNFCondition(d.sctx, newAccessItems...)}, hasResidual, nil
}
detachDNFCondAndBuildRangeForIndex 方法中會拉平 or 子項，然後進行遍歷，因為子項中可能嵌套子項，例如：where b=5 or ( b>5 and (b>6 or b <8) and b<12) 經過 FlattenDNFConditions 拉平之後會變成兩個子項：EQ 和 AND
那麼，對於 AND 子項來說會繼續調用 FlattenCNFConditions 拉平，之後進入到 detachCNFCondAndBuildRangeForIndex 進行範圍區間的提取，這個我們後面再說。先看看 EQ 這個子項的處理。
EQ 子項會進入到 build 方法中，根據類型判斷構建 point ：
func (r *builder) buildFromScalarFunc(expr *expression.ScalarFunction) []*point {
switch op := expr.FuncName.L; op {
case ast.GE, ast.GT, ast.LT, ast.LE, ast.EQ, ast.NE, ast.NullEQ:
return r.buildFormBinOp(expr)
...
case ast.In:
retPoints, _ := r.buildFromIn(expr)
return retPoints
case ast.Like:
return r.newBuildFromPatternLike(expr)
case ast.IsNull:
startPoint := &point{start: true}
endPoint := &point{}
return []*point{startPoint, endPoint}
case ast.UnaryNot:
return r.buildFromNot(expr.GetArgs()[0].(*expression.ScalarFunction))
}
return nil
}
buildFromScalarFunc 中包含了很多 buildFromXXX 方法，它們是計算一個具體函數的 range 的方法。比如 buildFromIn 便是處理 in 函數的方法。
每個 point 代表區間的一個端點:
type point struct {
value types.Datum
excl bool // exclude
start bool
}
value 表示端點的值， excl 表示端點為開區間的端點還是閉區間的端點，start 表示這個端點是左端點還是右端點。
我們這裡的 EQ 子項會進入到 buildFormBinOp 方法中。
func (r *builder) buildFormBinOp(expr *expression.ScalarFunction) []*point {
...
var col *expression.Column
var ok bool
// 因為有的人喜歡這樣寫表達式：where 5=b，所以這裡需要獲取表達式中的列名和值
// 判斷第一個參數是否是列字段
if col, ok = expr.GetArgs()[0].(*expression.Column); ok {
ft = col.RetType
// 獲取值
value, err = expr.GetArgs()[1].Eval(chunk.Row{})
if err != nil {
return nil
}
op = expr.FuncName.L
} else {
// 參數的第二個是列
col, ok = expr.GetArgs()[1].(*expression.Column)
if !ok {
return nil
}
ft = col.RetType
value, err = expr.GetArgs()[0].Eval(chunk.Row{})
if err != nil {
return nil
}
// 因為表達式是這樣寫的：where 5=b 所以需要將表達式中的符號做一下反轉
switch expr.FuncName.L {
case ast.GE:
op = ast.LE
case ast.GT:
op = ast.LT
case ast.LT:
op = ast.GT
case ast.LE:
op = ast.GE
default:
op = expr.FuncName.L
}
}
if op != ast.NullEQ && value.IsNull() {
return nil
}
...
//處理unsigned列
value, op, isValidRange := handleUnsignedCol(ft, value, op)
if !isValidRange {
return nil
}
// 處理越界情況
value, op, isValidRange = handleBoundCol(ft, value, op)
if !isValidRange {
return nil
}
// 構建區間端點
switch op {
case ast.NullEQ:
if value.IsNull() {
return []*point{{start: true}, {}} // [null, null]
}
fallthrough
case ast.EQ:
startPoint := &point{value: value, start: true}
endPoint := &point{value: value}
return []*point{startPoint, endPoint}
case ast.NE:
startPoint1 := &point{value: types.MinNotNullDatum(), start: true}
endPoint1 := &point{value: value, excl: true}
startPoint2 := &point{value: value, start: true, excl: true}
endPoint2 := &point{value: types.MaxValueDatum()}
return []*point{startPoint1, endPoint1, startPoint2, endPoint2}
...
}
return nil
}
buildFormBinOp 主要是對一些異常情況進行處理，如：unsigned列、越界、特殊列的值，然後構建區間端點 Point 數組。
然後就是調用 points2Ranges 將 Point 數組轉為 range：
func points2Ranges(sc *stmtctx.StatementContext, rangePoints []*point, tp *types.FieldType) ([]*Range, error) {
ranges := make([]*Range, 0, len(rangePoints)/2)
for i := 0; i < len(rangePoints); i += 2 {
startPoint := rangePoints[i]
...
endPoint := rangePoints[i+1]
...
ran := &Range{
LowVal: []types.Datum{startPoint.value},
LowExclude: startPoint.excl,
HighVal: []types.Datum{endPoint.value},
HighExclude: endPoint.excl,
}
ranges = append(ranges, ran)
}
return ranges, nil
}
上面的代碼形態我做了一些處理方面理解這段代碼的意思，主要就是獲取端點的開閉區間構建 Range。
detachCNFCondAndBuildRangeForIndex 合取範式
func (d *rangeDetacher) detachCNFCondAndBuildRangeForIndex(conditions []expression.Expression, tpSlice []*types.FieldType, considerDNF bool) (*DetachRangeResult, error) {
var (
eqCount int
ranges []*Range
err error
)
...
res := &DetachRangeResult{}
// accessConds 用於抽出 eq/in 可以用於點查的條件構建範圍查詢
// newConditions 用來簡化同字段出現多次的 eq 或 in 條件的情況，如：a in (1, 2, 3) and a in (2, 3, 4) 被簡化為 a in (2, 3)
accessConds, filterConds, newConditions, emptyRange := ExtractEqAndInCondition(d.sctx, conditions, d.cols, d.lengths)
eqOrInCount := len(accessConds)
// 根據access構建範圍區間
ranges, err = d.buildCNFIndexRange(tpSlice, eqOrInCount, accessConds)
if err != nil {
return res, err
}
res.Ranges = ranges
res.AccessConds = accessConds
checker := &conditionChecker{
colUniqueID: d.cols[eqOrInCount].UniqueID,
length: d.lengths[eqOrInCount],
shouldReserve: d.lengths[eqOrInCount] != types.UnspecifiedLength,
}
if considerDNF {
...
if eqOrInCount > 0 {
newCols := d.cols[eqOrInCount:]
newLengths := d.lengths[eqOrInCount:]
tailRes, err := DetachCondAndBuildRangeForIndex(d.sctx, newConditions, newCols, newLengths)
if len(tailRes.AccessConds) > 0 {
res.Ranges = appendRanges2PointRanges(res.Ranges, tailRes.Ranges)
res.AccessConds = append(res.AccessConds, tailRes.AccessConds...)
}
res.RemainedConds = append(res.RemainedConds, tailRes.RemainedConds...)
...
return res, nil
}
// 到這裡，說明eqOrInCount = 0
// 遍歷所有 conditions ，如果該condition是LogicOr Scalar Function類型的，則調用 DNF 相關函數進行處理
res.AccessConds, res.RemainedConds = detachColumnCNFConditions(d.sctx, newConditions, checker)
// 獲取 AccessConds 的範圍 range
ranges, err = d.buildCNFIndexRange(tpSlice, 0, res.AccessConds)
if err != nil {
return nil, err
}
res.Ranges = ranges
return res, nil
}
...
return res, nil
}
AND 表達式中，只有當之前的列均為點查的情況下，才會考慮下一個列。
例如：對於索引 (a, b, c)，有條件 a > 1 and b = 1，那麼會被選中的只有 a > 1。對於條件 a in (1, 2, 3) and b > 1，兩個條件均會被選到用來計算 range。
所以在這個方法中，首先會調用 ExtractEqAndInCondition 函數抽離出 eq/in 可以用於點查的條件構建範圍查詢賦值到 accessConds 中，剩餘的條件被抽離到 newConditions 中。
然後對於聯合索引中，如果第一個字段是 eq/in 點查詢，那麼 eqOrInCount 不為0，就可以繼續向後獲取其他字段的範圍。所以接下來會調用 DetachCondAndBuildRangeForIndex 獲取其他字段的範圍。
對於 eqOrInCount 等於0的條件，說明字段中不存在 eq/in 點查詢，或者聯合索引中左邊的字段查詢不為點查詢，那麼會調用 detachColumnCNFConditions 對單列索引進行處理。
Reference
//pingcap.com/zh/blog/tidb-source-code-reading-13
//github.com/xieyu/blog/blob/master/src/tidb/range.md
//www.youtube.com/watch?v=OFqkfJTVIc8
//www.cnblogs.com/lijingshanxi/p/12077587.html
//docs.pingcap.com/zh/tidb/stable/choose-index
