Redesign CascadingCompressor's exclusion list to be scheme-declared, following Rust's CompressorContext

[dfa1]

We already have the two mechanisms Rust's CompressorContext uses — but only in a generic form,
not the scheme-specific declarative shape Rust has, and I suspect we're "rediscovering" at each
recursion level what a scheme could just declare once.

What we already have (writer/src/main/java/io/github/dfa1/vortex/writer/encode/CascadingCompressor.java,
EncodeContext.java):

• Depth limit: ctx.allowedCascading(), decremented on descend, checked before accepting a
  non-terminal CascadeStep (CascadingCompressor.java:261,298).
• An exclusion set: ctx.excluded(), checked against every candidate's encodingId() before it's
  even sampled (CascadingCompressor.java:199,230,294).

How it's used today — generically, not scheme-declared: when an encoding like Dict recurses
into a child slot, CascadingCompressor excludes the winning encoding itself from that child's
competition (see the comment at DictEncodingEncoder.java:110-112: "excludes the winning
vortex.dict from that child's competition, so the pool is never wrapped in a second dict"). That's
a reasonable default, but it's a single hardcoded rule inside the compressor, not something each
scheme states for its own child.

What Rust does instead (vortex-compressor in spiraldb/vortex, per the blog post linked from
the README's "See also" / docs/explanation.md): each scheme builds its own exclusion list for
its child, naming exactly what doesn't make sense to re-try:

// Don't re-apply dictionary to the codes, and Sequence adds indirection without compressing.
let new_excludes = vec![IntCode::Dict, IntCode::Sequence];
let compressed_codes = compressor.compress(codes, ctx.descend(), &new_excludes);

Note the two exclusions: not just "don't re-apply myself" (Dict), but a second, unrelated
scheme (Sequence) that the author knows adds indirection without compressing dict codes
specifically. Our generic "exclude the winner" rule can't express that second exclusion — Sequence
would still compete on dict codes today, unless we've separately hardcoded it away somewhere (worth
checking SequenceEncodingEncoder.accepts/dtype gating while investigating).

Ask: audit every encoding that overrides encodeCascade
(Alp/Constant/Dict/Fsst/FrameOfReference/DateTimeParts/Patched/Ext/Sequence/SparseEncodingEncoder)
for the child-shape it produces, and give each one its own declared exclusion list for that child —
mirroring Rust's per-scheme new_excludes — instead of relying on CascadingCompressor's one
generic "exclude yourself" default. Look for:

• known-nonsensical combinations we're not currently excluding (Sequence-on-dict-codes is the one
  Rust calls out explicitly; there may be others — Sparse-on-Sparse, RunEnd values re-wrapped in
  RunEnd, etc.)
• whether the sampling work itself gets needlessly repeated across recursion levels for
  candidates that a scheme-specific exclusion would have skipped outright (the "rediscovering it
  every time" cost, not just a correctness/ratio concern)

This is a design/investigation ticket, not a scoped bug — the right first step is probably an ADR
(similar to how the cascading compressor's original design got one) rather than jumping straight to
code.

[dfa1]

Adding evidence from the #408 profiling session — it confirms both halves of this ticket, and the second one ('rediscovering it every time') is the bigger cost.

1. The API can't express Rust's new_excludes at all. EncodeContext.withExcluded takes a single EncodingId (EncodeContext.java:102), and both descend sites hardcode the same generic rule:

// CascadingCompressor.measureStep:287  and  spliceResult:322 — identical
EncodeContext childCtx = ctx.withDecrementedDepth().withExcluded(enc.encodingId());

So 'exclude yourself' is not just the default, it is the only expressible rule. Rust's vec![IntCode::Dict, IntCode::Sequence] has no encoding in our API. Confirms the ticket's suspicion: Sequence does still compete on dict codes today.

2. Measurement and the real encode are two independent full recursions. competeAndEncode runs measureStep for every candidate, discards all of it, then calls spliceResult(winner, ...) which re-descends and re-encodes the same subtree (CascadingCompressor.java:253-278). Inside that, measureBestChild loops over all accepting encodings and each non-terminal one recurses into measureStep → measureBestChild again — with 34 registered encodings and MAX_CASCADE = 3, nothing bounds the fan-out except accepts() and the depth counter. There is no memo anywhere: enc.encodeCascade(...) is re-run from scratch at every level, and encodeWithCtx recomputes ArrayStats.compute for each child at each level (CascadingCompressor.java:200-206).

3. What that costs, measured. JFR allocation profile of one 1M-row I64 write (JavaVsJniRunEndBenchmark.javaRunEndEncode), after the #408 fixes landed — the same chunk being re-derived by candidate after candidate:

allocation site	per benchmark run
ArrayStats$LongCounts.<init> via encodeWithCtx	25.8 GB
PrimitiveArrays.toLongs via RleEncodingEncoder	5.5 GB
PrimitiveArrays.toLongs via BitpackedEncodingEncoder	1.9 GB
PrimitiveArrays.toLongs via FrameOfReferenceEncodingEncoder	1.6 GB
FrameOfReference.residualsAsNativeArray	2.9 GB

Every one of those is a fresh full-width copy of a chunk some sibling candidate already materialized. After #408 the encode benchmark sits at 67.8 ops/s vs vortex-jni's 131.0 — and the remaining gap is spread thinly across exactly these re-scans, with no single hot loop left to fix. That makes this ticket, not a further micro-optimization, the next real lever on write throughput.

Suggested ADR scope, on top of what's already listed:

• widen withExcluded to take a set, and let each encodeCascade return the exclusions for its own children (declared next to the child slot it produces, not inferred by the compressor)
• decide whether measure-then-re-encode can collapse into one pass (keep the winner's CascadeStep rather than recomputing it), or at minimum memoize ArrayStats per (data, level)
• cache the long[] widening so candidates at one level share one copy instead of each allocating their own

[dfa1]

Verified the child-index mapping before translating any rule. Three findings, in increasing order of importance.

1. Rust's rule indices are NOT wire positions

This is the one that breaks naive copying. compress_child(child, ctx, self.id(), N, exec) — the N that ChildSelection::One(N) matches — is a scheme-local logical id the scheme author picks. The trait doc says so: "Each child should be identified by a stable index." It is independent of the array's serialized child order, and upstream's own code proves it:

scheme	logical ids used by exclusion rules	serialized order
Dict (all 4 dtypes)	values=0, codes=1	DictArray::new_unchecked(codes, values) → codes first
RunEnd	values=0, ends=1	RunEnd::new_unchecked(ends, values, ..) → ends first

Both are reversed between the two spaces. Our ChildSlot.parentChildIdx is the wire index — children[slot.parentChildIdx()] = ... writes straight into the EncodeNode children array (CascadingCompressor.java:330). So a rule written One(1) upstream is meaningless against our numbering without a per-encoder translation. Either we adopt a separate logical child-id space, or every ported rule gets hand-mapped. Recommend adopting logical ids — wire order is a format constraint and will drift from what a rule wants to name.

2. Our own Dict numbers its children two different ways

• DictEncodingEncoder primitive cascade (:95-102): {values=0, codes=1}
• DictEncodingEncoder Utf8 cascade (:152-164): {codes=0, values=1} — with the comment "Child order matches the terminal encodeUtf8: [codes, values]"

Same encoder, same EncodingId, opposite slot numbering by dtype. Any exclusion rule keyed on VORTEX_DICT + child index is ambiguous today. This needs settling regardless of whether we port anything — it is arguably a latent bug already.

Sparse is also inverted vs upstream: ours is indices=0, values=1 (SparseEncodingEncoder.java:118-119), Rust's int sparse is values=0, indices=1.

3. Most of Rust's rules have no live counterpart here — because those encodings don't cascade at all

Of our 34 registered encoders, only 10 override encodeCascade and open child slots:

Alp  Constant  DateTimeParts  Dict  Ext  FrameOfReference  Fsst  Patched  Sequence  Sparse

The other 24 take EncodingEncoder's default, which wraps encode() as terminal (EncodingEncoder.java:52-54). That list includes RunEnd, Rle, ZigZag, Delta, Bitpacked, AlpRd, Pco, Zstd.

Cross-referencing against the schemes that declare exclusion rules upstream:

Rust rule-declaring scheme	cascades for us?	its rules reachable?
Dict (int/float/string/binary)	yes	yes
Sparse (int/float/string)	yes	yes
FrameOfReference	yes (child 0 = residuals)	pull rule only, reachable
Sequence	yes	pull rule only, reachable
RunEnd	no — terminal	dead
RLE	no — terminal	dead
ZigZag	no — terminal	dead
Delta	no — terminal	dead

So roughly half the upstream rule set is unreachable here, not because we disagree with it but because those encodings never open a child for anything to be excluded from. Porting them would be writing rules against a cascade that does not happen.

Consequence for this ticket

The exclusion-list port is smaller and less valuable than it looked, and it is blocked behind two prerequisites:

1. Settle child-index identity — introduce logical child ids, and fix Dict's dtype-dependent numbering.
2. Decide whether RunEnd / RLE / ZigZag / Delta should cascade at all. Upstream cascades RunEnd's ends and ZigZag's output into FoR+bitpacking; we store them raw. That is plausibly a bigger compression win than any exclusion rule, and it is what makes the rules worth having.

Only then does the rule table (Dict/Sparse/FoR/Sequence live today, the rest after step 2) pay for itself. Note also two things upstream flags as unsound — a commented-out RunEnd rule in rle_descendant_exclusions (TODO(connor): This is wrong for some reason?) and MAX_CASCADE = 3 (TODO(connor): Why is this 3??? This doesn't seem smart or adaptive.) — neither should be copied on faith.

Suggest the ADR covers 1 and 2 as prerequisites, with the rule port as the third step rather than the first.

[dfa1]

Negative result, recorded so nobody repeats it.

Hypothesis: our RunEndEncodingEncoder.statsOptions() returns (countDistinct=true, trackMostFrequent=true) and ConstantEncodingEncoder returns (true, false), forcing the hash-based distinct-count pass onto every primitive column. The reference does not do this — only Dict and int Sparse set count_distinct_values; its RunEnd scheme reads average_run_length, which falls out of the base stats pass. So: add a cheap run count, switch RunEnd and Constant onto it, and the expensive pass should disappear for columns Dict cannot win.

It does not. Instrumenting rows through each path after the change:

corpus	rows through the HASHED pass	rows through a runs-only pass
runend-like	1.95x file	0
bitpacked-like	1.20x file	0

Every row still takes the hash path, because StatsOptions are OR-merged across all eligible encoders and DictEncodingEncoder declares countDistinct on essentially every primitive column. One greedy encoder keeps the expensive pass alive for everyone, so relieving RunEnd and Constant changes nothing.

Measured like-for-like (2 forks, same machine state — an earlier comparison was invalidated by background load, worth ~9% here):

	baseline	with the change
javaBitPackedEncode	102.5 ± 11.3	108.1 ± 2.7
javaRunEndEncode	94.7 ± 0.9	91.0 ± 12.8
javaWriteCascading	0.508 ± 0.007	0.479 ± 0.029

All overlapping; nothing demonstrable. Reverted — it cost a third StatsOptions flag, run tracking in nine typed loops and new verdict logic in two encoders, for no measured gain.

What this means for the ticket. The stats pass is ~1.2-1.95x the file's rows and equals the cost of the real encode, but it cannot be relieved encoder-by-encoder while options are OR-merged. The levers that remain are:

1. Make Dict's distinct count cheaper or conditional — it is the one keeping the hash pass alive. The reference's stats/cache.rs computes each stat lazily on first access, so a scheme that is skipped before it reads the stat never pays for it; our merge decides eagerly, before any verdict runs.
2. Cheap immediate verdicts (CompressionEstimate::Verdict(Ratio) in the reference) so candidates that cannot win are never sample-encoded. Our Estimate has no Ratio variant — every non-skipped candidate gets a full sample encode.

The one thing that did pay was aligning the sample size (dea70ab): ~1% with a 1024 floor instead of 5%/4096, matching the reference, byte-identical output, and roughly a third off write time.

[dfa1]

Implemented the per-slot exclusion in d72e64b, following the ChildSlot design rather than an EncodingEncoder callback.

public record ChildSlot(DType childDtype, Object childData, int parentChildIdx, Set<EncodingId> excluded)

Both recursion sites — the sample measurement in measureStep and the real encode in spliceResult — now derive the child context through one helper, so a child can no longer be measured under one exclusion policy and encoded under another:

private static EncodeContext childContext(EncodeContext ctx, ChildSlot slot) {
    return ctx.withDecrementedDepth().withExcluded(slot.excluded());
}

withExcluded(Set) unions instead of replacing, so a slot's own policy never drops an ancestor's exclusion (an edition guard, or an enclosing encoding), and returns this when the slot has nothing new to add.

Two deviations from the sketch, both deliberate:

1. No 3-arg convenience constructor. With the compressor's generic self-exclusion gone, a slot that omitted its policy would silently re-enable recursion into its own parent. Requiring the set means the compiler catches that instead of a fuzz run. All 18 construction sites pass one explicitly.
2. Dict's values slot got Set.of(VORTEX_DICT) as suggested, and every other cascading encoder names itself: Alp, DateTimeParts, Ext, FrameOfReference, Fsst, Patched, Sparse — exactly the audit table, which matched what I found in the code.

The Sequence-on-codes rule is a semantic guard, not a win today. SequenceEncodingEncoder requires a perfect arithmetic run end to end (it throws at the first index that breaks the step, multiplier 0 included). Dictionary codes can only satisfy that in two cases:

• cardinality 1 — all codes equal, a valid step-0 sequence, but then the column itself is constant, and Constant/Sequence beats Dict at the top level before any codes child exists;
• every value distinct — codes 0..n-1, which the dict ratio gate (valueMap.size() * 2 > n → notApplicable) rejects first.

So the rule cannot fire with today's gates. It is declared where upstream declares it, so it holds if either gate changes, but I did not write an end-to-end test that would pass with or without it. What is pinned instead: the declaration itself (DictEncodingEncoderTest asserts the codes slot bars Dict+Sequence and the values slot bars only Dict) and the union semantics (EncodeContextTest).

No selection changes: 1833 writer unit tests + 320 integration tests green, and every size-comparison figure is byte-identical to main — FileSizeComparison Java=1'174'292, GlobalDictComparison 2'487'862, NullableLowCardUtf8 33'517, PcoI64 1'702/376'358.

This also removes the child-index identity prerequisite from this ticket for exclusion purposes: a rule attached to the slot needs no stable (EncodingId, childIdx) key, so Dict's dtype-dependent numbering and our inverted Sparse order no longer matter here. Still open from the earlier analysis: whether RunEnd/RLE/ZigZag/Delta should cascade at all — that is where the remaining upstream rules would become reachable, and it is plausibly a bigger compression win than any of them.

[dfa1]

Progress plus one negative result.

RunEnd: done (#435). Ends and values are open child slots with Rust's RunEndScheme exclusions: Dict/RunEnd/RLE/Sparse are barred on ends, RunEnd on values. FileSizeComparison went from 1,174,359 to 1,161,559 bytes (−1.09%) and GlobalDict from 2,487,928 to 2,466,808 (−0.85%), and all interop suites are green.

ZigZag: tried and dropped. It cannot win against FoR. I implemented encodeCascade (encoded child as the unsigned counterpart, exclusions Dict/RunEnd/Sparse/ZigZag, not applicable without a negative) and also registered ZigZag as a cascade candidate, since it was never in buildCascadeCodecs. Sizes were byte-identical to main on FileSizeComparison and on a mixed-sign probe (uniform [-1000,1000], gaussian sd=20, gaussian+outliers, random walk). The reason is arithmetic: FoR's bit width is bits(max − min) and zigzag's is bits(2·max(|min|,|max|)), and max − min ≤ 2·max(|min|,|max|). They tie on data symmetric around zero, and FoR strictly wins otherwise (e.g. [-1, 1000]: 10 vs 11 bits). With FoR in the competition, zigzag + bit-packing never beats FoR + bit-packing, so it would only add a losing candidate, a widen pass and a zigzag pass to every signed column. Not worth it unless a slot ever excludes FoR.

Remaining: RLE (values/indices/offsets) and Delta (bases/deltas). Delta's deltas are signed, so the same FoR-dominance argument applies to any zigzag there.

[dfa1]

Correction to the comment above: ZigZag is not dropped. The goal of this refactor is scheme-by-scheme parity with Rust's vortex-btrblocks, not size wins, so ZigZag cascades as in Rust's ZigZagScheme (#436), with the same exclusions, the same no-negatives skip and registration as a cascade candidate. The FoR-dominance argument still holds, so its output is byte-identical; it is there for parity. Remaining: RLE and Delta, ported the same way.