CMSC724: Query Compilation and Morsel-Driven Parallelism
Instructor: Amol Deshpande
This chapter covers “Efficiently Compiling Efficient Query Plans for Modern Hardware” (Thomas Neumann, VLDB 2011), its 2021 retrospective, and “Morsel-Driven Parallelism” (Leis, Boncz, Kemper, Neumann; SIGMOD 2014).
The previous chapter reduced per-row overhead by processing batches. Here we examine specializing and fusing code for a chosen plan, then ask how to schedule its pipelines across cores. Compilation addresses the work within a pipeline; morsel-driven execution addresses how that work is divided.
1. The Same Diagnosis, a Different Cure
Both techniques respond to the cost of generic tuple-at-a-time execution, but target different boundaries.
Vectorization does more work per operator call. It retains operator interfaces and may store intermediate vectors between them. These stores can be inexpensive when the vectors stay in cache, and passing a vector does not always require copying its values.
Compilation can specialize expression evaluation and fuse adjacent operators into one loop. Specialization removes decisions already known from the plan; fusion removes selected runtime interfaces and intermediate stores.
In the figure’s join-and-group-by plan, producing a row may invoke several operators and expression routines. Compilation aims to expose the useful work directly to the machine-code compiler. It preserves SQL’s generality at the system level while generating code specific to each chosen plan.
This introduces a new cost: code generation and compilation happen before the specialized code can run. For a short query, saving execution time may not repay that setup cost.
2. HIQUE: Compiling the Operators
HIQUE uses operator templates to generate C code for a query, then compiles and executes it. A template describes an operator’s algorithm; substituting query-specific details produces its specialized implementation.
For a fixed-width integer field, generated code can know the field’s type and byte offset in advance. That removes repeated type dispatch and attribute-location work. Variable-width values, NULLs, and runtime data still require their appropriate checks.
HIQUE removes the tuple-at-a-time iterator structure, but operator boundaries remain visible through materialized results. Specializing each operator therefore does not eliminate the cost of moving data between operators. Neumann’s comparison also identifies the latency of invoking an external optimizing compiler. HyPer addresses both the data-flow boundary and the compilation path.
Compilation has several targets. An engine can generate native code directly, generate an intermediate representation, or generate code for a virtual machine. JVM bytecode is compiled code too, and a JVM may JIT-compile it to native instructions. The useful questions are which runtime overheads are removed, whether operators are fused, and what setup cost remains.
3. HyPer: Data-Centric Code Generation
The central objective is keep intermediate values in registers as long as practical. If a scan loads a value, a filter checks it, and a projection computes from it, those steps should reuse the value without constructing a new tuple at every boundary.
Function calls do not automatically empty registers. The difficulty is that independently compiled, general operator implementations constrain what the compiler can keep live across calls and may require explicit stores of intermediate results. Data-centric code generation organizes execution around a tuple’s path through useful work, rather than treating each operator as a separate runtime routine.
Pipeline breakers
A pipeline breaker, in this paper’s register-oriented sense, forces intermediate data into memory. This is related to, but broader than, the usual notion of an operator that blocks until it has consumed its input.
A sort must collect its input. A hash join’s build side stores tuples in a hash table. These are natural boundaries between generated pipelines. A filter, a projection, and a hash join’s probe side can instead participate in one fused pipeline: read a tuple, test it, find matches, and immediately process those matches.
The hash table itself is still in memory; fusion does not eliminate all memory accesses. It removes avoidable intermediate materialization between compatible operations.
Flipping the direction
The generated code follows a producer-to-consumer flow. Once a scan produces a row, the code carries out the downstream work until it reaches a materialization boundary.
For a simple filter and sum, the conceptual result is:
sum = 0
for row in Orders:
amount = row.amount
if amount > 100:
sum += amount
emit sumThis example assumes non-NULL amounts and omits SQL’s empty-input result rule. A real generator must implement both. The point is the code shape: scan, filter, and aggregate update are in one loop, with no per-row next() calls between them.
For a hash join, first generate a pipeline that constructs the build table. After it completes, run a probe pipeline that filters probe rows, looks up matches, and passes each match directly to its consumer. Push-style generated execution does not require a thread or queue per operator. It describes the control flow inside the fused code.
A reading note on the figure: the paper builds the hash table on the left side of the join. If you have been drawing the build input on the right, identify the build and probe roles explicitly before matching the code to the plan. Either drawing convention can represent the same algorithm.
Produce and consume
The engine still needs a modular way to generate code for arbitrary plan trees. Operators implement two code-generation methods:
produce()asks a child to generate the code that will supply rows.consume()emits code for processing a row supplied by a child.
At generation time, the root’s produce() descends toward the leaves. A scan emits a loop and invokes its parent’s consume() to fill in the loop body. A selection emits a condition and asks its parent to generate code inside it. An aggregate emits an update to its state.
Thus the scan, selection, and aggregate cooperate to construct the loop shown above. The traversal happens once during code generation; it does not recur for every runtime tuple. These methods preserve modularity in the generator while eliminating selected operator calls from the generated execution code.
At a pipeline breaker, the generator emits storage and establishes the next execution phase. Code generation therefore respects the same build-before-probe dependency as an interpreted hash join.
Compiling the generated code
Generating a high-level program and running an optimizing compiler can take too long for interactive queries. HyPer instead generates LLVM IR, a typed intermediate representation of instructions and control flow. LLVM’s just-in-time (JIT) compiler turns it into native code during query preparation.
LLVM supplies optimization and machine-code generation without requiring the database to implement a complete compiler backend. Skipping high-level source parsing also saves work, but optimizing IR still has a cost.
The relevant latency is generation + compilation + execution, not execution alone. If interpreted execution takes 5 ms, paying 50 ms to compile a 1 ms execution loses overall. For a long-running query or a frequently reused plan, that same compilation may pay off. This motivates caching compiled plans and adapting the amount of compilation to expected work.
How fast?
The reported comparisons show substantial gains over the tested PostgreSQL baseline, with much closer competition against vectorized execution. Those are results for particular workloads and implementations, not a universal ranking.
Both approaches remove much of the overhead of a generic tuple interpreter. Their remaining costs differ: a vectorized engine manages batches and temporary arrays, while a compiled engine pays code-generation costs and must control code size and compilation complexity.
Can an engine use both? Yes. Generated code can process batches, and vectorized operators can call compiled expressions. An engine chooses where fusion, batching, and SIMD each help. They are design dimensions that can be combined, although an effective combination requires attention to materialization boundaries and code size.
4. The Ten-Year Retrospective
The retrospective asks what changes when a compilation design must support a broader SQL workload and predictable response times. Its lesson is to evaluate compilation as part of the complete engine, including control flow, latency, and debugging.
One function, or one per pipeline
The original design favors one generated function containing the query’s execution phases. A later design uses one function per pipeline, coordinated by a state machine: an explicit record of which phase is ready and what follows it.
For a hash join, the controller runs the build pipeline, waits for completion, then enables the probe pipeline. More complex control flow, including recursive queries, needs phases that may repeat. Separate pipeline functions make those dependencies easier to represent and manage; a monolithic function is not incapable of recursion, but is less convenient for this architecture.
Away from LLVM
The slides report LLVM compilation times of roughly 40–90 ms for the discussed TPC-H workloads, compared with 1–2 ms for a specialized direct x86-64 backend. These are measurements of specific configurations, not general guarantees.
A compiler backend translates an intermediate representation into machine instructions. A database-specific backend can perform a narrower set of optimizations and prioritize predictable latency, whereas LLVM provides broad optimization machinery whose cost can vary with generated code complexity.
Adaptive compilation starts with an interpreter or cheaper execution tier and switches to optimized code when enough work remains to justify compilation. Faster direct code generation changes that tradeoff; it does not establish that adaptive strategies are always unnecessary. The decision still depends on query duration, reuse, and the quality of the generated code.
Debugging
Generated code creates a debugging challenge: a failure occurs in code that did not exist as a normal source file before the query ran. The engine needs ways to inspect generated representations and relate failures back to SQL expressions and physical operators.
This is a maintenance cost of compilation, alongside compile latency and correctness. The execution speedup must justify those costs for the workload the system serves.
5. Morsel-Driven Parallelism
Compilation explains how to run a pipeline efficiently on one core. Parallel execution also needs to decide which worker runs which part of the input.
A multi-socket server often has NUMA (non-uniform memory access): cores share an address space, but memory is attached to different nodes. Accessing a nearby node is typically cheaper than accessing memory across a socket interconnect. ccNUMA additionally provides cache coherence, so processors have a consistent view of shared memory; coherence does not make all accesses equally fast.
The slide’s server has two sockets, four memory nodes, and thirty-two cores. The exact topology is illustrative. The general challenge is to balance work while keeping memory accesses local.
Morsels and tasks
A morsel is a small horizontal slice of an input relation: a range of rows to process. A task runs a pipeline on one morsel. A pool of worker threads repeatedly asks a dispatcher for another task, so faster workers can process more morsels instead of waiting after finishing a fixed allocation.
For example, a million-row scan divided into ten 100,000-row morsels can run on four workers. Each begins with one morsel and requests another upon completion. If some morsels take longer after filtering or joining, the remaining work can still be assigned to available workers. The paper’s approximately 100,000-row size is a useful reference point, not a universal parameter.
Morsels and vector batches serve different purposes. A batch is the unit passed between operators; a morsel is the input unit given to a scheduler. A vectorized pipeline may process many batches within one morsel, and a compiled pipeline may loop over its rows directly.
Balancing work and preserving locality
The dispatcher prefers work whose input resides near the worker. If nearby work runs out, work stealing permits a worker to take work associated with another node. This trades some remote memory traffic for less idle time. Locality and balance are both objectives, and neither can always be maximized independently.
The connection to Chapter 2 is the separation of logical work units from physical workers. Morsels permit runtime balancing of many tasks. They do not automatically solve a single task that produces a huge join result, a serialized bottleneck, or skew in an indivisible shared structure.
Hash joins still need coordination
Build tasks populate the join state before probe tasks can use it. The paper describes a two-phase parallel construction of a shared hash table: workers first prepare build tuples, then construct the table using concurrent insertion. Probe morsels can then use that shared table. A dependency barrier ensures probing does not begin before the required build state is ready.
A shared structure avoids requiring every worker to build a complete private copy, but introduces concerns about contention, allocation, and NUMA placement. Morsel scheduling provides load balance; it does not remove the engineering needed inside parallel operators.
The three techniques answer different questions:
- Vectorization: how much data should an operator process per call?
- Compilation: which runtime decisions and interfaces can be specialized away?
- Morsel scheduling: how should pipeline work be distributed among workers?
A pipeline can be vectorized, compiled, and scheduled over morsels. Keeping these questions separate makes it easier to understand systems that combine the ideas.