A complex SQL query for analytics is broken down into a query plan consisting of multiple stages, called operators, which may be distributed across multiple machines for parallel execution. Query planners can perform a lot of optimizations by choosing which operators to use, in which order to execute them, and where to run each operator.
Within each operator, the query engine may need to do various things with the values in a column, such as finding all the rows where the value is among a particular set of values (perhaps as part of a join), or checking whether the value is greater than, say, 15. The query engine will likely also need to look at several columns for the same row—for example, to find all sales transactions where the product is “bananas” and the store is a particular store of interest.
For data warehouse queries that must scan millions of rows, we need to worry not only about the amount of data they have to read off disk, but also the CPU time required to execute complex operators. The simplest kind of operator is like an interpreter for a programming language. While iterating over each row, it checks a data structure representing the query to find out which comparisons or calculations it needs to perform on which columns. Unfortunately, this is too slow for many analytics purposes. Two alternative approaches for efficient query execution have emerged:
Query compilation
The query engine takes the SQL query and generates code for executing it. The code iterates over the rows one by one, looks at the values in the columns of interest, performs whatever comparisons or calculations are needed, and copies the necessary values to an output buffer if the required conditions are satisfied. The query engine then compiles the generated code to machine code (often using an existing compiler such as LLVM) and runs it on the column-encoded data that has been loaded into memory. This approach to code generation is similar to the just-in-time (JIT) compilation approach that is used in the Java Virtual Machine (JVM) and similar runtimes.
Vectorized processing
The query is interpreted, not compiled, but it is made fast by processing many values from a column in a batch instead of iterating over rows one by one. A fixed set of predefined operators is built into the database; we can pass arguments to them and get back a batch of results.
For example, we could pass the product_sk column and the ID of a product (say, “bananas”) to an equality operator, and get back a bitmap (one bit per value in the input column, which is 1 if it matches that ID). We could then pass the store_sk column and the ID of the store of interest to the same equality operator, and get back another bitmap. Finally, we could pass the two bitmaps to a bitwise AND operator, as shown in Figure 4-9; the result would be a bitmap containing a 1 for all sales of bananas in a particular store.
Diagram showing a bitwise AND operation between two bitmaps representing product and store IDs, resulting in a compressed bitmap for sales data.
Figure 4-9. A bitwise AND between two bitmaps lends itself to vectorization.
The two approaches are very different in terms of their implementation, but both are used in practice. Both can achieve very good performance by taking advantage of the characteristics of modern CPUs:
-
Preferring sequential memory access over random access to reduce cache misses
-
Doing most of the work in tight inner loops (i.e., with a small number of instructions and no function calls) to keep the CPU instruction processing pipeline busy and avoid branch mispredictions
-
Making use of parallelism such as multiple threads and single-instruction, multiple data (SIMD) instructions
-
Operating directly on compressed data without decoding it into a separate in-memory representation, which saves memory allocation and copying costs