GoKawiilPassing DBs Through Continuations
Dedicated to the Minnowbrook Analytic Reasoning Seminar with special thanks to Kris Micinski and Michael Ballantyne
Suppose you want to write a database. You'd probably start by implementing relational algebra operators — projection, filter, join, etc. The easy way is to implement them as functions that take in tables and return tables, and assemble them into a larger expression. That was how Prela worked in its first incarnation. The code was clean, but it was hella slow! Which was not surprising, because every operator materialized every intermediate result. The standard solution to this is the iterator model, where each operator implements an Iterator interface that streams intermediate tables row by row instead of materializing them. But implementing the iterator model naively still incurs overhead: every call to Iterator.next() triggers a dynamic dispatch, which costs vtable lookups and destroys cache locality. There are two standard remedies: vectorization and compilation. A vectorized database amortizes the overhead by implementing Iterator.next_batch() which returns a whole batch of data that can be processed together; a compiled database, well, compiles the incoming query directly to fast machine code that runs without any dynamic dispatch. Either approach takes a lot of very smart people spending their entire working life to build, and it's why systems like DuckDB and Umbra exist. I'm moderately smart but don't have a lot of time, so I was looking for a shortcut. The shortcut I stumbled upon was so beautiful that I literally cried when I finally understood it, and I hope my explanation below will make you cry too :' )
To keep things simple, let's suppose we're just dealing with lists of numbers, and we want to do two very simple things to them: inc adds 1 to every number, and dbl doubles them. That's pretty easy to write:
inc (xs) = [x + 1 for x in xs] (xs)[xfor xxs] dbl (xs) = [ 2 * x for x in xs] (xs)x for xxs]
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:
inc_n_dbl (xs) = [ 2 * (x + 1 ) for x in xs] (xs)(x) for xxs]
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:
function inc (xs, k) (xs, k) for x in xs xs k (x + 1 ) (x end end
... continue reading