To Database or Not To Database ~ glfmn.io

Name

To Database or Not To Database

I've been working on an implementation of the willow data model. As a result,<br>I've had databases on the mind as of late. After reading (probably too many)<br>papers, I decided to implement the matklad comptime ORM tutorial,<br>and it really helped me understand what the interface to a database/storage<br>engine could be.

I've still got a lot to sort out since the willow data model encourages<br>range based queries across 3 dimensions: path, subspace id (a public<br>key) and timestamp.

The properties of Entries create a few interesting challenges, which the willow<br>authors summarize pretty well:

Willow requires some features not found in off-the-shelf solutions. While<br>there exist several solutions for managing and querying multidimensional data<br>indexed by fixed-width integers or floating point numbers, lexicographically<br>sorted strings of strings (i.e., Paths) are a different beast. Fingerprint<br>aggregation is another feature you will not find in SQLite.

Given the Data Model's unique constraits, I ended up in an analysis paralysis,<br>and just needed to move forward with something. Thankfully, I remembered<br>matklad's tutorial, which was a blast to implement!.

I love the approach he takes by providing an interface and then directing you to<br>implement it. I learned a lot just from the provided interface, and even more by<br>comparing our implementations!

I was also able to speak a little bit with Sammy and Aljosha, and Aljosha keyed<br>me into LMDB, an in process database/key-value<br>store which memory maps files, and uses copy-on-write storage, and towards Zip<br>trees. Now that I've done the comptime ORM tutorial, it might be interesting to<br>experiment a bit with zip trees & using memory mapped files for the database.