I dream of a SQLite-like embeddable database engine based on Datomic’s data model and queryable with Datalog. Written in something like C, Rust, or Zig. I’m toying around with the idea of hacking something up, but it’ll likely stay in the dream realm until I have Heaps of Free Time on My Hands (tm).
Looking into SQLite’s innards is a great source of inspiration. Thanks for this post.
I've been doing something very similar, but based on extendible hashing algorithms and LSM trees. I've come to the conclusion that a DAG of constraints, triggers and validations on a flat KV + entity model is probably the ideal data structure for 99% of projects I've worked on. You can get the benefits of the Datomic-like history by... skipping compaction and including a TX instant next to all record/assertions. I've found SQLite, Postgres, the LSM papers, Bitcask, and many other papers to be very helpful in terms of inspiration.
Edit: I'm prototyping in Python and implementing in Rust with intent to create a C API and embedding a Scheme runtime for "server"-side query and constraint parsing.
I've had some append-only tables in Postgres and only recently realised that Postgres' system columns (https://www.postgresql.org/docs/14/ddl-system-columns.html) already effectively enabled some Datomic-like structure for such append-only tables! Specifically the xmin column allows me to identify the rows to treat atomically as a unit, and to ignore if I'm querying for a historical view.
TimescaleDB is packaged as a postgres extension, there's a GitHub project here if anyone is interested to check in on that https://github.com/timescale/timescaledb
It's got a LICENSE but not publicly listed yet. It's very rough, and has a ton of work left. Once I get it to a workable state I'll open it up under AGPL, though probably with a CLA because I'd like to turn it into a marketable product in the long-run. If I make significant progress on it, I'll reply to this thread with updates :)
I hope using an embeddable database will also free us from delegating the choice of query language to the database library. It should be possible to have a general purpose low level persistence API and many different query engines built on top of it.
I think the problem with querying is efficient query-planning requires understanding the indexes on the dataset, so you at least need to be able to expose indexes and the their properties in an API.
Imho the 90% of query planning is not that hard at all in practice. If it's your data, and your query you'll probably have a pretty good idea which table you'll want to filter first, and what to join the same you would with any data structures.
The hard part is getting all of that consistent with concurrent writes. Can rows change while you scan? can indexes? How do you check that your write is valid immediately before committing, etc. things like that.
I think SQL makes that pretty hard already, but in a "database-as-a-bag-of-data-structures" mode I think that's going to get even harder.
IMNSHO query planning is pretty hard. I recently found exponential behavior in SELECT query processing that depends on the depth of subselects. This happened with pretty seasoned database system, let me say.
To have good query optimization, you need to implement, at the very least, some form of dynamic programming, otherwise you will not be able to optimize queries that have more than half a dozen tables in selects. Then you have to implement selection of the best plan or approximation to it, which would make you implement beam search through space of all solutions you generated, and that's simplest case. For guaranteed optimization, you need to implement or utilize pseudoboolean optimization engine.
If you just pick a worst case optimal join algorithm with a limited table cardinality, i.e. triples like in the case of OP, so that you can materialise every possible index, you can perform a dynamic _instance optimal_ search (i.e. you can ignore skew), if you choose the best possible variable every time you have to pick a variable. This can be done by estimating the cardinality and jaccard index of the variables, which is pretty straightforward with the right datastructure.
If you don't want to limit yourself to just three columns, you can also go for cutting edge succinct data-structure magic. https://aidanhogan.com/docs/wco-ring.pdf
Either way, using a WCO join combined with a data-structure that allows for efficient range estimate and dynamic variable ordering, completely obliviates the need for query planning.
"Estimate the cardinality", "jaccard index", "succinct data structure" and, finally, some unknown abbreviation "WCO" (I guess, it stands for "worst case optimal").
Yes, of course, having implementation of all that completely obliviates the need for query planning. ;)
I can't help being sarcastic for a moment, sorry.
In my opinion, in your comment above you clearly demonstrated that even avoidance of query planning is hard, using as example (multi)set of triples for which it is possible to realize all indices.
If what you described is simpler than query planning, then query planning is hard.
While the technical terms may be unfamiliar, it's all pretty straightforward, and requires between 1-4kloc depending on how fast and fancy you want things to be.
(This includes everything from the basic copy on write data-structures to the query language.)
Building an immutable path compressed radix tree is pretty straightforward and requires around 1-2kloc, and it's easy to keep track of the n-smallest hashes of leaf values, as well as the total count of leafs in the nodes.
The sampling done by the min-hashes give you a good indication of two nodes overlap which the jaccard index is just a different name for.
The query engine itself is like 0.5kloc, and is just walking the different radix-trie indices simultaneously. The basic insight of worst case optimal (WCO) joins, is that it's a lot cheaper to join everything at once and treat it as a constraint propagation problem.
A LINQ style query parser takes up another 1-2kloc and is just a bunch of ol' boilerplate.
In total that's about as much code as your average large C++ codebase CMake file.
You could sketch the entire thing on a napkin and build it in a week if you've build something like it before.
"If you build something like that before". I think I can add that to the list of famous last words. ;)
Please, excuse my sarcasm again. But, tell me what to do if I didn't built something like this before? What if I built something like equality saturation engine, pseudoboolean optimization using SAT solver and/or beam search? Will it help me somehow?
You estimated code size at 4.5KLOC max. Given that C++ programmer delivers 20-25 debugged lines of code per hour in the long run (IBM's stats), it would take 225 hours of work. Given that PSP/TSP recommends planning for 4 hours-on-task per day, it will take 56 work days. My calculation suggests 2.5 work months to implement all that in the worst case of 4.5KLOC. Even the best case of 2.5KLOC would take a month and a half of work.
Yours' proposition is not a week's project. Not at all, you can't squeeze it that much.
Query planning is hard. Even if you try your best to avoid it.
And we have not even started talking about WHERE, GROUP BY and ORDER BY clauses' optimizations.
[1] shows the use of loop nest optimization combined with beam search. SQLite uses translation of joins into loop nests, and it transforms loop nests into a graph, the path in the graph represents a solution. The [1] shows simplified nesting graph that is linear, and in general it will be quadratic to the number of tables.
I really like that approach. This is exactly an equality saturation [2] (saturate loop nesting through loop nesting commutativity) with the beam search as a selection phase.
I think that equality saturation with beam search is a week long project if you already have built something like that. The difference? It will work for arbitrary jons.
Of course I am making fun of your statements.
Equality saturation requires quite careful planning and will not work for couple of months, you will keep finding something that fails. Beam search is just as hard. You can encode optimal solution selection problem as a pseudoboolean optimization problem, which is more straightforward than beam search, and [2] shows that Pueblo is no slouch there.
This is not to say that query planning is easy when you do it my way. Query planning is hard. NP-hard, actually. Sometimes you can get away with a simpler less general solution, but it will bite you sooner than you expect.
C++ is probably the slowest programming language in terms of development speed there is, but even if it takes you 3 months to build something like that from scratch it'll still be an order of magnitude less time than building a clone of another SQL database.
`WHERE, GROUP BY and ORDER BY` are relatively straightforward to tack on into the variable ordering.
Having written a sat solver would kinda help you, because modern sat solving algorithms are fundamentally very similar to worst case optimal join algorithms.
The query plan produced by combining binary joins is always going to be off by up to an exponential factor when compared to a WCO join. If you're fine throwing all that complexity onto your problem to generate sub-par query plans, be my guest.
The paper you provided has two important omissions: 1) it does not mention Tseitin transformation to encode Disjunctive Normal Form into a Conjunctive Normal Form and 2) does not look at decision diagrams, especially, zero-suppressed decision diagrams for set representation.
Tseitin transformation prevents exponential expansion in conversion from DNF to CNF.
The fact that paper's algorithm employs disjunctive normal form suggests the use of binary decision diagrams. ROBDDs represent DNFs naturally, for one example. ZDDs represent sets of sets and were relatively successfully used in non-trivial approaches to the SAT solving problem like [1].
Also, the paper you mentioned has this right in abstract: "However, there is still the quest of making the new worst-case optimal join algorithms truly practical in terms of (1) ease of implementation and (2) secondary index efficiency in terms of number of indexes created to answer a query."
WCO is hard to implement and it might be computation-wise prohibitive.
The intuition is that if your join is a triangle you might be forced to join every relation only to discover that the result is empty on the last join, which requires m^n intermediary results, where m is the size of the relations and n is the number of relations.
A WCO join algorithm will figure out quite quickly that the output is empty and is in practice much more dependent on the actual output size, than the size of the input relations.
Thank you, second link of yours starts with the explanation of benefits expected, which is great.
The difference is not exponential, if I may nitpick. It is sublinear in the case of the "triangles example" - WCO would produce O(n^(1.5)), binary join will produce O(n^2), the difference is O(n^(0.5)) or O(sqrt(n)). The difference is big, but not exponential.
That blogpost is a godsend, it provides a great explanation and intuition, and resolved a few questions that I was left with after reading a lot of WCO join papers.
Good nitpick, I think you can construct larger rings where the difference becomes larger than one, but I might be wrong.
The dynamic variable ordering trick makes a huge difference in practice, especially when skew is in play. (https://arxiv.org/pdf/1310.3314.pdf)
In general you're right, WCO joins are a relatively young field of study and sometimes struggle with large constant factors, but they are maturing quickly and in a limited (triple) setting like the one OP "wished for", a lot more feasible than for the general case.
Thanks for the interesting discussions, looking forward to reading the references you provided in depth!
Edit:
I just remembered this paper, which might be of interest to you. They seem to recover WCO bounds in a pairwise setting, by choosing very smart intermediary join representations:
http://www.cs.ox.ac.uk/dan.olteanu/papers/co-tr16.pdf
My old idea was to perform planning after some of the work has been done, because remaining statistics can be different. These papers are of great help!
>you'll probably have a pretty good idea which table you'll want to filter first, and what to join
Until the day you load a bunch of new data and it gets skewed, or you delete a bunch of data without shrinking and oops, your join order and method is not efficient anymore.
The API should definitely either allow directly managing indexes or provide even lower level primitives that let the query engine create its own indexes.
Embeddable... in the java ecosystem.
I often see comments about datalog/datomic on HN and it seems interesting but I never see it anywhere else, is it because it's mostly known and used in the java and clojure ecosystem? Do you know of any free database with similar models usable from e.g. python?
mentat was archived by mozilla back in 2017, but there are a bunch of forks. Because github is dumb and has a terrible interface for exploring forks [0], I used the Active GitHub Forks tool [1] that helped to find:
qpdb/mentat [2] seems to be the largest (+131 commits) and most recently modified (May this year) fork of mozilla/mentat.
[0]: https://github.com/mozilla/mentat/network/members - Seriously, how am I supposed to use this? Hundreds of entries, but no counts for stars, contributors, or commits, no details about recent commits. Just click every one?
I tried. It's not easy because of how limiting SQLites indexes are. You have to build your own indexes using `TRIGGER`s or in a software wrapper and tables.
Commendable attempt! I've considered writing a datalog storage backend on sqlite just like your prototype. Thank you for sharing, now I can lazily study your prototype instead of doing the hard work myself. :) I'm curious, what kinds of limitations of SQLite indexes are you referring to?
Sparse indexes are pretty limited and it only supports B-tree, which make implementing AVET and VAET difficult. Further efficiently finding the current value for a E + A is difficult to do in SQL in a way that doesn't require maintaining a whole copy of the data. I actually bumped up against what I believe are weird edge-case bugs in the SQLite query planner when dealing with sparse indexes as well.
I think I gave up when trying to implement one-many relationships because the SQL was getting too gnarly.
Looking into SQLite’s innards is a great source of inspiration. Thanks for this post.