作者：君启
介绍
在上篇文章《每次都需要解释大量指令？使用 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
【相关阅读】
每次都需要解释大量指令？使用 PolarDB-X 向量化引擎
如宝马3系和5系：PolarDB-X 与 DRDS 并驾齐驱
