Paper: Efficiently Compiling Efficient Query Plans for Modern Hardware — Thomas Neumann, PVLDB 2011.

The core claim: the Volcano iterator model is the wrong abstraction for modern CPUs, and the fix is to compile queries into native machine code that keeps data in CPU registers rather than passing it through function call chains. This is the paper behind HyPer’s query compilation engine, and the model adopted by DuckDB, Umbra, and most high-performance analytical databases built after 2011.

# Why the Iterator Model Fails on Modern Hardware

The Volcano open/next/close model (from the Volcano paper ) has three problems on modern CPUs:

1. next is called once per tuple: for a scan of millions of records, millions of function calls. Each call evicts CPU registers, forcing intermediate results to memory and back.

2. Virtual function calls: next is typically a function pointer or virtual call. Modern CPUs predict branches well for direct calls but consistently mispredict indirect calls, adding ~10–20 cycles per call.

3. Poor data locality: a table scan over a compressed relation must remember the decompression state between next calls — state is in a heap-allocated state record rather than CPU registers, forcing memory round-trips even for simple predicates.

Block-oriented processing (MonetDB, VectorWise) amortises the function-call overhead by passing batches of tuples, but it breaks pipelining: to produce more than one tuple at a time, results must be materialised somewhere — consuming memory bandwidth and losing the ability to fuse adjacent operators.

# The Key Insight: Data-Centric Execution

Reverse the data flow direction.

Instead of operators pulling tuples from their inputs (demand-driven), operators push tuples towards their consumers. Data moves forward from one pipeline-breaker to the next.

Pipeline-breaker: an algebraic operator is a pipeline-breaker for a given input side if it takes an incoming tuple out of the CPU registers (i.e., it must materialise it). A full pipeline-breaker materialises all tuples before continuing.

Examples:

• Selection, projection: not pipeline-breakers — they filter or transform a tuple and pass it directly to the parent, keeping it in registers.

• Hash join (build side): full pipeline-breaker — must materialise all of the build relation into a hash table before the probe side can start.

• Hash join (probe side): not a pipeline-breaker — each probe tuple finds its match and flows to the parent immediately.

• Sort, aggregation: full pipeline-breakers.

The execution model: data is always pushed from one pipeline-breaker into another. Within a pipeline, all operators execute as a single tight loop with tuples kept in CPU registers — no intermediate materialisation, no function calls.

# The produce/consume Interface

Operators expose two conceptual functions to the query compiler (not to each other at runtime):

• produce(): ask the operator to start producing tuples. It recursively calls produce on its inputs, then pushes tuples to its parent via consume.

• consume(attributes, source): called by the operator’s input when a tuple is ready. The operator processes the tuple and calls its parent’s consume.

This interface exists only at compile time — it is used to generate imperative code, not to call at runtime. The generated code has no operator boundaries: the logic of scan, selection, and hash-build collapse into one tight loop.

Translation rules for the running example ⋈_{a=b}(σ_{x=7}(R₁), Γ_{z,count(*)}(σ_{y=3}(R₂))):

⋈.produce:      ⋈.left.produce(); ⋈.right.produce()
⋈.consume(a,s): if s==⋈.left:
                    "materialise tuple in hash table"
                else:
                    "for each match in hashtable[a.joinattr++]"
                    ⋈.parent.consume(a+new attributes)

σ.produce:      σ.input.produce
σ.consume(a,s): print "if "+σ.condition;
                σ.parent.consume(attr,σ)

scan.produce:   print "for each tuple in relation"
                scan.parent.consume(attributes,scan)

Applying these rules to the query tree generates the imperative pseudocode in Figure 4 directly — four sequential loops with no function calls between them.

# Code Generation via LLVM

The compiler generates LLVM IR (intermediate representation) rather than C++ or source code.

Why not C++?

• Compiling generated C++ to machine code takes multiple seconds — unacceptable for ad-hoc queries.

• C++ gives no control over register allocation or overflow flags — can lead to suboptimal code.

Why LLVM IR?

• LLVM offers an unbounded number of virtual registers (SSA form) — the compiler can pretend every attribute has its own CPU register.

• LLVM’s JIT compiles to native code in milliseconds (vs seconds for C++).

• LLVM is architecture-portable and strongly typed.

• LLVM is a full-strength optimising compiler: it eliminates dead code, reorganises branches for prediction, and generates SIMD instructions.

Mixed C++ / LLVM execution model (Figure 6 — “cogwheels”):

Complex operators (sort, hash table management, spilling to disk) are pre-compiled C++ “cogwheels”. The LLVM-generated code is the “chain” connecting them. C++ methods can be called directly from LLVM IR and vice versa with no wrapper overhead — both compile to native code with the same calling convention.

This means:

• Hot path (99% of tuples): pure LLVM, all data in registers, tight loop.
• Cold path (memory allocation, overflow, new pages): calls into C++.

# Pipeline Fragments

A query plan decomposes into pipeline fragments — the code between two consecutive pipeline-breakers. Each fragment is one tight loop:

Fragment 1: scan R₁ → filter x=7 → build hash table ⋈_{a=b}
Fragment 2: scan R₂ → filter y=3 → aggregate Γ_z → build hash table ⋈_{z=c}
Fragment 3: scan Γ_z result → materialise into ⋈_{z=c}
Fragment 4: scan R₃ → probe ⋈_{z=c} → probe ⋈_{a=b} → output

All logic within a fragment runs without crossing a function boundary. Tuple attributes are LLVM virtual registers throughout.

# Performance Tuning Details

Hashing: on TPC-H Q1 (scan + aggregate), more than 50% of initial execution time was in hash table lookups, despite hashing only two simple values. Root cause: the natural while(iter) loop structure for collision chains mixes two tests (does entry exist? did we reach end of chain?) into a 50/50 branch — worst case for branch prediction. The fix:

// Bad: 50% mispredict on the second branch
Entry* iter = hashTable[hash];
while (iter) { ... iter = iter->next; }

// Good: nearly always true (entry exists), nearly always false (no collision)
Entry* iter = hashTable[hash];
if (iter) do { ... iter = iter->next; } while (iter);

Restructuring the branch layout improved hash table lookups by >20%.

Attribute loading: load attributes as late as possible — only when the predicate or computation actually needs them. If a predicate on column A filters out 90% of tuples, loading column B before that predicate wastes 90% of B’s memory bandwidth. The LLVM optimizer handles this automatically when attributes are kept as virtual registers.

SIMD: processing blocks of tuples simultaneously using SIMD registers fits naturally into the framework since LLVM models SIMD values as vector types. Used for predicate evaluation and aggregation.

# Performance Results

OLTP (TPC-C, Table 1): HyPer + LLVM achieves 169,491 tps vs 161,794 tps for HyPer + C++. More importantly, total compile time drops from 16.53 s (C++) to 0.81 s (LLVM) — a 20× reduction. LLVM’s JIT is the difference between practical and impractical for OLTP.

OLAP (TPC-H queries Q1–Q5, Table 2):

HyPer + LLVM is 2–4× faster than VectorWise and 4× faster than HyPer + C++ for scan-heavy queries. Q1 highlights the register effect most clearly: it is a single scan + aggregation with a natural C++ implementation that “looks efficient” but cannot keep data in registers, while LLVM’s tight loop can.

Branch and cache analysis (Table 3, callgrind): LLVM code has dramatically fewer branch mispredictions than MonetDB across all queries (e.g., Q1: 188K vs 456K mispredictions; Q3: 697K vs 1.9M). L1 and L2 cache misses are also 2–10× lower, confirming the code locality argument.

Microbenchmarks (Figure 8, cascading selections): interpreted iterator model is the slowest by a large margin. Compiled iterator model (eliminating virtual calls but keeping structure) is better. Block-oriented processing is better still. Data-centric compilation (this paper) matches or beats all others — and uniquely, with zero filter conditions the query takes near-zero time because the compiler optimises away the entire computation over empty fragment work.

# Key Takeaways

The data-centric, push-based, LLVM-compiled model described here is now the standard for high-performance analytical databases. HyPer, Umbra, DuckDB, SingleStore, and CockroachDB’s vectorised engine all trace directly to the ideas in this paper.