I am working on a Datalog database engine à la Datomic on top of object storage. The system is called Triplox (a portemanteau of Triple and Blocks). In an attempt to become a better communicator I decided to start a little log to explain some concepts in Triplox.
Thoughts on N-way joins in DBSP and WCOJ in DBSP after some discussion on the Feldera Discord server
Edit(2026-04-30): After having thought some more about this post there a multiple issues. The algorithm is not correct and the claim about WCOJ needs to be more precise. There are multiple definitions for worst-case optimality in the context of IVM and I need to get them straight before actually claiming anything. The more serious issue is correctness. Let $P_{i}$ be the set of prefixes at level…
Edit(2026-04-30): There are some issues with the complexity claims below. I am working on some udates to the WCOJ series. Also see the edit at the top of WCOJ - WCOJ meets DBSP.
Edit(07-06-2026): I have realized that the OrPrefixExtender below is not quite right, as variable instantiations from other or branches can “leak” into extensions in lower variable levels. Or branches need to get executed in isolation, at least for the variables they participate in. The other option is to check the branch again when it gets extended for a particular prefix, but that seems…
Explanation of a worst-case-optimal variable oriented join algorithm - GenericJoin 1 The algorithm explained in this post is called GenericJoin and from the following paper https://arxiv.org/abs/1310.3314.
An introduction and motivation for Worst Case Optimal Joins
Continuation Passing Style (CPS henceforth) is usually something from esoteric functional programming languages. I want to show you a little example of how it is used in the XTDB Expression Engine. Before we start, let’s have a look at what CPS actually is. A continuation in a Lisp-flavoured language like Clojure is a function of the value of a subexpression to the value of the program (also an…
Alex Miller recently wrote a good blog post in which he details how to decompose transactional systems according to the following steps:
TLDR: Some practical information of how to implement window functions based on the paper: Efficient Processing of Window Functions in Analytical SQL Queries, Leis et al.