A few weeks ago I read Remy Wang’s blog post on continuation-passing style and the day after, I kept thinking about Inkfuse, a query engine I’d been picking apart on and off for a while. The two felt related in a way I couldn’t quite articulate, so I’m writing this to figure out why.

Inkfuse is a vectorized-meets-compiled query engine out of TUM. It comes from the same group that brought us HyPer, the system most people point at when they want to talk about compiled query execution. If you’ve read Neumann’s 2011 paper on data-centric code generation, Inkfuse sits on the same shelf, only with a different set of trade-offs that I’ll get to later. The implementation is available on Github and reading it side by side with the paper made some things click that the paper alone didn’t.

CPS is what functional programmers reach for when they want to make control flow explicit. Instead of a function returning a value to its caller, the caller hands the function a continuation, a “what-to-do-next” callable, and the callee calls it with the result. You can compile any program to CPS, and the resulting program no longer has a call stack in the usual sense: every call is a tail call, every return is just another call.

The reason I started seeing CPS in Inkfuse is that data-centric compiled query engines are under this lens a hand-written CPS transform of an iterator-based plan.

Pull versus Push

The textbook way to execute a query plan is the Volcano iterator model. Each operator exposes open / next / close. To get a tuple out of the root, you call next, which calls next on its child, which calls next on its child, and so on. The control flow walks down to the leaf¹, picks up a tuple, walks back up evaluating filters and projections, and hands a tuple to the caller. The model gives you a clean separation between operators but pays for it in virtual calls and instruction-cache misses, both of which add up at high tuple rates.

To keep things concrete, here’s the plan I’ll keep coming back to. It’s the simplest query plan shape: a scan, a filter, an aggregate.

In Volcano, running this query pulls from the root. The aggregate’s next calls the filter’s next, which calls the scan’s next in a loop until a row passes the predicate, then the row walks back up. In Rust, with iterators standing in for operators, that’s roughly:

// A row tuple (a, b, c).
type Row = (i64, i64, i64);

fn run_pull(rows: Vec<Row>) -> i64 {
    rows.into_iter()
        .filter(|r| r.2 > 10)
        .map(|r| r.0 * r.1)
        .sum()
}

The HyPer model flips that. Instead of pulling from the top, you produce from the bottom. The compiler walks the plan and calls produce on each operator, top-down. When produce reaches a scan it emits a loop, and the body of that loop is the consume of the scan’s parent, whose body is the consume of its parent, and so on up the tree. By the time code generation is done, the pipeline is a single tight loop with no virtual dispatch and the tuple lives in registers the whole way up. Neumann calls this data-centric code generation. DuckDB implements a similar push model but using a vectorized approach instead of code generation.

The same query in push form looks more like this:

fn scan(rows: &[Row], mut consume: impl FnMut(&Row)) {
    for r in rows {
        consume(r);
    }
}

fn filter(
    rows: &[Row],
    pred: impl Fn(&Row) -> bool,
    mut consume: impl FnMut(&Row),
) {
    scan(rows, |r| if pred(r) { consume(r) });
}

fn run_push(rows: &[Row]) -> i64 {
    let mut acc = 0;
    filter(rows, |r| r.2 > 10, |r| acc += r.0 * r.1);
    acc
}

The consume callback at the bottom is the aggregate’s body. filter takes it, wraps it in its own predicate check, and passes the wrapped callback down to scan. After inlining, the whole thing collapses to a single loop: the aggregate body sitting inside the filter body sitting inside the scan body.

Looking at the shape of that we can see that each operator takes its parent’s consume and threads control into it. Nothing returns a tuple back up the chain; every operator just hands off to the next consumer by calling its continuation.

That is what I pointed out as CPS here the consume function is the continuation and the operator chain is the call chain and the IU bindings threaded through each operator are the environment the continuation closes over. A tuple passed to consume is the value the continuation receives and code generation is the CPS transform itself, emitting machine code instead of source.

Inkfuse

Pure HyPer-style compilation makes a different trade-off than dynamic dispatch instead you pay an LLVM compilation tax up front. For short queries that tax can be longer than just running the query in an interpreter. People have tried various ways around it: cheaper compiler backends like custom bytecode VMs (NoisePage went this way), speculative compilation that runs an interpreter and switches over to native code once it’s ready, or breaking the pipeline into pieces small enough that you don’t have to generate fresh code for them at all.

That last option is more or less what Inkfuse does. Instead of compiling each pipeline as a single monolithic function, it composes the pipeline out of small fused fragments that are themselves precompiled ahead of time. There is still a code-generation step, but it stitches fragments together rather than emitting fresh IR for every operator combination. First-tuple latency drops, and long-running queries still get most of the benefit of full compilation.

I am going to draw an analogy that I don’t believe might be fully accurate from a PL perspective; if a compiled pipeline is a CPS-transformed query plan then a fused fragment is a closed continuation i.e. a piece of compiled code that knows how to consume some tuple shape and pass it along.

Stretching that further we can describe stitching fragments at runtime as a kind of defunctionalization: you keep a tag that says which fragment runs next and the runtime looks it up. Defunctionalization is the standard technique for turning higher-order CPS code into first-order code.

If we map this back to the Rust above filter(rows, pred, |r| aggregate(r)) is a call whose continuation is a closure over pred and aggregate becomes a pipeline like [expr_i64_gt, agg_sum_i64_mul]: a list of names identifying precompiled fragments that the runtime chains by looking each one up in the fragment library.

In the code base this all shows up as Suboperator. The interface is the direct equivalent of the push closure I wrote in Rust above:

struct Suboperator {
   /// Generate initial code for this operator when IUs are requested
   /// the first time. Will usually call open on all children and make
   /// the target IUs available to the parent operator.
   virtual void open(CompilationContext& context);
   /// All downstream consumers have been closed - this operator can be
   /// closed as well.
   virtual void close(CompilationContext& context);
   /// Consume a specific IU from one of the children.
   virtual void consume(const IU& iu, CompilationContext& context){};
   /// Consume once all IUs are ready.
   virtual void consumeAllChildren(CompilationContext& context){};
   // ...
};

The definition is from Suboperator.h, L47-L63

The consume(iu, context) call is the continuation when called it doesn’t move data but instead it emits code into context that consumes the IU². The compiler walks the DAG calling consume up through the parents, and what falls out the other end is one fused loop body.

Relaxed operator fusion

The Inkfuse paper builds on relaxed operator fusion (ROF) by Menon et al., Relaxed Operator Fusion for In-Memory Databases. The idea in ROF is that full pipeline fusion is sometimes too aggressive. Some operators want to work on a batch of tuples at a time, either because they want SIMD, or because they want to overlap memory stalls with computation through software prefetching³ by fusing everything into one tight loop we kind of give up that batching.

ROF introduces stage boundaries inside an otherwise fused pipeline where between two stages, tuples materialize into a small vector that sits in L1, and the next stage consumes the vector. Inside a stage you still get the compiled, tight-loop shape and across a stage boundary you get the vectorized shape.

Drawing it on the same query, the stage boundary sits between filter and aggregate:

Stage one is the same fused loop as before and stage two runs its own loop over the buffer, which is the part the compiler can vectorize or prefetch-pipeline. The aggregate’s consume is still its body, it just gets called by a different driver.

If you keep the CPS picture in your head, a stage boundary is the place where the continuation gets trampolined. Rather than calling the next consumer directly, you push the tuple into a buffer, return, and let the runtime call the next consumer once the buffer fills up. This is also where prefetching becomes possible: once you have a buffer of pending keys, you can issue prefetches for the hash-table probes that will happen in the next stage and overlap them with the work in the current one.

Kersten et al.’s Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask is a useful read in parallel with the Inkfuse paper. It compares the two execution models head to head with controlled benchmarks. Once you’ve seen those numbers it becomes hard to defend either model as universally better, and the ROF/Inkfuse direction starts to look like the obvious thing to want.

There’s also Ngom et al. (DaMoN 2021), which I keep coming back to whenever I think about the runtime layer around the compiled code. Tangential to the CPS argument, but it shaped how I think about where materialized state lives during execution, an important implementation detail that is often not discussed in papers.

Where I think the framing helps

I’m not claiming that calling Inkfuse a CPS engine gives you a new optimization. It mostly doesn’t, because the people building these systems already understand what they’re doing, they just describe it operationally. The thing it gives me, as someone reading the papers and the code, is a way to ask cleaner questions.

When I want to decide whether two operators can be fused, I can ask whether the continuation between them stays inlined or has to be reified into a buffer. For stage boundaries, the question becomes where in the plan it pays to reify the continuation explicitly. And for understanding fragments in Inkfuse, the question is what closed continuation a given fragment encodes.

That last question is the one I find most useful. Inkfuse’s fragment library is, in effect, a set of compiled continuations parameterized by tuple type. You can see exactly what that library looks like in ExpressionFragmentizer.cpp, L45-L58, the piece that builds fragments for binary expressions:

void ExpressionFragmentizer::fragmentizeBinary()
{
   // All binary operations on the same type.
   for (auto& type : types) {
      for (auto operation: op_types) {
         auto& [name, pipe] = pipes.emplace_back();
         auto& iu_1 = generated_ius.emplace_back(type, "");
         auto& iu_2 = generated_ius.emplace_back(type, "");
         auto& iu_out = generated_ius.emplace_back(
            ExpressionOp::derive(operation, {type, type}), "");
         auto& op = pipe.attachSuboperator(
            ExpressionSubop::build(nullptr, {&iu_out}, {&iu_1, &iu_2}, operation));
         name = op.id();
      }
   }
}

Every (type, op) pair becomes one named pipeline that gets baked into the fragment shared object at build time. At query time, the runtime looks up the fragment by name and chains it into the pipeline. The name in this case is the defunctionalized continuation tag I mentioned earlier.

If you read the compile step as a CPS transform, the difference between Inkfuse and a full HyPer-style compile is just which continuations get reified ahead of time and which get built from source for this particular query this is mostly a knob that you can tune and Inkfuse picks a setting that favors latency without giving up much throughput.

The PL literature has two standard ways to eliminate first-class continuations before runtime, and both show up here. One is to inline every continuation call at compile time such that the continuation disappears into the surrounding code effectively inlined and no closure survives. That is HyPer: one monolithic function per pipeline and everything specialized to this query. The other is defunctionalization where you give each continuation a name and dispatch on it at runtime, that’s what Inkfuse does each fragment is a named continuation and the runtime chains them by name.

Things I’m still not sure about

A few things I’ve been chewing on and haven’t worked out.

One is how far the analogy goes when you bring parallelism in. Morsel-driven parallelism (also TUM) gives each worker a chunk of input and runs the pipeline on it. In CPS terms each worker has its own continuation, but they share the join-side state. I haven’t found a clean way to express that and I don’t think there is one at least not from the literature I’ve read and I haven’t looked much into parallelism and concurrency in functional languages so there might be something there to unearth.

Another is what happens at the operator boundaries that aren’t really operators: null handling, type dispatch, NULL-aware comparisons, all of these become branches inside the compiled pipeline that aren’t represented in the plan, and I don’t know whether the CPS framing helps or hurts in reasoning about them. In fact I think this is one reason why this entire framing might be “too pure” in the practical sense.

References

• Remy Wang, Continuation-passing style.
• The Inkfuse paper from TUM.
• Menon, Mowry, Pavlo, Relaxed Operator Fusion for In-Memory Databases.
• Kersten et al., Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask.
• Ngom et al., DaMoN 2021.
• Thomas Neumann, Efficiently Compiling Efficient Query Plans for Modern Hardware.
• Inkfuse source: github.com/wagjamin/inkfuse.

1. In a classical Volcano plan a leaf is any operator with no children — table scan, index scan, VALUES, or a materialized subquery/CTE reference. In pipeline-oriented compilation the boundary moves: a pipeline can also start from the probe side of a hash join or the read side of a grouping, both leaf-like from that pipeline’s perspective because their build side has already materialized into a hash table before this pipeline runs. ↩

2. IU stands for “Information Unit” — Moerkotte’s term from Building Query Compilers for a named value threaded through the plan. Think of it as a variable: a column read from a scan, an intermediate expression result, a group key. Each IU has a type and a lifetime; the compiled code lowers it to a register or a stack slot. Operators declare which IUs they consume from their children and which they produce for their parents, and the plan is well-formed exactly when every IU a consumer reads is produced somewhere above it in the tree. ↩

3. The stall is usually a hash-table probe. Looking up a key in a table that’s too big for cache means a load that misses L1, L2, L3 and ends at DRAM roughly 200-300 CPU cycles of waiting. In a tight one-tuple at-a-time loop there’s nothing else to run during that wait, so the core just sits. Software prefetching turns the wait into useful work: with a buffer of pending keys, you issue a prefetcht0 (x86; prfm on ARM) on the bucket for keys[i + k] while you do the actual probe for keys[i]. By the time iteration i + k comes around, its bucket is already in L1 and the probe hits cache. The lookahead k is tuned to memory latency divided by per-iteration cycle cost. Chen et al., Improving Hash Join Performance Through Prefetching, is the canonical reference. None of this works in a fully fused pipeline, because there is no buffer of upcoming keys to prefetch from. ↩