#draupnir — Public Fediverse posts
Live and recent posts from across the Fediverse tagged #draupnir, aggregated by home.social.
-
After staring at IRs for several months and pretending like they're representative of computation, it's lovely to start seeing #Draupnir coming to life. On a 4GHz AMD box, a moderately-sized (still in-mem) join takes 2us per result (~10000 cycles if my math works out). That feels painful, but is probably not so bad given where the implementation is in the implementation/optimization cycle.
Plenty of low-hanging fruit, including adding an expression IR that accesses tuple fields by position rather than by name.
For now though, I think I'll get more of a win by adding a deduplication pass (and fixing this deadlock self-own).
-
After a day of dealing with stupid stupid issues related to how BTree keys are constructed, #Draupnir is finally computing one of #DDisasm's relations! (And at that, one that Souffle claims is the 2nd largest).
Still need to check that the relation is correct... but considering there's still a lot of low-hanging optimization fruit to go, 4ms + printing overheads is not too shabby.
-
On the bright side, #draupnir now speaks enough Souffle to fully parse DDisasm, slice out one of its memory-bound relations, and (modulo any further errors), should be able to replay the queries that construct the relation from ground-truth inputs.
-
On the one hand, progress towards directly processing souffle code is going slowly.
On the other hand, #Draupnir now has some sweet error message pretty-printing.
-
All basic test cases pass! Enough for tonight. Tomorrow, we start testing recursion.
-
My love-hate relationship with the #rust borrow checker continues. On the one hand, it just forced a refactor of #Draupnir's cursor interface. On the other hand, the refactored cursor interface is cleaner, simpler, requires less (and less complicated) external state management, and has much clearer memory ownership behavior.
Quite literally, we're epsilon away from testing on recursive (datalog) queries on disk.
-
This overhaul of #Draupnir's interpreter backend is coming close...
It's going to be slooooow, but the two main selling points (recursive queries, and disk-backed storage) are almost fully working.
Watch out Soufflé. We're coming for you :).
-
Refactoring #Draupnir 's scheduler, the power of reactive programming really came to the fore. We want a lot of expressiveness out of our workflows, and that forces the scheduler logic into a giant mess of dynamically interlocking state machines.
A recent refactor using a reactive programming paradigm led to much more readable "pull" style code, more visibility into current state, and far far less book-keeping logic and state. So much nicer!
-
6k line Souffle program status: Appears to parse successfully.
Bonus: #Draupnir now has mildly cleaner parse error reporting.
-
#UBODIn will be at #NEDB_Day_2026 on Jan 16 with two posters!
"Flow-centric Query Evaluation Pipelines" (Victoria, Andrew, Krishna) presents our preliminary efforts to make a scheduler-friendly query evaluation pipeline for our #Draupnir datalog engine. The key insight behind our work is decoupling state from operators. By making operators (mostly) stateless, we can inline better, and we can expose IO to the scheduler more efficiently.
"Benchmarking Tabular Representation Models on Longitudinal Data" (Pratik) presents our work on data integration for longitudinal studies. Longitudinal studies generate a slew of datasets that are almost alike, but not quite. Coupled with the fact that attributes are identified by prose questions rather than simple identifiers, they aren't a great fit for existing data integration/unionability tools. We'll specifically be presenting a benchmark, painstakingly adapted from the American National Election Survey, which shows that we need new data integration tools.
-
... and here I thought our out-of-core datalog compiler might be perceived as archaic...
-
Ended up backtracking a bit on recursion in #Draupnir. Two colleagues independently made a suggestion that elegantly gets rid of an awkward abstraction, while playing very nicely into our dataflow execution model: instead of making higher order primitives to support recursion, edges in the dataflow graph now identify which operator iterations talk to each other. It feels a bit like there's something similar to the parallel communication algebra that the #Dryad folks came up with... but for recursion.
-
Recursion in #Draupnir is getting closer, making it very nearly a proper #Datalog compiler. What would normally be a simple task is becoming considerably harder due to the need to support general monoid bases for the relations (which we want for cleaner aggregates than Souffle), as well as the need to handle batch scheduling to support disk.
The main challenge so far has been coming up with an execution plan that safely batches each iteration, while playing nicely with our push+pull scheduler, and simultaneously making sure that it maintains the correct arity of each tuple. Not hard... but very finicky.
We've come up with a pretty clean set of extensions to our logical pipeline DAG that seem like they elegantly capture recursion, and compiling a simple (count the paths) query to the logical stage appears to be producing a sensible graph. This has revealed some bugs in the pipeline optimizer, and we still need to add support into the interpreter... but it's progressing.
-
I don't think I've ever been so happy to get basic join support working. Expressivity usually comes at the expense of performance, and we are aiming for a TON of expressivity in #Draupnir.
It's been a heck of a time getting the "good" cases to optimize down to what a standard database would do (e.g., simple Hash Joins), but the end is in sight... The group theory bits are (mostly) implemented, and now we just need to deal with simple operational issues like the scheduler freaking out when it tries to poke an unordered CSV file for a cursor that supports indexed seeks.
The effort is worth it though... with this latest change, we should be able to support the ring-style factorization optimizations you get in #DBToaster, while simultaneously supporting non-ring aggregates like Min and Max like #Souffle, as well as #Rel's map relations.
The project name seems more apropos than we realized when we first named it... The key insight has been the realization that we need to give up the ring (and settle for the monoid/group).
-
I don't know if our database needed a bytecode compiler...
... or if the bytecode runtime and associated scheduler needed support for green threads...
... but I guess it has both now.
-
I don't know if I needed a bytecode interpreter for my database... but I have one now.
-
TFW you optimize your compiler to the point where it realizes that your test case is a no-op.
-
After a huge refactor in, our new and improved "Powered by Monoids™" query engine, #Draupnir , processed its first SQL and Datalog queries end-to-end last night!
There's still a long list of todos: Most of the classical optimizations are still missing, evaluation logic is still running in an AST-based interpreter, there's no recursion yet, no SIMD, and it's still entirely in-memory.
That said, the current incarnation is far cleaner than the hackjob I first cobbled together while learning Rust. Among other things, it supports a much nicer flavor of datalog that allows composition at the level of aggregate values (a bit like LogiQL or the recent breed of lattice-based datalogs). e.g., a simple count the number of paths program:
```
Path(A, B) :- Edge(C, B).
Path(A, B) = x * y :- Path(A, C) = x, Edge(C, B) = y.
```Note the 2nd rule's use of `=`. `x` and `y` reference the number of paths or edges between A and C, and C and B respectively. The rule *increments* Path by the product of x and y. What's kinda neat is that almost the same query can be used to compute shortest path.
I also think the dataflow model we came up is *really* neat. It allows operators to be purely stateless (state is managed by the scheduler), and opens the door to direct plan-level optimization of data structures that would normally be embedded into operator implementations (Shared Arrangements + Morsels, all rolled into one).
-
Most pipeline-based database engines seem to take one of two paths to passing state between operators. Streaming or actor-based systems pass tuples, forcing operators to be stateful, while batch-processing systems pass around entire relations in some standard encoding (e.g. Spark's RDDs). With #Draupnir, I've been playing around with a middle ground, where the physical plan compiler includes a step that selects a data structure for each edge based on the needs of downstream operators. The operator just gets a cursor with the guarantee that its requested operations will work, and requested constraints on the data (completeness, unique keys, sort order, etc...).
Combined with the monoid-map data model we're using, this has the effect of making aggregation, and the join build phase, just constraints on the data structure used to store intermediate state. Both of these become data structure, rather than algorithm selection problems.
-
Some fairly obvious and low-hanging optimizations later, the #Draupnir interpreter is only somewhat slower than SQLite on the trivial TPCH Q1 (instead of embarrasingly so). Might poke at a few more low hanging opts, but time to handle the big enchillada: Joins.
The execution framework we selected for this, compiling to an imperative IR, has a really nice perk: There is no explicit join algorithm! Most other join algorithms' probe phase is (are) just an index-nested loop. We can (should be able to?) replicate 1pass hash, nlj, bnlj, and probably also grace hash and smj, by just picking the right physical encoding of the relation to materialize into during the build phase(s). Will need some thought on how to pull this off for some of the more advanced wcojs like leapfrog.
-
Another #Draupnir refactor appears to be bearing fruit. The IR now has an non-analyzed flavor, which makes the parser way cleaner. As a bonus, it can now print pretty error messages for semantic bugs in input code. That made finishing up the hand translation of TPC-H Query 1 easier.
Tomorrow, we see how badly my draft interpreter performs on Q1. :/