Thanks Prateek, this is very interesting, having more number of encoding options would always be helpful for random access usecases. The FSST spec today allows multiple encodings, and the spec is aware of FSST8/FSST16. The symbol table generation is blackbox to the format, we can incorporate OnPair16 and make changes if required if we decide to go through FSST route. Either way, having OnPair as an option would be helpful, thanks for your efforts. (I had evaluated OnPair16 and FSST16 evaluation here [1])
Warm Regards, Arnav [1] https://docs.google.com/document/d/1Xg2b8HR19QnI3nhtQUDWZJhCLwJzW6y9tU1ziiLFZrM/edit?tab=t.0#heading=h.52l8mh2dqmg8 On Wed, Aug 5, 2026 at 3:23 PM Andrew Lamb <[email protected]> wrote: > > 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. > > I think that is a great way of putting it. > > I also expect significant research effort into symbol table construction > algorithms in the next year or two, so the writers could evolve and cater > to different usecases without any changes to the format > > Andrew > > On Tue, Aug 4, 2026 at 9:23 PM PRATEEK GAUR <[email protected]> wrote: > > > 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 > > > > > > > > > >
