Repository navigation
Description
Is your feature request related to a problem or challenge? Please describe what you are trying to do.
Upstream in DataFusion, there is a common common pattern where we have multiple input RecordBatches and want to produce an output RecordBatch with some subset of the rows from the input batches. This happens in
FilterExec-->CoalesceBatchesExecwhen filteringRepartitionExec-->CoalesceBatchesExec
The kernels used here are:
FilterExecusesfilter, takes a single inputArrayand produces a single outputArrayRepartitionExecusestake, which also takes a single inputArrayand produces a single outputArray``RepartitionExeceach take a single input batch and produce a single outputArrayCoalesceBatchesExeccallsconcatwhich takes multple Arrays and produces a single Array as output
The use of these kernels and patterns has two downsides:
- Performance overhead due to a second copy: Calling
filter/takeimmediately copies the data, which is copied again inCoalesceBatches(see illustration below) - Memory Overhead / Performance Overhead for GarbageCollecting StringView: Buffering up several
RecordBatches with StringView may consume significant amounts of memory for mostly filtered rows, which requires us to run gc periodically which actually slows some things down (see Reduce copying inCoalesceBatchesExecfor StringViews datafusion#11628)
Here is an ascii art picture (from apache/datafusion#7957) that shows the extra copy in action
┌────────────────────┐ Filter
│ │ ┌────────────────────┐ Coalesce
│ │ ─ ─ ─ ─ ─ ─ ▶ │ RecordBatch │ Batches
│ RecordBatch │ │ num_rows = 234 │─ ─ ─ ─ ─ ┐
│ num_rows = 8000 │ └────────────────────┘
│ │ │
│ │ ┌────────────────────┐
└────────────────────┘ │ │ │
┌────────────────────┐ ┌────────────────────┐ │ │
│ │ Filter │ │ │ │ │
│ │ │ RecordBatch │ ─ ─ ─ ─ ─ ▶│ │
│ RecordBatch │ ─ ─ ─ ─ ─ ─ ▶ │ num_rows = 500 │─ ─ ─ ─ ─ ┐ │ │
│ num_rows = 8000 │ │ │ │ RecordBatch │
│ │ │ │ └ ─ ─ ─ ─ ─▶│ num_rows = 8000 │
│ │ └────────────────────┘ │ │
└────────────────────┘ │ │
... ─ ─ ─ ─ ─ ▶│ │
... ... │ │ │
│ │
┌────────────────────┐ │ └────────────────────┘
│ │ ┌────────────────────┐
│ │ Filter │ │ │
│ RecordBatch │ │ RecordBatch │
│ num_rows = 8000 │ ─ ─ ─ ─ ─ ─ ▶ │ num_rows = 333 │─ ─ ─ ─ ─ ┘
│ │ │ │
│ │ └────────────────────┘
└────────────────────┘
FilterExec RepartitonExec copies the data
creates output batches with copies *again* to form final large
of the matching rows (calls take() RecordBatches
to make a copy)
Describe the solution you'd like
I would like to apply filter/take to each incoming RecordBatch as it arrives, copying the data to an in progress output array, in a way that is as fast as the filter and take operations. This would reduce the extra copy that is currently required.
Note this is somewhat like the interleave kernel, except that
- We only need the output rows to be in the same order as the input batches (so the second
usizebatch index is not needed) - We don't want to have to buffer all the input
Describe alternatives you've considered
One thing I have thought about is extending the builders so they can append more than one row at a time. For example:
Builder::append_filteredBuilder::append_take
So for example, to filter a stream of StringViewArrays I might do something like;
let mut builder = StringViewBuilder::new();
while let Some(input) = stream.next() {
// compute some subset of input rows that make it to the output
let filter: BooleanArray = compute_filter(&input, ....);
// append all rows from input where filter[i] is true
builder.append_filtered(&input, &filter);
}And also add an equivalent for append_take
I think if we did this right, it wouldn't be a lot of new code, we could just refactor the existing filter/take implementations. For example, I would expect that the filter kernel would then devolve into something like
fn filter(..) {
match data_type {
DataType::Int8 => Int8Builder::with_capacity(...)
.append_filter(input, filter)
.build()
...
}Additional context
Activity
[-]Optimize take/filter from multiple input arrays to a single output array[/-][+]Optimize take/filter from multiple input arrays to a single large output array[/+]alamb commentedon Nov 5, 2024
FYI
devanbenz commentedon Nov 7, 2024
@alamb just to clarify your idea is to modify the existing
take&filterkernels. Not create a new one right?jayzhan211 commentedon Nov 7, 2024
If creating a new one helps, no reason not to do it.
tustvold commentedon Nov 7, 2024
I think the idea is sound in principle, but needs a concrete API proposal.
I'm not sure the proposed builder API makes sense, as the typing for nested types like ListBuilder and DictionaryBuilder is not what we want here, and they can't easily be type erased. We also ideally want to avoid overly bloating the arrow-array crate with kernel logic. This isn't even touching on the fact these kernels don't use the builders for performance reasons.
I think we'd need to introduce a new type-erased MutableArray abstraction or something, potentially replacing the rather problematic MutableArrayData.
The only remaining challenge concerns dictionaries, as the output dictionary needs to be computed up front. Simply not supporting dictonaries could potentially be a valid workaround though.
jayzhan211 commentedon Nov 7, 2024
Not sure about other type but for StringView, I can only think of iterating all the filtered row and
append_valueone by one. If there is no further optimization we can do, I think we can implement the append logic in datafusiondevanbenz commentedon Nov 7, 2024
'append_value' does a copy though. Wouldn't that effectively still be a large amount of copies?
jayzhan211 commentedon Nov 7, 2024
With this approach, we reduce the copying to a single step. Compared to the current approach, where copying happens in multiple stages (filtering, garbage collection, and coalescing), my proposal combines these steps into one. While benchmarks are needed to confirm any performance gains, this method should, at the very least, not perform worse than the existing one
devanbenz commentedon Nov 7, 2024
That makes sense. This would be a change downstream within Datafusion then correct?
jayzhan211 commentedon Nov 7, 2024
yes, you can work on it if you want to
alamb commentedon Nov 7, 2024
So it sounds like the consensus is to work out how this might look downstream in DataFusion (maybe starting with StringView as that is what is giving us the most trouble now) and then use some of that knowledge to propose something upstream in Arrow -- sounds like a good idea to me
alamb commentedon Nov 7, 2024
@jayzhan211 yes I think this is effectively what would happen -- however the actual iteration over filtered values is quite optimized in the
filterkernel (checkout what the FilterBuilder does) based on how many values are filtered and other aspectThe fact that
filteris so fast in arrow means it is quite hard to get as good / faster :)alamb commentedon Nov 7, 2024
@tustvold
This is reasonable -- though I could imagine adding type erased builders like
DynListBuilderfor this usecaseIs there some fundamental reason the builders can't made faster? If we could make the builders fast enough to use for filter that would seem to be valuable in its own right. But I am likely just dreaming here
A builder based approach could help (e.g. optimize for the case where the input batches had the same dictionary and handle the case where they didn't -- either via deferred computation or on the fly or something else)
Rachelint commentedon Nov 7, 2024
Does approach seems like that for filter?
input arrayandinput predicatetrueininput predicate), andappend_valueto the builderAnd at least, we can avoid generate multiple small batches, and concat them(a ton of copies) when big enough.
9 remaining items
alamb commentedon Mar 20, 2025
I agree
Does that mean you have an implementation that you could potentially share / contribute?
ctsk commentedon Mar 24, 2025
I've opened draft PRs for the changes in arrow (#7325) and in datafusion (apache/datafusion#15392).
In arrow, I added a "take_in" kernel, that takes an array, indices and a builder, then appends the elements of
arrayat indicesindicesto the given builder. I also added aRecordBatchBuilderthat holds a collection ofArrayBuildersfor convenience (Similar to how a RecordBatch holds a collection of Arrays).In datafusion, I tried modifying the RepartitionExec to use this API. This meant
coalescestep closer to thetakestep: Currently, datafusion only coalesces after distributing the batch to the destination partition, to use this kind of API, we need to coalesce in each producing thread before distributingRecordBatchBuilderI suspect this currently fails to build due to the
chronoissue...alamb commentedon Mar 24, 2025
Thanks @ctsk -- this looks pretty sweet -- I will try and give it a careful look tomorrow
ctsk commentedon Apr 8, 2025
I've been contemplating how to best add an
appendingtake kernel and these my current thoughts:Coming from DataFusion...
Based on the experimental implementation of
take_in, I believe the interface needed for DataFusion's use case looks like this:ColumnSink maintains internal state, with
ColumnSink::takelogically appending the result of thetakeoperation to its internal state. A key property is that ColumnSink can output its state incrementally rather than requiring a single vector output. This makes ColumnSink at least as capable as DataFusion's current approach, as it can fall back to using the currenttakekernel and leave concatenation to aCoalesceBatchesExec.I believe this abstraction belongs to DataFusion rather than arrow-rs.
Allocation-minimal kernels in arrow-rs
Ideally, ColumnSink would produce perfectly-sized batches of a given size, requiring it to control the destination area's sizing. This calls for a version of take that writes into a provided buffer. I propose:
The question is what type should replace
???. I've considered these options:Option 1:
Box<dyn ArrayBuilder>|&mut dyn ArrayBuilderThis was the starting point for this issue. ArrayBuilder is convenient because it already contains the appropriate data structures. While
PrimitiveArrayshold all state in the result array, forDictionaryArrays, we'd want the destination to hold a hash table that won't be in the finished array.The challenge with using ArrayBuilder is that builders don't sufficiently expose their internals for kernel implementations.
Potential approaches:
Expand the builder interface: Add methods giving callers more control over builder mutation. The challenge is finding reusable abstractions between builders, as well as balancing between
unsafemethods that might leave the builder in an inconsistent state and enforcing consistency after each manipulation.Deconstruction approach: Each builder would implement
into_partsandnew/new_unchecked, similar to what exists for Arrays. Kernels could arbitrarily mutate these buffers and then reconstruct the builder. This seems cleaner than expanding the builder interface further.The deconstruction approach has the drawback of requiring ownership of the builder, whereas a mutable reference would make more sense semantically.
Option 2:
&mut MutableArrayTaking the deconstruction approach further, we could introduce mutable counterparts (
MutablePrimitiveArray<T>, etc.) for each array type as the output ofinto_parts.We would add a type-erased MutableArray abstraction on top. This type would essentially hold the same state as a builder but could be more freely mutated without many consistency guarantees. Consistency would be checked when converting from MutableArray to Array.
Each concrete mutable array would expose methods to manipulate each of its fields, making its internal data and workings transparent.
The trait could be:
It wouldn't need common methods to manipulate the MutableArray since kernels would downcast it before manipulation. It could feature a method to modify the optional null buffer.
All names are subject to change
Thoughts?
tustvold commentedon Apr 8, 2025
Perhaps it might be worth thinking about what use-cases we're trying to improve with this effort, this will ensure we design something that adequately addresses that use-case?
If we're just talking about PrimitiveArray and StringViewArray types, then I suspect any performance delta is likely to be relatively minor as concatenating such arrays is already extremely cheap.
If, however, we're looking to improve the performance of DictionaryArray, this becomes a whole different can of worms as any append-based interface is likely to struggle to efficiently handle arrays with heterogeneous dictionary values. I'm not sure if there is a good solution here tbh.
The only array types where I could see such an append interface potentially having compelling performance benefits are (Large)StringArray, as it would allow eliding potentially large string copies. That being said this would be reliant on knowing the expected amount of string data up-front, which an append interface won't necessarily know, and use-cases should probably just use StringViewArray...
The initial issue also stated
But I am honestly not entirely sure how an append interface really changes this, you need to perform some sort of GC at some point, it is unclear to me why doing it as part of a Coalesce operation or as part of the filter itself would behave materially differently...
Edit: In fact it looks like @jayzhan211 tried this and confirmed it didn't make much difference - #6692 (comment)
alamb commentedon Apr 8, 2025
The core usecase is my mind is to save a copy (and associated allocation overheads, etc) when building up an output array from subsets of multiple input arrays.
Today this operation requires using a two step process with two kernels:
filterortake--> intermediate and thenconcatto form the outputIn certain queries in DataFusion this copying show up in profiles. For example, it appears in queries with relatively unselective filters that involve Strings, such as these clickbench queries where the predicate
SearchPhrase <> ''passes the long strings through.Example
The theory is that by eliminating the intermediate copy and build the desired output array directly we will improve performance
The same pattern also happens when repartitioning high cardinality aggregates (again on Strings)
alamb commentedon Apr 8, 2025
I still don't understand why extending the ArrayBuilders with "native" support for appending filtered/take output isn't a viable solution, such as:
This is exactly why I am suggesting the filter/take thing in the ArrayBuilder itself -- where the low level details of the source/target arrays can be used.
If the concern is that adding filter/take code in the
arrow-arraymodule woud increase code bloat too much I am sure we could sort that out somehow.alamb commentedon Apr 8, 2025
Maybe to @tustvold 's point, someone can start the project by implementing some benchmarks illustrating what we are trying to do:
Then we can properly consider how to make new APIs faster
tustvold commentedon Apr 8, 2025
Is this using StringViewArray or StringArray? I can see there being potential benefits for the latter, but then I wonder if it is worthwhile expending effort on an array type we are trying to move away from...
It is viable, but isn't trivial (especially for dictionaries or nested arrays) and it isn't clear at least to me why it would make all that much of a performance difference for anything other than StringArray
alamb commentedon Apr 8, 2025
It was both as I recall, but it probably bears double checking.
[-]Optimize take/filter from multiple input arrays to a single large output array[/-][+]Optimize take/filter/concat from multiple input arrays to a single large output array[/+]alamb commentedon May 20, 2025
I have been playing around with various options for this feature in the context of #7456 where I want to save the results of applying a filter with minimal buffering
We already have the
concatmethod on some buildersSeveral of the array builders already have a
append_arrayfunctionAdding some new
concat_arraymethods for other builders seems reasonable and follows the existing patterns in this crateCould expose the contents of
takeandfilteras extension traits onBuildersI was thinking we could potentially add new
filtermethods on the builders using the same implementations as the filter kernelI think we could likely the refactor the filter kernels to potentially use that trait internally.
The same thing can be done for
takeI plan to try prototyping it to see if it makes a difference in the context of
zhuqi-lucas commentedon May 22, 2025
Great idea @alamb , looking forward the prototype!
If i make sense right, it means we can only pass original array, and append filter. And finally we will only apply once using the original array and the filter. Very interesting!
Add `coalesce` kernel and`BatchCoalescer` for statefully combining se…
alamb commentedon Jun 24, 2025
An update here:
BatchCoalescer): Addcoalescekernel andBatchCoalescerfor statefully combining selected b…atches: #7597coalesecekernel (BatchCoalescer) #7761