Skip to content

Compress fixed-size lists without their null rows - #10425

Merged
robert3005 merged 3 commits into
developfrom
rk/compress-fsl-validity
Nov 9, 2026
Merged

robert3005 merged 3 commits into
developfrom
rk/compress-fsl-validity

Conversation

@robert3005

@robert3005 robert3005 commented Oct 10, 2026 •

Copy link
Copy Markdown
Contributor

Add SparseScheme for FixedSizedList. Instead of compressing just the elements we attempt compressing whole lists using SparseArray

Readers need no changes, because Sparse already canonicalizes fixed-size lists.

On the data from #10417:

Before After
Mostly-null file (1 row in 20 valid) 25,296 B 9,056 B
Rewrite of both files 292,808 B 190,768 B

@codspeed

codspeed Bot commented Oct 10, 2026 •

Copy link
Copy Markdown

Merging this PR will not alter performance

2 warnings

⚠️ Walltime results may be unreliable

Some benchmarks used the Walltime instrument outside CodSpeed Macro Runners, which can make the results inconsistent.

Learn more about Macro Runners

See affected benchmarks

⚠️ 1 benchmark is dominated by system calls

System calls cannot be simulated consistently and are left out of the measure. The reported value understates the real cost. Switch to the Walltime instrument to measure them.

Learn more about system calls

See affected benchmarks

✅ 1916 untouched benchmarks
⏩ 48 skipped benchmarks1


Comparing rk/compress-fsl-validity (d9c26d9) with develop (a1fbac6)

Open in CodSpeed

Footnotes

  1. 48 benchmarks were skipped, so the baseline results were used instead. If they were deleted from the codebase, click here and archive them to remove them from the performance reports. ↩

@robert3005
robert3005 force-pushed the rk/compress-explicit-fallback branch from c3ad942 to 8d11832 Compare October 19, 2026 18:08
Base automatically changed from rk/compress-explicit-fallback to develop October 19, 2026 18:16
@robert3005
robert3005 force-pushed the rk/compress-fsl-validity branch from c05ea8e to 24e77ed Compare October 19, 2026 20:28
@myrrc myrrc added the action/bench-all Runs all CPU benchmarks. Do not combine with other benchmark labels; GPU is the only exception. label Oct 28, 2026
@robert3005
robert3005 force-pushed the rk/compress-fsl-validity branch from 24e77ed to 8e2e106 Compare November 8, 2026 00:17
A fixed-size list stores `list_size` elements for every row, null or not, and
the compressor only ever compressed those elements, so it had to encode
whatever sits under the null rows. A UUID column that is mostly null was
compressed as dense bytes unless the elements happened to be 90% zeros, and
once mixed with a dense chunk not at all.

The compressor now offers fixed-size lists to schemes before compressing their
elements, after canonicalizing the elements so a scheme's output is compared
against the list's real size. The new `FixedSizeListSparseScheme` estimates the
saving of storing only the valid rows plus their bit-packed positions, and
when it is at least 10% encodes the list as `Sparse` with a null fill, its
values being the valid rows compressed recursively.

On the data from #10417, the mostly-null file shrinks from 25,296 to 9,056
bytes and the rewrite of both files from 292,808 to 190,768 bytes.

Claude-Session: https://claude.ai/code/session_015XzXtnsrnEsBNVa9R2VqKQ

Signed-off-by: Robert Kruszewski <[email protected]>
@robert3005
robert3005 force-pushed the rk/compress-fsl-validity branch from 94a3fb0 to d9c26d9 Compare November 9, 2026 19:39
@robert3005
robert3005 enabled auto-merge (squash) November 9, 2026 19:39
@robert3005
robert3005 merged commit 2e1b05b into develop Nov 9, 2026
71 checks passed
@robert3005
robert3005 deleted the rk/compress-fsl-validity branch November 9, 2026 19:49
0ax1 added a commit that referenced this pull request Nov 10, 2026
…eset (#10917)

## Summary

- Tracking Issue: #10914
- Depends on #10915 and #10916; this branch contains both. The diff of
its own is one line plus a test.

`CompressionMode::Cuda` excludes `StringDictScheme`, but
`execute_dict_varbinview` already decodes string dictionaries on the
GPU. Keeping the scheme makes GPU-mode files 16.0% smaller across
compress-bench's 17-dataset GPU suite (3,351.3 → 2,813.9 MB).
Per-dataset gains: CMSprovider 45.7%, Food 52.9%, HashTags 33.2%, both
TPC-H l_comment variants 12.2%, Euro2016 10.7%. The issue has the full
table.

## Changes

- `vortex-btrblocks/src/builder.rs`: drops `StringDictScheme` from the
Cuda exclusions and updates the comment. A new test checks that the
preset keeps string dictionaries but not binary ones. This is the only
change to CPU-compressor code.

Evidence with this branch (A40, CUDA 13.0):
- `--gpu-verify` passes on all 17 datasets. develop plus only this line
fails 5: taxi, CMSprovider, Euro2016, Food, HashTags.
- The CPU-fallback census is identical to develop's: 59 constant-array
fallbacks, none from dictionaries.
- The dictionary gather takes at most 6.1% of decode time and reaches
62-85% of the measured 563 GB/s.
- `vortex-cuda` lib suite on this branch: 723 passed, 0 failed.
- `compress_gpu` fuzz (CI flags, ASAN): 100,000 runs in 256 s, 0
crashes.

## Benchmarks

Setup:
- `compress-bench --gpu-decompress --iterations 5`, a fresh process per
run, `taskset -c 2-7`, 3 ABBA rounds.
- Speedup = develop time / branch time.
- The same-design A/A floor is 0.14 in |log|, so a "faster" claim needs
a 95% CI above 1 and a speedup above 1.32×.

| Dataset | File MB, develop → branch | Speedup [95% CI] | |
|---|---|---:|---|
| Food | 84.7 → 39.9 | 1.55× [1.41, 1.71] | faster |
| CMSprovider | 771.0 → 418.5 | 1.37× [0.66, 2.86] | within noise |
| Euro2016 | 163.3 → 145.9 | 1.46× [0.92, 2.32] | within noise |
| TPC-H l_comment chunked | 169.6 → 148.8 | 1.36× [0.55, 3.34] | within
noise |
| taxi | 52.0 → 51.5 | 1.28× [0.32, 5.11] | within noise |
| HashTags | 235.2 → 157.0 | 1.22× [0.89, 1.69] | within noise |
| TPC-H l_comment canonical | 169.6 → 148.8 | 1.18× [0.71, 1.96] |
within noise |
| Arade | 144.2 → 141.7 | 1.05× [0.42, 2.68] | within noise |

The nine datasets whose files don't change got one AB/BA round each.
Eight came out at 1.01-1.18×, and one (wide table cols=1000 chunks=50)
at 0.91×, inside the A/A floor. The measurements are from an A40
(GA102); the repo's GPU benchmarks run on A10G.

## API changes

`only_cuda_compatible()`, and therefore `cuda_write_strategy`, can now
emit string dictionaries.
- An `ArrowDeviceArrayStream` with the default
`DictionaryExport::Preserve` rejects a batch whose Arrow schema differs
from the first.
- With this change, 6 of CMSprovider's 14 string columns mix dictionary
and constant chunks.
- Today's Cuda files already do this in numeric columns: 7 of taxi's 18
numeric columns and 5 of CMSprovider's 12.
- Streams with `DictionaryExport::Decode`, which the FFI scan uses, are
unaffected.

Overlap: #10425 adds a line next to the removed one, so whichever merges
second needs a one-line rebase. #9762 changes dictionary selection, so
the sizes are as of a59294e.

## AI assistance

Developed with Claude Code (Claude Opus 5.5), which wrote most of the
code, tests and this description under my direction. I reviewed the diff
and the measurements.

🤖 Generated with [Claude Code](https://claude.com/claude-code)

---------

Signed-off-by: Tanish Gudise <[email protected]>
Co-authored-by: Claude Opus 5.5 <[email protected]>
Co-authored-by: Alexander Droste <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

action/bench-all Runs all CPU benchmarks. Do not combine with other benchmark labels; GPU is the only exception. changelog/feature A new feature

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants