Vectorized Execution

Vectorized execution is a query processing model in which operators — scan, filter, aggregate, join — pass batches of values to each other rather than one row at a time. A filter receives, say, a thousand values of a column, evaluates the predicate over all of them in a tight loop, and hands the survivors on as another batch.

It changes nothing about which data is read. It changes how much CPU work it takes to process the data once it has been read.

The problem it solves

The classical design for query execution is the Volcano iterator model. Every operator exposes a next() call that returns one row, and a query plan is a tree of operators pulling rows from their children. It is clean and composable, which is why it became standard.

Its cost shows up when a query processes hundreds of millions of rows. The 2005 MonetDB/X100 paper by Boncz, Zukowski, and Nes measured it. In MySQL, adding two values took 38 instructions and roughly 49 CPU cycles on the machine they tested, about 20 of which were the function call itself — overhead paid again for every single value. The paper’s broader argument was that row-at-a-time execution both wastes cycles on interpretation and hides the work from the compiler: a loop that performs one addition per call gives the compiler and CPU nothing to optimize across.

The opposite extreme had been tried too. MonetDB’s earlier model processed a whole column per operator, which removed the per-value overhead but materialized entire columns between steps. The paper found that design bound by memory bandwidth instead: the CPU spent its time waiting for large intermediate results to move through memory.

How the middle position works

Vectorized execution keeps the pull-based operator tree but makes each call return a vector of values. Three things follow.

• Call overhead is amortized. The cost of invoking an operator is spread over hundreds or thousands of values instead of charged to each.
• Inner loops become simple. The actual work is a loop over a typed array, which a compiler can optimize and a CPU can pipeline — the opportunity the paper found hidden in per-row calls.
• Intermediate results stay in cache. Vectors are small enough to fit in CPU cache, avoiding the memory bottleneck of whole-column materialization.

The vector size is the tuning point between the two failure modes. X100 used a default of 1024 values, reasoning that all the vectors in play should fit comfortably in cache, while vectors that are too small lose the loop efficiency and bring back the per-call overhead. On a 100 GB TPC-H workload the authors reported raw execution performance one to two orders of magnitude above the systems they compared against — a 2005 result on 2005 hardware, best read as evidence of how large the overhead was rather than as a figure to expect today.

What it does not do

Vectorized execution is often confused with neighboring ideas, and the differences matter when comparing engines.

• It is not columnar storage. Columnar storage reduces the bytes read. Vectorized execution reduces the CPU work per byte. An engine that reads columnar files but executes row-at-a-time gets the first benefit and not the second, which is one reason two engines reading the same Parquet files can perform very differently.
• It is not parallelism across machines. Vectorization makes one execution unit efficient. Massively parallel processing divides work among many units. A query can suffer from either problem, and fixing one does not fix the other.
• It does not help every data type equally. A fixed-width numeric column fits the tight-loop model well. Variable-length strings require indirection and length checks, so string-heavy workloads gain less.

For someone choosing or operating an analytical engine, the practical reading is this: when a query is slow after filtering has already cut the data down, the question is no longer how much is read but how efficiently it is processed, and the execution model is where that answer lies. Where it sits among the other layers of an analytical engine is worked through in Analytical Engines: Where the Speed Actually Comes From.

References: Boncz, Zukowski, and Nes, MonetDB/X100: Hyper-Pipelining Query Execution (CIDR 2005).