Proposal: Planar Page Layout for Lance 2.3

[Xuanwo]

• Visit https://xuanwo.io/sketches/lance-planar-page-layout/ first for a quick glance.

---

This proposal builds on #7631 / PR #7628: SparseLayout lands first as a standalone page layout in unstable 2.3. What follows is a rework of the overall page-layout metadata that absorbs SparseLayout — together with MiniBlock, FullZip, and Constant — into a single planar model before 2.3 stabilizes. The sparse structural representation itself (position/count sets, the unraveler, extraction from per-layer repdef) is reused unchanged; only where it mounts into the format changes.

Summary

Lance 2.3 replaces the one-message-per-layout shape of PageLayout with a single planar pair: a structural plane (how nested structure is represented: dense rep/def levels, or sparse slot mappings) times a value plane (how values are stored: chunked, zipped, constant, or none). MiniBlock, FullZip, Constant, AllNull, and the landed Sparse layout (#7628) all become cells of this matrix; "miniblock" and "fullzip" stop being format concepts and survive as user-facing aliases for the dense × chunked and dense × zipped combinations — the semantics of today's MiniBlockLayout and FullZipLayout. Every combination that 2.3 keeps is bit-for-bit identical to its 2.2 physical format (one deliberate exception: complex constant/all-null pages switch to the sparse representation, which is smaller), so this is a metadata-level rework, not a new on-disk data format.

This proposal introduces no new encoding and leaves the performance of existing pages untouched — the sparse gains ship with #7628, not here. What the planar model buys is composability and evolution: combinations that each would have required another hand-written layout become plain cells of the matrix — sparse × zipped for mostly-null wide-value columns (e.g. backfilled embedding columns, which no layout serves today), sparse × constant/none replacing the page-level rep/def buffers of complex constant/all-null pages, dictionary alongside sparse structure — and any future structural or value representation (RLE/bitmap structure, new value encodings) is a oneof variant in one plane instead of a new layout re-implementing the other plane.

Problem

In 2.1/2.2, every structural idea hardens into a PageLayout oneof variant that re-implements its own surroundings. Dense rep/def — a single structural representation — already exists in three placement copies: MiniBlockLayout (levels interleaved inside chunks), FullZipLayout (per-record control words), and ConstantLayout (page-level buffers, used by complex all-null pages). The landed SparseLayout (#7628) continues the pattern: it duplicates miniblock's value fields yet lacks dictionary support, adds a fourth parallel scheduler silo on the read side, and welds sparse structure to chunked value storage, so it cannot serve sparse wide-value columns. Meanwhile one kind of decision — how values are stored — is split across two format levels (the miniblock/fullzip choice and constant detection). On this trajectory, every structural-representation × value-storage combination costs a hand-written layout.

Proposed Design

PageLayout is the planar pair

message PageLayout {
  StructuralPlane structure = 1;
  ValuePlane values = 2;
  uint64 num_items = 3;
  uint64 num_visible_items = 4;
}

The division of labor: the structural plane maps rows to visible items and rebuilds repdef; the value plane stores exactly the num_visible_items visible leaf values and maps visible items to bytes. Everything structurally invisible — nulls, empty lists — is the structural plane's job.

A new protos/encodings_v2_3.proto (package lance.encodings23, following the 2.0→2.1 precedent) imports all CompressiveEncoding messages from encodings21 unchanged. Placement is not an independent axis — where structural bytes live is fully determined by the (structural codec, value codec) pair — so there is no top-level layout variant left to choose.

BlobLayout does not carry over. Blob v2 (since 2.2) stores descriptor structs through regular layouts plus an object layer and never emits BlobLayout pages; v1 BlobLayout remains legacy-read-only. Should a genuinely non-planar layout ever appear, it gets a new proto package rather than a speculative extension point here.

The two planes

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

message DenseRepDef {
  // Pure logical semantics, zero physical content. How the level streams are
  // physically carried is described by the value codec (see below).
  repeated RepDefLayer layers = 1;
}

message ValuePlane {
  oneof codec {
    ChunkedValues chunked  = 1;  // small compressed chunks
    ZippedValues  zipped   = 2;  // per-record zipped storage
    ConstantValue constant = 3;  // inline scalar, <= 32 bytes
    NoValues      none     = 4;  // no visible leaf values
  }
}

message ChunkedValues {
  message DenseLevels {
    CompressiveEncoding rep = 1;        // present iff layers contain a list layer
    CompressiveEncoding def = 2;        // present iff layers contain a nullable layer
    uint32 repetition_index_depth = 3;  // accompanies the rep stream
  }
  DenseLevels levels = 1;  // level streams carried inside each chunk
  // value/dictionary compression, num_buffers, has_large_chunk, chunk metadata ...
}

message ZippedValues {
  message DenseLevels {
    uint32 bits_rep = 1;  // control-word width; present iff layers contain a list layer
    uint32 bits_def = 2;  // present iff layers contain a nullable layer
  }
  DenseLevels levels = 1;  // per-record control words
  // per-value compression, bits_per_value / bits_per_offset, stride or offset index ...
}

Why DenseRepDef carries no physical fields: sparse structural metadata is index-like — O(sparsity) small, stored in its own page buffers, read once at page open, after which all addressing happens in memory. Dense levels are payload-like — O(items) large — so they must ride the value storage at its own IO granularity (interleaved in chunks, or as per-record control words), which is what preserves single-IO cold random access on nested data and is exactly where 2.1 already stores them. DenseRepDef.layers alone determines which level streams exist: a list layer implies a rep stream (even all-valid lists have variable-length offsets), a nullable layer implies a def stream, and the repetition index accompanies rep. Each value codec's DenseLevels sub-message describes only how its storage carries the declared streams; readers validate the two by derivation, the same way num_positions must match set cardinality.

New cells unlocked by the matrix (every dense × * cell maps to an existing 2.2 form; see coverage below):

New cell	Use case
sparse × chunked	Exactly SparseLayout (#7628), re-mounted; bytes unchanged
sparse × zipped	Mostly-null wide-value columns. No control words; the offset index shrinks from rows + 1 to visible + 1 entries (4 orders of magnitude at 99.99% null, expected); takes read exactly one value; empty takes do zero IO
sparse × constant / sparse × none	Sparse constant values / nested all-null with O(1) metadata

Two legality rules keep every page's encoding canonical:

• There is no all-valid structural codec. It would be byte-identical and cost-identical to the dense degenerate form (all-ALL_VALID_* layers, zero structural bytes), so a separate variant would only create a second wire encoding for the same page. Trivial structure must always be written as the dense degenerate form, never as sparse. The bar for a structural codec is a distinct cost/capability profile; dense and sparse clear it, all-valid does not.
• dense × constant/none is legal only in the degenerate form. Those value codecs have no value storage for level streams to ride, and a page with non-trivial structure but no value data is exactly what sparse expresses in O(1) sets. (Storing levels in standalone page buffers — as 2.2 ConstantLayout does, or ORC-style full stream separation more generally — was considered and rejected: it either costs an extra IO per nested random access or a new chunk byte format. Worst case for the sparse replacement, a constant page with dense random nulls, is ~2–3x larger structural metadata — small in absolute terms, and a future bitmap structural codec can close it.) With value codec none, the structural plane must make every leaf invisible.

Coverage of existing 2.1/2.2 forms

pb2.0 (Lance 2.0 files) is out of scope: 2.0 has no page-layout concept — structure lives in the ArrayEncoding tree — and it already runs on a frozen legacy path in the reader. Every pb21 form (2.1/2.2 files, plus the 2.3-unstable interim SparseLayout) maps into the planar model with physical bytes unchanged:

pb21 form	Sub-case	Maps to
MiniBlockLayout	with rep/def (incl. repetition_index_depth, has_large_chunk)	dense × chunked
	rep/def compression absent (all valid)	dense degenerate × chunked
	with dictionary	same, dictionary in chunked params
FullZipLayout	bits_per_value (fixed width)	dense × zipped, stride addressing
	bits_per_offset (variable width; second buffer is the rows + 1 row-offset index)	dense × zipped
	bits_rep = bits_def = 0 (NIL control words)	dense degenerate × zipped
ConstantLayout (formerly AllNullLayout in 2.1; evolved in place by #5641)	inline_value present, no rep/def buffers	dense degenerate × constant
	inline_value present + rep/def buffers	read as legacy; 2.3 writers emit sparse × constant instead
	inline_value absent (all-null, incl. compressed rep/def since #4990)	simple → dense degenerate × none; complex → read as legacy, 2.3 writers emit sparse × none
BlobLayout (v1 blob)	inner_layout mapped recursively	read as legacy outer wrapper, no 2.3 counterpart
SparseLayout (#7628, 2.3-unstable interim)	structural metadata buffer + value chunks	sparse × chunked, bytes unchanged

Compatibility and Migration

• Old files: 2.0/2.1/2.2 files are untouched and remain fully readable; no data migration.
• Old readers reject 2.3 files via the existing file-version gate; nothing relies on proto field-level compatibility.
• Public API: the structural_encoding field-metadata values "miniblock"/"fullzip" are kept and map to forcing the historical combinations dense × chunked / dense × zipped (which also suppresses automatic sparse selection, matching the PR feat: add sparse structural encoding #7628 behavior where an explicit request disables auto-sparse).
• Writer defaults: value codec is chosen as today (constant detection, then narrow → chunked, wide → zipped); structure stays dense unless the page exceeds the miniblock rep/def budget or is detected sparse — the PR feat: add sparse structural encoding #7628 trigger, with room to evolve toward cost-based selection later.
• Blob v1 writes close in 2.3: today Binary/LargeBinary blob fields still take the v1 encoder without a version gate; a 2.3 writer returns an explicit error pointing to blob v2 struct input, with no silent conversion.
• Window: 2.3 is unstable with zero stable releases. SparseLayout lands first within unstable 2.3; this rework must complete before 2.3 stabilizes, so that the stable format freezes the planar model rather than four layout variants. Files written with the interim SparseLayout carry no compatibility promise — they remain readable through the mapping above, or can be regenerated.
• Rollout (independently reviewable PRs, after feat: add sparse structural encoding #7628 has merged): (1) the planar rework — the 2.3 proto plus normalization of every pb21 form (including SparseLayout → sparse × chunked) into one internal representation, with the writer switching to the new metadata; acceptance is byte-for-byte equivalence (dense combinations against 2.2, sparse × chunked against SparseLayout pages), and the only behavior change is complex constant/all-null pages switching to sparse × constant/none, whose encode path already exists; (2) sparse × zipped writer support for mostly-null wide-value columns.