Patent Review-SIMD Series–Vectorization Engine
1. Patent Content
Alibaba‘s patent:Method and Device for Vectorized Data Processing, the main idea is: for query scenarios involving row-oriented tables or a mix of row and column storage, it is necessary to manually convert row-oriented tables into column-oriented tables before performing vectorized processing, which is costly. Alibaba provides a method to identify sub-tree nodes in the query plan tree that do not support vectorized operations and convert the data into a format that supports vectorized operations. Essentially, it means attaching a conversion operator to operators that do not support vectorization, transforming row-oriented data into the columnar format required for vectorized execution.openGauss does this by attaching a RowToVec operator, which converts rows to vectors, to operators that are row-oriented, enabling the entire execution plan tree to be executed in a vectorized manner. Of course, if the output requires a row format, it then attaches a VecToRow operator to convert the vector back to rows.StarRocks‘s patent:A Database Expression Based on a Vectorized Execution Engine, the main idea: traditional databases mostly use a volcano model, where operators and expressions are executed row-wise. Compared to traditional databases, vectorized execution engines have fewer virtual function calls, fewer branching decisions, are more CPU cache-friendly, and are easier to optimize with SIMD instructions. For expression computation and vectorized execution, a method for reusing expression calculations is proposed, with the main innovation being the idea of expression reuse. For example, a SQL statement:SELECT a+b,a+d,a+b+c,a+b+c+d FROM table; it provides a way to find the common expression parts among the 4 expressions, which are:a+b,a+b+c. It treats a+b as a logical projection, naming it tmp1, and then substitutes tmp1 into the a+b+c expression, resulting in tmp1+c; next, it treats a+b+c as a logical projection, naming it tmp2, and substitutes tmp2 into a+b+c+d. The final expressions are:tmp1,a+d,tmp1+c,tmp2+d. This reduces redundant calculations of expressions.Oriental Guoxin‘s patent:Query Methods and Devices for Vectorized Databases: For databases containing NULL values and overflows, existing CPU processes data using branching judgments, which can incur clock cycle damage if the branching judgment is incorrect, and the looping due to branching judgments leads to inefficiency in handling NULL values and overflows. For example, the process of checking NULL and performing addition is as follows:
For i=0 to N{ if(!(c1_isNull[i] & c2_isNull(i))) result[i] = C1[i]+C2[i];}where N is the total number of rows, c1 and c2 are two columns of data in the database, c1_isNull and c2_isNull are the null indicators for c1 and c2, respectively, and result is the query result. Within the loop, for each row, an if judgment is executed first, and through the bitwise AND operation of c1_isNull and c2_isNull, if the operation result does not satisfy that at least one of c1 and c2 is NULL, then the addition operation is performed on c1 and c2. By the end of the loop, N rows are processed, but 2N operations were executed, including N times for the if branching judgment and another N times executing corresponding operations based on the branching judgment results.Innovation point: the process is as follows, removing the branching judgment
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];}where N is the total number of rows, c1 and c2 are two columns of data in the database, tmp_c1 and tmp_c2 are the null handling results for c1 and c2, respectively, and c1_isNull, c2_isNull, and result_isNull are the null indicators for c1, c2, and result, respectively, with result being the query result.Within the loop, for each row, the result_isNull is obtained through the bitwise AND operation of c1_isNull and c2_isNull, indicating whether result is null. Here, the identification rules for c1_isNull, c2_isNull, and result_isNull are that if the corresponding data is null, they are all 0; if the corresponding data is not null, they are all 1. By the end of the loop, the number of processed rows is N, and the number of operations performed is N, which reduces the number of operations by half compared to traditional query processes.Furthermore, this concept can be extended to SIMD vectorization. The For loop processes a batch of data at once. The main idea remains to eliminate branching judgments.
2. References
https://www.modb.pro/doc/55436https://www.modb.pro/doc/49941https://www.modb.pro/doc/50225