最近在嘗試自己寫資料庫查詢模塊，滿足 http://sigmod18contest.db.in.tum.de/task.shtml 的功能要求。一邊看著 TiDB 的代碼，一邊寫… 這個過程中發現了一些 TiDB 優化點。

join reorder

每個資料庫系統基本都要實現 join reorder，修改表連接的順序，從而提高 join 的性能，比如下面這個查詢：

select a.id, b.id, c.id
from a, b, c
where a.id = b.a_id and a.id = c.a_id;

查詢要連接 a/b/c 三張表，可以先連接 a 和 b，也可以先連接 a 和 c，當然如果你想不開的話，也可以先連接 a 和 c。如果 a join b 產生的數據比 a join c 產生的數據多，那麼先計算 a join c 一般性能會更好。

很多資料庫在表少的時候會使用動態規劃來解決這個問題，比如 這篇文章 中介紹的演算法。大致思路是根據表和用來連接的條件看做是一個無環圖，表是節點，篩選條件是邊。要計算最優的連接順序，就是根據這張圖計算出一個 sJoin Tree，Join Tree 除葉子節點以外其他的節點都是 Join。動規的過程是將圖拆分成各種子圖的組合併從中找出最優組合。

下面是 TiDB 中 join reorder 的主體代碼：

func (s *joinReorderDPSolver) solve(joinGroup []LogicalPlan, conds []expression.Expression) (LogicalPlan, error) {
// joinGroup 可以簡單認為是要連接的 table 列表，代碼中先計算出圖的鄰接表的結構和「邊」列表
adjacents := make([][]int, len(joinGroup))
totalEdges := make([]joinGroupEdge, 0, len(conds))
addEdge := func(node1, node2 int, edgeContent *expression.ScalarFunction) {
totalEdges = append(totalEdges, joinGroupEdge{
nodeIDs: []int{node1, node2},
edge: edgeContent,
})
adjacents[node1] = append(adjacents[node1], node2)
adjacents[node2] = append(adjacents[node2], node1)
}
// Build Graph for join group
for _, cond := range conds { // 根據篩選條件的列，找到每個條件中連接的表，記錄表之間的連接關係
sf := cond.(*expression.ScalarFunction)
lCol := sf.GetArgs()[0].(*expression.Column)
rCol := sf.GetArgs()[1].(*expression.Column)
lIdx, err := findNodeIndexInGroup(joinGroup, lCol)
//...
rIdx, err := findNodeIndexInGroup(joinGroup, rCol)
//...
addEdge(lIdx, rIdx, sf)
}
visited := make([]bool, len(joinGroup))
nodeID2VisitID := make([]int, len(joinGroup))
var joins []LogicalPlan
// BFS the tree.
// 使用 BFS 計算出聯通子圖，如果存在多個子圖，子圖之間沒有連接關係，子圖之間 join 結果是他們的笛卡爾乘積
for i := 0; i < len(joinGroup); i++ {
if visited[i] {
continue
}
visitID2NodeID := s.bfsGraph(i, visited, adjacents, nodeID2VisitID)
// Do DP on each sub graph.
// 使用 DP 演算法找到每個子圖的最優 join 順序
join, err := s.dpGraph(visitID2NodeID, nodeID2VisitID, joinGroup, totalEdges)
if err != nil {
return nil, err
}
joins = append(joins, join)
}
// Build bushy tree for cartesian joins.
return s.makeBushyJoin(joins), nil
}

下面是 bp 部分的代碼，演算法使用點陣圖來表示不同的子圖，使用了自下而上的方式，從小到大的計算每個子圖的最優 join 順序，從而最終計算出整個圖的最優解。演算法中使用了點陣圖，拆分子圖和判斷子圖之間是否連接的代碼感覺很棒，非常的簡潔高效。

func (s *joinReorderDPSolver) dpGraph(newPos2OldPos, oldPos2NewPos []int, joinGroup []LogicalPlan, totalEdges []joinGroupEdge) (LogicalPlan, error) {
// 使用點陣圖來表示不同子圖，使用自下而上的方式計算每個子圖的最優 join 順序
nodeCnt := uint(len(newPos2OldPos))
bestPlan := make([]LogicalPlan, 1<<nodeCnt)
bestCost := make([]int64, 1<<nodeCnt)
// bestPlan[s] is nil can be treated as bestCost[s] = +inf.
for i := uint(0); i < nodeCnt; i++ {
bestPlan[1<<i] = joinGroup[newPos2OldPos[i]]
}
// 從小到大羅列所有子圖
for nodeBitmap := uint(1); nodeBitmap < s << nodeCnt); nodeBitmap++ {
if bits.OnesCount(nodeBitmap) == 1 {
continue
}
// This loop can iterate all its subset.
for sub := (nodeBitmap - 1) & nodeBitmap; sub > 0; sub = (sub - 1) & nodeBitmap {
remain := nodeBitmap ^ sub
if sub > remain {
// 由於是無向圖，所有相同兩個子圖的組合，只計算一遍
continue
}
// 如果 sub/remain 這兩個子圖中某一個不是強連通的，不繼續計算
if bestPlan[sub] == nil || bestPlan[remain] == nil {
continue
}
// Get the edge connecting the two parts.
usedEdges := s.nodesAreConnected(sub, remain, oldPos2NewPos, totalEdges)
if len(usedEdges) == 0 {
// 如果 sub 和 remain 是不連通的，也不再繼續計算
continue
}
join, err := s.newJoinWithEdge(bestPlan[sub], bestPlan[remain], usedEdges)
if err != nil {
return nil, err
}
// 更新 nodeBitmap 所代表的子圖中最優的 join 順序
if bestPlan[nodeBitmap] == nil || bestCost[nodeBitmap] > join.statsInfo().Count()+bestCost[remain]+bestCost[sub] {
bestPlan[nodeBitmap] = join
bestCost[nodeBitmap] = join.statsInfo().Count() + bestCost[remain] + bestCost[sub]
}
}
}
return bestPlan[(1<<nodeCnt)-1], nil
}

需要注意的是，bp 演算法中需要估算每個 join 的代價，評估代價的過程當中需要使用統計信息，統計信息有的時候會不準確，這會影響 bp 演算法的結果。

補充知識

從上面的代碼可以看到，評估 join 代價的時候主要還是看 join.StatsInfo().Count() 的數值大小，這個數值表示 join 會產生的數據條數。評估 join 的數據條數和評估單表的數據條數的計算方法不同，這塊的知識可以看一下 資料庫概念 13.3.3 的講解和 TiDB 的代碼實現。

復用 Chunk

為了提高查詢執行器的執行速度，特別是在數據量比較大的情況下，TiDB 使用了 chunk。在執行查詢的過程中，執行器每次不再只返回一條數據，而是返回一組數據。

除了使用 Chunk 以外，TiDB 的執行器還增加了 Chunk 復用的邏輯，有效的降低了內存的開銷。在做一個數據量很大的 HashJoin 時（比如外表有幾百萬條數據），TiDB 會啟動多個 worker 來計算 join 結果，worker 之間通過 Chunk 分發任務、接收計算結果。如果沒有復用 Chunk 的話，查詢過程會差生大量的 Chunk，GC 勢必會影響性能。

TiDB 中當 worker 使用完了 chunk 以後，會通過特定的 channel 將 chunk 還回從而實現 Chunk 的復用。這塊的代碼不易拆分出來，暫略。

推薦閱讀：