ClickHouse divides data into multiple partitions, each partition is further divided into multiple index granularities, and then processes part of it using multiple CPU cores to achieve parallel data processing. With this design, a single query can utilize all CPUs of the machine. The extreme parallel processing capability significantly reduces query latency.

Distributed Computing

In addition to excellent single-machine parallel processing capabilities, ClickHouse also provides linearly scalable distributed computing capabilities. ClickHouse automatically breaks down queries into multiple tasks dispatched to the cluster, performing multi-machine parallel processing, and finally aggregating the results.

Vectorized Execution and SIMD

ClickHouse not only stores data in columns but also performs calculations in columns. Traditional OLTP databases usually adopt row-based calculations because point lookups are predominant in transaction processing, and the SQL computation load is small, making the benefits of implementing these technologies not very obvious. However, in analytical scenarios, the computation load involved in a single SQL can be very large, and processing each row as a basic unit can lead to significant performance losses:

1. Each row of data requires calling the corresponding function, leading to a high proportion of function call overhead;

2. The storage layer stores data in columns, organized in memory by columns, but the computation layer processes by rows, failing to fully utilize the CPU cache’s prefetching capability, resulting in severe CPU cache misses;

3. Row processing cannot utilize efficient SIMD instructions;

ClickHouse implements a vectorized execution engine, which calls SIMD instructions once for a batch of columnar data in memory (instead of calling it for each row), not only reducing the number of function calls and lowering cache misses but also fully leveraging the parallel capability of SIMD instructions, significantly shortening computation time. The vectorized execution engine can typically bring several times the performance improvement.

What Is SIMD?

SIMD

It stands for Single Instruction Multiple Data, meaning a single instruction stream can execute multiple data streams. A simple example is vector addition and subtraction.

Relationship Between SSE and SIMD

SSE (Streaming SIMD Extensions) is a new instruction set introduced by Intel when launching the Pentium III processor in 1999. As its name suggests, SSE is a SIMD instruction set. SSE has eight 128-bit registers, XMM0 to XMM7, which can hold four 32-bit single-precision floating-point numbers. It is evident that SSE is a set of instructions specifically designed for SIMD (Single Instruction Multiple Data) architectures. Through it, users can execute operations on multiple data segments simultaneously, achieving data parallelism (aka: vector processing).

SSE2 is an upgraded version of the SSE instruction set, with the same register and instruction format as SSE, but it can handle more data types, such as double-precision floating-point numbers. SSE3 adds 13 new instructions.

Reference: https://www.cnblogs.com/xidian-wws/p/11023762.html

Three Methods of Using SIMD Programming in C++

There are three ways to use the SIMD instruction set: 1) Compiler optimization, which involves writing programs in C/C++ and compiling them with SIMD optimization options. If supported by the CPU, the compiler optimizes according to its own rules. 2) Using intrinsic instructions, referring to Intel manuals, for SIMD instructions, certain built-in library functions can be directly used during programming, and the compiler will generate corresponding SIMD instructions under the support of the CPU and compiler. For example: double _mm_cvtsd_f64 (__m128d a) will be translated into the instruction: movsd during compilation. 3) Embedded assembly, directly embedding corresponding SIMD instructions in the program.

Intrinsic Header Files and Corresponding SIMD Instruction Sets and Visual Studio Versions

Both VS and GCC support the SSE instruction Intrinsics. SSE has multiple different versions, with corresponding Intrinsics included in different header files. If you are sure to use a specific version of the SSE instruction, you only need to include the corresponding header file.

For example, to use SSE3, you would include:

#include <tmmintrin.h>

If you are not concerned about which version of the SSE instruction to use, you can include all:

#include <intrin.h>

Reference: [https://www.cnblogs.com/huaping-audio/p/4115890.html]

Comparison of Simple Operations Between Intrinsics and SSE Instructions

Code using Intrinsic functions:

__m128 a1, b2; __m128 c1; for (int i = 0; i < count; i++) { a1 = _mm_load_ps(a); b2 = _mm_load_ps(b); c1 = _mm_add_ps(a1, b2); }

Corresponding assembly instruction code:

for(int i = 0; i < count; i++) _asm { movaps xmm0, [a]; movaps xmm1, [b]; addps xmm0, xmm1; }

Brief explanation of one operation:

addps XMM,XMM/m128 source memory contents aligned by double word, adding four single-precision floating-point numbers to the destination register, with the result sent to the destination register.

Computer Hardware Support and Compiler Support

To use Intel’s SIMD instruction set, you need not only the hardware support of the current Intel processor but also the support of the compiler.

$ grep -q sse4_2 /proc/cpuinfo && echo "SSE 4.2 supported" || echo "SSE 4.2 not supported"

If your machine supports SSE4.2, it will print:

SSE 4.2 supported

Considerations for Using SIMD

• Utilize advantages: Frequently called basic functions and a large amount of parallelizable computations.

• Avoid: The SSE instruction set has very poor branch handling capabilities, and extracting certain element data from 128-bit data comes at a significant cost, making it unsuitable for computations with complex logic.

How Does ClickHouse Use SIMD?

In articles searching for why CLICKHOUSE is fast, many mention the technologies used by CH, such as columnar storage, compression, and the vector engine.

CH extensively uses SIMD wherever it can improve CPU computation efficiency.

This article takes a simple example of the LowerUpperImpl function in ClickHouse (which converts case).

It tests and produces a benchmark efficiency comparison between SIMD mode and non-SIMD mode.

The code is as follows, with key points annotated:

template <char not_case_lower_bound, char not_case_upper_bound> struct LowerUpperImpl { public: static void array( char * src, char * src_end, char * dst){ //32 const auto flip_case_mask = 'A' ^ 'a'; #ifdef __SSE2__ const auto bytes_sse = sizeof(__m128i); const auto src_end_sse = src_end - (src_end - src) % bytes_sse; const auto v_not_case_lower_bound = _mm_set1_epi8(not_case_lower_bound - 1); const auto v_not_case_upper_bound = _mm_set1_epi8(not_case_upper_bound + 1); const auto v_flip_case_mask = _mm_set1_epi8(flip_case_mask); for (; src < src_end_sse; src += bytes_sse, dst += bytes_sse) { //_mm_loadu_si128 means: Loads 128-bit value; that is, loads a 128-bit value. //Loads 16 contiguous 8-bit characters at once const auto chars = _mm_loadu_si128(reinterpret_cast<const __m128i *>(src)); //_mm_and_si128(a,b) means: Perform bitwise AND operation between a and b, i.e., r=a&&b //_mm_cmpgt_epi8(a,b) means: Compare each 8-bit integer of a to the corresponding 8-bit integer of b; if greater, return 0xff, otherwise return 0x00. //_mm_cmplt_epi8(a,b) means: Compare each 8-bit integer of a to the corresponding 8-bit integer of b; if less, return 0xff, otherwise return 0x00. //The following line of code performs operations on this 128-bit register in parallel three times, ultimately yielding a 128-bit number, where the positions with 0xff indicate that the 8-bit number is within the range of [case_lower_bound, case_upper_bound]; the remaining positions, filled with 0, are numbers outside the operation range. const auto is_not_case = _mm_and_si128(_mm_cmpgt_epi8(chars, v_not_case_lower_bound), _mm_cmplt_epi8(chars, v_not_case_upper_bound)); //Each 0xff position is ANDed with 32, changing the original 0xff position to 32, meaning that every number within the range of [case_lower_bound, case_upper_bound] is now changed to 32, while others remain unchanged. const auto xor_mask = _mm_and_si128(v_flip_case_mask, is_not_case); //XOR the source chars content with xor_mask; bytes that meet the criteria may switch from uppercase to lowercase or vice versa; those not within the range remain as is. const auto cased_chars = _mm_xor_si128(chars, xor_mask); //Store the result set in dst _mm_storeu_si128(reinterpret_cast<__m128i *>(dst), cased_chars); } #endif #ifndef __SSE2__ for (; src < src_end; ++src, ++dst) if (*src >= not_case_lower_bound && *src <= not_case_upper_bound) *dst = *src ^ flip_case_mask; else *dst = *src; #endif }};

The complete code is available at the git repository.

Test results are as follows:

For 32-bit input:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefgh took 6.8059 seconds root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefgh took 9.39051 seconds

For 64-bit input:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh took 9.26642 seconds root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh took 17.3588 seconds

For 128-bit input:

root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread sse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh took 10.2672 seconds root@2458d1317fc8:/var/tmp# g++ -std=c++11 -Wall -pedantic -pthread nosse.cpp && ./a.out new des is abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh took 31.7568 seconds

This is just one simple function. But why is ClickHouse fast? A glimpse into the details reveals much.

ClickHouse has emerged in the OLAP field in just a few years, which is closely related to its pursuit of perfection in design and details.

For Russians, open-sourcing a product is a significant event. If it’s not open-source, that’s fine. But once it is, it’s a major industry event, just like nginx.