Tier-2 vectors: CSR ragged (values/offsets/cell_ids) + t-digest as List<FixedSizeList<2>>

[espg]

Follow up to #40 and #29

We want both CSR ragged, and t-digest; is t-digest best to implement as an arrow kernel?

[espg]

🤖 from Claude

The two asks here are separable, and keeping them separate is what makes the design clean:

1. CSR ragged carrier — storage for variable-length per-cell payloads (values / offsets / cell_ids).
2. t-digest — a compute + merge concern that happens to produce a ragged payload, so it rides on (1).

On "is t-digest best as an Arrow kernel?"

The key distinction is build-once vs. mergeable sketch. Arrow does have a tdigest/approximate_median compute kernel, but it returns a final quantile scalar — it does not hand back storable, re-mergeable digest state. The whole reason t-digest came up (the waveform/#40 discussion: scalar quantiles aren't mergeable, a (means, weights) digest is) is that we need to store partial per-cell digests and merge them across shard/partial writes. Arrow's kernel can't do that. So:

• (A) Arrow compute kernel only — good for one-shot quantiles over a fully-materialized cell; fails the mergeable-across-shards requirement. Not sufficient on its own.
• (B) Pure-Python/numpy t-digest producing (means, weights), carried as the approved List<FixedSizeList<2>> Tier-2 layout. Pros: full control of merge() semantics, true mergeability across partial writes, easy to test, no compiled dep. Cons: per-cell Python overhead; needs a chosen/vendored algorithm (dependency call).
• (C) Compiled kernel (a mortie-style PyO3 crate, or a maintained lib like crick/pytdigest) for build+merge, results stored via the CSR carrier. Pros: speed + real mergeability. Cons: a compiled/maintained dependency (§4 discussion).

My lean: land the CSR ragged carrier first as the general Tier-2 mechanism (it's instrument-agnostic and is the same List/LargeList → values/offsets/cell_ids machinery we already pointed at), then add t-digest as its first consumer via option B (mergeable (means,weights)), reaching for a compiled kernel (C) only if profiling says Python merge is the bottleneck. Arrow's tdigest kernel stays useful for the non-mergeable "just give me the median now" path.

Open questions for you

1. Mergeability — confirm digests must be stored and re-merged across partial shard writes (not just computed once per fully-materialized cell). That single answer decides whether Arrow's kernel is viable at all.
2. Dependency appetite — OK to add a t-digest lib (pure-Python pytdigest/tdigest, or compiled crick), or do you want it hand-rolled/vendored to avoid a dep?
3. Centroid budget — fixed compression/δ (bounds the ragged width per cell) vs. unbounded?
4. Scope split — land CSR ragged carrier as its own PR, then t-digest as a follow-on consumer (one issue → one PR), or bundle?

Marking waiting on your read.

---

Generated by Claude Code

[espg]

land the CSR ragged carrier first as the general Tier-2 mechanism (it's instrument-agnostic and is the same List/LargeList → values/offsets/cell_ids machinery we already pointed at), then add t-digest as its first consumer via option B (mergeable (means,weights)) -- we'll profile and see if IO runtime vs compute justifies a compiled extension.

Mergeability — confirm digests must be stored and re-merged across partial shard writes (not just computed once per fully-materialized cell). That single answer decides whether Arrow's kernel is viable at all.

digests must be stored, and they should be able to be re-merged in the future... could we modify the tdigest/approximate_median compute kernel in arrow?

Dependency appetite

hesitant to add a t-digest lib given the hassle it introduces for packaging into the lambda. If we were going with a compiled extension, we'd certainly roll our own and include it as a rust crate.

Centroid budget

fixed compression ; δ = 512 to start, although we'll probably try a few δ values

Scope split — land CSR ragged carrier as its own PR, then t-digest as a follow-on consumer (one issue → one PR), or bundle?

Bundle ; t-digest as last / final phase(s)

[espg]

🤖 from Claude

Phased implementation plan, incorporating your decisions: bundle into one PR, CSR ragged carrier first with t-digest as the final phase(s), fixed compression δ = 512 to start, no external t-digest dependency (roll our own as a Rust crate only if profiling later justifies a compiled extension).

On "could we modify the Arrow tdigest/approximate_median compute kernel?"

Not viably. That kernel is compiled C++ inside the pyarrow wheel — "modifying" it means forking and rebuilding Arrow C++, which is exactly the packaging hassle you want to avoid for the Lambda layer, plus an unbounded maintenance burden. More fundamentally, the kernel is designed to return a final quantile scalar, not storable/re-mergeable digest state — so even a patched kernel doesn't give us the mergeable (means, weights) we need across partial shard writes. So: our own mergeable digest state (option B), with Arrow's stock kernel kept only for the non-mergeable "just give me the median of this materialized cell now" path. If profiling says the Python merge is the bottleneck, that's when a roll-our-own Rust crate (no PyPI dep) enters — as its own §4 discussion.

Phase 1 — CSR ragged output signature (config)

Extend the Option-B field-kind machinery already landed for #29/#40 with a ragged kind. A ragged field declares its element dtype (+ optional fixed inner width, e.g. the 2 of a (mean, weight) centroid). get_output_signature returns the ragged descriptor; _validate_output_kind accepts it alongside scalar/vector. Scalar/vector configs byte-for-byte unchanged.

• Files: src/zagg/config.py, tests/test_config.py.
• Acceptance: ragged field validates; scalar/vector unchanged; bad ragged descriptor rejected.

Phase 2 — ragged per-cell payloads through the Arrow seam

calculate_cell_statistics returns a per-cell variable-length payload for ragged fields (empty cells → empty list). Carry it through the existing #30/#40 Arrow handoff as List<...> / LargeList<...> (reusing _concat_and_group/_group_columns). Pure-scalar/vector paths stay on their existing routes.

• Files: src/zagg/processing.py, tests/test_processing.py.
• Acceptance: ragged cells round-trip through the Arrow carrier with correct per-cell lengths; empty cells carry an empty list.

Phase 3 — CSR writer + reader to Zarr v3

Store each ragged field as the CSR triple — a flat values array, an offsets array (per-cell start indices), and cell_ids (the populated cells), as Zarr v3 arrays (variable-length is representable this way without a ragged dtype). Add a leaf→Zarr→read round-trip test.

• Files: src/zagg/grids/base.py (template/spec), src/zagg/processing.py (write site), tests/test_grids.py, tests/test_processing.py.
• Acceptance: CSR triple round-trips; reconstructed per-cell slices match; reducers can re-read and merge.

Phase 4 — t-digest as the first ragged consumer (mergeable)

Pure-Python/numpy mergeable t-digest producing (means, weights) centroids at fixed δ = 512, stored as the ragged List<FixedSizeList<2>> payload. Implements merge() so partial per-shard digests combine across writes (the load-bearing requirement). No external dependency.

• Files: new src/zagg/stats/tdigest.py (or alongside the reducers), wired as a reducer; tests.
• Acceptance: digest merges across partial shard writes and reconstructs quantiles to ~1 cm on a waveform-like distribution; deterministic at fixed δ; mergeable-vs-one-shot equivalence within tolerance.

Phase 5 — δ sweep + profiling note (no new code path)

Exercise a few δ values (e.g. 128 / 256 / 512 / 1024) for the accuracy/width tradeoff and record an IO-vs-compute profiling note that calibrates whether a compiled Rust digest is worth a future §4 discussion. No dependency added here.

Out of scope (recorded)

• External t-digest libs (pytdigest/tdigest/crick) — Lambda packaging hassle; roll our own Rust crate later only if profiling justifies.
• Modifying Arrow's compiled kernel — not viable (above).

Open questions

1. CSR layout — flat values + offsets + cell_ids per ragged field as separate Zarr arrays (above), or a single combined group? (Lean: separate arrays, simplest to read/merge.)
2. δ sweep set — {128, 256, 512, 1024}, or a different range to start?
3. Inner-width declaration — declare the centroid width (2) on the field as FixedSizeList<2>-of-ragged, or leave the inner shape implicit to the t-digest reducer?

No code written (this is plan). Marking waiting on your read.

---

Generated by Claude Code

[espg]

...the real question we aren't addressing above is the csr implementation. The point of zagg supporting numpy is for people to be able to write there own, vectorized functions so we don't need to bring in external libraries or compiled extensions.

The t-digest naturally models as a csr sparse array. My read from above is that we're rolling our own here (please correct me if that's wrong). SciPy already implements csr natively... so we could (presumably) keep our codebase leaner if we had scipy. Is this correct? My sense is that phase 3 would effectively drop out, since there's presumably already support for flushing csr scipy arrays to zarr natively. Or perhaps I'm missing this-- maybe we stay in dense space for the worker, and only the cast is to sparse, which means that we can side step scipy altogether.

The larger question remains though-- should we extend the universe of zagg lambdas to include scipy? It's a slippery slope... the next question becomes, do we support scipy too? At some point we're looking at including pytorch as well. This could be a good thing-- maybe one day zagg is orchestrating GPU workloads. But realistically, we're getting over our skis at this point in time; there's no 'per GB second' GPU equivalent server-less offering from aws that I know of (again, correct me if I'm wrong). The closest thing is sagemaker, and sagemaker bedrock.

In any case, we need to discuss how we speed up things like t-digest. Options we should weigh are:

• Use numpy
• Use numpy + scipy
• Use numpy + scipy + sklearn
• Rust crates that are added
• cython as an escape hatch
• allow for jitting via jax or numba or similar
• your idea (not listed above)

Something to consider, but not over weight, is what these choices mean for backend extensibility beyond lambda. We'll always have local (for unit testing); we may add vaex at some point, or slurm for byo hpc, or another cloud backend. What are the pros / cons of each approach? What's the expected size impact of covering scipy (and potentially sklearn) as arm64 lambda environments? Does the jit'ing approach even work on arm64? What's the complexity-- both of implementation, and of maintenance? What decision has the best user experience, and cleanest template construction?

I want to iterate on this question first, before answering the other 'open design questions' that were enumerated.