Now, we can chain them together with dbl(inc(xs)) which will do two steps in sequence. Problem is, because each function takes in a list and returns a list, our program produces an intermediate, namely inc(xs). This allocates a new list only to be thrown away by the call to dbl. Things only gets worse when we chain together multiple calls to inc and dbl. A more efficient implementation would fuse together the operations:

Of course, we can't write down every possible combination of operators like this. Is there a way to define each operator modularly, yet still have them compose into tightly fused operations automatically? Yes, if we use a bit of magic from functional compilers — continuation-passing style (CPS).

The key idea of CPS is to define operators that do things instead of making things. inc and dbl as defined above each takes in a list and makes a list. Instead, the CPS version of each operator takes in a list and an additional input k: this k is a function that the caller passes in, specifying what it wants to do with each element after the operator's work is done. k is called the continuation. Let's look at some code:

Now suppose k is the print function, then inc as defined above will add 1 to each number, then print the result. Note that nothing is returned, and inc only does its job (adding 1) then performs what it's told to (apply k). As an exercise, you can try and write down dbl in CPS style.

But currently each of inc and dbl still takes in a list, and there's no obvious way to compose multiple operators. To do that, we replace xs with a "child" operator op:

Intuitively, inc now trusts its child op to do its job, namely, that op will apply the continuation it receives to each item. So instead of iterating over xs, inc simply tags the + 1 step onto the continuation and passes it to op. I've also defined a "source" operator scan that connects the input list to the operators. Let's see the code in action.

1. Start by calling inc(scan(xs), print).
2. According to the definition of inc, this will call scan(xs, x -> print(x + 1))
3. Plugging in the definition of scan, this gets us for x in xs; print(x + 1); end

So chaining together inc and scan indeed does what we want! Now let's try a longer chain dbl(inc(scan(xs)), print):

1. Expanding dbl gets us inc(scan(xs), x -> print(x * 2))
2. Expanding inc gets us scan(xs, x -> print((x + 1) * 2))
3. Finally, expanding scan gets us for x in xs; print((x + 1) * 2); end

In other words, the column store co-iterates the columns in one pass to compute the query.

Let's first look at how Prela used to run this query. The most important operator in Prela is the relation composition \rightarrow, which generalizes function composition the same way relations generalize functions. In standard relational algebra: R \rightarrow S = \pi_{x, z}(R \Join_{R.y = S.y} S) where R's schema is over x and y, and S's schema is over y and z. The second most important Prela operator is the product \times which takes two binary relations and joins them: R \times S = R \Join_{R.x = S.x} S where R's schema is over x, y, and S's schema is over x and z.

So SELECT * FROM movie is spelled \text{movie} \rightarrow \text{year} \times \text{title} in Prela. Now, this requires first joining year with title, whose result is joined with movie. We can make this a bit cheaper if we can assume the primary key IDs are dense and continuous, in which case we can just store year as an array of integers and title as an array of strings; and for IDs, we only need to store one single number n which says how many IDs there are. But even with this, we still need to do the work to join the tables.

Instead, let's define compose and product in CPS:

Let's go over each line carefully. Semantically compose is supposed to return a (binary) relation by composing the lhs and rhs relations. In CPS, its job is to apply k to every pair in this composition. Its first argument, lhs, represents a binary relation and applies the given continuation to every pair. The rhs is a little different: it represents a relation that supports lookup, i.e., rhs(key, k) will look up the values associated with key, then apply k to each such value. Now going back to compose — we're saying that, for each (x, y) tuple in the LHS, we will look up y from the RHS, then for each matching z, we apply k(x, z). In loops this will be:

Which is exactly a hash join and a projection that throws away y.

Next, product itself is a relation supporting lookup, and so are its arguments. To lookup x in a product, we first look it up from the lhs which gets us a bunch of ys. Then for each y, we now look up x from the rhs, getting a bunch of zs. Finally, for each (y, z) pair, we apply the continuation k((y, z)). In loops:

This is what will happen if you look up x in R \Join_{R.x = S.x} S.

Finally, we have the "source" operators scan_id and probe. scan_id is scan but specialized for a dense ID relation where we only store n: it simply increments i from 0 to n and applies k to (i, i). probe represents an input relation that supports looking up a primary key i and which is backed by a dense vector, so looking up an ID i simply indexes col[i] and applies k to the value.

We're now ready to put everything together and pull the trigger: the Prela query \text{movie} \rightarrow \text{year} \times \text{title} desugars to compose(scan_id(n), product(probe(year), probe(title))) where n is the number of movies. Here are the definitions again for reference:

And taking k = print, we finally have:

Spectacular!!

To keep the examples small, I've made several simplifications. The actual Prela implementation defines two methods drive and probe for each operator which fire depending on how the operator is accessed — scanned or probed. But that's pretty much it, and the complete source is around 1000 lines of Julia code in a single file, supporting select, project, join, groupby, aggregation, CTEs, UDFs, and with performance matching DuckDB on TPCH and Join Order Benchmark. I should note that the performance numbers are riding on lots of assumptions though, the strongest ones being:

• Currently I don't care about compile time, and Julia does take some time to JIT the queries
• The engine aggressively takes advantage of the fact that PKs are dense in both TPCH and JOB, which may or may not hold in the real world

Nevertheless, the CPS approach cleanly separates the responsibility of the data engine — which is to map queries to efficient code in some target language — and the responsibility of the compiler which is to produce fast code quickly, and we see there's a lot of room for the compiler to improve. The assumption that PKs are dense can also be relaxed with the help of B-trees, bitmap filters, and other data structures.

But perhaps the biggest strength of the CPS style is that it makes Prela extensible, as users can write their own operator in a natural way with a few lines of code, with the assurance that it will be compiled and fused with the rest of the query for efficient execution.