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.

Current status

The implementation stack has landed on main:

• refactor(encoding): clarify mini-block repdef budget #7751 clarified the dense mini-block rep/def budget contract.
• fix(encoding): decode empty inline-bitpacked blocks #7752 fixed empty inline-bitpacked decoding.
• The sparse reader and explicit writer were consolidated in feat(format): read and write sparse structural pages #7754; the reviewed change landed on main through feat(format): read and write sparse structural pages #7889, and the separate feat(encoding): write sparse structural pages explicitly #7755 was closed as absorbed.
• perf(encoding): auto-select sparse structural pages #7756 added automatic sparse selection and recorded the final integration benchmark.
• The original problem in Can we come up with a new structural encoding for sparse data? #6841 is resolved.

This tracker remains open for the proposal and format-vote bookkeeping in format proposal #7631, the pre-2.3 cascading-compression follow-up in #7886, and closing the superseded prototype #7628.

Context

• Original problem: Can we come up with a new structural encoding for sparse data? #6841
• Format proposal: format proposal #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 integration benchmark is recorded in #7756. The prototype numbers remain evidence for the design and are not relabeled as measurements of the merged head.

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

The five planned deliverables are complete. The reader and explicit-writer work were consolidated during landing:

• PR 1: refactor(encoding): clarify mini-block repdef budget — Merged in refactor(encoding): clarify mini-block repdef budget #7751.
• PR 2: fix(encoding): decode empty inline-bitpacked blocks — Merged in fix(encoding): decode empty inline-bitpacked blocks #7752.
• PR 3: sparse reader and wire contract — Reviewed in feat(format): read and write sparse structural pages #7754 and landed on main through feat(format): read and write sparse structural pages #7889.
• PR 4: explicit sparse writer — Absorbed into feat(format): read and write sparse structural pages #7754 / feat(format): read and write sparse structural pages #7889; feat(encoding): write sparse structural pages explicitly #7755 was closed without a separate merge.
• PR 5: perf(encoding): auto-select sparse structural pages — Merged in perf(encoding): auto-select sparse structural pages #7756.

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 the landed sparse layout, but any SparseLayout wire-contract change must land before Lance 2.3 is declared stable.

Format merge gates

• Freeze final protobuf tags and remove draft-only allocation artifacts.
• 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 the remaining unchecked items above are resolved, any required pre-2.3 wire-contract follow-up is complete, and #7628 is closed as superseded.