8 ms·

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 toy

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.

kebman 4y ago
Your dream sounds very nice.
packetlost 4y ago
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.
- ftdyuio9p0iugy 4y ago
  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 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.
  - packetlost 4y ago
    You could probably do it with BRIN indexes similar to how TimescaleDB handles their time-series hypertables
    - LoriP 4y ago
      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 https://github.com/timescale/timescaledb
    - zresdtfugyihoi 4y ago
      Indeed! That seems like quite the ideal use-case for BRIN indexes.
- sauruk 4y ago
  Do you have a public repo for that yet? (Assuming you're planning to open-source)
  - packetlost 4y ago
    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 :)
Kinrany 4y ago
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.
- packetlost 4y ago
  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.
  - Kinrany 4y ago
    The API should definitely either allow directly managing indexes or provide even lower level primitives that let the query engine create its own indexes.
    - packetlost 4y ago
      I mean, if you have a KV-like store that supports enumeration, you can pretty much always index the data yourself.
  - kjeetgill 4y ago
    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.
    - thesz 4y ago
      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. I am a database engine developer right now. ;)
klysm 4y ago
I’m surprised something like this doesn’t exist yet - I wonder if it’s possible to build it on top of SQLite somehow?
- packetlost 4y ago
  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. You can see me prototype here: https://git.sr.ht/~chiefnoah/quark https://git.sr.ht/~chiefnoah/quark
  - infogulch 4y ago
    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?
    - packetlost 4y ago
      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.
sherbondy 4y ago
Obligatory link to Project Mentat: https://github.com/mozilla/mentat https://github.com/mozilla/mentat No longer actively maintained, but maybe a nice starting point for hacking on your dream!
- infogulch 4y ago
  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 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? [1]: https://techgaun.github.io/active-forks/index.html https://techgaun.github.io/active-forks/index.html [2]: https://github.com/qpdb/mentat https://github.com/qpdb/mentat
EastLondonCoder 4y ago
What about https://xtdb.com/ https://xtdb.com/
huahaiy 4y ago
Sounds like Datalevin https://github.com/juji-io/datalevin https://github.com/juji-io/datalevin Embeddable, check. Datomic data model and Datalog query, check. Storage written in C, check.
- packetlost 4y ago
  Ooh, this looks good. LMDB backend though, meh. Edit: it's written in Clojure, so JVM. Extra bleh
- artemisart 4y ago
  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?
chakkepolja 4y ago
There's a bunch of resources on r/databasedesign.
- HyperMassive 4y ago
  I can't seem to find this subreddit. Do you have a link?
  - benbjohnson 4y ago
    I think it's this one: https://www.reddit.com/r/databasedevelopment/ https://www.reddit.com/r/databasedevelopment/
michael_j_ward 4y ago
if litestream ever enables logical replication, I think you could do `SQLite logical replication --> embedded materialize-db --> back to SQLite`
user5678 4y ago
krn 4y ago
> I dream of a SQLite-like embeddable database engine based on Datomic’s data model and queryable with Datalog. You can have this today by running XTDB[1] on top of SQLite via JDBC. > Written in something like C, Rust, or Zig. And then compiling your application into native executables with GraalVM Native Image[2]. [1] https://xtdb.com/ https://xtdb.com/ [2] https://www.graalvm.org/native-image/ https://www.graalvm.org/native-image/
solarkraft 4y ago
What about DataScript/Datahike? The obvious issue is that they're fairly deeply embedded in the Clojure(Script) ecosystem.

kebman 4y ago

Your dream sounds very nice.

packetlost 4y ago

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.

ftdyuio9p0iugy 4y ago
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 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.
- packetlost 4y ago
  You could probably do it with BRIN indexes similar to how TimescaleDB handles their time-series hypertables
  - LoriP 4y ago
    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 https://github.com/timescale/timescaledb
  - zresdtfugyihoi 4y ago
    Indeed! That seems like quite the ideal use-case for BRIN indexes.
sauruk 4y ago
Do you have a public repo for that yet? (Assuming you're planning to open-source)
- packetlost 4y ago
  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 :)

Kinrany 4y ago

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.

packetlost 4y ago
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.
- Kinrany 4y ago
  The API should definitely either allow directly managing indexes or provide even lower level primitives that let the query engine create its own indexes.
  - packetlost 4y ago
    I mean, if you have a KV-like store that supports enumeration, you can pretty much always index the data yourself.
- kjeetgill 4y ago
  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.
  - thesz 4y ago
    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. I am a database engine developer right now. ;)

klysm 4y ago

I’m surprised something like this doesn’t exist yet - I wonder if it’s possible to build it on top of SQLite somehow?

packetlost 4y ago
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. You can see me prototype here: https://git.sr.ht/~chiefnoah/quark https://git.sr.ht/~chiefnoah/quark
- infogulch 4y ago
  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?
  - packetlost 4y ago
    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.

sherbondy 4y ago

Obligatory link to Project Mentat: https://github.com/mozilla/mentat https://github.com/mozilla/mentat No longer actively maintained, but maybe a nice starting point for hacking on your dream!

infogulch 4y ago
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 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? [1]: https://techgaun.github.io/active-forks/index.html https://techgaun.github.io/active-forks/index.html [2]: https://github.com/qpdb/mentat https://github.com/qpdb/mentat

EastLondonCoder 4y ago

What about https://xtdb.com/ https://xtdb.com/

huahaiy 4y ago

Sounds like Datalevin https://github.com/juji-io/datalevin https://github.com/juji-io/datalevin Embeddable, check. Datomic data model and Datalog query, check. Storage written in C, check.

packetlost 4y ago
Ooh, this looks good. LMDB backend though, meh. Edit: it's written in Clojure, so JVM. Extra bleh
artemisart 4y ago
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?

chakkepolja 4y ago

There's a bunch of resources on r/databasedesign.

HyperMassive 4y ago
I can't seem to find this subreddit. Do you have a link?
- benbjohnson 4y ago
  I think it's this one: https://www.reddit.com/r/databasedevelopment/ https://www.reddit.com/r/databasedevelopment/

michael_j_ward 4y ago

if litestream ever enables logical replication, I think you could do `SQLite logical replication --> embedded materialize-db --> back to SQLite`

user5678 4y ago

krn 4y ago

> I dream of a SQLite-like embeddable database engine based on Datomic’s data model and queryable with Datalog. You can have this today by running XTDB[1] on top of SQLite via JDBC. > Written in something like C, Rust, or Zig. And then compiling your application into native executables with GraalVM Native Image[2]. [1] https://xtdb.com/ https://xtdb.com/ [2] https://www.graalvm.org/native-image/ https://www.graalvm.org/native-image/

solarkraft 4y ago

What about DataScript/Datahike? The obvious issue is that they're fairly deeply embedded in the Clojure(Script) ecosystem.