Default block_size for StringViewArray

[XiangpengHao]

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

Related to apache/datafusion#10918 and #5374

Current default block size (i.e., buffer capacity) is 8KB, it is a reasonable initial value -- we only waste up to 8KB of data.

However, it is not great for large StringViewArrays. With default 8KB block size , 4GB of strings will require half a million buffers, causing a significant slowdown even for APIs like get_array_memory_size

We want to have a small number of buffers for the following reasons: (1) faster buffer lookup due to better Vec<Buffer> locality, and (2) faster concatenation. Query engines (e.g., DataFusion) often need to concatenate multiple batches, which needs to concatenate two Vec<Buffer> into a new one. Smaller Vec<Buffer>s has better concat performance.

Describe the solution you'd like

(Simple) Change the default block size to 2MB. 2MB is the default size of huge page in many systems, and I believe 2MB is a reasonable choice. The drawback is that we may waste up to 2MB of memory for small arrays, which can be fixed using the method below.

(Advanced) Exponential increase until we hit 2MB. 4KB -> 8KB -> 16KB -> .. -> 512 KB -> 1MB -> 2MB -> ... -> 2MB -> 2MB

Describe alternatives you've considered

We currently allow user to provide a block size when building the string view array. However, the implication of this block size is not straightforward and can take quite a lot of efforts to understand, and the user don't even know the default size without looking at the source code.
I can expect the users of StringViewArray easily run into performance issues because of this non-trivial reason (like what I had run into)

Additional context

[alamb]

I recommend:

1. We document some of the nuances with block size
2. We add an API that lets the user pick between the simple / advanced strategy (as any particular API is unlikely to be optimal for the reasons you mention)

For example, perhaps something like

enum GrowthStrategy {
  /// New buffers are allocated with the specified size, in bytes
  Fixed(usize),
  /// New buffers are allocated expotentially in size, until the max is hit
  /// For example, starting with 8K buffers, with a max of 2MB
  /// would allocate 8K -> 16K -> .... 2MB
  Exponential {
    starting_size: usize,
    max_size: usize 
  }
  // and you can imagine more sophisticated strategies eventually like UserDefined or something
}

impl StringViewBuilder {
  /// specify the growth strategy for buffers in this buffer
  fn with_buffer_allocation(mut self, strategy: GrowthStrategy) {
...
  }
}
...

I wonder if @a10y @ariesdevil or others have any thoughts 🤔

[XiangpengHao]

Take, as I have convinced myself that current default value is really not good for query engines. Fixing this will make sure users of StringViewArray won't fall into these kind of performance issues

[alamb]

label_issue.py automatically added labels {'arrow'} from #6154