# Same graph, smaller suitcase: Galactus DB 1.5.0

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.

![Heap before and after Galactus DB 1.5.0](/blog/charts/release-150-memory.svg)

## 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:

![Time saved per operation in Galactus DB 1.5.0](/blog/charts/release-150-speed.svg)

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:

```text
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.