Application of SIMD Technology in MPP Databases

1. Background

SIMD stands for (Single Instruction Multiple Data), representing the ability to operate on a batch of data with a single instruction, allowing parallel operations on multiple sets of data with a set of instructions. This technology was first applied in video acceleration decoding, where Intel’s Pentium series introduced MMX (Multi-Media Extensions) technology to support MPEG video decoding. The common data formats used in images are RGB565, RGBA8888, YUV422, etc. The characteristic of these formats is that a component of a pixel is always represented by data less than or equal to 8 bits. If traditional processors perform calculations, although the processor’s registers are 32 bits or 64 bits, they can only use the lower 8 bits of these data, which seems a bit wasteful. If we split a 64-bit register into eight 8-bit registers, we can complete eight operations simultaneously, thus improving computational efficiency by eight times. Later, Intel further implemented the SSE, SSE2~SSE4, and AVX instruction sets. The following two diagrams illustrate the functional differences of each instruction set and the richness of the instruction sets supported by different CPUs.

Table 1: Functional Iteration Supported by Different Instruction SetsFigure 2: Illustration of SIMD Instruction Sets Supported by Different CPU SeriesWith the development and popularization of mobile internet and IoT technology, the amount of data that systems can use is growing exponentially. How to cope with the rapid processing and querying of massive data has led big data software vendors to urgently need to use SIMD vector acceleration to process large volumes of data. SIMD instructions can control multiple parallel processing micro-units on a controller simultaneously, executing multiple data streams with a single instruction operation. In this way, within the same clock cycle, the CPU’s ability to process data is greatly increased. SIMD instructions are essentially very similar to a vector processor, capable of executing the same operation on a set of data (also known as a “data vector”) simultaneously, thus achieving spatial parallelism. It can effectively improve floating-point operation speed by using single instruction multiple data technology and parallel processing of multiple floating points within a single clock cycle.To illustrate the difference and advantages of SIMD computation compared to traditional CPU computation, let’s consider multiplication:Figure 3: Traditional CPU Multiplication Calculation MethodFigure 3 presents a simple multiplication calculation: four numbers need to be multiplied by 3. A total of 12 instructions need to be executed:◇ 4 load memory instructions◇ 4 multiplication instructions◇ 4 memory write-back instructionsFigure 4: SIMD Calculation MethodFrom Figure 4, we can see that a CPU with a 128-bit register can hold four 32-bit numbers and perform a calculation in one go, making it four times faster than executing one instruction at a time. Using SIMD instructions allows for batch processing of data, reducing the original 12 instructions down to just 3. Contemporary X86 processors typically support SIMD instructions such as MMX, SSE, AVX, etc., to accelerate CPU calculations. Of course, SIMD instructions have certain conditions as can be inferred from the above diagrams.◇ The data being processed needs to be continuous, and aligned memory can achieve better performance◇ The register usage is higher than that of traditional SISD CPUsThere are generally two ways to generate SIMD instructions:Auto VectorizedAutomatic vectorization, where the compiler automatically analyzes whether a for loop can be vectorized. If possible, it automatically generates vectorized code, typically with the -O3 optimization flag enabling auto vectorization.Handwritten SIMD InstructionsSIMD can also be supported through libraries. It can also be done directly using libraries provided by Intel for vectorized programming, such as the header file for SSE API being xmmintrin.h, and for AVX being immintrin.h. This implementation method is the most efficient, but requires programmers to be familiar with SIMD coding, and is not universal. For example, an AVX vectorization algorithm cannot run on machines that do not support the AVX instruction set, nor can it be replaced with the SSE instruction set.

2. Common Application Scenarios of SIMD in MPP Databases

SIMD instructions provide new opportunities for enhancing the performance of analytical database engines. We studied the use of SIMD in open-source OLAP databases such as StarRocks and ClickHouse to see how they use SIMD instructions to accelerate queries in various SQL execution processes.◆2.1 Acceleration of Sort CalculationsIn data analysis scenarios, most SQL queries require sorting of a certain column of data. How to leverage SIMD instructions to accelerate data sorting is a very important research direction for MPP databases.However, the sorting scale using SIMD technology is limited by the length of the vector registers, so the sorting network implemented by SIMD can only serve as a building block. It generates multiple ordered small vectors, which are then merged at the outer layer. Quick sort is not suitable for optimization using SIMD because the sub-blocks produced by quick sort are not uniform. In contrast, for merge sort, nearly all sub-block sizes are equal, making it possible to accelerate the sorting of sub-blocks using SIMD when the sub-block size reaches the vector length threshold.Bitonic sorting is particularly suitable for parallel computation. Before introducing bitonic sorting, we first need to explain bitonic sequences and Batcher’s theorem.Bitonic Sequence: A sequence that is first monotonically increasing and then monotonically decreasing (or vice versa), such as 1, 5, 8, 6, 3.Batcher’s Theorem: Divide any bitonic sequence A of length 2n into two equal halves X and Y, and compare the elements in X with those in Y in their original order, that is, a[i] with a[i+n] (i<n). and="" any="" are="" bitonic="" element="" goes="" in="" into="" is="" larger="" max="" min="" not="" one="" resulting="" sequence="" sequence,="" sequence.="" sequence.Bitonic Sorting: Assuming we have a bitonic sequence, we can partition it into two bitonic sequences according to Batcher’s theorem, then recursively partition each bitonic sequence to obtain shorter bitonic sequences until the length of the resulting subsequence is 1, at which point the output sequence is sorted in monotonically increasing order.See the diagram below: For ascending sorting, the specific method is to split a sequence (1…n) in half, assuming n=2^k, then compare 1 and n/2+1, placing the smaller one above, followed by comparing 2 and n/2+2, and so forth; then treat them as two sequences of length (n/2), as they are both bitonic sequences, we can repeat the above process; a total of k rounds are repeated, with the last round comparing sequences of length 2, resulting in the final sorted output.Illustration of Bitonic SortingThe above describes the process of completing sorting with a bitonic sequence, but not all sequences are bitonic sequences. First, we need to generate a bitonic sequence.The process of generating a bitonic sequence is called Bitonic merge, which is essentially a divide and conquer approach. It is a bottom-up process—treating two adjacent monotonic sequences with opposite monotonicity as a bitonic sequence, merging these two adjacent monotonic sequences each time to generate a new bitonic sequence, then sorting (same as the third step of bitonic sorting). As long as the two adjacent sequences of length n have opposite monotonicity, we can connect them to obtain a bitonic sequence of length 2n, then perform a bitonic sort on this 2n sequence to make it ordered, and finally merge the two adjacent 2n sequences (during sorting, the first is in ascending order, and the second in descending order). Starting with n as 1, doubling each time until it equals the length of the array, at which point we only need to perform a single-direction (monotonicity) sort.Taking an array of 16 elements as an example:1. Merge adjacent elements to form 8 monotonic sequences with opposite monotonicity.2. Merge pairs of sequences to form 4 bitonic sequences, sorting them in opposite monotonicity.3. Merge the 4 sequences of length 4 with opposite monotonicity, generating 2 sequences of length 8, and sort them.4. Merge the 2 sequences of length 8 with opposite monotonicity to generate 1 sequence of length 16, and sort.As shown in the diagram:Finally, here’s a complete sorting illustration for an 8-element array:Having discussed the bitonic sorting algorithm, let’s look at how to use SIMD instructions to accelerate bitonic sorting.Compile using g++ -o test test.cc -mavx2 and run ./test to verify the sorting results of this algorithm, achieving a speedup of 4-5 times compared to the std::sort implementation, as shown in the actual data below:If you want to sort larger arrays, you can use merge_sort to recursively call this basic sorting algorithm.◆2.2 Acceleration of Numerical Condition ComparisonsSQL statements like select a from tbl1 where a>1 are very common. Accelerating the execution process of the filter operator in SQL statements using SIMD instructions is highly beneficial.Taking the expression a>1 as an example, let’s see how ordinary data filtering is implemented.Figure 5: Memory Predicate CalculationTraverse column a, comparing the data in a with 1, and writing the comparison results into a filter result array, which consists of UInt8 (1 byte) where 1 represents satisfying the filter condition and 0 represents not satisfying the filter condition.Traverse the filter result array to obtain the offsets of elements that are 1, copying the corresponding data stored in the database to the result column.The following demonstrates how StarRocks 2.3 obtains target data based on the filter result:The above code snippet is based on StarRocks 2.3 version. BinaryColumnBase<T>::filter_rangeAfter loop unrolling, AVX2 instructions are used to accelerate the calculations. At 256 bits, each calculation processes 32 bytes (SIMD_BYTES), which corresponds to 32 elements. Each loop compares 8 bits with 0, writing a 1 to the target if greater than 0. Assuming all 32 comparisons are 1, then the target will have 32 bits set to 1.if(mask==0) If all are 0, it means none of the 32 elements in this loop satisfy the condition, so do nothing.else if(mask==0xffffffff) If all are 1, it means all 32 elements in this loop satisfy the condition, thus all 32 elements can be copied to the result column at once. Since columns in StarRocks are represented as arrays, this involves copying continuous memory. The loop unrolling reduces register dependencies, and continuous memory copying is CPU cache friendly.If neither all 0 nor all 1, it is necessary to continue to individually assess the 32 elements, first converting the mask into a 32-bit integer, then copying the values of the elements that are 1 to the result column.From the above, it can be seen that when filtering int values, this function compresses 8 filtered data (i.e., int type) into a __m256i in each loop. Each call to the above instruction processes 32 8-bit integers, where 8 bits cannot overflow, precisely fitting into 256 bits. Based on SIMD, the CPU can shift from calculating one value at a time to calculating a group of values simultaneously, significantly boosting computational efficiency and speed.The AVX2 instructions involved in this code snippet are introduced as follows:#ifdef__AVX2__ indicates that the current environment supports the AVX2 instruction set.__m256i contains a vector of several integer data types, such as char, short, int, unsigned long long, etc. For example, a 256-bit vector can hold 32 chars, 16 shorts, or 8 ints, where these integers can be either signed or unsigned;_mm256_setzero_si256() initializes a 256-bit (32-byte) bitmap to all zeros, i.e., one XMM register;_mm256_loadu_si256() reads a 256-bit integer data (32-byte address without alignment) from a memory address;_mm256_cmpgt_epi8(f,all0) processes 8-bit integers, comparing two 256-bit integers f and all0, filling the corresponding bits with 1 if the corresponding 8 bits of f are greater than those of all0, otherwise filling with 0;_mm256_movemask_epi8() creates a mask based on the highest bits of each 8-bit group in the 256-bit integer;

◆2.3 Acceleration of Join Calculations

Join calculations are typically the most time-consuming operators. Optimizing the latency of join operators can generally be divided into two approaches. The first approach is to improve the join calculation algorithm, such as optimizing the implementation of HashJoin (including reducing the computational complexity of the hash function and the query complexity of collision columns). It can also involve partitioning tables appropriately to enhance parallelism, balancing between network transmission and computational parallelism.The second approach is to trim the data as much as possible during the actual computation, reducing the amount of data participating in the operator’s calculation. Runtime Filter has shown particularly good effects in scenarios involving star schema models where fact tables join dimension tables. In such scenarios, the fact table is usually very large, and most filtering conditions are on the dimension tables.Runtime Filter (hereafter referred to as RF) filters data at runtime, typically occurring during the join phase. When multiple tables are joined, filtering often accompanies optimizations such as predicate pushdown to reduce the scanning of data in join tables and minimize I/O generated during shuffle stages, thereby enhancing query performance. The optimization method of RF also filters data but does so without requiring user configuration; the execution engine automatically performs filtering optimizations during query execution.In StarRocks, to fully utilize the parallel processing capabilities of AVX2 instructions, a SIMD-based Runtime Filter has been implemented to further accelerate multi-table joins.The following illustrates a scenario in which StarRocks utilizes Runtime Filter to accelerate joins:As shown in the figure, the Fact and Dim tables join via the id field. The left side shows the unoptimized scenario, where the left table needs to scan 1 billion rows of data, while the optimized scenario only requires scanning 1 million rows, significantly reducing data scanning and greatly enhancing query efficiency. The implementation here is the Runtime Filter, which pushes the query results of the right table down to the left table during SQL execution, achieving early filtering effects. Currently, both broadcast and shuffle runtime filters are supported, and the entire process is optimized automatically.The following is a code snippet that uses SIMD to accelerate the construction of a Bloom filter during the runtime filter process:◆2.4 Acceleration of Case Conversion for StringsCase conversion is also a common operation in SQL. Taking the ASCII Latin character case conversion functions (i.e., toLower() and toUpper()) as an example, let’s look at the implementation of string case conversion in ClickHouse.The principle is quite simple: it uses the flip_case_mask to flip the case of characters (the ASCII values of uppercase and lowercase letters differ by 32). The not_case_lower_bound and not_case_lower_bound are used to mark the range of characters to be converted, such as a~z or A~Z. However, with the support of SSE2, we can load 16 characters for conversion at once.◆2.5 Accelerating Substring Searches in StringsSubstring matching similar to LIKE is also a common scenario in SQL queries. For both prefixes and suffixes, dictionary tree indexing + inverted organization can be used for fast searches. However, for substring matching like %abc%, it is not easy to use indexing, and a row-by-row matching approach is typically employed. Thus, accelerating substring searches within single rows of data is very meaningful. Let’s look at the conventional substring matching algorithm:The principle involves matching one character at a time, but it has the following disadvantages:◇ Byte-by-byte comparison requires sequential memory access, wasting CPU cycles;◇ Incorrect branch predictions waste even more CPU cycles;◇ Such code is difficult to execute in a disordered parallel manner.So how can we use SIMD to optimize substring search performance in MPP databases? Assuming we have some 8-byte registers, we want to search for the substring “cat” within the string “a_cat_tries”.First, we fill the first and last bytes of “cat” into two registers, repeating as much as possible until the registers are full.Then we load the string “a_cat_tries” into two other registers, one of which starts loading from the substring length – 1 character.Next, we compare the contents of the two sets of registers, where matching contents correspond to 1, and non-matching contents correspond to 0.Finally, we merge the contents of the two registers using a bitwise AND operation.At this point, we find that only the second bit (starting from zero) is 1, indicating that searching can only start from this position to potentially find the substring. This reduces our search times.The following provides an implementation based on the AVX2 instruction set in SIMD instructions:◆2.6 Summary of ScenariosFrom the above scenarios, with the increasing richness of the instruction sets provided by modern CPU architectures, different instructions can be used to perform various parallel operations on multiple data. Many basic operators in current MPP databases have been rewritten based on SIMD instruction sets to achieve corresponding performance improvements. The operators mentioned above are just a few examples; many more operators can be accelerated using SIMD instruction sets. Accelerating operators based on SIMD instruction sets is a very important direction for improving MPP performance.

3. Conclusion

Enhancing the analytical performance of OLAP engines in big data scenarios is a timeless topic. In recent years, new technological directions have continuously emerged in this field, including storage formats, data trimming, CodeGen, vectorized computing, and more. Vectorized computing fully utilizes the SIMD instructions of CPU hardware to perform parallel computations on contiguous memory data to achieve execution speedup. SIMD utilizes data-level parallelism independent of concurrency, allowing the same instruction to be executed on multiple data in the same clock cycle. Currently, Intel compilers are configured with the AVX-512 (Advanced Vector Extensions) instruction set, which increases the width of SIMD registers to 512 bits, meaning 16 four-byte integer column values can be computed in parallel. To effectively use SIMD instruction sets for vectorized processing, it is essential to organize data correctly to maximize benefits. How to properly and reasonably organize data and fully utilize SIMD instructions is a very important research direction for improving OLAP engine performance.

4. References

1. https://blog.csdn.net/nazeniwaresakini/article/details/1080015432. https://blog.csdn.net/wypblog/article/details/1231735073. https://www.addesp.com/archives/54864. https://blog.csdn.net/junerli/article/details/1238324315. https://github.com/Geolm/simd_bitonic6. https://www.intel.com/content/www/us/en/develop/documentation/cpp-compiler-developer-guide-and-reference/top/compiler-reference/intrinsics.html