Optimize reading FixedSizeBinary arrays from parquet

[alamb]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
We have anecdotal evidence in DataFusion (see @samuelcolvin 's ticket apache/datafusion#11170) that reading 16 byte UUID values from Decimal128 is much faster than FixedSizeBinary, despite seemingly very little difference between the two

@appletreeisyellow found that most of the time is spent reading parquet: apache/datafusion#11170 (comment)

@etseidl also noted the slowness when working with FixedSizeBinary here #6159 (comment)

Describe the solution you'd like
Look into improving the parquet reader so reading FixedSizeBinary was faster

Describe alternatives you've considered

Additional context

[tustvold]

I think there might be some confusion here, apache/datafusion#11170 (comment) appears to be misreading of a profile.

Whereas #6159 (comment) concerns the non-arrow codepaths which are not optimised and perform an allocation for each value

[alamb]

I could definitely be confused -- is there any low hanging fruit left for reading FixedSizeBinary in the ArrowReader that you know of?

[tustvold]

Not that immediately springs to mind, but it has been almost 2 years so I could just have forgotten

[alamb]

It appears @etseidl is on the case #6220 #6222 🕵️

[tustvold]

Unless I'm mistaken those are PRs for the non-arrow reader and some newly added unreleased functionality

[etseidl]

Unless I'm mistaken those are PRs for the non-arrow reader and some newly added unreleased functionality

Correct, but #6222 is at least in the same module as this issue 😅. While I'm working on that I can take a look at the other decoders and see if there's any low hanging fruit (although tbh I'm not seeing any at the moment).

[etseidl]

It seems like the majority of time is spent converting FixedSizeBinary to other arrow types (most of the magic happens in collect). @tustvold left a TODO

arrow-rs/parquet/src/arrow/array_reader/fixed_len_byte_array.rs

Line 165 in 5c5a94a

// TODO: An improvement might be to do this conversion on read

for a possible improvement, but the conversion has to happen eventually, so I don't know if there's any more room for improvement.

[etseidl]

I did a quick test of FIXED_LEN_BYTE_ARRAY(16)/Decima128 vs unannotated FIXED_LEN_BYTE_ARRAY(16), and the latter was much faster.

arrow_array_reader/FIXED_LENGTH_BYTE_ARRAY/Decimal128Array/plain encoded, mandatory, no NULLs
                        time:   [1.0326 ms 1.0456 ms 1.0595 ms]

arrow_array_reader/FIXED_LENGTH_BYTE_ARRAY/FixedLen(16)Array/plain encoded, mandatory, no NULLs
                        time:   [110.30 µs 110.48 µs 110.67 µs]

I don't think FLBA decoding in the arrow reader is the culprit.

[etseidl]

Pardon a little more spam on this, but as I dig deeper into the FixedSizeBinaryArray->PrimitiveArray<T> transformation, one thing I noticed is that we're creating an iterator of Option<NativeType>, and passing that to from_iter

arrow-rs/arrow-array/src/array/primitive_array.rs

Line 1318 in a693f0f

fn from_iter<I: IntoIterator<Item = Ptr>>(iter: I) -> Self {

which iterates over the values, collecting them into a Buffer, while creating a null buffer as it goes. But in FixedLenByteArrayReader::consume_batch, we already have a null buffer in binary

arrow-rs/parquet/src/arrow/array_reader/fixed_len_byte_array.rs

Line 163 in a693f0f

let binary = FixedSizeBinaryArray::from(unsafe { array_data.build_unchecked() });

so it seems a waste to create one again.

I'm wondering if it would make sense here to (in the cases where we're converting from FixedSizeBinaryArray to PrimitiveArray<>) take the null buffer from binary, modify the iterator to return the native type rather than an Option, and create the PrimitiveArray from the iterator and the stolen null buffer. I've implemented a PoC that knocks off a good bit of time (1.0ms -> 740us for the FLBA/Decimal128 bench).

            ArrowType::Decimal128(p, s) => {
                let nb = binary.take_nulls();
                let decimal = binary
                    .iter()
                    .map(|o| match o {
                        Some(b) => i128::from_be_bytes(sign_extend_be(b)),
                        None => i128::default(),
                    });
                let decimal = Decimal128Array::from_iter_values_with_nulls(decimal, nb)
                    .with_precision_and_scale(*p, *s)?;
                Arc::new(decimal)
            }

Am I missing something subtle (not out of the question...this is my 5th attempt or so) that would break this? In particular, is it safe to assume the null buffer in binary would be the same as computed in from_iter()?
@tustvold @alamb

[tustvold]

It sounds plausible, but I've not spent much time with this code beyond what was necessary to allow ripping out the legacy ComplexObjectArrayReader, and that was almost 2 years ago. There is almost certainly some low hanging fruit when it comes to reading Decimal128Array and IntervalArray, that is part of why I was quite so confused to see this issue which suggests the opposite.

[etseidl]

Thanks. I'll clean up what I have and submit a PR in the next day or two then. I agree that the initial report was likely a misunderstanding.