深入解析分散式資料庫 ZNBase 的 SQL 引擎優化

往期回顧： 深入解析 ZNBase 分散式 SQL 引擎架構的五大服務元件

導讀

前文提到，ZNBase 是由浪潮開源的一款 NewSQL 分散式資料庫，基於谷歌 Spanner+F1 的論文設計，完美繼承了 Spanner 的設計理念，實現了基於對等架構的分散式 SQL 引擎。ZNBase 的 SQL 引擎包含連線、編譯、快取、分散式日誌和分散式執行五大服務元件，實現了多叢集多節點協同的高效計算，大大提升了使用者的查詢效率。

為了進一步提升 SQL 引擎的效能，ZNBase 研發團隊結合實際業務需求，在原有架構的基礎上，針對 SQL 引擎的編譯服務、執行服務、演算法等方面進行了一系列深度定製化的優化改進工作。本文將這些改進工作逐一展開介紹。

ZNBase 針對 SQL 引擎的優化改進

1.編譯服務優化

1.1 類型、功能、語法相容

隨著日益增多的場景需要，ZNBase 陸續完善了對 PostgreSQL 、Oracle、MySQL 語法、類型、函數的相容。

1.2 計劃優化

1.2.1 直方圖

ZNBase 還擴展了統計資訊功能，除了：表的行數，表中列的 Distinct 值（某一列的唯一值總共有多少條），還額外引入了直方圖。為 CBO 的優化提供了更多的一句。

統計資訊獲取的簡單流程如下：

對每個 range 進行抽樣，用蓄水池演算法生成樣本集合，然後用樣本進行各種統計資訊的預估，將結果通過寫入函數 writeResults，寫進系統表 system.table_statistics 中。

1.2.2 執行計劃管理

ZNBase 擴展了對執行計劃的管理，包括執行計劃繫結、自動捕獲繫結、自動更新繫結等。執行計劃繫結功能使得可以在不修改 SQL 語句的情況下選擇指定的執行計劃。使用者通過繫結執行計劃，可以將計劃存入 ZNBase 中，下次再執行解析後計劃相同的 SQL 語句時，只要取出之前存入的計劃即可，省去了構建計劃的時間。ZNBase 還會智慧地自動捕獲執行頻率較多的並且使用者之前沒有手動為其創建繫結的 SQL 語句，在後臺自動為其創建計劃繫結。

由於表資料的變化，如：資料變化、資料結構變化、統計資訊變化，可能會導致之前繫結的執行計劃執行效率降低，ZNBase 將自動檢測執行時間，將繫結好的執行計劃進行優化，為使用者提高複合當前資料場景的更高的執行效率。

2. 執行優化

2.1 向量運算元

ZNBase 還引入了向量運算元，相比基於 Goetz Graefe 論文的「火山」模型，「向量」模型在計算行數明顯大於列數的場景下，效能會有極大的提升。

從原理上講，這是用一系列專門針對資料類型和計算的特定編譯迴圈代替了通用的類似於直譯器的 SQL 表示式評估器，因此計算機可以連續執行許多更簡單的任務，大大節省了重複的計算所需要的時間。配合 ZNBase 團隊開發的列式儲存，查詢效能還將有進一步的提升。

目前向量運算元支援的類型有：Array、BIT、BOOL、BYTES、COLLATE、DATE、DECIMAL、INET、INT、INTERVAL、JSONB、SERIAL、TIME、TIMESTAMP、TIMESTAMPTZ、UUID、FLOAT、STRING 等。

目前 ZNBase 支援的向量運算元有：Noop、TableReader、Distinct、Ordinality、Hashjoiner、MergeJoiner、Sorter、Windower 等。

舉例來說，請考慮一個包含三列的 People 表：Id，Name 和 Age。在火山模型中，每個資料行由每個運算元處理一次 —— 一種逐行執行方法。相比之下，在向量化執行引擎中，我們一次傳遞了有限大小的面向列資料的批處理。我們使用一組列，而不是使用元組陣列的資料結構，其中每一列都是特定資料類型的陣列。在該示例中，分批處理將由一個Id的整數陣列，一個 Name 的位元組陣列和 Age 的整數陣列組成。下圖顯示了兩個模型中資料佈局之間的區別：

火山模型

向量模型

SELECT Name, (Age - 30) * 50 AS Bonus FROM People WHERE Age > 30;

這樣的語句查詢，在火山模型中，頂級使用者向 Project 運算元請求一行，該請求被傳播到底層的 Scan 運算元。掃描從鍵值儲存中讀取一行，並將其傳遞給 Select，Select 將檢查該行是否通過了 Age> 30 的謂詞。如果該行通過了檢查，則將其返回給 Project 運算元以計算 Bonus = (Age - 30) * 50 作為最終輸出。

火山模型流程圖

一次處理一行，對於每一行，我們都在呼叫一個完全通用的標量表達式的過濾器！表示式可以是任何東西：乘法，除法，相等檢查或內建函數，甚至可以是一長串這樣的東西。由於這種通用性，計算機在每一行上都有很多工作要做——必須在甚至無法執行任何工作之前檢查表示式的含義。與編譯後的語言相比，這種計算方式與解釋型語言同樣麻煩。

在向量化模型中，我們採用不同的方式。每個向量化運算元背後的原理是在執行期間不允許任何自由度或運行時選擇。這意味著對於任務，資料類型和屬性的任意組合，應該由一個專門的運算元來負責這項工作。對於示例查詢，使用者從運算元鏈中請求一批。每個運算元都向其子級請求一批，執行其特定任務，然後將一批返回給其父級。

向量模型流程圖

為了對此進行視覺化，請考慮由 SelectIntGreaterThanInt 處理的 People batch。該運算元將選擇所有大於 30 的 Age 值。這個新的 sel_age batch 然後傳遞到 ProjectSubIntInt 運算元，該運算元執行簡單的減法運算以生成 tmp batch。最後，將這個 tmp batch 傳遞給 ProjectMultIntInt 運算元，該運算元將計算最終 Bonus =（Age-30）* 50 值。

向量模型流程圖

2.2 並行優化

在ZNBase的開發過程中也對運算元進行了優化，提高了運算效率。

2.2.1 tablereader 並行

Tablereader 通過拆分 Span 進行並行的 baRequest 下發讀取資料，返回的資料封裝進 baResponse 裡面，放入管道由 tablereader 進行並行處理。

tablereader的並行分為以下幾步：

Step1：Span 拆分，邏輯計劃完成後會生成一個 Span ALL（索引、主鍵查詢除外），Span ALL 會根據 table 的 range 邊界拆分從成多個範圍更小的 Span，每個 Span 會獲得相應的 range 資訊，根據 rangeID 可以取得對應 range 的副本資訊，再根據副本選擇策略（就近選擇、隨機選擇、lease holder（預設）），獲取到對應副本的 nodeID，再將該 Span 放入一個 Map 結構（Map[nodeID][]Span）中;

當 tablereader 下發到了對應節點後，再將 Spans 進行均勻分配進 tablereader 的各個 worker fethcer 當中進行並行的資料讀取：

Step2：BatchRequest 下發，對應節點的 tablereader 的每個 fetcher 的 spans 的每一個 span 會封裝為一個 ScanRequest 請求，多個 ScanRequest 請求封裝進一個 BatchRequest（BacthRequest 請求中 header 資訊可以指定一次請求返回的最大 kv 數目），該 BacthRequest 經過分發層邏輯後下發至對應節點的對應 Store 進行資料查詢，返回的資料封裝為 BatchResponse，包含多個對應的 ScanResponse，將 ScanResponse 的 kv 資料放入 channel 中，再由每個 fetcher 繫結的 worker 進行 kv 解碼以及後續的處理：

Step3：資料返回，每個 fetcher 的 worker 協程處理(經過 filter 或 render )完每行 kv 資料後都會放入一個 buffer 當中（預設 buffer 快取<= 64 行），每個 worker 每完成一個 buffer 會將該 buffer 放入 tablereader 的結果管道中，提供 NextRow 和 NextChunk 兩類介面供上層運算元呼叫：

2.2.2 hashjoin 優化

原有 hashjoin 流程圖如下：

原有執行流程存在如下問題：

• 單點流程是序列化執行，導致取出 outer 表的一行資料需要等待正在進行的 hashjoin 計算完成。

• hashjoin 計算只由一個協程執行，資料量大的時候比較耗時。

經過優化後 hashjoin 由 3 個部分完成：

1. Main thread：構造 hash 表；啟動 Outer Fecther 和 Join Workers；從 join Woker 拿取計算結果，返回至上層；等待所有的 join worker 結束，更新狀態為計算完成。

2. Outer Fetcher（協程）：迴圈讀取 Outer 表每一行資料，將讀取的資料通過 channel 傳遞給 Join Woker 進行計算；通知 Join Wokers Outer 表讀取完成。

3. Join Workers（協程）：將 Outer Fetcher 傳送來的資料進行 hash join 計算；將計算結果通過 channel 傳送至 Main thread。

優化前後對比分析：

• 設構造 inner（storedSide）一側的 hash 表時間為 t1

• 設讀取一條 outer（otherSide）資料時間為 t2

• 設執行一輪 hashjoin 時間為 t3

• 設 outer（otherSide）表有 m 條資料

執行完 hashjoin：

優化前耗時≈t1+m*t2+m*t3

優化後耗時≈t1+(m/n)*t3

Δt≈(m(n-1))/n t3+m*t2

預期：隨著 outer 表資料增多和 join worker 協程數增加，理論上優化越明顯。

經優化後有如下優勢：

1. 計算讀取分離：將讀取 outer 表和 hash join 計算分離，使得讀取 outer 表下一行資料不必再等待上一個 hash join 計算完成。

2. 平行計算：啟用多個 join worker 參與 hash join 計算，提高了並行度。

展望未來

大資料行業的發展促進了國產分散式資料庫的演進，為適應這種發展大潮，云溪 NewSQL 資料庫 ZNBase 也會促使分散式 SQL 引擎更趨向完善，未來會在語法上完全相容 Oracle 等傳統資料庫，計劃上加入更豐富的 HBO，完善 Cascade 框架，更加智慧的提高使用者的使用體驗，執行上會相容 HTAP 計算方式，順應當下飛速增長的資料量，適配更多的大資料、人工智慧、機器學習場景，提供一個更智慧、更高效的 SQL 計算引擎。

參考文件 [1]. Volcano-An Extensible and Parallel Query Evaluation System