Proposal: Native Sparse Structural Layout for Lance 2.3

[Xuanwo]

• Visit https://xuanwo.io/sketches/lance-discrete-sparse-layout/ first for more design details.
• Visit feat: add sparse structural encoding #7628 for impl references.

---

Summary

This proposal adds SparseLayout, a new structural page layout in Lance file format 2.3 for sparse nested data. Instead of expanding Arrow structure into a dense repetition/definition event stream, a sparse page stores each structural layer as a native slot-domain mapping — non-empty list slots, their child counts, and null slots — while the value side stores only the leaf values that actually exist, still mini-block compressed. Arrow semantics (null list vs. empty list, struct validity, fixed-size-list dimensions) are preserved exactly, and structural cost becomes O(non_empty_slots + null_slots + count_variation) instead of O(rows) or O(structural_events).

The target workloads are mostly-empty list columns, sparse nested structs, and ML metadata where leaf values are far fewer than rows. On a 100M-row benchmark over S3, sparse layout reduces a combined table from 137 MB / 9,933 pages (mini-block) to 105 MB / 6 pages, and cuts warm random-take latency on a deeply nested sparse column from ~1.6 s to ~1 ms.

Problem

Today Lance expresses nested structure as a dense rep/def stream carried by the mini-block or full-zip layouts. This works well for dense nested data, but sparse nested data pays a linear cost for its default states. A typical sparse shape is: most list slots are valid empty lists, a few slots have child ranges, a few slots are null, and leaf values are far fewer than top-level rows.

Compressing the rep/def stream (e.g. RLE) only fixes the bytes. Two costs remain structural:

• The page planner budgets uncompressed rep/def levels, so sparse nested pages get split into thousands of small pages even when their compressed payload is tiny.
• Random take must decode dense structural events for every row in the covered range before it can locate the few hit values.

Proposed Design

Structural layers

A sparse page describes Arrow structure as ordered layers, outer-most to inner-most (SparseStructuralLayer):

Layer kind	Parent domain → child domain	Stored sparse state
validity (nullable item / struct)	slots → same slots	null positions
list	parent slots → child slots	non-empty positions, child counts, null positions
fixed-size-list	parent slots → parent × dimension	dimension, null positions

Absence has defined semantics: a list slot in neither non_empty_positions nor null_positions is a valid empty list; a validity slot not in null_positions is valid; a fixed-size-list slot maps to a child range determined by the dimension. Each layer records its parent and child domain sizes (num_slots, num_child_slots) so readers can validate layer chaining.

Semantic position and count sets

Structural sets are semantic, not necessarily materialized arrays:

• SparsePositionSet is one of empty, all, range (one contiguous slot range), or explicit (a delta-compressed, strictly increasing u64 buffer).
• SparseCountSet is one of empty, constant (one child count shared by all non-empty list slots), or explicit (a compressed u64 buffer).

Common shapes therefore need no structural payload at all: an all-valid layer is null_positions = empty; a dense prefix of non-empty lists is a range; a fixed-degree adjacency column (e.g. HNSW neighbor lists) is range/explicit + constant.

Page contents

Buffer	Contents
0	value chunk metadata, 8 bytes per chunk (chunk byte size and visible value count)
1	mini-block compressed value chunks, with no rep/def levels
2+	one buffer per explicit position/count set, in layer order

Page metadata (SparseLayout) stores the value compression descriptor, the structural layers, the total structural item count (num_items), and the visible leaf value count (num_visible_items). Values reuse the existing mini-block value compression path unchanged; only the structural side is new.

Validation

Readers must reject malformed sparse pages with a format error rather than decode garbage: the physical buffer list must match the layer metadata exactly (one buffer per explicit set, no unused compression descriptors), explicit positions must be strictly increasing and within the layer domain, per-layer domain sizes must chain, and chunk metadata must sum to num_visible_items and to the value buffer size.

Read Semantics

The reader decodes the structural layers once into a cacheable structural plan, then translates selected top-level ranges layer by layer into child ranges:

selected top-level ranges
  -> validity / list / fixed-size-list domain projection
  -> leaf value ranges
  -> value chunk reads (only chunks intersecting those ranges)
  -> Arrow offsets + validity + leaf values

If the projected leaf ranges are empty, the reader reconstructs offsets and validity purely from the plan and reads no value payload. This read contract — never expanding a dense structural stream on the hot path — matters more than any internal decoder structure; implementations may use any adapter that preserves Arrow semantics.

Layout Selection

Sparse is a page layout, not a column-level promise; readers identify it only via PageLayout.sparse_layout. Writers select it two ways:

• Explicitly, with field metadata lance-encoding:structural-encoding=sparse (invalid before 2.3; the metadata is a writer input only and must never be used by readers to infer page layout).
• Automatically in 2.3+, when no explicit structural encoding is requested, the dense rep/def stream exceeds the mini-block structural page budget (the page would need row splits, or a single row alone is over budget), and a sparse structural plan can be built for the page.

The automatic policy is deliberately conservative and is not part of the on-disk contract — it can evolve toward a real cost model without any format change. Mini-block and full-zip remain the layouts for dense nested data and for value types the sparse writer does not yet cover.

Compatibility and Migration

SparseLayout is gated on file version 2.3, which is unstable. Version 2.2 stable files are unchanged, and writers must not emit the layout for older versions. Readers that predate the new PageLayout variant reject 2.3 files under the existing version-compatibility rules, so no old reader ever misreads a sparse page.

The reference implementation currently has these limitations, all compatible with the contract above: dictionary-encoded and packed-struct value blocks are not yet sparse-encoded (they fall back to dense layouts); structural sets are stored as separate page buffers rather than one packed structural sidecar; and automatic selection is intentionally narrower than what the format allows.

[westonpace]

My overall thought is that it makes a lot of sense we would want a new structural layout for sparse data. I'm not entirely certain I understand the proposal yet.

I think the basic argument here is to store a "selection list" instead of a "selection bitmap" (repdef) which would be a good approach I think.

The page planner budgets uncompressed rep/def levels, so sparse nested pages get split into thousands of small pages even when their compressed payload is tiny.

I agree this is a big problem. I had hoped to handle it by changing the page planner to create pages based on the compressed size. Though this is a bit tricky because it means we have to worry about:

• Accumulate 8MB of data
• Pick compressor
• Compress data
• Not big enough, keep accumulating data
• What happens if next batch of data doesn't match compressor we picked?

How does this proposal address this problem? Do you keep accumulating after you've picked a sparse plan?

Or maybe "page" here means mini-block chunk?

Random take must decode dense structural events for every row in the covered range before it can locate the few hit values.

Good point.

A sparse page describes Arrow structure as ordered layers, outer-most to inner-most (SparseStructuralLayer):

In this table the "stored sparse state" for a validity layer is "null positions". If the data is sparse wouldn't you want that to be "valid positions"?

This is somewhat in contrast with the list layer because in the list layer both valid AND null are rare (with empty list being the common case) if I am understanding correctly. Actually, is empty list the common case? Or is null list the common case? Or do you need to plan for both cases?

[Xuanwo]

How does this proposal address this problem? Do you keep accumulating after you've picked a sparse plan?

Or maybe "page" here means mini-block chunk?

We are encoding the whole physical page and the value inside is encoded as chunks.

In this table the "stored sparse state" for a validity layer is "null positions". If the data is sparse wouldn't you want that to be "valid positions"?

Actually, is empty list the common case? Or is null list the common case? Or do you need to plan for both cases?

Nice catch. Yes, I think we should support plan both and picked based on input data shape.