Experimenting with Databases

What was prohibitively expensive is now a cheap experiment. LLMs rebalance the economy of software, even flip it over. We seemingly enter the era of bespoke software, tailored to the case. I ran this small project to probe this new reality with questions:

Economies are shaped by tradeoffs. We live in an era of cheap transport and expensive labor. Think of a plain white cotton t-shirt. The cotton grew in Brazil, Vietnam made the cloth, Bangladesh sewed the t-shirt that went to the EU to find a buyer. If unsold, it travels to Chile to be dumped in a desert. Ancient Romans would see our processes as peak insanity. Their economy was globalized, in a sense. But, they wove wool not far from the flock, then shipped the garment. Glass was shipped in ingots, iron as bars. A local craftsman would blow a cup or forge a knife of requested shape. Labor was cheap, transport was expensive. Today, imagine skill and complexity becoming cheap, and transport expensive. We may switch to shipping industrial rolls of yarn and filament, bags of metal powder, and other high-density commodities. The final goods would be produced where the demand is.

This kind of U-turn likely happens to the software industry. More local software that fits exact use cases, fewer complex products meant to fit most users out there. This is what we are going to explore.

NeoClear (pronounced "nuclear") is a bit of a pun on Datomic. Its internals are very simple and primitives are few. Still, it does not fit some textbook category. The database has an interesting mix of LSM, columnar and triplet traits.

The data is represented as oid-attribute-value triplets. Each attribute is a directory containing .att files of sorted {oid->val} pairs and .idx files of sorted {val->oid} pairs. Values and oids are both 64-bit, so we speak of large u64 arrays here. Oids and timestamps are Lamport-like, sequential being a corner case. String and blob values go into a separate log and get referred to by an offset. Both .att and .idx files are maintained the LSM way, as a logarithmical number of big-old and small-new runs (aka "pups"). Both types of files are tailed by per-page ToC, in the same pair format. The optional oplog consists of {oid,att,value,timestamp} u64x4 quads. The memtable is per-attribute sorted-runs of {oid,value,timestamp}. No B-trees used.

Due to the fact attributes are stored separately, in LSM-like runs, the store is able to mix write-friendliness of an LSM store and fast scans of a columnar format. SQL and Datalog are implemented on top of that store. Neither is necessary to use it.

Due to the pups being immutable and the oplog being append-only, memory management is mmap-based. The entire project is implemented in a zero-malloc dialect of C. No Rust.

Now, the argument between H.Chu of LMDB and A.Pavlo of CMU/ClickHouse. Is it enough to use mmap or maybe we must implement our own page manager? I lean to agree that many today's use cases involve layers of abstraction. For example, I have no idea what else can be happening on my VPS. Then, trying to be smart is futile, while simple LRU I already have from the OS. At least, the kernel knows about the concurrent workloads a bit more than I do. We also take into the account that LSM data is either read-only or in-mem. Hence, the arguments for a page manager are thin.

One additional argument is Don't stack your log on my log. SSDs, journalled filesystems and databases (esp. LSM) are logs riding logs. In case you use btrfs, for example, a database may be a B-tree riding a B-tree.

A page manager is necessary to implement compression. But, some filesystems natively implement compression too. A generic compression (e.g. zstd) can either boost or harm performance. That all depends on your case; NVMes are fast enough to move uncompressed data. If compression can be on/off at fs/db level, that makes 4 degrees of smartness. In fact, degree 0 is good enough for most cases.

On top of that, columnar databases have their own compression tricks. We leave that opportunity open.

Overall, we let things work at the lowest level where they can work "OK".

The attribute-cloud layer only provides fetches and cursors over the data. All the objects, rows, and queries get implemented at higher layers. So, the attribute-cloud plays the same role as the more common key-value store. It took 2-3 days to achieve 99.8% compatibility on sqllogictest. A Datalog layer was also implemented; these numbers are less interesting as NeoClear is natively a triplet store.

To implement the store I ran a pretty normal "$200 Claude" workflow. The core functions have been implemented in libabc long ago and are stable. The core solutions and rules have been written by hand in policy documents. The rest was iterated by Claude using some reference (e.g. IMDB JOB bench). The author rarely looked into the code :) Some house cleaning was necessary to mop up the slop. For example, Claude implemented half a dozen custom hash tables, which all eventually got unified into standard mmapped ABC containers. Similarly, it used malloc() a lot, which was also eradicated. One extremely useful source of feedback was round-the-clock fuzzing. It controlled both for stability and compliance. References were sqlite and the SQL standard per se. The more cores you have, the more regression control you can run like this.

Overall, it was pretty straightforward process with few to none adventures.

Our reference benchmark was IMDB JOB against sqlite. In general, two databases are too different to have a someone-wins comparison. NeoClear was much faster at scans and joins, much slower at inserts. Overall, it was at parity. That is not a surprise as columnar formats have certain advantages. They also have pain points, e.g. scattered insertions into wide tables. NeoClear softens that with its memtables, to some degree.

Overall, these are normal database design tradeoffs. What matters is that we achieved reasonable general-case performance.

In this experiment, we implemented a perfectly usable database. The point of its architecture is to be as malleable as it gets. That means, it can be optimized for very particular workloads, very specific queries, access patterns, filesystem(s) and hardware. That changes the entire approach. Instead of intricate core and robust interfaces, we have robust core. The underlying data format is insultingly simple and mostly immutable. It can survive a lot of mistreatment. That way, any further work may laser-focus on features that matter. To put it to the extreme, to develop a database for a specific list of queries, or a specific mobile device, or both.

The dataset itself can be split into subsets both horizontally and vertically. So, we may ship/sync a particular subset of rows and attributes. Then, queries can be responded by a small local replica. Such a local-firtstest database has round-trip times of about 0.

The database is incrementally syncable both by the log and by the state. AP/CP distributed architectures are both open options.

What gets shipped is essentially reusable low-level code and conventions. Then, a product gets into a particular shape at the point of demand. Like in the Roman times.

NeoClear vs SQLite 3.54.1 on an IMDB subset (about 25% of JOB's IMDB: 1.84M names, 9.34M cast rows), 15 JOB queries plus 4 extra ones. Both engines journalled: NeoClear with its oplog, SQLite in WAL mode with synchronous=FULL. Query times are warm, best of 3.