[Parquet] Prototype ALP encoding

[alamb]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

• part of [EPIC] [Parquet] Implement new Parquet encodings in arrow-rs #8747

The parquet community is considering adding new encodings to the format.

One proposed encoding is:

• ALP: Proposal: ALP : Floating Point Encoding for Parquet (mailing list thread)

Describe the solution you'd like

I would like someone(s) to create a branch of arrow-rs 's parquet reader and implement this proposed encoding in the context of parquet to see how it would work.

This would involve likely

1. Adding a new encoding to the metadata: source link
2. Add the appropriate encoder/decoders in parquet (existing code)
3. Add some basic tests showing data could be round tripped with these encodings: examples of similar tets here
4. Add some benchmarks: examples of similar benchmarks

Here are some existing crates

• https://crates.io/crates/alp
• https://crates.io/crates/vortex-alp (maybe this code)

Describe alternatives you've considered

Additional context

[alamb]

FYI @liamzwbao we were speaking about this

[alamb]

Here is a C/C++ implementation from @prtkgaur:

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

[alamb]

If anyone is interested, there is now a draft spec that we could try to implement

• [Proposal] Add ALP encoding support in parquet file format parquet-format#533

[alamb]

Update here is that the ALP spec is pretty close to being finalized in the C++ side - the current version of the spec is this document: https://docs.google.com/document/d/1xz2cudDpN2Y1ImFcTXh15s-3fPtD_aWt/edit (I haven't translated it into markdown yet)

I think this ticket is ready for someone to try and implement it in Rust

In parallel, we are also trying to get some example files to test with

As an aside, @julienledem noted in the Parquet sync call today that he had good luck with Claude code translating the C/C++ implementation and the spec into a working java implementation. Maybe we can use such an approach with the Rust implementation as well

[sdf-jkl]

I'd like to give this a go

[sdf-jkl]

take

[alamb]

BTW I started working on generating example Parquet files that are encoded using ALP using the C++ implementation. See here

• [WIP] CLI program to write ALP encode example parquet files arrow#49154

It doesn't have the entire setup, but this file should be enough to verify the plumbing is working:

single_f64_ALP.zip

To begin I suggest

1. Update to the thrift definitions (to include the new encoding value)
2. Add the ALP value to the encoding enum, and wire it up through the decoder (throw a Not implemented error when it gets to actually decoding the pages)

With that framework in place, we can begin working on the actual decoding algorithm