PolarDB-X 向量化引擎的类型绑定与代码生成

2022-01-07 00:00:00 分配 类型 表达式 向量 量化

介绍



在上篇文章《每次都需要解释大量指令?使用 PolarDB-X 向量化引擎》中,我们介绍了PolarDB-X向量化引擎的原理,以及运行时的结构。本文将对向量引擎的上下文构建进行详细介绍。


所谓上下文构建,就是为向量化引擎准备好合适的执行环境,可以概况为以下几个问题:


  1. 如何确定表达式的输入输出类型,并为SQL中的表达式分配合适的原语?

  2. 每个原语需要使用不同的向量来进行输入和输出,如何正确地为原语分配向量?

  3. 每种原语仅为特定类型进行服务,那么我们必然需要为一个表达式配备大量不同的原语,来适应不同的数据类型。如何应对原语数量爆炸这一问题?


PolarDB-X引入了表达式绑定、静态类型系统、代码模板等多种技术来解决上述问题。



上下文构建



表达式绑定


在优化器完成优化阶段之后,我们从中得到代表着表达式树形结构的RexNode树,对其进行表达式绑定操作。表达式绑定需要对表达式树进行前序遍历,并完成以下工作:


  1. 对于遍历到的函数调用节点,提取函数签名信息,通过函数签名进行反射,实例化向量化原语;

  2. 在遍历过程中进行将遍历到的RexNode节点(包括列、表达式调用、常量等)按遍历顺序分配向量位置下标。下标分配完成后,在运行时依据下标信息统一进行内存分配,供表达式输入、输出使用。


下图是表达式 ((a+b)-c)*((a/b)%2) 的表达式树结构,以及通过表达式绑定得到的向量化原语实例,和分配得到的Batch结构:



此外,通过在表达式绑定时分配输入、输出向量的位置下标,我们可以灵活的处理各类数据依赖问题,包括以下的数据依赖场景:


  1. 多个表达式输出到一个向量中,例如case表达式中的各个then、else子表达式。可以给这些子表达式分配相同的输出向量Index;

  2. 多个表达式将同一个向量作为输入。例如select fun_1(expr), fun_2(expr),expr表达式输出的结果可以作为fun_1和fun_2表达式的输入。可以通过分配相同的输入向量Index来实现。

  3. 某些条件下,作为输出的中间结果向量可以覆盖掉作为输入的中间结果向量。


静态类型系统


在基于行的执行器中,类型系统的静态绑定并不是必须的。例如在 MySQL 中,表达式构成一个树状结构,上层的表达式结构通过调用下层提供的不同返回值类型的接口(例如:val_int()、val_decimal()、val_str() 等),递归地计算出终结果。这种方式实现简单,但是直到运行时才能确定表达式的输入返回类型,进而决定需要调用的计算函数,效率比较低。


向量化系统则要求静态类型系统。在解析器和优化器完成执行计划的构建之后,必须保证每个表达式的类型是正确的、不需要运行时确定的。只有这样,才能为它实例化正确的向量化原语、分配正确类型的向量。


PolarDB-X将用户传来的SQL解析为AST之后,对于树形的AST需要自顶向下地进行类型推导,确定整个表达式树的类型信息。具体过程包括:


  1. 操作数类型检查(Operand Type Checker)。子表达式的返回类型,会作为父表达式的操作数类型。每个表达式配备有相应的操作数类型检查规则,通过此规则来检查操作数类型是否合法;

  2. 隐式类型转换(Type Coercion)。当子表达式的返回类型不能成为合法的父表达式操作数类型时,我们需要调用相应的类型转换规则,尝试进行返回值类型return type到操作数类型operand type的转换。办法是,生成一个合法的IMPLICIT_CAST表达式,将return type强制转换为合法的operand type类型。由于此转换对于用户来说是透明的,所以称为隐式类型转换。

  3. 返回值类型推导(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 = ; 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


来源 https://mp.weixin.qq.com/s/4M56FHni593jyd823XMzQA

相关文章