Storage format 2.3 · Design sketch

One page layout, two planes.

Lance 2.2 picks a page layout from a list — MiniBlock, FullZip, Constant — and the sparse work adds another entry. This rework replaces the list with a product: every page is a structural plane times a value plane, and the old layouts become cells of the matrix. The bytes on disk do not move.

RefactorNo new encoding. Kept combinations stay byte-for-byte identical to 2.2.
Free cellssparse × zipped, sparse × constant, sparse × none appear without new layouts.
EvolutionA future structural codec is a oneof variant, not a fifth silo.
PageLayout · 2.3 two planes
structure
dense rep/def
sparse sets
×
values
chunked
zipped
constant
none
The structural plane maps rows to visible items and rebuilds rep/def. The value plane stores exactly the visible leaf values and maps them to bytes. "miniblock" and "fullzip" survive as aliases for dense × chunked and dense × zipped.
01

Every structural idea became another layout.

In 2.1/2.2 the PageLayout oneof grows one variant per idea, and each variant re-implements its surroundings. Dense rep/def — a single structural representation — is already stored three different ways.

MiniBlockLayout

2.1
dense rep/def · in chunks value chunks dictionary repetition index

FullZipLayout

2.1
dense rep/def · control words per-value storage row-offset index no dictionary

ConstantLayout

2.2
dense rep/def · page buffers inline scalar complex all-null silo

SparseLayout

#7628
sparse position/count sets value chunks · copied no dictionary no wide values

Three copies of the same dense representation, then a fourth silo that re-implements the chunked value machinery minus dictionary — and welds sparse structure to narrow values. On this trajectory, every structural-representation × value-storage combination costs a hand-written layout. The next idea would be a fifth.

02

A page is structure × values.

The 2.3 proto has no layout variants left. PageLayout holds the two planes directly; each plane is a small oneof of codecs with genuinely different cost profiles.

encodings_v2_3.proto · sketch
message PageLayout {
  StructuralPlane structure = 1;
  ValuePlane values = 2;
  uint64 num_items = 3;
  uint64 num_visible_items = 4;
}

message StructuralPlane {
  oneof codec {
    DenseRepDef     dense  = 1;
    SparseStructure sparse = 2;  // as specified in #7631
  }
}

message DenseRepDef {
  // pure logical semantics, zero physical fields
  repeated RepDefLayer layers = 1;
}

message ValuePlane {
  oneof codec {
    ChunkedValues chunked  = 1;
    ZippedValues  zipped   = 2;
    ConstantValue constant = 3;
    NoValues      none     = 4;
  }
}

Structural plane rows ↔ visible items

Declares the nesting shape and rebuilds rep/def on read. Everything invisible — nulls, empty lists — is its job. Dense addresses through the repetition index or control words; sparse addresses through its own position sets.

Value plane visible items → bytes

Stores exactly num_visible_items visible leaf values and maps them to bytes: chunk metadata for chunked, stride or offset index for zipped, an inline scalar for constant, nothing for none.

Aliases stay API unbroken

structural_encoding = "miniblock" forces dense × chunked; "fullzip" forces dense × zipped — the exact semantics those names have today, which also suppresses automatic sparse selection.

03

Five layouts become eight cells.

Every existing layout lands in a cell with its bytes unchanged; three cells are new capability that previously would each have cost another layout. Click a cell for the details.

chunked
zipped
constant
none
denserep/def levels
sparseposition/count sets
byte-identical to 2.2 re-mounted from #7628 new capability degenerate form only

Pick a cell

Each cell describes one combination of structural codec and value codec. Colors mark whether it maps to an existing 2.2 form, re-mounts the landed SparseLayout, or is capability the matrix unlocks for free.

04

Placement is derived, not encoded.

Structural data has two consumption modes, and each mode fixes where its bytes live. Nothing about placement is a choice a writer records — it follows from the pair of codecs.

Index-like · sparse sets

page-level
page
position/count sets value chunk value chunk …

O(sparsity) small: read once at page open, then all addressing happens in memory. Structure first, then only the value bytes a take actually reaches. Empty takes do zero IO.

Payload-like · dense levels

rides the value store
chunked
repdefvalues… repdefvalues…
zipped
ctrlvalue ctrlvalue ctrlvalue

O(items) large: reading levels up front would read the page twice, so they ride the value store at its IO granularity — inside each chunk, or as per-record control words. That is what keeps nested cold random access at one IO, and it is exactly where 2.1 already puts them.

Streams are declared by layers, carried by the value codec

A list layer implies a rep stream (even all-valid lists have variable-length offsets); a nullable layer implies a def stream. DenseRepDef carries only layers — each value codec's DenseLevels sub-message describes how its own storage carries the declared streams, and readers validate the two by derivation. There is no degree of freedom to coordinate between the planes.

05

A refactor claims refactor benefits.

This proposal ships after SparseLayout (#7628) lands and builds on it. Being honest about what belongs to whom keeps the review focused.

a

No new encoding

The sparse performance numbers — 26.5x to 334x smaller on the benchmark shapes — ship with #7628, not here. Existing pages keep their exact bytes; kept combinations are verified byte-for-byte against 2.2 and against SparseLayout pages.

b

The delta is the matrix

Three unlocked cells — sparse × zipped for mostly-null wide values, sparse × constant, sparse × none — plus dictionary composing with sparse structure. Each of these would otherwise have been another hand-written layout.

c

One rejected alternative

A fully separated, self-owned level store (ORC-style) would make the planes physically independent too — but it turns one-IO nested takes into two, or requires new chunk byte formats. Expression cleanliness alone did not clear that bar.

06

Old files keep working; stable 2.3 freezes the planar model.

The reader normalizes every pb21 form into the same internal planar representation, so one decode framework serves all versions. 2.3 is still unstable — the rework must land before it stabilizes.

pb2.0 · frozen

2.0 files have no page-layout concept — structure lives in the encoding tree. They keep their existing frozen legacy path and stay out of normalization.

pb21 · normalized

2.1/2.2 files, plus 2.3-unstable files written with the interim SparseLayout, all map into planar cells with bytes unchanged. Complex constant/all-null pages read as legacy states.

pb23 · planar

New 2.3 files carry the planar pair. Complex constant/all-null pages switch to sparse sets — the one deliberate behavior change. Stable 2.3 freezes this model, not four layout variants.

  • Old readers reject 2.3 files through the existing file-version gate — nothing depends on proto field-level compatibility.
  • structural_encoding keeps its values: "miniblock" and "fullzip" force the historical dense combinations.
  • Blob v1 pages stay readable; the v1 write path closes in 2.3 with an explicit error pointing at blob v2.
  • Rollout is two reviewable steps: the planar rework with byte-for-byte acceptance, then sparse × zipped for wide values.

Context: proposal discussion #7635 · sparse layout discussion #7631 · PR #7628 · companion sketch: Lance discrete sparse layout