专利研读-SIMD系列-向量化引擎

专利研读-SIMD系列-向量化引擎

1、专利内容

阿里巴巴的专利：向量化处理数据的方法及装置，主要思想为：对于行存表或行、列存混合存储的查询场景，需要手工将行存表转换成列存表再在列存表基础上进行向量化处理，这种方式代价较高。阿里提供了一种方法从查询计划树中识别出数据不支持向量化操作的子树节点，将数据转换成支持向量化操作的数据。理解其实就是在不支持向量化的算子上再挂一个转换算子，将行存数据转换成向量化执行需要的列存形式。openGauss就是这么干的，针对行存的算子，在其上再挂个RowToVec即行转向量的算子，以支持整个执行计划树执行时能够向量化执行。当然，若输出需要行的形式，那再挂一个VecToRow的算子，即将向量再转成行。

StarRocks的专利：一种基于向量化执行引擎的数据库表达式，主要思想：传统数据库大多是火山模型，火山模型的算子和表达式都是按行执行。和传统数据库相比，向量化执行引擎具有更少的虚函数调用，更少的分支判断，CPU缓存更友好，易于SIMD指令优化等优点。针对表达式向计算向量化执行，提出了一种表达式计算的复用方法，当然主要创新点还是表达式复用的思想。比如一个SQL语句：SELECT a+b,a+d,a+b+c,a+b+c+d FROM table；提供一种方式找出4个表达式计算中的公用表达式部分，这里的公用表达式：a+b,a+b+c。将a+b作为一个逻辑投影，命名为tmp1，然后将tmp1带入a+b+c表达式中，即tmp1+c；接着将a+b+c作为一个逻辑投影，当作tmp2，并将tmp2带入a+b+c+d。最后表达式：tmp1,a+d,tmp1+c,tmp2+d。也就是减少表达式的冗余计算。

东方国信的专利：向量化数据库的查询方法及装置：对于数据库中存在NULL值和溢出，现有CPU利用分支判断对数据进行处理，一旦分支判断错误会产生时钟周期的损害，而且存在分支判断的循环导致处理NULL值和溢出的效率低下。比如判断NULL并进行相加的流程：

For i=0 to N{if(!(c1_isNull[i] & c2_isNull(i)))result[i] = C1[i]+C2[i];
}

其中，N为数据总行数，c1和c2为数据库中的两列数据，c1_isNull和c2_isNull分别为对应c1和c2的空标识，result为查询结果。在循环内，对于每一行都要先执行一个if判断，通过c1_isNull和c2_isNull的按位与运算，在其运算结果不满足c1和c2其中至少存在一个NULL的情况下，使c1和c2执行加法运算。直至循环结束，处理的行数为N，却执行了2N次操作，其中有N次在执行if的分支判断，另外N次根据分支判断结果执行对应的操作。

创新点：流程如下，去掉了分支判断

For i=0 to N{result_isNull[i] = c1_isNull[i] & c2_isNull[i];tmp_c1[i]=result_isNull[i]&c1[i];tmp_c2[i]=result_isNull[i]&c2[i];result[i]=tmp_c1[i]+tmp_c2[i];
}

其中，N为数据总行数，c1和c2为数据库中的两列数据，tmp_c1和tmp_c2分别为对应c1和c2的空值处理结果，c1_isNull、c2_isNull和result_isNull分别为对应c1、c2和result的空标识，result为查询结果。在循环内，对于每一行，先通过c1_isNull和c2_isNull的按位与运算获取result_isNull，用于指示result是否为空。其中，c1_isNull、c2_isNull和result_isNull对应的标识规则为，若对应的数据为空，则全为0；若对应的数据不为空，则全为1。直至循环结束，处理的行数为N，对应执行了N次操作，相较于传统的查询流程操作次数降低一半。

再将上述思想扩展到SIMD向量化中。For循环一次处理一批数据。其实主要思想还是去掉分支判断。

2、参考

https://www.modb.pro/doc/55436

https://www.modb.pro/doc/49941

https://www.modb.pro/doc/50225