You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "metesynnada (via GitHub)" <gi...@apache.org> on 2023/07/27 14:45:30 UTC
[GitHub] [arrow-datafusion] metesynnada opened a new issue, #7113: HashJoinExec output order is not correct
metesynnada opened a new issue, #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113
### Describe the bug
In the current implementation of `calculate_hash_join_output_order`, we operate under the assumption that the order of the build side is also preserved lexicographically.
For example, if the left side order is `a ASC` and the right side order is `b ASC`, the outcome was `b ASC, a ASC`.
However, changes to the join hash table implementation now mean that the order on the left side is maintained, but in reverse, as the chain pointer begins at the end and concludes at the start of the row indexes, i.e., `[5,4,3,2,1]`.
@Dandandan, I'm interested in your perspective on this. My inclination is that maintaining the order lexicographically could significantly benefit aggregations. Yet, I'm struggling to identify an obvious solution.
### To Reproduce
NA
### Expected behavior
NA
### Additional context
NA
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan commented on issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1658457735
Yeah, totally! Thanks @metesynnada
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan commented on issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1654252407
Something I was also considering before as optimization, which also will fix this is to end the build phase by copying the offsets over to a new (`ListArray` with u64 values) array that has the offsets pre-calculated for each index.
This will save some work during probing phase (if we have multiple values per unique key on the probe side) as we can copy the indices directly from the list array instead of traversing the chained list.
i.e. for 2 unique keys with 6 and 4 values the array will look like this:
```
offsets: [0, 5]
values: [1,2,5,6,7,8,0,3,4,9]
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] metesynnada commented on issue #7113: HashJoinExec output order is not correct
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1655137896
> Something I was also considering before as optimization, which also will fix this is to end the build phase by copying the offsets over to a new (`ListArray` with u64 values) array that has the offsets pre-calculated for each index.
>
> This will save some work during probing phase (if we have multiple values per unique key on the probe side) as we can copy the indices directly from the list array instead of traversing the chained list.
>
> e.g. for the build structure with 2 unique keys with 6 and 4 values the array will look like this:
>
> So the structure that looks like this (subtracted 1 to make it more clear)
>
> ```
> map:
> - hash: x, first: 8
> - hash: y, first: 9
>
> next: [END,1,END,0,3,2,5,6,7,4]
> ```
>
> can be converted to a list array with the following contents (by doing it for each index (0..N))
>
> ```
> offsets: [0, 5]
> values: [1,2,5,6,7,8,0,3,4,9]
> ```
>
> The benefit is (besides being in order) that instead of traversing it time after time in backwards order we can just copy the slice `1,2,5,6,7,8` or `0,3,4,9` into the target array :)
I think this is quite elegant. Does this converting process occur in every single probe?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] metesynnada commented on issue #7113: HashJoinExec output order is not correct
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1658429107
```┏━━━━━━━━━━━━━━┳━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┓
┃ Query ┃ main ┃ solve-hash-order ┃ Change ┃
┡━━━━━━━━━━━━━━╇━━━━━━━━━━━━━╇━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━┩
│ QQuery 1 │ 411.17ms │ 410.71ms │ no change │
│ QQuery 2 │ 68.87ms │ 69.94ms │ no change │
│ QQuery 3 │ 173.74ms │ 173.73ms │ no change │
│ QQuery 4 │ 109.44ms │ 111.52ms │ no change │
│ QQuery 5 │ 210.58ms │ 211.62ms │ no change │
│ QQuery 6 │ 109.10ms │ 109.40ms │ no change │
│ QQuery 7 │ 304.66ms │ 301.47ms │ no change │
│ QQuery 8 │ 249.95ms │ 249.18ms │ no change │
│ QQuery 9 │ 359.94ms │ 359.13ms │ no change │
│ QQuery 10 │ 290.14ms │ 287.78ms │ no change │
│ QQuery 11 │ 62.68ms │ 64.34ms │ no change │
│ QQuery 12 │ 205.89ms │ 207.75ms │ no change │
│ QQuery 13 │ 310.27ms │ 309.37ms │ no change │
│ QQuery 14 │ 149.65ms │ 150.51ms │ no change │
│ QQuery 15 │ 100.57ms │ 101.37ms │ no change │
│ QQuery 16 │ 73.91ms │ 73.71ms │ no change │
│ QQuery 17 │ 227.69ms │ 230.02ms │ no change │
│ QQuery 18 │ 488.88ms │ 487.13ms │ no change │
│ QQuery 19 │ 314.24ms │ 316.17ms │ no change │
│ QQuery 20 │ 165.74ms │ 168.86ms │ no change │
│ QQuery 21 │ 445.91ms │ 439.85ms │ no change │
│ QQuery 22 │ 76.71ms │ 74.62ms │ no change │
└──────────────┴─────────────┴──────────────────┴───────────┘
```
@Dandandan I think there is no performance penalty on this. I will be opening a PR for this if this is OK.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] alamb commented on issue #7113: HashJoinExec output order is not correct
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1654137280
FYI @Dandandan and @mingmwang
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan commented on issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1654214985
🤔 Maybe we can build the order in reverse (so the original) order instead.
Potentially could be faster too during probing as we can iterate the arrays in order.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] metesynnada commented on issue #7113: HashJoinExec output order is not correct
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1658340249
I am checking the performance of
```rust
for (row, hash_value) in hash_values.iter().enumerate().rev() {
// Get the hash and find it in the build index
// For every item on the build and probe we check if it matches
// This possibly contains rows with hash collisions,
// So we have to check here whether rows are equal or not
if let Some((_, index)) = build_hashmap
.map
.get(*hash_value, |(hash, _)| *hash_value == *hash)
{
let mut i = *index - 1;
loop {
build_indices.append(i);
probe_indices.append(row as u32);
// Follow the chain to get the next index value
let next = build_hashmap.next[i as usize];
if next == 0 {
// end of list
break;
}
i = next - 1;
}
}
}
build_indices.as_slice_mut().reverse();
probe_indices.as_slice_mut().reverse();
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan closed issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan closed issue #7113: HashJoinExec output order is not correct
URL: https://github.com/apache/arrow-datafusion/issues/7113
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan commented on issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1658320608
@metesynnada
I tried my own suggestion but so far did not recover the performance.
A simple solution might be just reversing the order of the candidate build/probe indices, which doesn't seem to give much difference in performance:
```
diff --git a/datafusion/core/src/physical_plan/joins/hash_join.rs b/datafusion/core/src/physical_plan/joins/hash_join.rs
index ce1d6dbcc..488af68c1 100644
--- a/datafusion/core/src/physical_plan/joins/hash_join.rs
+++ b/datafusion/core/src/physical_plan/joins/hash_join.rs
@@ -781,6 +781,8 @@ pub fn build_equal_condition_join_indices(
}
}
}
+ build_indices.as_slice_mut().reverse();
+ probe_indices.as_slice_mut().reverse();
let left: UInt64Array = PrimitiveArray::new(build_indices.finish().into(), None);
let right: UInt32Array = PrimitiveArray::new(probe_indices.finish().into(), None);
@@ -2757,12 +2759,12 @@ mod tests {
)?;
let mut left_ids = UInt64Builder::with_capacity(0);
- left_ids.append_value(0);
left_ids.append_value(1);
+ left_ids.append_value(0);
let mut right_ids = UInt32Builder::with_capacity(0);
- right_ids.append_value(0);
right_ids.append_value(1);
+ right_ids.append_value(0);
assert_eq!(left_ids.finish(), l);
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] Dandandan commented on issue #7113: HashJoinExec output order is not correct
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1655174851
> > Something I was also considering before as optimization, which also will fix this is to end the build phase by copying the offsets over to a new (`ListArray` with u64 values) array that has the offsets pre-calculated for each index.
> > This will save some work during probing phase (if we have multiple values per unique key on the probe side) as we can copy the indices directly from the list array instead of traversing the chained list.
> > e.g. for the build structure with 2 unique keys with 6 and 4 values the array will look like this:
> > So the structure that looks like this (subtracted 1 to make it more clear)
> > ```
> > map:
> > - hash: x, first: 8
> > - hash: y, first: 9
> >
> > next: [END,1,END,0,3,2,5,6,7,4]
> > ```
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > can be converted to a list array with the following contents (by doing it for each index (0..N))
> > ```
> > offsets: [0, 5]
> > values: [1,2,5,6,7,8,0,3,4,9]
> > ```
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> >
> > The benefit is (besides being in order) that instead of traversing it time after time in backwards order we can just copy the slice `1,2,5,6,7,8` or `0,3,4,9` into the target array :)
>
> I think this is quite elegant. Does this converting process occur in every single probe?
Currently the process of following the chain of indices does occur for every probe for each (possible) match.
The above suggestion is to do it only once (for every key) during build time.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow-datafusion] metesynnada commented on issue #7113: HashJoinExec output order is not correct
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #7113:
URL: https://github.com/apache/arrow-datafusion/issues/7113#issuecomment-1655188947
Wow, you are right 😀 Cool idea @Dandandan.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org