lance-format / lance-format/lance

Support cascading compression for sparse structural arrays

Open
#7,886 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-encoding A-format enhancement format-change
Dominant language
Rust
Stars
7.1k
Forks
852
Avg merge
3d 18h
Merged PRs (30d)
272

Description

Goal

Use the shared cascading compression framework for sparse structural position and count arrays instead of growing a separate set of format-specific encoding choices.

Context

#7754 represents position sets as empty, all, range, or explicit and count sets as empty, constant, or explicit. Explicit positions are converted to deltas before the resulting u64 array enters CompressionStrategy; explicit counts enter the same strategy directly. The metadata-only variants avoid structural buffers and let readers retain O(1) normalized forms.

The review in https://github.com/lance-format/lance/pull/7754#discussion_r3622578345 noted that these choices overlap with cascading compression. General delta and range encodings could simplify the sparse wire contract while also benefiting non-sparse integer and offset paths.

This follow-up does not block #7754. If it changes the Lance 2.3 SparseLayout wire contract, the change must land before 2.3 is declared stable; compatibility with draft 2.3 files is not required.

Requirements

  • Add composable delta and range encodings to the block compression path.
  • Let cascading selection consider constant, delta, range, RLE, bitpacking, dictionary, general compression, and flat encoding where applicable.
  • Define whether sparse positions enter the cascade as absolute positions or deltas, including the cost model used to choose.
  • Preserve metadata-only or otherwise zero-payload representations for empty, all, range, and constant sequences.
  • Preserve O(1) normalized sparse plans for those representations instead of materializing large u64 arrays.
  • Keep malformed metadata and decoded ordering, bounds, cardinality, and overflow checks returning format errors without panics.
  • Compare wire complexity, encoded size, planning memory, and scan / point-read performance with the representation introduced by #7754.
  • Exercise the generic encodings on representative non-sparse integer or offset paths so this is not a sparse-only codec subsystem.

Part of #7750.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start with the block compression path and shared CompressionStrategy described in the issue, then compare the sparse representation introduced by #7754. Decide how delta and range encodings participate in cascading selection and how their cost model treats absolute positions versus deltas. Done means the required metadata-only behavior, validation, generic non-sparse coverage, and wire-size, memory, and performance comparisons are documented and tested.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data-engineering, performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.