Columnar Storage

Columnar Storage

Column-oriented storage keeps the values of each column together instead of storing complete rows next to one another. For MemCP this serves two related goals:

• Compression: values of one column usually have similar types, ranges, repetition, or ordering and can use a specialized compact encoding.
• Cache locality: a query reads only referenced columns, so scans avoid moving unrelated row fields through memory and CPU caches.

Compression is not only a capacity feature. A lightweight decoder can be cheaper than fetching additional cache lines from a larger uncompressed representation.

Main and delta storage

Each shard separates stable main rows from recent changes. Main storage is columnar and compressed. Inserts, updates, and deletions are represented through delta structures and transaction visibility metadata until rebuild work produces a new main generation.

Scans combine main and delta data without exposing that physical split to SQL. Ordered indexes merge their compressed main-record permutation with index-local delta entries; deleted or invisible records remain filtered according to the active transaction.

This design keeps immutable compressed columns efficient while allowing writes without rebuilding the complete column for every statement. See Shards, RecordIDs, Main Storage, Delta Storage.

Interface design

The storage interface has to support several competing requirements:

• concurrent random reads for point lookups;
• efficient sequential and arbitrary-ID batch reads;
• format-specific cached decoding without sharing mutable reader state between goroutines;
• analysis of incoming values before selecting a representation;
• statistics for query planning;
• stable persistence across software upgrades;
• optional native JIT emission for hot value access.

The original implementation can be understood through this deliberately reduced two-pass model. It is not the complete current Go interface, but it exposes the stable idea more clearly than the optimized implementation:

<syntaxhighlight lang="go">type ColumnStorage interface {

   GetValue(recordID uint32) any

   // analysis pass
   prepare()
   scan(recordID uint32, value any)
   proposeCompression() ColumnStorage

   // build pass
   init(size uint32)
   build(recordID uint32, value any)
   finish()

   Serialize(io.Writer)
   Deserialize(io.Reader)

}</syntaxhighlight>

The optimized code adds batch readers, transaction-aware access, statistics, versioned serialization and JIT hooks around this model; it does not change the analyze → choose representation → build sequence.

The current read side is split into ColumnStorage and a per-goroutine ColumnReader:

<syntaxhighlight lang="go">type ColumnReader interface {

   GetValue(recid uint32) Scmer
   GetValueMulti(recids []uint32, target []Scmer, stride int)
   GetValueRange(recid, count uint32, target []Scmer, stride int)

}</syntaxhighlight>

GetValue supports one random RecordID. GetValueRange reads consecutive IDs, allowing bit-position calculations, binary searches, or decoder initialization to be shared by a complete run. GetValueMulti gathers arbitrary IDs such as an index permutation and detects consecutive regions where the encoding benefits from a sequential path.

Both batch methods write into a caller-provided target with a configurable stride. A scan assembling an interleaved row buffer can therefore fetch one column at a time without allocating an intermediate list for every value.

GetCachedReader() returns a reader optimized for repeated access. Such a reader belongs to one goroutine and must not be shared. Transaction-dependent formats can provide a transaction-bound reader; callers should use shard/table helpers rather than reaching into column maps directly.

Analysis and build phases

Column creation and shard rebuild use a two-pass process so the format can be selected from the actual data before allocating its final representation.

1. Analyze
   • prepare() resets format-specific observations.
   • Each future value is passed to scan(recordId, value).
   • The implementation records facts such as type, range, scale, distinctness, repetition, NULL/default frequency, run structure, and string dictionary potential.
   • proposeCompression(size) may return a more suitable lossless storage implementation.
   • If the format changes, analysis repeats for the proposed representation.
2. Build
   • init(size) allocates the final structures.
   • build(recordId, value) encodes every value.
   • finish() releases temporary builder state and finalizes dictionaries or indexes needed by the representation.

This makes compression a data-dependent decision rather than a fixed mapping from SQL type to one physical format. The selected storage still reports a cheap distinct-count estimate for physical planning.

Storage formats

The current implementation includes and composes formats such as:

Format	Purpose
StorageSCMER	Generic Scheme values and the universal starting representation when no narrower format is yet known.
StorageConst	One repeated value without storing it once per record.
StorageSparse	Sparse/default-heavy columns represented by exceptional RecordIDs and values.
StorageInt	Bit-packed integers whose width and offset are derived from the observed range.
StorageSeq	Arithmetic sequences and runs such as ordered identifiers.
StorageDecimal	Exact fixed-scale decimals backed by an appropriate integer representation.
StorageFloat	IEEE floating-point values.
StorageString	Dictionary or buffer-based strings with specialized batch decoding.
StoragePrefix	Prefix/suffix decomposition for strings where that representation is applicable; currently experimental for automatic selection.
StorageEnum	rANS entropy coding for suitable low-cardinality values.
OverlayBlob	External large binary/blob values layered over a base representation.
computed/cache proxy	Values derived from other columns or populated on demand while retaining the column-reader contract.

Formats can be nested. For example, a decimal delegates its scaled integer payload to another storage, and string or sequence metadata can itself use compressed integer representations.

Batch execution and late materialization

MemCP scan operators fetch filter columns first and process RecordIDs in batches. Only surviving IDs need map, join, or output columns. Consecutive survivors use GetValueRange; ordered or index-derived ID lists use GetValueMulti.

This is late materialization: complete logical rows are assembled only at an edge that needs them. Filters, projections, aggregation, RecSet operations, and ordered scans can remain column-oriented in the hot path. It also avoids one interface call and one decoder restart per element.

For supported hot expressions, a storage can emit native access code through JITEmit. Unsupported JIT shapes retain the normal reader path and must preserve identical values.

Concurrency and locking

A stable ColumnStorage pointer can be read concurrently, but the shard structures that publish it are protected by the shard lock. Scan and planner code must obtain storages through helpers such as getColumnStorageOrPanic, ColumnReader, or their transaction-aware forms instead of reading the shard's column map directly.

Read-only snapshots use the shard read lock; mutation, rebuild, log replay, delta changes, and index publication require the write lock and concurrency rights. Locks and rights must be released through panic-safe cleanup. Per-goroutine cached readers avoid a lock or mutable decoder shared inside the element loop.

Persistence and compatibility

Every serialized column begins with a permanently assigned magic byte identifying its storage type. Most types then carry a layout-version byte. Binary layout changes must increment that version and retain all older deserializers so existing database files remain readable.

Legacy magic bytes 1, 2, 13, and 40 have no version byte. An incompatible change to one of those layouts requires a new magic byte; the legacy assignment remains a read-only reader forever. Magic values must never be renumbered or reused.

Serialization compatibility is therefore part of the user-visible durability contract, not merely an internal implementation detail. See Persistency and Performance Guarantees.

Measuring compression

An early 55 MiB JSONL experiment produced the following observations. It mixed disk and RAM measurements and did not record schema, cardinalities, process baseline, engine mode, versions, warm-up or repeatability, so it is historical evidence—not a controlled MySQL comparison or a universal ratio.

Representation	Reported size
MySQL InnoDB source	55 MiB disk
JSONL export	55 MiB disk
Imported maps in delta storage	233 MiB RAM
Main storage using only StorageSCMER	81 MiB RAM
Integer columns using StorageInt	46 MiB RAM
String columns using StorageString	58 MiB RAM
Combined integer and string encodings	23 MiB RAM

A useful evaluation should report the source dataset and generator, schema and row count, per-column cardinality/range, selected storage formats, main/delta split, MemCP commit, ENGINE, process baseline, measured column sizes, indexes, and repeatable query timings. Compare equal logical data and distinguish allocated RAM, resident memory, serialized bytes, and external backend usage. See Performance Measurement and In-Memory Compression, Columnar Compression Techniques.