Published
Every database has a little admin overhead. A name tag here, a lanyard there,
a folder to keep the paperwork in. Ours had been quietly charging every
property on every node a 150-byte admin fee before it would even look at
the value. A property holding the number 42 was carrying around more
filing than a mortgage application.
Galactus DB 1.5.0 has had a tidy-up. Same graph, same files on disk, same queries, a third less memory for a typical database, and nearly half for a database kept entirely in memory. It got faster on the way out of the door, too.
Where was it all going?
Before changing anything we measured where every byte went, one structure at a time, with an allocator that counts exactly what the database asks for. The answers were a bit embarrassing:
- Each property cost 110 to 150 bytes of bookkeeping. One entry in the node's list of keys, and another in a database-wide map whose 24-byte keys and tree nodes cost several times the value they were filing.
- A unique index cost about 170 bytes per node. Every distinct value, such as every email address or every order number, got its own little set, built to hold many nodes and almost always holding exactly one.
- Labels and property keys on every node and relationship sat in general-purpose collections sized for crowds, when most nodes have one label and a handful of keys.
Properties and indexes were most of the memory. The actual data was a modest part of it.
What we changed
Nothing you can see from Cypher, and nothing on disk.
- Properties now live with their owner. Each node and relationship keeps a short, sorted list of its own properties. Finding one is a direct jump to the node and a quick search through a handful of keys. That's about 50 bytes of overhead per property, down from 110 to 150.
- Index entries travel light. An index value held by one node stores that node directly and only builds a set when a second node turns up. A unique index entry dropped from about 170 bytes to about 75.
- Labels and keys are packed. A small sorted array, exactly the right size, instead of a structure designed for thousands of entries.
The wins
On a graph of 200,000 people and 400,000 relationships between them, with four properties per person, two per relationship and two indexes:
| 1.4.2 | 1.5.0 | ||
|---|---|---|---|
| Heap after reopening (Hybrid engine) | 600 MB | 397 MB | −34% |
| Heap with 1M nodes (in-memory engine) | 1,510 MB | 788 MB | −48% |
| Reopening the database | 1.57 s | 1.47 s | −7% |
| Loading relationships | 0.73 s | 0.66 s | −9% |
Less bookkeeping also means less to walk through on every read, so nearly everything got quicker:
The biggest jumps are in the work that reads a lot of properties: scanning relationship properties takes 43% less time, a range seek 30% less and a filtered label scan 26% less. The everyday lookups, such as finding a node by an index and walking out from it, are 9 to 13% quicker. Small write transactions are 7% quicker.
Nothing got slower. One query, counting people by city, wobbled between runs on both versions, so we're calling it a draw.
How much your own database saves depends on its shape. The more properties and unique indexes it has, the closer it gets to half. A graph that is mostly relationships with few properties saves less, perhaps 15 to 20%.
How we measured
The figures are medians of five rounds that alternated which version ran first. Both versions were built with the same release settings and run in-process on the same machine: an Intel Core i9-13900K with 64 GB of RAM on Windows 11. The database used the Hybrid storage engine (the server default) with buffered durability, the default 16 MiB property cache and one query worker. The in-memory figure is a separate one-million-node build of the same shape. Memory is the live heap requested by the database, measured by a counting allocator.
Upgrading
Pull the new image and restart. That's it:
docker pull ianknowles/galactus-db:1.5.0
The data, commit log and snapshot formats haven't changed, so 1.4.2 and 1.5.0 open each other's databases. If you need to step back for any reason, you can.
What's next
The property cache is next. It keeps recently read values decoded and ready, and it's a big reason the Hybrid engine is quick. But its budget counts the size of each value on disk rather than what the cached copy really costs in memory, so the default "16 MiB" setting uses a good deal more than that. We want the setting to mean exactly what it says, without giving back any of the speed. We'll write about it when it's done.
In the meantime: same graph, smaller suitcase. Enjoy the legroom.