CMSC724: Vectorized Execution
Instructor: Amol Deshpande
This chapter follows “MonetDB/X100: Hyper-Pipelining Query Execution” (Boncz, Zukowski, Nes; CIDR 2005), with background on MonetDB and its MIL execution model.
Chapter 1’s iterator model passes one tuple per call. X100 asks: can we retain that composability while doing enough work per call to use the CPU efficiently? Its answer is to process small batches of column values. We first introduce the hardware concepts that explain why this helps, then contrast tuple-at-a-time, whole-column, and vector-at-a-time execution.
1. How a Modern Processor Works
Pipelining
An instruction passes through several stages, conceptually including fetch, decode, execution, memory access, and write-back. Instruction pipelining overlaps these stages for different instructions, much as an assembly line works on several items at once.
The key distinction is latency versus throughput. An instruction may take several cycles from start to finish, while a pipeline can start new instructions before earlier ones finish. Overlap improves throughput without making each individual instruction finish in one cycle. Real processors are more complicated than this five-stage model, but the distinction remains useful.
The figure illustrates that overlap: in one cycle, different instructions occupy different stages. Keeping those stages busy requires a supply of useful instructions and available operands. Dependencies, branches, and cache misses can interrupt that supply.
Branch prediction
A conditional branch chooses which instructions come next. In if (a > 10) ..., the processor may need to fetch later instructions before the comparison’s result is available. Branch prediction guesses the path so execution can continue speculatively.
A correct guess avoids a wait. A wrong guess discards work on the incorrect path and redirects execution. The penalty depends on the processor and when the branch resolves; it cannot be calculated simply from pipeline depth.
For a database filter, predictability depends on the pattern of qualifying rows. Mostly true or mostly false conditions can be easy to predict. Random outcomes near 50% are often harder. Two datasets with the same fraction of qualifying rows may therefore behave differently if one is clustered and the other randomly ordered.
Superscalar and SIMD
Two additional mechanisms exploit parallelism within a core:
Superscalar execution issues multiple instructions in a cycle when resources and dependencies permit. Out-of-order execution can run ready instructions while others wait, while preserving the program’s required results. Independent operations across several rows give the processor more opportunities to overlap work.
SIMD (single instruction, multiple data) applies one instruction to several values in parallel. For example, a 256-bit vector can hold four 64-bit numbers, so one vector instruction can add four pairs. The supported widths and operations depend on the processor.
These are different: superscalar execution overlaps different instructions; SIMD performs the same operation on several data items. A compiler may generate SIMD automatically from a suitable loop, or an implementation may use explicit vector intrinsics. Batch processing creates opportunities for SIMD but does not guarantee it.
Registers and caches
Registers are small, fast storage locations used for operands and temporary results inside the CPU. Caches hold recently accessed memory in a hierarchy between registers and main memory. Reusing values in registers or cache avoids slower accesses farther down that hierarchy.
A working set is the data actively used during a computation. If it is too large for cache, repeated passes may repeatedly fetch data from main memory. A cache miss means the requested data is absent at the relevant cache level; the CPU must obtain it from a slower level.
Function calls can require saving values or storing them in memory, and can limit compiler optimization across boundaries. They do not automatically erase every register. Similarly, a branch misprediction discards speculative work, not the program’s committed register state. The execution-engine goal is to make useful data reuse and instruction overlap easy.
2. Why Databases Are Nearly the Worst Case
Now consider a scan, filter, and aggregate over millions of rows. In a tuple-at-a-time interpreter, each row crosses operator interfaces and its expressions are evaluated by general routines.
For price * (1 - discount), a generic evaluator may inspect expression nodes, locate attributes, handle their types and NULL flags, and dispatch arithmetic operations. The multiplication is useful work; repeated decisions about how to multiply are overhead.
Several costs can follow:
- Dispatch overhead: many calls relative to the small amount of work per row.
- Limited optimization: indirect calls and general expression code can obstruct inlining, loop transformations, and automatic SIMD generation.
- Instruction footprint: moving among substantial operator implementations can reduce instruction-cache locality.
- Data movement: values may be stored and reloaded at operator boundaries instead of being reused cheaply.
None of these is inevitable for every iterator engine. The point is that per-row abstraction costs become visible when disk I/O no longer dominates.
Amortization means spreading a fixed cost over more useful work. If a call costs c and processes one row, the cost per row is c. If it processes N rows, the interface cost per row is roughly c/N. Batching helps most when each row’s useful work is small compared with the interface overhead.
This chapter focuses on CPU execution. GPUs and FPGAs offer different forms of parallelism, but also introduce data-transfer, programming, and workload constraints; more raw compute alone does not settle the execution design.
3. The Branch Misprediction Experiment
The experiment selects array positions satisfying src[i] < v. The selectivity is the fraction that qualify. A straightforward implementation branches for each element:
int j = 0;
for (int i = 0; i < n; i++)
if (src[i] < v) out[j++] = i;An alternative always writes the candidate index but advances the output position only when the comparison succeeds:
int j = 0;
for (int i = 0; i < n; i++) {
out[j] = i;
j += (src[i] < v); // the comparison contributes 0 or 1
}Assume out has space for n entries; only its first j entries are valid. A failed candidate is overwritten by the next candidate. This eliminates the data-dependent if in the source, although the generated machine code must be checked to confirm the intended transformation.
On the paper’s Athlon MP, the branching version is most expensive near 50% selectivity for the random data tested. The arithmetic version has a flatter runtime curve because it does similar work for every element. It is not necessarily faster at extreme selectivities: avoiding mispredictions costs extra writes and arithmetic. The paper also uses Itanium 2 to illustrate hardware-supported predication.
Predication replaces a control decision with conditional data effects. The general lesson is that fewer source-level operations do not necessarily mean faster execution. To reproduce the experiment, use compiled code and inspect compiler output: the compiler may already transform the branch. Row ordering also affects the result.
4. What the Numbers Looked Like
The paper benchmarks TPC-H Query 1, which filters a single table, computes arithmetic expressions, and groups the surviving rows. It has no joins, so it exposes the costs of scanning, expression evaluation, and aggregation. The reported comparison is roughly 0.5 seconds for MonetDB/X100 versus 26 seconds for MySQL. These are historical measurements of the tested configurations, not a prediction for current releases.
They also compare against hand-coded C for the specific query — no interpretation whatsoever, everything hard-coded. On the same AthlonMP, hand-coded comes in at 0.22 s against X100’s 0.50 s, so X100 is within about a factor of two of code written for this one query:
A general-purpose system that executes arbitrary SQL getting close to hand-written code for a specific query is a strong result — though do not expect it to hold for more complex queries.
Profiling separates useful arithmetic from the surrounding work. The paper’s MySQL measurements show far more cycles spent in general evaluation machinery than the arithmetic itself should require. That motivates a controlled target: make a general engine approach specialized code by removing overhead, while retaining support for arbitrary queries.
The experiment does not isolate batch size as the only cause of the speedup. Storage layout, type specialization, aggregation implementation, and other system differences also contribute.
5. MonetDB and the BAT Model
MonetDB uses a decomposition storage model (DSM): represent a logical table through separate columns rather than complete rows. Its Binary Association Tables (BATs) conceptually associate a row identifier with a column value. The row identifier is an OID, or object identifier.
For a table with rows (price, discount), corresponding entries in the two columns must be aligned so the engine multiplies each price by its own discount. Dense identifiers can be implicit positions rather than physically repeated in every column.
In the historical MIL execution model, a query becomes a sequence of whole-column operations. A filter produces qualifying row identifiers; an arithmetic operation produces a result column; a join produces associations between matching rows. Each operation finishes and materializes its result before the next uses it.
These operations use type-specialized primitives, such as a routine for adding integer columns and another for adding floating-point columns. Choosing the primitive once avoids deciding the arithmetic type separately for each value. That is different from compiling an entire query into machine code.
The storage and execution choices are related but independent. Storing columns does not require materializing an entire column between every operator, which is precisely the choice X100 revisits.
MonetDB’s two problems
Large intermediates. A whole-column operation produces its entire output before the consumer begins, so temporary columns can consume substantial memory.
Repeated memory traffic. If those columns exceed cache capacity, the next operation must fetch them again from main memory. An engine is memory-bandwidth bound when moving bytes, rather than performing arithmetic, limits its throughput.
This creates a tradeoff. Tuple-at-a-time execution does little work per call but can pass a row through several operators promptly. Whole-column execution amortizes dispatch over many values and exposes tight loops, but writes and rereads large intermediates. X100 aims for the useful middle ground.
6. X100: Combining the Two
X100 retains a Volcano-style interface, but a call produces a vector: a batch of values rather than one tuple. Each operator processes a batch and passes it onward before moving to the next batch.
For example, a scan returns aligned batches of price and discount. A primitive computes discounted prices for those positions, and an aggregate consumes that batch. The temporary result is small enough to be reused through cache rather than becoming a whole-table column in main memory.
The vector size balances two objectives: enough values to amortize calls and expose efficient loops, but a small enough active working set for good cache reuse. The footprint depends on the number and width of columns, temporary vectors, and operator state—not just row count. The paper finds a broad useful range, rather than a single universally optimal size.
What if a filter retains only some positions? A selection vector can record indices of qualifying rows. For values [5,12,7,20] and predicate value > 10, it contains [1,3] using zero-based indices. A consumer reads those positions from any aligned column, avoiding a copy of every surviving value.
A boolean mask, [false,true,false,true], is another representation. An index list and a mask carry similar information but have different costs. Engines may also compact selected values; the best choice depends on selectivity and the consumer.
The example plan shows the physical operators: get the BAT for shipdate, apply the condition, produce a selection vector, and pass that selection vector along to the operators consuming the other vectors.
Generating the per-type code
Specialization requires many variants: addition of two integer vectors, addition of a vector and a scalar constant, and so on. A primitive is one such small processing routine, usually a tight loop over values of known types.
X100 generates these variants from templates and selects an appropriate one for the query. Type and argument-form decisions happen outside the inner loop. This provides specialization without hand-writing every variant or compiling a new complete program for every query.
Updates
X100 is a column store, so it has the update problem from the storage module, and it solves it the same way: a delta structure recording deletes and inserts separately, periodically merged into the columnar storage. Updates are handled as a delete plus an insert.
This is the same split we have seen throughout — operational databases that do updates, and column-store-style systems that do analytics with batch updates.
7. A Note on the Word
In execution-engine papers, vectorized execution usually means batch processing, not necessarily hardware SIMD. SIMD is one possible optimization within the batch loops.
Also distinguish a column’s storage layout from execution granularity. A column store may process whole columns, small column batches, or individual values. Pull versus push is a further independent choice: either control structure can move batches.
| Execution style | Unit crossing an operator boundary | Main benefit | Main concern |
|---|---|---|---|
| Tuple-at-a-time | One row | Simple composition and prompt consumption | Per-row dispatch overhead |
| Whole-column | A complete intermediate column | Long specialized loops | Large intermediates and memory traffic |
| Vector-at-a-time | A bounded batch | Amortized dispatch and cache reuse | Batch management and temporary storage |
Vectorization makes efficient loops visible to the compiler and gives the engine control over the size of transient intermediates. It does not make every branch predictable or force a large join hash table into cache. Its contribution is a practical compromise between modular operators and efficient execution. Chapter 4 explores another route: generating code that removes selected runtime operator boundaries entirely.