Tracking: Land native sparse structural layout in Lance 2.3

[Xuanwo]

Goal

Land the native sparse structural page layout in Lance file format 2.3 through a sequence of reviewable, independently testable pull requests.

Sparse nested data currently produces much more repetition/definition information than visible leaf data. This either forces full-zip, which is inefficient for sparse reads, or splits the structure into many small pages. SparseLayout solves this by storing Arrow structure as native slot-domain mappings instead of a dense rep/def event stream.

Context

• Original problem: Can we come up with a new structural encoding for sparse data? #6841
• Format proposal: Proposal: Native Sparse Structural Layout for Lance 2.3 #7631
• Prototype implementation and full benchmark results: feat: add sparse structural encoding #7628
• Design visualization: https://xuanwo.io/sketches/lance-discrete-sparse-layout/

The prototype validates the complete direction:

• Structural layers are ordered outer-most to inner-most.
• Position sets support empty, all, range, and explicit representations.
• List counts support empty, constant, and explicit representations.
• Validity can store either valid or null positions, selected by encoded cost.
• Leaf values remain mini-block compressed.
• Readers project requested row ranges through structural layers and only read intersecting value chunks.
• Lance 2.2 remains unchanged; writers may emit sparse pages only in 2.3+.

On the 100M-row S3 prototype:

• Uniform sparse data was 26.5x smaller than mini-block and 4,277x smaller than full-zip.
• Deep sparse nested data was 334x smaller than mini-block and 872x smaller than full-zip.
• Warm random take on deep sparse data was 85.9x faster than mini-block and 183x faster than full-zip.
• HNSW-shaped data showed smaller but still positive size and scan improvements, with random take near parity.

The final stack must be benchmarked again after integration cleanup. The prototype numbers are evidence for the design, not a substitute for validating the merged implementation.

Merge principles

• Introduce the final wire contract once. Do not merge intermediate draft representations.
• Land reader support before any production writer can emit sparse pages.
• Include malformed-input validation with the reader, not as a later hardening PR.
• Keep explicit writer support separate from automatic layout selection.
• Preserve all Lance 2.2 behavior.
• Do not make ordinary dense 2.3 writes pay for sparse planning.
• Keep sparse implementation in dedicated modules instead of expanding primitive.rs and repdef.rs further.

Pull request stack

Dependencies:

format proposal and vote -> PR 3 -> PR 4 -> PR 5
PR 1 -------------------------------------> PR 5
PR 2 ---------------------> PR 3

• PR 1: refactor(encoding): clarify mini-block repdef budget

  • Rename the current structural page plan to describe what it actually measures: the dense mini-block rep/def budget.
  • No format, sparse, or behavioral changes.

• PR 2: fix(encoding): decode empty inline-bitpacked blocks

  • Handle zero-value inline-bitpacked blocks for 8/16/32/64-bit widths.
  • Keep this generic codec fix independent from the sparse reader.

• PR 3: feat(format): read sparse structural pages

  • Freeze the final protobuf field allocation and format specification.
  • Add reader-side 2.3 version gating.
  • Add semantic structural sets, metadata validation, cached structural plans, range projection, and selective value-chunk reads.
  • Add malformed-page tests and a checked-in 2.3 sparse fixture.
  • Do not add a production writer in this PR.

• PR 4: feat(encoding): write sparse structural pages explicitly

  • Add explicit lance-encoding:structural-encoding=sparse support for 2.3.
  • Build semantic structural layers once and share the normalized representation with dense/sparse serialization.
  • Avoid reconstructing dense rep/def solely to calculate sparse metadata.
  • Cover nullable primitive/struct, list/large-list/map, fixed-size-list, null/empty lists, both validity polarities, and all semantic position/count representations.
  • Document and test the constant/all-null page boundary.

• PR 5: perf(encoding): auto-select sparse structural pages

  • Select sparse when dense mini-block rep/def requires page splitting or one row exceeds the budget.
  • Preserve explicit mini-block/full-zip selection.
  • Define eligibility before selection so automatic 2.3 writes cannot turn previously supported dictionary or packed-struct writes into NotSupported errors.
  • Verify that within-budget dense pages do not construct sparse plans.
  • Rerun the final 100M-row S3 size, cold-read, and warm-read benchmarks.

Follow-up work

• Support cascading compression for sparse structural arrays #7886 - Consolidate sparse structural position/count arrays with generic cascading compression.
  • This does not block PR feat(format): read and write sparse structural pages #7754, but any SparseLayout wire-contract change must land before Lance 2.3 is declared stable.

Format merge gates

• Update Proposal: Native Sparse Structural Layout for Lance 2.3 #7631 to describe valid/null validity polarity.
• Freeze final protobuf tags and remove draft-only allocation artifacts.
• Complete the required format vote and link it from the format PR.
• Verify reader rejection of SparseLayout in pre-2.3 files.
• Verify malformed metadata returns format errors without panics.
• Verify scan, range, and discontiguous take across deeply nested Arrow structures.
• Verify no regression in Lance 2.2 output or behavior.
• Verify final size, page-count, cold-read, and warm-read results.

This issue is complete when all five PRs are merged, any required pre-2.3 wire-contract follow-up is resolved, the final format vote is linked, #7628 is closed as superseded, and the original problem in #6841 is resolved.