Repository navigation
Description
This epic is for making improvements to our compressor (including our default compressor, which is just all of our encodings/schemes + our sampling compressor).
Status
Proposed.
We know that we want to improve this but it is not super clear what are the most meaningful changes we can make right now.
Motivation
We made several large structural changes to the compressor (tracked in #7216), which both made the sampling compressor pluggable and also made observability into what the compressor is doing easier (perfetto tracing and a clearer sampling algorithm).
Those improvements gave a few insights in different ways we could optimize the compressor, but it is unclear the degree to which those improvements would help.
Below are a list of ideas that I have that I think could be improvements to the compressor, in no particular order.
TODO make subissues for these things
- Scheme priorities (i.e., trying one scheme before another)
- More exclusion rules (with more formal proofs on why they are correct)
- Hardcode
DictSchemelogic into the compressor? (likely more controversial...) - Unify stats with the rest of Vortex (aggregates)
- Do stats collection in a single pass (is this even possible?)
- Fine-grained stats collection. Not all schemes need all stats, we can be even more lazy with stats generation.
- Some scheme estimation has to compress the entire array to see if it makes sense (like
SequenceScheme, but then we throw away the entire array and recompress later. That can definitely be fixed. - Replace hardcoded
MAX_CASCADE = 3with adaptive cascading that leverages the exclusion-bounded search tree (this is a stretch goal as the search space is potentially exponential) - Unify stats (this is likely linked to a much larger change)
Unresolved questions
- Should
MAX_CASCADEbe replaced with an adaptive search strategy now that the exclusion system bounds the search space? - Is there a way we can improve FSST scheme estimation and compression? We currently sample for FSST compression every time, which is super expensive. But I tried being smarter with FSST estimation (try to not sample every single time and predict when FSST is good) but that basically only caused regressions (see Potentially better FSST estimation #7611). It is unclear to me if there is a better way to quickly check if FSST is good for the whole array.
- Because we sample to 1024 values, it is possible for null-dominated sparse arrays to cause sampling to return 0 non-null values, which means the sampled compression ratio is technically infinite. This is obviously wrong, and it is extra wrong because the sampler will assume the entire array is all-null, which we check far in advance. It is unclear what the best solution to this is, see Sampling somehow compresses into 0 bytes #7268.
Activity
[-]Tracking Issue: Compressor Optimizations[/-][+]Tracking Issue: Compressor Improvements[/+]Schemes #8434[-]Tracking Issue: Compressor Improvements[/-][+]Epic: Compressor Improvements[/+]ConstantSchemelogic into the compressor #8666Add golden-corpus determinism tests for the default compressor (#8697)
Introduce crate-private Candidate bookkeeping in scheme selection
Add cost module: Cost, CostModel trait, and the SizeCost default
Introduce crate-private Candidate bookkeeping in scheme selection
Add cost module: Cost, CostModel trait, and the SizeCost default
Reorganize the compressor (#8745)
Extract scheme-selection policy into a pluggable CostModel
Extract scheme-selection policy into a pluggable CostModel
Extract scheme-selection policy into a pluggable CostModel
Extract scheme-selection policy into a pluggable CostModel
Extract scheme-selection policy into a pluggable CostModel