Database, Rust
Unitylist
A difference-encoded columnar store. A cell holds the cheapest recipe for rebuilding its value from a reference value called a sink, unless storing the value raw is cheaper.
- 1 bit
- The cost of ADD, the most common opcode on the wire.
- 1.0 ms
- To open a store of 2 million rows.
- 15.8 ms
- For GROUP BY with SUM over those rows.
One value, one recipe
Recipe encoder
A simplified version of the idea. The real encoder prices every opcode in wire bits across a whole column; this picks an exact recipe when one fits and a delta when none does.
- Stored as
- 0
The format
- Wire format v3Packed files use continuous bit-packed column streams. The ADD opcode, the workhorse, costs one bit and the rarest opcodes cost eight. Cells are self-delimiting, which saves about 3.5 bits per cell of padding.
- Catalog and zone mapsMinimum, maximum and kind per column load with the catalog, so opening a file does not decode every cell. Columns decode lazily and stay cached.
- Cost-model sinksCompression plans sinks by measured wire bits: values are sorted and deduplicated, then split wherever the saving exceeds the catalog cost of one more sink. There is no fixed cluster count.
- Columnar SQLWHERE compiles to a typed predicate evaluated in parallel over shared column vectors, with zone-map pruning, hash aggregation, and top-k ordering when a limit is present. Joins fall back to a row engine with a hash join.
- Supported SQLSELECT, WHERE, DISTINCT, GROUP BY and HAVING, aggregates, ORDER BY, LIMIT and OFFSET, JOIN and LEFT JOIN, UNION, WITH, batched INSERT, in-place UPDATE, physical DELETE, EXPLAIN.
Spatial mode
A separate store, USPT v4, where a sink is a coordinate plot: a grid cell for point tables or a primary key bucket for relational tables.
Each sink carries a 32 bit locator, and point payloads store add-deltas from the plot point through a 5-bit digit table. Each sink also records how far its contents stray from the plot point, so an ST_DWithin query rejects sinks that cannot reach the radius without opening their files. Rows live in columnar blocks of up to 8,192.
| 2 million rows | Before | After |
|---|---|---|
| Store open | 350 ms | 1.0 ms |
| GROUP BY with SUM | 2,137 ms | 15.8 ms |
| COUNT with WHERE | 2,977 ms | 56.0 ms |
| Self-join | 2,955 ms | 41.7 ms |
| RANK with GROUP BY | 4,124 ms | 17.6 ms |
| ST_DWithin with join | 478 ms | 0.4 ms |
| Peak memory | 750 MB | 222 MB |
Warm minimum of three runs from the dbbench gate, before and after rows moved into blocks. Loading 2 million rows takes about 14 seconds, up from 13.