[QST] Invitation to provide feedback on New Parquet Encoding: Adaptive Lossless Floating Point Compression

[alamb]

👋 from the Parquet community

The Parquet community is working on a proposal to implement ALP: Adaptive Lossless floating-Point Compression, (SIGMOD 2024) as a new Parquet encoding

cuDF is listed on the Parquet Implementation Status page

Since you may feel pressure to implement newly added encodings, I think having your feedback on the spec as a stakeholder would be immensely valuable.

Also, I believe you can help us understand if the encoding can be efficiently implemented on GPUs, which is an important consideration

The proposed addition is here : Parquet ALP Encoding Specification (Google Doc)

There is also a prototype C++ implementation for review here

• GH-48701: [C++][Parquet] Add ALPpd encoding apache/arrow#48345

See also: mailing list discussion (link) and parquet-format PR

Thank you for your consideration

[alamb]

FYI @Matt711 @vyasr @rjzamora @quasiben @vuule and @jameslamb
(sorry for the direct pings, but I don't know how issues are treated in this repo, and you have merged PRs recently)

[vyasr]

Thanks for the heads-up! @mhaseeb123 and @vuule are probably our main experts on Parquet.

[mhaseeb123]

Thanks for opening this. I am going to study this and will provide my thoughts. Also CC'ing @pmattione-nvidia

[GregoryKimball]

Thank you @alamb for reaching out about the ALP encoding proposal. Based on an initial assessment, we expect that a GPU implementation of ALP decode would be reasonably efficient, similar to RLE and dictionary decode.

My understanding is that ALP is designed for each ~1024 elements to be decoded independently by a CPU thread. Decoding the 1024 elements would likely be too much work for a GPU thread, and ideally we want GPU threads in the same warp (group of 32 threads) working on adjacent bytes for the best memory access pattern. After discussing with @vuule, we expect to end up with one warp scanning all the page headers in a parquet column chunk, spinning off other warps to decode the ~1024 element vectors. Maybe the page headers would be better processed on host rather than device.

It seems GPU-friendly at the default vector size of 1024. I kicked off a few internal discussions to solicit more feedback. Thank you again for including us 💚

Update: there is a detailed reference here for us to consider. "G-ALP: Rethinking Light-weight Encodings for GPUs"
https://dl.acm.org/doi/10.1145/3736227.3736242. I see a reference in the "Improvements for a possible future version" of the proposal. We would ask for a more careful consideration of the layout for exceptions in the first version!

[alamb]

Thanks @GregoryKimball

Decoding the 1024 elements would likely be too much work for a GPU thread, and ideally we want GPU threads in the same warp (group of 32 threads) working on adjacent bytes for the best memory access pattern

One proposed way to handle this is by interleaving the bit packed values. One proposal for doing so is the so called "unified transposed layout" described in the "Fast Lanes" paper https://dl.acm.org/doi/10.14778/3598581.3598587 / https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf (many same authors of the ALP/G-ALP papers).

Note there are discussions on the parquet mailing list and spec doc that refer to "fast lanes bit packing" which is referring to this interleaving mechanism

Another item I have heard that could be improved for GPU efficiency is "exception handling" -- the current spec calls for storing exception indexes in a an array for each 1024 element vector -- so to decode each element the decoder has to first check if the element was an exception.

[eschmidt-nvidia]

Hi @alamb ,

I'm a lead author of nvCOMP, our GPU accelerated library for data compression. cuDF would implement ALP by calling nvCOMP APIs.

We're definitely interested in G-ALP support in the library.

From our perspective, at minimum G-ALP is needed over ALP to achieve good performance on GPU. If time allows, we would also like to collaborate with the G-ALP authors to improve the format even further. What timeline is the Parquet community considering for this adoption?

[alamb]

What timeline is the Parquet community considering for this adoption?

It is pretty close to being ready for voting -- I would say in the next month or two. If you want to influence the design now is the time.

It would be especially useful to provide help / undestanding about the transposed layout vs a non transposed layout -- the current proposal as of now does not have a transposed layout