作者：君啟
介紹
在上篇文章
《每次都需要解釋大量指令？使用 PolarDB-X 向量化引擎》中，我們介紹了PolarDB-X向量化引擎的原理，以及運作時的結構。本文将對向量引擎的上下文建構進行詳細介紹。
所謂上下文建構，就是為向量化引擎準備好合适的執行環境，可以概況為以下幾個問題：
- 如何确定表達式的輸入輸出類型，并為SQL中的表達式配置設定合适的原語？
- 每個原語需要使用不同的向量來進行輸入和輸出，如何正确地為原語配置設定向量？
- 每種原語僅為特定類型進行服務，那麼我們必然需要為一個表達式配備大量不同的原語，來适應不同的資料類型。如何應對原語數量爆炸這一問題？
PolarDB-X引入了表達式綁定、靜态類型系統、代碼模闆等多種技術來解決上述問題。
上下文建構
表達式綁定
在優化器完成優化階段之後，我們從中得到代表着表達式樹形結構的RexNode樹，對其進行表達式綁定操作。表達式綁定需要對表達式樹進行前序周遊，并完成以下工作：
- 對于周遊到的函數調用節點，提取函數簽名資訊，通過函數簽名進行反射，執行個體化向量化原語；
- 在周遊過程中進行将周遊到的RexNode節點（包括列、表達式調用、常量等）按周遊順序配置設定向量位置下标。下标配置設定完成後，在運作時依據下标資訊統一進行記憶體配置設定，供表達式輸入、輸出使用。
下圖是表達式 ((a+b)-c)*((a/b)%2) 的表達式樹結構，以及通過表達式綁定得到的向量化原語執行個體，和配置設定得到的Batch結構：
此外，通過在表達式綁定時配置設定輸入、輸出向量的位置下标，我們可以靈活的處理各類資料依賴問題，包括以下的資料依賴場景：
- 多個表達式輸出到一個向量中，例如case表達式中的各個then、else子表達式。可以給這些子表達式配置設定相同的輸出向量Index；
- 多個表達式将同一個向量作為輸入。例如select fun_1(expr), fun_2(expr)，expr表達式輸出的結果可以作為fun_1和fun_2表達式的輸入。可以通過配置設定相同的輸入向量Index來實作。
- 某些條件下，作為輸出的中間結果向量可以覆寫掉作為輸入的中間結果向量。
靜态類型系統
在基于行的執行器中，類型系統的靜态綁定并不是必須的。例如在 MySQL 中，表達式構成一個樹狀結構，上層的表達式結構通過調用下層提供的不同傳回值類型的接口（例如：val_int()、val_decimal()、val_str() 等），遞歸地計算出最終結果。這種方式實作簡單，但是直到運作時才能确定表達式的輸入傳回類型，進而決定需要調用的計算函數，效率比較低。
向量化系統則要求靜态類型系統。在解析器和優化器完成執行計劃的建構之後，必須保證每個表達式的類型是正确的、不需要運作時确定的。隻有這樣，才能為它執行個體化正确的向量化原語、配置設定正确類型的向量。
PolarDB-X将使用者傳來的SQL解析為AST之後，對于樹形的AST需要自頂向下地進行類型推導，确定整個表達式樹的類型資訊。具體過程包括：
- 操作數類型檢查（Operand Type Checker）。子表達式的傳回類型，會作為父表達式的操作數類型。每個表達式配備有相應的操作數類型檢查規則，通過此規則來檢查操作數類型是否合法；
- 隐式類型轉換（Type Coercion）。當子表達式的傳回類型不能成為合法的父表達式操作數類型時，我們需要調用相應的類型轉換規則，嘗試進行傳回值類型return type到操作數類型operand type的轉換。辦法是，生成一個合法的IMPLICIT_CAST表達式，将return type強制轉換為合法的operand type類型。由于此轉換對于使用者來說是透明的，是以稱為隐式類型轉換。
- 傳回值類型推導（Return Type Inference）。當表達式具備了合法的操作數之後，可以調用相應的傳回值推導規則，通過操作數推出正确的傳回值類型。
以上三個步驟如下圖所示：
關于類型系統這部分，在接下來的文章中會進行詳細介紹。
代碼生成技術
PolarDB-X采用apache freemarker架構，根據代碼模闆來批量生成向量化原語的源碼，避免了Type-Specific引入的代碼量激增的問題。原語 = 代碼模闆 X 類型配置，原語就是由代碼模闆，配合以不同的類型，在項目編譯時批量生成的。
一個簡化後的原語代碼模闆如下所示，其中${} 符号代表在編譯時将要被替換成特定類型和表達式。
public class ${className} {
public ${className}(int outputIndex, VectorizedExpression[] children) {
super(DataType.${type.outputDataType}Type, outputIndex, children);
}
@Override
public void eval(EvaluationContext ctx) {
super.evalChildren(ctx);
VectorBatch batch = ctx.getVectorBatch();
${type.inputType1}[] array1 = ((${type.inputVectorType1}) leftInputVectorSlot).${type.inputType1}Array();
${type.inputType2}[] array2 = ((${type.inputVectorType2}) rightInputVectorSlot).${type.inputType2}Array();
${type.outputType}[] res = ((${type.outputVectorType}) outputVectorSlot).${type.outputType}Array();
for (int i = 0; i < batchSize; i++) {
int j = sel[i];
res[j] = (${type.outputType})array1[j] ${operator.op} (${type.outputType})array2[j];
}
}
} 注：*左右滑動閱覽
參考文獻
[1] MonetDB/X100: Hyper-Pipelining Query Execution
[2] Materialization Strategies in a Column-Oriented DBMS
[3] Rethinking SIMD Vectorization for In-Memory Databases
[4] Breaking the Memory Wall in MonetDB
[5] Relaxed Operator Fusion for In-Memory Databases: Making Compilation, Vectorization, and Prefetching Work Together At Last