IVCSC/IVCSR on-disk format with a byte-offset index (proposed v2 format)

[fishidaho]

The current IVCSC/IVCSR format has no byte-level index. major_ptr indexes value-groups, not bytes — row_indptr = value_ptr[major_ptr] gets you to a group boundary, but locating cell N's bytes still requires decoding (or, via _ivcsc's self-synchronizing LEB128 realignment, scanning) through everything before it. The format is an archive today, and not a queryable store. This means random or metadata-driven cell selection can't skip straight to the bytes it needs. The parallel-decode machinery in _ivcsc.py (_realign_forward, _group_chunk_boundaries) is real engineering, but it exists specifically because there's no byte index; a real offset index would let self-contained records replace that machinery rather than need it.

A separate, related design lesson worth encoding up front: the addressing quantum and the compression quantum are not the same knob. Using one chunk size for both (both the byte-level unit callers seek by, and the unit Blosc2 compresses) costs read throughput — large chunks defeat Blosc2's internal blocking. They need to be independently tunable.

Proposed scope

• A per-major-slice (or per-superchunk) byte-offset index, stored alongside packed_indices, cheap enough to keep in memory even at atlas scale (a few bytes per cell should be enough).
• Two independent size parameters: an addressing quantum (cells per superchunk, tuned for locality under the read patterns real callers use, can be random vs. sample-clustered) and a compression quantum (kept small, tuned for decode throughput, likely close to what the current format's incidental chunking already gets right).
• A decision on whether cell ordering (clustering cells by a query key) is a format-level concern (a stored permutation/sort key) or purely a caller concern. This affects whether the format needs to store anything beyond raw byte offsets.
• Explicitly scope what "v2" means for compatibility: new files only, or a migration path for existing v1 (current-format) files.

Acceptance criteria

• A written design (this issue's discussion, or a linked doc) settling the
  index layout, the two-quantum split, and the cell-ordering question.

Implementation details

• Implement the byte-offset index and two-quantum layout from above in _ivcsc.py/_io.py.
• Create a frozen conformance fixture which can be some small, checked-in file (or generator) that every future change to the codec must keep reading correctly.
• Version negotiation: read_h5ad/read_zarr detect v1 vs. v2 (via the existing encoding-version attribute pattern already used in _io.py) and dispatch accordingly; v1 files keep reading without requiring a re-export. Alternatively, decide that all v1 files should be converted (no backwards compatibility).
• Update write_h5ad/write_zarr's format= parameter (or add a new value) so callers can opt into v2 explicitly.

Acceptance criteria

• A v2 file round-trips exactly (values, shape, ordering) through write → read.
• Reading a small fraction of cells at random costs roughly that same fraction of a full read's bytes and time, measured end to end on the
  shipped format.
• A v1 file written by the current released version still reads correctly with no user-visible change.
• The conformance fixture is checked in and covered by CI.

References

• src/vsparse/_ivcsc.py (_realign_forward, _group_chunk_boundaries),
  src/vsparse/_io.py.

[aarmey]

Something to think about—I don't think blosc provides any benefit to this format. We might just compress with LZ4 or zstd at a low compression level for fast access.

Also, I am fine with just breaking the file format, if we re-save our existing files. We are the only users at this point.