Pileon SQL stores a recipe for each value instead of the value

Most columnar stores compress a column by finding a pattern in it: runs, a dictionary, a frame of reference. Pileon SQL takes a narrower view of each cell. Every column stands on one or more reference values called sinks, and a cell stores the cheapest recipe for rebuilding its value from its sink. When no recipe beats the value itself, the value is stored raw.

One value, one recipe

Say a sink holds 8821. A cell whose value is 9640 is stored as +819. A cell whose value is 4410 is stored as /2, because 8821 divided by two and truncated is exactly 4410, and an exact operation is cheaper on the wire than a delta. A cell holding the text vienna has nothing to measure from, so it stays raw.

Those three cases are fixtures in the test suite: if a change to the encoder ever picks a different recipe for any of them, the build fails.

The cost of a recipe is counted in wire bits. Opcodes sit in a prefix-free tree, so the most common one, ADD, costs a single bit and the rarest cost eight. Cells are self-delimiting, which saves about 3.5 bits per cell that would otherwise go on padding.

Choosing the sinks

How many sinks a column gets is not a fixed number. The compressor sorts and deduplicates the values, then splits the range wherever the bits saved are worth more than the catalog cost of one more sink. A column with one tight cluster of values ends up with one sink; a column with several distant clusters gets one each.

Wire format v3

Packed files use continuous bit-packed column streams instead of one record per cell.

Catalog and zone maps

The minimum, maximum and kind of every column load with the catalog, so opening a file decodes no cells. Columns decode lazily and stay cached.

Query engine

WHERE compiles to a typed predicate that runs 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.

SQL

SELECT, 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 and EXPLAIN.

Spatial mode

Spatial data lives in a separate store, USPT v4. There 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 its plot point. An ST_DWithin query can therefore reject every sink that cannot possibly reach the search radius without opening its file. Rows sit in columnar blocks of up to 8,192.

Blocks, measured

The largest single change to Pileon SQL was moving rows into those blocks. Before it, a 2 million row relational table averaged about one row per storage unit, so every scan paid per-unit overhead on every row. The numbers below are the warm minimum of three runs from the benchmark gate, before and after.

Loading the 2 million rows takes about 14 seconds, up from 13. That is the one figure that went the wrong way.

Two lessons from benchmarking it

Benchmarks run as one process per query hid real behaviour. Spawning a fresh command line for every query paid about 25 ms of startup and rebuilt every lazily built structure, including the primary key locator, which is built once per process by scanning all rows. Measured against a running server, the self-join took 41 ms where one-shot runs had shown 204 ms. Pileon SQL is now benchmarked through its server.

Spatial scans turned out to be bound by memory, not CPU. Counting 2 million rows took 3.2 s on one worker and 2.3 s on two, then got slower with every worker added after that, reaching 4.9 s on sixteen while CPU time grew eightfold. The scan uses two workers, and the work since has gone into doing less per row instead of adding threads.

Read the Pileon SQL project page for a working recipe encoder you can type values into.

Written by Caisson AI. Questions or corrections go to hello@caissonai.co.