Make StringViewArray::slice() and BinaryViewArray::slice() faster / non allocating

[alamb]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
While working on an upstream project apache/datafusion#12092 which switched DataFusion to use StringViewArray rather than StringArray

When I did, one of the queries got much slower.

Profiling revealed that the time difference was almost entirely explained by the time spent in StringViewArray::slice()

Here is the flamegraph with StringArray:

Here is the same query with StringViewArray:

I am pretty sure the additional time is due to the time spent allocating / copying / deallocating the Vecs of buffers here:

arrow-rs/arrow-array/src/array/byte_view_array.rs

Line 118 in 341ec35

buffers: Vec<Buffer>,

Where calling slice on a StringArray can be done with a few Arc increments.

arrow-rs/arrow-array/src/array/byte_array.rs

Lines 88 to 91 in 3490639

	data_type: DataType,
	value_offsets: OffsetBuffer<T::Offset>,
	value_data: Buffer,
	nulls: Option<NullBuffer>,

Describe the solution you'd like
I would like StringViewArray::slice to be faster (aka don't allocate)

Describe alternatives you've considered

We can (and probably should) change DataFusion not to use slice in this case (see apache/datafusion#6906, apache/datafusion#6906 (comment) specifically) but I think making slice faster / non allocating for StringViewArray will be useful in general

Additional context

[alamb]

fyi @a10y and @XiangpengHao

[alamb]

On solution here would be to replace Vec<Buffer> with Arc<[Buffer]> after construction -- that would make managing the buffers on slice extremely cheap

[XiangpengHao]

On solution here would be to replace Vec with Arc<[Buffer]> after construction

I agree, this should fix the problems. In fact, many other operations (e.g., take) also need to clone the Vec, changing to Arc<[Buffer]> will benefit them as well.

However, I would be a bit more careful about why cloning the buffer taking so long -- often indicating the Vec is large, which often means gc is not being called timely. So in addition to changing to Arc<[Buffer]>, I would also examine the plan to make sure gc (in CoalesceBatchesExec) is being invoked properly. cc @WetABQ who might be interested in this discussion.

I plan to work on this later this week but anyone else feel free to run faster than me!

[XiangpengHao]

replace Vec with Arc<[Buffer]> after construction -- that would make managing the buffers on slice extremely cheap

But that also means an extra indirection to read buffers, not sure if it matters

[Rachelint]

The slice maybe can't be eliminated until the epic apache/datafusion#7065 is finished...
Because it will still be called here https://github.com/apache/datafusion/blob/a08f923c2acb1a46614970231d9a672c36ce3ad2/datafusion/physical-plan/src/aggregates/row_hash.rs#L713

[alamb]

But that also means an extra indirection to read buffers, not sure if it matters

I think an Arc<Vec<Buffer>> would add another indirection. I was thinking/hoping that Arc<[Buffer]> would only still have one indirection

[alamb]

The slice maybe can't be eliminated until the epic apache/datafusion#7065 is finished...

FWIW the slice that I looked at in apache/datafusion#12092 (comment) is a different one:

https://github.com/apache/datafusion/blob/a08f923c2acb1a46614970231d9a672c36ce3ad2/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs#L435-L438

(This is called once for each distinct group in each batch being aggregates, which is quite bad -- the better way to solve this is to implement a Min/Max accumulator for strings that avoids slicing at all, which we are tracking in apache/datafusion#6906)

I think the fact that slice is used many different places makes it all the more important to optimize in arrow-rs

[alamb]

However, I would be a bit more careful about why cloning the buffer taking so long -- often indicating the Vec is large, which often means gc is not being called timely

This is a good point

[Rachelint]

The slice maybe can't be eliminated until the epic apache/datafusion#7065 is finished...

FWIW the slice that I looked at in apache/datafusion#12092 (comment) is a different one:

https://github.com/apache/datafusion/blob/a08f923c2acb1a46614970231d9a672c36ce3ad2/datafusion/functions-aggregate-common/src/aggregate/groups_accumulator.rs#L435-L438

(This is called once for each distinct group in each batch being aggregates, which is quite bad -- the better way to solve this is to implement a Min/Max accumulator for strings that avoids slicing at all, which we are tracking in apache/datafusion#6906)

I think the fact that slice is used many different places makes it all the more important to optimize in arrow-rs

Yes, maybe it should be ensured to be a cheap operations, it is used in many many places...

[ShiKaiWi]

@alamb @XiangpengHao Could assign this ticket to me? I guess I can make it after understanding the proposal in the discussion.

BTW, I find there is no benchmark case for the slice method, and I guess the benchmark case is necessary to prove the proposal implementation.

[XiangpengHao]

You can self assign by commenting "take"

I think adding benchmark is the right first step! Looking forward to it!

[alamb]

Tahank you @ShiKaiWi -- can't wait to check it out