作者：君啟
介紹
PolarDB-X是阿裡巴巴自研的雲原生分布式資料庫，采用了計算-存儲分離的架構，其中計算節點承擔着大量的表達式計算任務。這些表達式計算涉及到SQL執行的各個環節，對性能有着重要的影響。為此PolarDB-X引入向量化執行引擎，為表達式計算帶來了幾十倍的性能提升。
傳統資料庫執行器的缺陷
現代資料庫系統的執行引擎，大多采用一次計算一行資料（Tuple-at-a-time）的處理方式，并且需要在運作時對資料類型進行解析和判斷，來适應複雜的表達式結構。我們稱之為“标量（scalar）表達式”。這種方式雖然易于實作、結構清晰，但是當需要處理的資料量增大時，它具有顯著的缺陷：
為了适應複雜的表達式結構，計算一條表達式往往需要引入大量的指令；對于行式執行來說，處理單條資料需要算子樹重新進行指令解釋（instruction interpretation），進而帶來了大量的指令解釋開銷。據論文《MonetDB/X100: Hyper-Pipelining Query Execution》統計，在MySQL執行TPC-H測試集的 Query1 時，指令解釋就耗費了90%的執行時間。
此外，在最初的Volcano結構設計中，算子内部邏輯并沒有避免分支預測（branch prediction）。錯誤的分支預測需要CPU終止目前的流水線，将ELSE語句中的指令重新載入，我們将這一過程稱為pipeline flush或pipeline break。頻繁的分支預測錯誤會嚴重影響資料庫的執行性能。
向量化執行系統
資料庫向量化執行系統最早由論文《MonetDB/X100: Hyper-Pipelining Query Execution》提出，它有以下幾個要點：
- 采用vector-at-a-time的執行模式，即以向量（vector）為資料組織機關。
- 使用向量化原語（vectorization primitives）來作為向量化算子的基本機關，進而建構整個向量化執行系統。原語中避免産生分支預測。
- 使用code generation（代碼生成）技術來解決靜态類型帶來的code explosion（代碼爆炸）問題。
向量化引擎為PolarDB-X的表達式計算帶來了顯著的性能提升。在下圖中，橫軸為向量大小，縱軸為吞吐量，不同标量表達式和向量化表達式的性能測試對比結果如下：
case表達式性能測試對比結果如下：
整體流程
PolarDB-X中，向量化表達式的執行分為以下幾個階段：
- 使用者SQL經解析後，在validator中進行校驗，推導和修正表達式的類型資訊；這一階段為向量化運算提供正确的、靜态的類型資訊；
- 在優化器形成執行計劃之後，需要對表達式樹進行表達式綁定，執行個體化對應的向量化原語，同時配置設定好向量下标，供運作時記憶體配置設定；
- 執行階段，依據Volcano式的結構，自頂向下的觸發執行向量化原語，并将向量作為運作時資料結構。
運作時結構
資料結構
在PolarDB-X向量化執行系統中，采用以下的資料結構來存放資料：
向量化表達式執行時，所有的資料都會存放在batch這一資料結構中。batch由許多向量（vector）和一個selection數組而組成。其中，向量vector包括一個存儲特定類型的數值清單（values）和一個辨別null值位置的null數組組成，它們在記憶體中都是連續存儲的。null數組中的bit位以0和1來區分數值清單中的某個位置是否為空值。
我們可以用vector(type, index)來辨別batch中一個向量。每個向量有其特定的下标位置(index)，來表示向量在batch中的順序；類型資訊（type）來指定向量的類型。在進行向量化表達式求值之前，我們需要周遊整個表達式樹，根據每個表達式的操作數和傳回值來配置設定好下标位置，最後根據下标位置統一為向量配置設定記憶體。
延遲物化
selection數組的設計展現了延遲物化的思想，參考論文《Materialization Strategies in a Column-Oriented DBMS》。所謂延遲物化，就是盡可能地将物化（matrialization）這一過程後推，減少記憶體通路帶來的開銷。在執行表達式計算時，往往會先經過Filter表達式過濾一部分資料，再對過濾後的資料執行求值處理；每次過濾都會影響到batch中所有的向量。以上圖中的batch為例，如果我們針對第0個向量設定 vector(int, 0) != 1這一過濾條件，假設vector(int, 0)中有90%的資料滿足該過濾條件（選擇率selectivity = 0.9），那麼我們需要将batch中所有向量90%的資料重新物化到另一塊記憶體中。而如果我們隻記錄滿足該過濾條件的位置，存入selection數組，我們就可以避免這一物化過程。相應的，以後每次向量化求值過程中，都需要參考此selection數組。
向量化原語
向量化原語是向量化執行系統中的執行機關，它最大程度限制了執行期間的自由度。原語不用關注上下文資訊，也不用在運作時進行類型解析和函數調用，隻需要關注傳入的向量即可。它是類型特定（Type-Specific）的，即一類原語隻能處理特定類型。
向量化原語的主體是Tight-Loop的代碼結構。在一個循環體内部，隻需要進行取值和運算即可，沒有任何的分支運算和函數調用。一個簡單的向量化原語結構如下所示：
map_plus_double_col_double_col(int n,
double*__restrict__ res,
double*__restrict__ vector1, double*__restrict__ vector2,
int*__restrict__ selection)
{
if (selection) {
for(int j=0;j<n; j++) {
int i = selection[j];
res[i] = vector1[i] + vector2[i];
}
} else {
for(int i=0;i<n; i++)
res[i] = vector1[i] + vector2[i];
}
} 注：*左右滑動閱覽
其運算過程利用了selection數組，逐漸對向量進行取值、運算和存值，如下圖所示：
向量化原語帶來了以下優點：
- Type-Specific以及Tight-Loop的結構，大大減少了指令解釋的開銷；
- 避免分支預測失敗和虛函數調用對CPU流水線的幹擾，同時也能有利于 loop pipeline 優化【論文引用】
- 從向量中存取資料，有利于觸發cache prefetch，減少cache miss帶來的開銷。
我們為各種标量化表達式提供相應的原語實作，進而完成從标量到向量化的轉變。例如将加法運算 plus(Object, Object) 針對不同操作數類型生成原語，包括plus(double，double)，plus(long, long)等。
短路求值
在向量化原語的基礎上，我們可以進一步對分支運算（也稱為控制流運算 Control-Flow）進行短路求值（short-circuit calculation）優化，提升表達式計算的性能。
例如，case 表達式由n個when表達式、n-1個then表達式、1個else表達式構成。對于表達式
select case when a > 1 then a * 2
when b > 1 then b * 2
else a * b 其邏輯語義是：
- 對于滿足 a > 1 的向量位置，計算 a * 2；
- 對于滿足 a <= 1 and b > 1 的向量位置，計算 b * 2；
- 對于滿足 a <= 1 and b <= 1 的向量位置，計算 a * b；
- 把所有位置的數值組合在一起形成新的向量，輸出。
具有以下樹形結構：
由于标量化表達式按照volcano結構編排，并提供了統一的next()的接口，case表達式必須執行完所有的子表達式a>1，a*2，b>1，b*2和a*b之後，将全部結果彙總到一起，最後做case語義處理。這種執行方式不能根據when表達式的處理結果及時終止計算過程，而是對全部子表達式無差别執行。
引入向量化執行器以後，我們可以設計短路求值來優化此問題，每一個子表達式需要被提供合适的selection數組，進而正确選擇列中合适的位置來進行向量運算。設第i個when條件表達式接受的selection元素集合為
，其輸出的selection元素集合為
，也就是第i個then條件表達式接受的selection元素集合。那麼滿足
，其中
是原始的selection數組中的下标集合。我們把求取selection元素集合的步驟稱為substract selection，case運算的整個過程如下圖所示：
總結
PolarDB-X向量化引擎利用原語（primitive）來建構表達式，以向量作為運作時資料結構。每種原語僅為特定類型進行服務，進而減少了指令總數；原語中的tight-loop結構不僅對CPU流水線十分友好，也允許CPU進行資料預取，并且避免分支預測。此外，一些優化如延遲物化、短路求值，進一步提升了表達式求值性能。
然而，從使用者SQL到向量化執行之間，存在着一道巨大的鴻溝。我們需要解決以下幾個重要問題：
1. 如何确定表達式的輸入輸出類型，并為SQL中的表達式配置設定合适的原語？2. 每個原語需要使用不同的向量來進行輸入和輸出，如何為正确地為原語配置設定向量？3. 每種原語僅為特定類型進行服務，那麼我們必然需要為一個表達式配備大量不同的原語，來适應不同的資料類型。如何應對原語數量爆炸這一問題？
在下一篇文章中，我們将為上述問題的解決方案進行詳細介紹。