[Parquet] Reduce reallocations when reading StringView in parquet

[alamb]

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

I am profiling clickbench query 10 with predicate pushdown enabled as part of

• Enable parquet filter pushdown (filter_pushdown) by default datafusion#3463

samply record -- /Users/andrewlamb/Software/datafusion2/target/profiling/datafusion-cli   -f q.sql  > /dev/null  2>&1

SELECT "MobilePhoneModel", COUNT(DISTINCT "UserID") AS u FROM hits WHERE "MobilePhoneModel" <> '' GROUP BY "MobilePhoneModel" ORDER BY u DESC LIMIT 10;

While looking at the profile, I noticed that 7% of the time is spent in allocating / regrowing vectors (aka reallocating and copying)

Describe the solution you'd like
Avoid the time spent regrowing these vectors

It appears that the vectors in question are part of the ViewBuffer struct:

arrow-rs/parquet/src/arrow/buffer/view_buffer.rs

Lines 30 to 33 in 02fa779

	pub struct ViewBuffer {
	pub views: Vec<u128>,
	pub buffers: Vec<Buffer>,
	}

Describe alternatives you've considered
Since we know how many views will be in each output buffer, we could create the ViewBuffers with the correct size initially

Something like like

ViewBuffers::with_capacity

Additional context

[alamb]

Here is one potential change:

diff --git a/parquet/src/arrow/array_reader/byte_view_array.rs b/parquet/src/arrow/array_reader/byte_view_array.rs
index f881690f805..71e517ffb61 100644
--- a/parquet/src/arrow/array_reader/byte_view_array.rs
+++ b/parquet/src/arrow/array_reader/byte_view_array.rs
@@ -162,11 +162,12 @@ impl ColumnValueDecoder for ByteViewArrayColumnValueDecoder {
             ));
         }

-        let mut buffer = ViewBuffer::default();
+        let num_values = num_values as usize;
+        let mut buffer = ViewBuffer::with_capacity(num_values);
         let mut decoder = ByteViewArrayDecoderPlain::new(
             buf,
-            num_values as usize,
-            Some(num_values as usize),
+            num_values,
+            Some(num_values),
             self.validate_utf8,
         );
         decoder.read(&mut buffer, usize::MAX)?;
diff --git a/parquet/src/arrow/buffer/view_buffer.rs b/parquet/src/arrow/buffer/view_buffer.rs
index 2802f97f8f3..fab5a2488b9 100644
--- a/parquet/src/arrow/buffer/view_buffer.rs
+++ b/parquet/src/arrow/buffer/view_buffer.rs
@@ -33,6 +33,14 @@ pub struct ViewBuffer {
 }

 impl ViewBuffer {
+    /// Create a new ViewBuffer with capacity for the specified number of views
+    pub fn with_capacity(capacity: usize) -> Self {
+        Self {
+            views: Vec::with_capacity(capacity),
+            buffers: Vec::new(),
+        }
+    }
+
     pub fn is_empty(&self) -> bool {
         self.views.is_empty()
     }
@@ -111,7 +119,6 @@ impl ValuesBuffer for ViewBuffer {

 #[cfg(test)]
 mod tests {
-
     use arrow_array::Array;

     use super::*;

There were several other places in the decoder where I wasn't sure if the reserve function was being called appropriately which should also be studied

[alamb]

I spent some time with @lyang24 working on this issue with #9093

I printed out the buffer capacity for reads. They are almost all 0 and the reader doesn't then reserve enough space

You can actually see most of the reads have an empty buffer

ewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
ByteViewArrayDecoder::read called with len 8192, current views capacity: 0
Read batch with 8192 rows and 105 columns
ByteViewArrayDecoder::read called with len 5120, current views capacity: 0
ByteViewArrayDecoder::read called with len 3072, current views capacity: 5120
ByteViewArrayDecoder::read called with len 6144, current views capacity: 0
ByteViewArrayDecoder::read called with len 2048, current views capacity: 6144

I tracked it down in a debugger and the default buffer is being created here:

https://github.com/apache/arrow-rs/blob/02fa779a9cb122c5218293be3afb980832701683/parquet/src/arrow/record_reader/mod.rs#L76-L75

ByteViewArrayDecoderPlain does reserve capacity https://github.com/apache/arrow-rs/blob/e2b2b8f5ec9ccf10bf7d584cf94e56018e2ac800/parquet/src/arrow/array_reader/byte_view_array.rs#L333-L332

However, ByteViewArrayDecoderDictionary::read does not seem to reserve capacity
https://github.com/apache/arrow-rs/blob/e2b2b8f5ec9ccf10bf7d584cf94e56018e2ac800/parquet/src/arrow/array_reader/byte_view_array.rs#L442-L441

Whole Test Program

use std::fs::File;
use std::io::{BufReader, Read};
use std::sync::Arc;
use arrow::datatypes::{DataType, Field, FieldRef, Schema};
use parquet::arrow::arrow_reader::{ArrowReaderOptions, ParquetRecordBatchReaderBuilder};
use bytes::Bytes;
use parquet::file::metadata::ParquetMetaDataReader;

fn main() {
    let file_name = "/Users/andrewlamb/Downloads/hits/hits_0.parquet";
    println!("Opening file: {file_name}", );
    let mut file = File::open(file_name).unwrap();
    let mut bytes = Vec::new();
    file.read_to_end(&mut bytes).unwrap();
    let bytes = Bytes::from(bytes);

    let schema = string_to_view_types(ParquetRecordBatchReaderBuilder::try_new(bytes.clone()).unwrap().schema());

    //println!("Schema: {:?}", schema);

    let options = ArrowReaderOptions::new()
        .with_schema(schema);
    let reader = ParquetRecordBatchReaderBuilder::try_new_with_options(bytes, options).unwrap()
        .with_batch_size(8192)
        .build().unwrap();

    for batch in reader {
        let batch = batch.unwrap();
        println!("Read batch with {} rows and {} columns", batch.num_rows(), batch.num_columns());
    }

    println!("Done");


}


// Hack because the clickbench files were written with the wrong logical type for strings
fn string_to_view_types(schema: &Arc<Schema>) -> Arc<Schema> {
    let fields: Vec<FieldRef> = schema
        .fields()
        .iter()
        .map(|field| {
            let existing_type = field.data_type();
            if existing_type == &DataType::Utf8 || existing_type == &DataType::Binary {
                Arc::new(Field::new(
                    field.name(),
                    DataType::Utf8View,
                    field.is_nullable(),
                ))
            } else {
                Arc::clone(field)
            }
        })
        .collect();
    Arc::new(Schema::new(fields))
}

[alamb]

I think we could probably sprinkly some "reserves" in there locally, but I think we can probably do much better if we reserve the correct capacity when creating the output buffers in the first place (as we know the (max) output size = batch_size)

i have some ideas on how to wire this in.

Basically, it will involve https://github.com/apache/arrow-rs/blob/9a1e8b572d11078e813fffe3d5c7106b6953d58c/parquet/src/arrow/record_reader/buffer.rs#L21-L20

Changing ValuesBuffer so that instead of

pub trait ValuesBuffer : default {
...
}

It must be explicitly created with capacity

pub trait ValuesBuffer {
  /// create a new buffer with an allocation  for `capacity` items
  fn new_with_capacity(capacity: usize) -> Self;
}

And then use the compiler to find all the relevant places and add the appropriate capacies

[lyang24]

I think we could probably sprinkly some "reserves" in there locally, but I think we can probably do much better if we reserve the correct capacity when creating the output buffers in the first place (as we know the (max) output size = batch_size)

i have some ideas on how to wire this in.

Basically, it will involve https://github.com/apache/arrow-rs/blob/9a1e8b572d11078e813fffe3d5c7106b6953d58c/parquet/src/arrow/record_reader/buffer.rs#L21-L20

Changing ValuesBuffer so that instead of

pub trait ValuesBuffer : default {
...
}
It must be explicitly created with capacity

pub trait ValuesBuffer {
/// create a new buffer with an allocation for capacity items
fn new_with_capacity(capacity: usize) -> Self;
}
And then use the compiler to find all the relevant places and add the appropriate capacies

Hi @alamb, its looks like the bench results are mixed

doing well with large scan (full table scan) querys

arrow_reader_clickbench/async/Q20 1.18 130.2±1.59ms ? ?/sec 1.00 110.7±0.82ms ? ?/sec
arrow_reader_clickbench/async/Q21 1.29 165.5±0.99ms ? ?/sec 1.00 128.6±0.93ms ? ?/sec
arrow_reader_clickbench/async/Q22 1.24 318.7±11.80ms ? ?/sec 1.00 257.3±6.26ms ? ?/sec
some regressions with high selectivity

arrow_reader_row_filter/int64 > 90/exclude_filter_column/async 1.00 2.6±0.02ms ? ?/sec 1.31 3.5±0.08ms ? ?/sec
arrow_reader_row_filter/int64 > 90/exclude_filter_column/sync 1.00 2.4±0.02ms ? ?/sec 1.35 3.2±0.03ms ? ?/sec
regression with - i am guessing preallocate large blocks messes up cpu cache?

arrow_array_reader/FIXED_LEN_BYTE_ARRAY/Float16Array/plain encoded, mandatory, no NULLs 1.00 75.9±0.46µs ? ?/sec 1.56 118.1±0.43µs ? ?/sec
arrow_array_reader/FIXED_LEN_BYTE_ARRAY/Float16Array/plain encoded, optional, half NULLs 1.00 232.7±2.34µs ? ?/sec 1.23 285.9±3.00µs ? ?/sec
arrow_array_reader/FIXED_LEN_BYTE_ARRAY/Float16Array/plain encoded, optional, no NULLs 1.00 80.8±0.46µs ? ?/sec 1.53 123.7±0.34µs ? ?/sec

is it possible do preallocate conditionally - skip preallocate for Plain numeric (Float16, Int32, Float64) types, if possible skip with high selectivity filters

[alamb]

n my mind, preallocating should never hurt -- and if the benchmarks show a regression it is either due to

1. Noise
2. Allocator ordering (not a real effect in my mind)
3. We are pre-allocating too much (e.g. an extra allocation at the end of the reader or something)

[Dandandan]

Allocating more elements than strictly necessary in might also hurt performance as subsequent operations will have worse locality so perhaps always reserving the batch size is not beneficial in all cases...

[Dandandan]

Looking a bit the code related to ViewBuffer / read methods I also see the pattern of pushing / appending elements element-by-element.

Converting it to use extend should also help here as it will not use the per-element capacity check / improve code output / can use the faster TrustedLen optimizations.

[Dandandan]

arrow_array_reader/StringViewArray/plain encoded, mandatory, no NULLs
                        time:   [213.83 µs 214.48 µs 215.21 µs]
                        change: [−4.4321% −4.1985% −3.9360%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  4 (4.00%) high mild
  4 (4.00%) high severe
arrow_array_reader/StringViewArray/plain encoded, optional, no NULLs
                        time:   [217.85 µs 218.37 µs 218.92 µs]
                        change: [−3.4934% −3.2692% −3.0797%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 16 outliers among 100 measurements (16.00%)
  3 (3.00%) low mild
  10 (10.00%) high mild
  3 (3.00%) high severe
arrow_array_reader/StringViewArray/plain encoded, optional, half NULLs
                        time:   [193.28 µs 195.83 µs 200.70 µs]
                        change: [−2.6488% −1.5565% +0.3592%] (p = 0.04 < 0.05)
                        Change within noise threshold.
Found 5 outliers among 100 measurements (5.00%)
  1 (1.00%) low mild
  3 (3.00%) high mild
  1 (1.00%) high severe
arrow_array_reader/StringViewArray/dictionary encoded, mandatory, no NULLs
                        time:   [157.27 µs 158.09 µs 158.76 µs]
                        change: [−21.737% −21.334% −20.984%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
  4 (4.00%) low severe
  4 (4.00%) low mild
  4 (4.00%) high mild
  2 (2.00%) high severe
arrow_array_reader/StringViewArray/dictionary encoded, optional, no NULLs
                        time:   [159.43 µs 159.68 µs 159.92 µs]
                        change: [−23.907% −21.932% −20.479%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 9 outliers among 100 measurements (9.00%)
  3 (3.00%) low mild
  4 (4.00%) high mild
  2 (2.00%) high severe
arrow_array_reader/StringViewArray/dictionary encoded, optional, half NULLs
                        time:   [170.78 µs 171.11 µs 171.54 µs]
                        change: [−10.570% −10.385% −10.165%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

This is what I could see in #9236

[Dandandan]

Can we check this again?
I believe #9236 did address this at least a bit.

[alamb]

I think this may help a bunch too from @lyang24

• [Parquet] perf: preallocate capacity for ArrayReaderBuilder #9093