Tracking Issue: Pluggable execution-speed-aware compressor cost model

[connortsui20]

This is a tracking issue for making the compressor's selection policy a pluggable CostModel. The goal here is to have different cost models (instead of the hard-coded compression ratio as cost), so that we can choose encodings that optimize for execution time instead of just size.

I have a bunch of (LLM) research on separate branches:

• Research README (TL;DR + doc index)
• Design doc (Candidate + CostModel, how selection changes, the presets)
• Original implementation plan (the original full ladder and the decisions taken on the open design questions)

Current direction: the research documents capture the original full ladder. The sequencing and scope below are authoritative where they differ from IMPLEMENTATION-PLAN.md.

Motivation

Right now, the only objective the compressor understands is estimated compression ratio. But we clearly already have opinions about execution speed, they just have nowhere to live, so they are somewhat hacked in:

• The Delta "tax": DELTA_PENALTY = 0.95 plus a 1.25 min-ratio floor, which is an execution-speed judgment expressed as a ratio multiplier inside the scheme.
• The ALL_SCHEMES registration-order comment "Prefer all other schemes above delta, for now (since its slower to decompress)".
• The hand-maintained only_cuda_compatible() exclusion list, which is really a cost model with exactly two values (possible/impossible).

A user writing Vortex files cannot say "optimize for scan speed on NVMe" or "optimize for point lookups", and the same column genuinely wants different encodings under those two workloads, so no single hardcoded policy can serve both.

Doc 1 maps out where every one of these judgments lives today.

Design

The first extraction separates candidate cost computation from scheme estimation:

vortex-compressor/src/cost

pub trait CostModel: Send + Sync + 'static {
    fn cost(&self, candidate: &Candidate<'_>) -> Option<Cost>;              // None rejects
    fn canonical_cost(&self, data: &ArrayAndStats, n_values: u64) -> Cost;  // the baseline to beat
}

SizeCost remains the default and reproduces today's ratio-based selection. The initial extraction deliberately does not include deferred-work pruning, Delta policy relocation, builder/file-writer plumbing, or an execution-time model. Those follow only after the interface has landed independently and the measurement work has established what a real non-size model needs.

Note that even if we do not decide to have a cost model that optimizes for execution time, I think it is still beneficial to split this logic out as it makes the compressor more modular (and I think it will be easier to understand).

Steps

(LLM-generated)

Details

Track A: establish the baseline and extract selection policy

• Golden encoding-tree regression suite: Add golden-corpus determinism tests for the default compressor #8697
  • Closes Better compressor tests (does it compress into the right thing)? #6171.
  • Snapshots complete encoding trees and exact array-level byte counts across a fixed corpus.
  • OnPair is excluded because its training is nondeterministic.
• Candidate + CostModel + SizeCost; selection becomes argmin cost: Extract scheme-selection policy into a pluggable CostModel #8698
  • Default selection behavior remains unchanged.
  • Candidate remains compressor-owned and evolution-safe.
  • Cost has a finite total order.
  • Scheme::evaluate produces model-independent evaluation::CandidateEstimate evidence; the compressor adds scheme/input/sample/cascade context to construct the Candidate passed to CostModel::cost.
  • The selector retains and compares only Cost. Compression ratio remains transient evidence consumed by SizeCost, not selector state.
  • Deferred callbacks no longer receive current-winner state or a ratio threshold. Delta and Sequence finish evaluation before the model assigns cost; model-aware pruning is a follow-up once a non-size model defines the required lower-bound contract.
  • This is a breaking scheme-facing API change: expected_compression_ratio, CompressionEstimate, EstimateVerdict, DeferredEstimate, and EstimateFn are replaced by the candidate-evaluation API.
  • No model-driven pruning, Delta policy relocation, or builder plumbing in this PR.

Track B: measure before designing the execution-time follow-ups

• Root-forcing decision-regret harness:
  • Force the root scheme while retaining the normal descendant scheme pool.
  • Measure {bytes, decode ns, filtered-scan ns, take ns} for complete produced trees.
  • Report this initially as root-family regret, not a full encoding-tree oracle.
• Missing per-encoding decode benches (ALP decode, dict gather, delta, pco/zstd).
• cargo xtask calibrate: emit a machine-readable DecodeCostTable, checking in defaults for one architecture class.
• Un-gate the compression micro-benches from the codspeed exclusion.
• Private sequential-scan cost-model spike.
• Stop/go checkpoint: evaluate the regret numbers and prototype accuracy, then record the outcome here.

Track C: the payoff (gated on the checkpoint)

• Sequential-scan objective + scan_speed(bandwidth) preset.
• Capability-aware and random-access objectives.
• gpu_decode, point_lookup, and query presets.
• Builder, file-writer, Python, DuckDB, and DataFusion plumbing.
• Per-column workload profiles.
• Documentation and public API stabilization.

Superseded drafts

• Generalize the deferred-estimation early-exit to the cost model #8699 — deferred pruning will be redesigned after a real non-size model establishes the required lower-bound contract.
• Relocate Delta's selection policy into cost-model priors; plumb the model through the builders #8700 — Delta policy relocation and builder plumbing are postponed until the base interface and policy-composition semantics are settled.

Separate issues

Zero-byte sampled outputs are part of the broader zero-tuple representation problem tracked in #7268. This work preserves the compressor's current treatment of that case; resolving it is not a prerequisite or part of this tracking issue.

Unresolved questions

• Should the default ever move off max_ratio (e.g. to scan_speed(NVMe) if most Vortex reads are NVMe-local)? This is a product decision that the regret harness should inform. There is no default flip anywhere in this plan.
• Where does dictionary policy live? The writer's DictStrategy decides integer dict encoding above the compressor, so the model cannot reach the most workload-sensitive encoding decision. I think the answer is that DictStrategy eventually consults the cost model, but that is deliberately a follow-up, not part of the initial extraction.
• Per-chunk decisions can flap between encodings across chunks of the same column, which execution pays for and no per-leaf model can see. We punt on this by design, but the regret harness records flap counts so a future sticky-choice layer has evidence.
• Which selection paths must eventually participate in a non-size objective (AlwaysUse, extension-vs-storage selection, stats compression)?
• What session/capability context must a future execution-time model receive?
• How should btrblocks-specific compatibility policy, such as Delta's current handicap, compose with a replaceable objective?
• OnPair's dictionary training is nondeterministic run-to-run (surfaced by the golden suite in Add golden-corpus determinism tests for the default compressor #8697, which had to exclude it). This is a pre-existing bug and needs its own issue.

Implementation history

• Add golden-corpus determinism tests for the default compressor #8697
• Extract scheme-selection policy into a pluggable CostModel #8698
• Generalize the deferred-estimation early-exit to the cost model #8699 (superseded draft)
• Relocate Delta's selection policy into cost-model priors; plumb the model through the builders #8700 (superseded draft)

[connortsui20]

I think that is a good point, though because this is very experimental I think that we should focus on purely the static information we have available before trying to make use of online / runtime behavior. The purpose of this feature is to make this possible in the first place rather than find an optimal solution for compression.