Hi Andrew. After running some experiments I agree with you :). I've been trying to build a mental model of where these two actually diverge, so I put both on one code base and changed the settings between them one at a time over 30 string columns. Apart from the two differences you mentioned, I think a wider code space doesn't help by itself, it only pays off once the trainer has seen enough input to fill it, so code width looks to me like a consequence of the table selection rather than an independent choice. Swapping one search algorithm for the other moved size and decode very little in our runs, it mostly showed up in encode speed. What seems to dominate is something I hadn't been counting as a difference at all: how much of the column the writer reads before it picks symbols (all of my observations could be oversampling on the datasets I picked, but that's why I tried to select 30 datasets).
If that holds up, it makes me more optimistic about the single encoding you're describing, possibly with fewer knobs in the spec than I'd assumed. Code width and the symbol length cap have to be there since the decoder needs them, and the cap looked cheap enough that the spec could just pick one. The search algorithm and how much evidence the writer gathers before choosing symbols feel like the writer's business, and the decoder can't tell the difference either way. That would leave a writer free to trade compression against encode throughput without a format change. Wanted to capture this in a separate doc and not update the existing doc. Document <https://docs.google.com/document/d/1-rRJHFbZcF5ljqzOUXwzclj4sVfT8tzi/edit> : FSST vs OnPair. (numbers are in section "Per column, every configuration") Branch : https://github.com/apache/arrow/pull/50791 Best Prateek On Mon, Aug 3, 2026 at 2:27 AM Andrew Lamb <[email protected]> wrote: > Thanks Prateek, > > I also wanted to explicitly mention here on the mailing list again how > similar I think FSST and OnPair are in terms of encodings -- specifically > they both define symbol tables and then encode the text as sequences of > those symbols. The differences are > 1. the number of bits used to encode each symbol (8 vs up to 16) > 2. The algorithm used to select the tables > > In other words, I think we could add an encoding to Parquet that > encompasses both techniques > > Andrew > > On Mon, Aug 3, 2026 at 2:12 AM PRATEEK GAUR <[email protected]> wrote: > > > Hi team, > > > > I came across a recent string compression algorithm called OnPair and > spent > > some time experimenting with it as a Parquet encoding, benchmarked > against > > FSST, DELTA_LENGTH_BYTE_ARRAY, dictionary encoding, and the usual > > zstd/lz4/snappy page compression across 30 string corpora. > > > > Report > > < > https://docs.google.com/document/d/1cctFqNVh_Ul6huiXyMeFWNaGhZba0fMJ/edit > > > > > > > Short version: it trades encode speed for ratio and decode speed — it > > decodes faster than every compressed alternative measured and wins ratio > on > > most text-heavy columns, but its training pass makes encode substantially > > slower. > > > > Apologies in advance for slow replies — I'm travelling. > > > > Best > > Prateek > > >
