[
https://issues.apache.org/jira/browse/ARROW-11030?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17256456#comment-17256456
]
Daniël Heres commented on ARROW-11030:
--------------------------------------
|So in summary, what looks like is the problem here: * for the left side of the
join we {{.iter()}} on the left side batches each iteration (a couple of times,
in the join implementation itself and in {{MutableDataArray}}) when we process
a probe-side batch.
* if we halve the batch size, the number of items in the build-side array
grows by two, but also the number of probe-side batches we process in the join,
thus the {{n*n}} slowdown.
I am not sure what way best to solve it. I think we have to have something for
the left-side batches so we can reuse a "prepared" structure which can be used
in O(1) time in build_batch_from_indices.
|
Delete branch
> [Rust] [DataFusion] HashJoinExec slow with many batches
> -------------------------------------------------------
>
> Key: ARROW-11030
> URL: https://issues.apache.org/jira/browse/ARROW-11030
> Project: Apache Arrow
> Issue Type: Bug
> Components: Rust - DataFusion
> Reporter: Andy Grove
> Priority: Major
> Fix For: 3.0.0
>
>
> Performance of joins slows down dramatically with smaller batches.
> The issue is related to slow performance of MutableDataArray::new() when
> passed a high number of batches. This happens when passing in all of the
> batches from the build side of the join and this happens once per build-side
> join key for each probe-side batch.
> It seems to get exponentially slower as the number of arrays increases even
> though the number of rows is the same.
> I modified hash_join.rs to have this debug code:
> {code:java}
> let start = Instant::now();
> let row_count: usize = arrays.iter().map(|arr| arr.len()).sum();
> let num_arrays = arrays.len();
> let mut mutable = MutableArrayData::new(arrays, true, capacity);
> if num_arrays > 0 {
> debug!("MutableArrayData::new() with {} arrays containing {} rows took {}
> ms", num_arrays, row_count, start.elapsed().as_millis());
> } {code}
> Batch size 131072:
> {code:java}
> MutableArrayData::new() with 4584 arrays containing 3115341 rows took 1 ms
> MutableArrayData::new() with 4584 arrays containing 3115341 rows took 1 ms
> MutableArrayData::new() with 4584 arrays containing 3115341 rows took 1 ms
> {code}
> Batch size 16384:
> {code:java}
> MutableArrayData::new() with 36624 arrays containing 3115341 rows took 19 ms
> MutableArrayData::new() with 36624 arrays containing 3115341 rows took 16 ms
> MutableArrayData::new() with 36624 arrays containing 3115341 rows took 17 ms
> {code}
> Batch size 4096:
> {code:java}
> MutableArrayData::new() with 146496 arrays containing 3115341 rows took 88 ms
> MutableArrayData::new() with 146496 arrays containing 3115341 rows took 89 ms
> MutableArrayData::new() with 146496 arrays containing 3115341 rows took 88 ms
> {code}
>
>
>
>
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
