?一、單節(jié)點(diǎn)執(zhí)行

在單節(jié)點(diǎn)環(huán)境執(zhí)行一條簡單的 SQL 語句 SELECT * FROM NATION ORDER BY N_NAME。NATION 是一張小表，只有 25 條記錄；對第 2 列 N_NAME 進(jìn)行升序排列。

1. 抽象語法樹

上述示例中的 SQL 語句經(jīng)過分析器解析后得到 AST，如下圖所示：

2. 邏輯計(jì)劃

將 AST 轉(zhuǎn)換成一個(gè)樹狀結(jié)構(gòu)的 Plan，稱之為邏輯查詢計(jì)劃。抽象語法樹中的每一個(gè)語法元素都被轉(zhuǎn)換成一個(gè)查詢邏輯單元，例如 scanNode, sortNode, joinNode 等。

邏輯計(jì)劃可以通過一系列規(guī)則進(jìn)行優(yōu)化，稱之為 RBO（Rule Base Optimization）。

舉一個(gè)簡單的例子，SQL 語句 SELECT * FROM t WHERE a + 1 > 4 通過規(guī)則改寫可以轉(zhuǎn)換為 SELECT * FROM t WHERE a > 3 。從數(shù)據(jù)庫的計(jì)劃角度，兩者有很大差別。

前者只能掃描全表，每次讀取一條記錄并計(jì)算表達(dá)式判斷是否符合過濾條件；后者可以利用 a 列索引信息減少掃描范圍，即使沒有索引也不需要每次進(jìn)行表達(dá)式計(jì)算。

例子中的邏輯計(jì)劃很簡單，就是掃描節(jié)點(diǎn) Scan 和排序節(jié)點(diǎn) Sort。命令 Explain SELECT * FROM NATION ORDER BY N_NAME 顯示如下：

3. 物理計(jì)劃

(DistSQLPlanner).PlanAndRun 方法把邏輯計(jì)劃轉(zhuǎn)換為物理計(jì)劃，其中遞歸調(diào)用 createPlanForNode 方法生成各個(gè)物理算子，交給執(zhí)行器具體執(zhí)行。

生成物理計(jì)劃也是一個(gè)優(yōu)化過程，稱之為 CBO（Cost Base Optimization）。例如邏輯計(jì)劃的表連接，在具體實(shí)現(xiàn)時(shí)可以交換順序，也可以有不同的實(shí)現(xiàn)方法（Nest Loop Join，Sort Merge Join和Hash Join）。

此時(shí)就需要通過代價(jià)模型（Cost Model）在巨大的搜索空間中尋找一個(gè)合理的物理執(zhí)行計(jì)劃。這是一個(gè) NP 問題，所以一般只能找到一個(gè)相對最優(yōu)解。

此外，KaiwuDB 根據(jù)底層 KV 數(shù)據(jù)的分布和預(yù)估返回?cái)?shù)據(jù)集的大小，決定是否需要生成分布式執(zhí)行計(jì)劃；這個(gè)例子是一個(gè)本地執(zhí)行的物理計(jì)劃。

邏輯計(jì)劃節(jié)點(diǎn)和物理計(jì)劃節(jié)點(diǎn)并不是一一對應(yīng)關(guān)系，但是這個(gè)例子中，邏輯計(jì)劃中的 Scan 和 Sort 分別對應(yīng)物理計(jì)劃中的 TableReader 算子和 Sorter 算子。

4. 執(zhí)行引擎

最后調(diào)用(DistSQLPlanner).Run 方法執(zhí)行物理計(jì)劃。執(zhí)行引擎采用火山模型（Volcano），每一層執(zhí)行算子通過調(diào)用下一層的 Next 方法獲取一條記錄。執(zhí)行偽代碼如下：

5.排序分析

下面具體分析排序算子操作，首先了解一下數(shù)據(jù)在各個(gè)階段的存儲格式。

（1）數(shù)據(jù)格式

在 KV 存儲引擎中，數(shù)據(jù)的存儲格式如下：

TableReader 通過 KV 存儲接口，讀取一條數(shù)據(jù)后返回一個(gè) EncDatumRow 對象，里面添加了 KaiwuDB 的編碼信息。

Sorter 算子的 fill 方法將 EncDatumRow 對象中的數(shù)據(jù)解碼后加入 MemRowContainer 對象的 chunks 里，用于后續(xù)的排序。

chunks 是一個(gè)二維數(shù)組[][]Datum，Datum 是一個(gè)接口，代表 SQL 中的值，具體的實(shí)現(xiàn)類包括 DBool, DInt, DString 等。KaiwuDB 中盡量使用原生數(shù)據(jù)類型，比如 DBool/DInt/DString 分別被定義成 bool/int64/string，并實(shí)現(xiàn)了 Datum 接口方法；而 DDecimal 就是一個(gè)自定義結(jié)構(gòu)體。

直覺上 []Datum 應(yīng)該對應(yīng)表里的一行數(shù)據(jù)，但是為了減少 golang 里切片擴(kuò)容帶來的影響，KaiwuDB 將 64 行數(shù)據(jù)打包放在了一個(gè) []Datum 里。Nation 表的數(shù)據(jù)在 chunks 中打印顯示如下：

內(nèi)存中的 chunks 結(jié)構(gòu)：

?

（2）排序方法

最常用的排序執(zhí)行算子叫做 sortAllProcessorSorter，將全部待排序結(jié)果讀入后（內(nèi)存或磁盤），進(jìn)行一次排序輸出最終結(jié)果。調(diào)用時(shí)序圖如下：

MemRowContainer 的 Sort 方法實(shí)現(xiàn)了內(nèi)存中對 chunks 數(shù)組的排序：

• 數(shù)組長度小于等于 12 時(shí)，采用插入排序；

• 快速排序，遞歸最大深度 2*ceil(lg(n+1))；

• 遞歸到了最大深度，采用堆排序；

如果需要排序的數(shù)據(jù)超出了閾值（WorkMemBytes，默認(rèn) 64MB），會調(diào)用 spillToDisk 方法將 MemRowContainer 中的數(shù)據(jù)寫入 DiskRowContainer 中，后者將 OrderBy 列的信息作為 Key 值寫入 KV 存儲引擎。

此外為了提高 KV 寫入速度，DiskRowContainer 不會每次只寫一條數(shù)據(jù)，而是有一個(gè) buffer 負(fù)責(zé)累積一批鍵值對，然后一起寫入。

其他的兩種排序執(zhí)行算子包括：

• sortTopkProcessor:?Limit 下推到 Sorter 時(shí)，算子只分配 N 行的排序空間，然后進(jìn)行堆排序；

• sortChunksProcessor:?多列排序時(shí)，如果前 i 列 (0 < i < N) 已經(jīng)有序，算子逐行讀入輸入數(shù)據(jù)，直到前 i 列出現(xiàn)不同值；重復(fù)對讀入的批次進(jìn)行排序。處理完數(shù)據(jù)集后前 i+1 列已經(jīng)有序，迭代前面的步驟對后續(xù)列進(jìn)行排序，直到結(jié)果集多列排序完成。

二、多節(jié)點(diǎn)執(zhí)行

在三節(jié)點(diǎn)環(huán)境上執(zhí)行 SQL 語句 SELECT * FROM LINEITEM ORDER BY L_SHIPDATE。LINEITEM 是一張大表，有約 6000 萬條數(shù)據(jù)；對第 11 列 L_SHIPDATE 進(jìn)行升序排列。

1. 邏輯計(jì)劃

邏輯計(jì)劃和單節(jié)點(diǎn)環(huán)境的計(jì)劃相似。

2. 物理計(jì)劃

KaiwuDB 在多節(jié)點(diǎn)環(huán)境中將數(shù)據(jù)分片放在不同的節(jié)點(diǎn)中，每個(gè)分片數(shù)據(jù)有多個(gè)備份。示意圖如下：

分布式執(zhí)行計(jì)劃根據(jù) Span 信息分為多個(gè) tableReader 算子在多個(gè)節(jié)點(diǎn)上執(zhí)行；AddNoGroupingStage 方法將 sorter 算子加入到所有的 tableReader 算子之后，對各個(gè)節(jié)點(diǎn)上的分片數(shù)據(jù)進(jìn)行排序。

最后 FinalizePlan 方法會增加一個(gè) No-op 算子，歸并匯總最終的結(jié)果集。生成的分布式物理計(jì)劃如下：