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/31 14:48:29 UTC
[GitHub] [arrow-datafusion] metesynnada opened a new pull request, #7155: HashJoin order fixing
metesynnada opened a new pull request, #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155
# Which issue does this PR close?
Closes https://github.com/apache/arrow-datafusion/issues/7113.
# Rationale for this change
Fixing the HashJoin order.
# What changes are included in this PR?
Reversing indices.
# Are these changes tested?
Yes, with existing tests.
# Are there any user-facing changes?
No
--
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 a diff in pull request #7155: HashJoin order fixing
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on code in PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#discussion_r1280178495
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -757,7 +757,7 @@ pub fn build_equal_condition_join_indices(
let mut build_indices = UInt64BufferBuilder::new(0);
let mut probe_indices = UInt32BufferBuilder::new(0);
// Visit all of the probe rows
- for (row, hash_value) in hash_values.iter().enumerate() {
+ for (row, hash_value) in hash_values.iter().enumerate().rev() {
Review Comment:
Sure, I am on it.
--
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] mustafasrepo commented on pull request #7155: HashJoin order fixing
Posted by "mustafasrepo (via GitHub)" <gi...@apache.org>.
mustafasrepo commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661982971
> If we don't consider the special case ...
> Does we can get the right result?
Yes, the result will be correct but it would be sub-optimal. Consider the hash join where left table ordering is `left ASC` and right table ordering is `right ASC`. If the join type is right output ordering of the hash join would be `right ASC`. If the join type were, inner join output ordering would be `right ASC, left ASC`. (lexicographical). This special case handles this. If we do not use it, we would produce `right ASC` for inner join. This is correct also.
--
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 a diff in pull request #7155: HashJoin order fixing
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#discussion_r1279568013
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -757,7 +757,7 @@ pub fn build_equal_condition_join_indices(
let mut build_indices = UInt64BufferBuilder::new(0);
let mut probe_indices = UInt32BufferBuilder::new(0);
// Visit all of the probe rows
- for (row, hash_value) in hash_values.iter().enumerate() {
+ for (row, hash_value) in hash_values.iter().enumerate().rev() {
Review Comment:
Why does this need to be reverted as well?
--
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 pull request #7155: HashJoin order fixing
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661669084
Thanks @metesynnada and @ozankabak for the extra review.
I felt certain that this is the correct change so went ahead with the merge. @liukun4515 let us know if you have any worries.
--
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 merged pull request #7155: HashJoin order fixing
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155
--
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] liukun4515 commented on pull request #7155: HashJoin order fixing
Posted by "liukun4515 (via GitHub)" <gi...@apache.org>.
liukun4515 commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661988145
>
> > If we don't consider the special case ...
> > Does we can get the right result?
>
> Yes, the result will be correct but it would be sub-optimal. Consider the hash join where left table ordering is `left ASC` and right table ordering is `right ASC`. If the join type is right output ordering of the hash join would be `right ASC`. If the join type were, inner join output ordering would be `right ASC, left ASC`. (lexicographical). This special case handles this. If we do not use it, we would produce `right ASC` for inner join. This is correct also.
Thanks for your explanation.
--
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 pull request #7155: HashJoin order fixing
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661903930
In the JoinType::Inner match arm, we also preserve the left ordering.
```rust
JoinType::Inner => {
// We modify the indices of the right order columns because their
// columns are appended to the right side of the left schema.
let mut adjusted_right_order =
adjust_right_order(right_order, left_len)?;
if let Some(left_order) = maybe_left_order {
adjusted_right_order.extend_from_slice(left_order);
}
Some(adjusted_right_order)
}
```
Since the function is changed into `calculate_join_output_ordering` into `calculate_join_output_order` in a previous PR, this function is not currently in main. However, the new function is also adding left order in case of the inner join.
--
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 pull request #7155: HashJoin order fixing
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1660033771
@liukun4515 Is there anything I can clarify for you about some points?
--
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 a diff in pull request #7155: HashJoin order fixing
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#discussion_r1279648646
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -757,7 +757,7 @@ pub fn build_equal_condition_join_indices(
let mut build_indices = UInt64BufferBuilder::new(0);
let mut probe_indices = UInt32BufferBuilder::new(0);
// Visit all of the probe rows
- for (row, hash_value) in hash_values.iter().enumerate() {
+ for (row, hash_value) in hash_values.iter().enumerate().rev() {
Review Comment:
Ah because otherwise the order of is wrong - I get it. Could we add some comments for both changes?
--
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] liukun4515 commented on pull request #7155: HashJoin order fixing
Posted by "liukun4515 (via GitHub)" <gi...@apache.org>.
liukun4515 commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661960108
>
> In the JoinType::Inner match arm, we also preserve the left ordering.
>
> ```rust
> JoinType::Inner => {
> // We modify the indices of the right order columns because their
> // columns are appended to the right side of the left schema.
> let mut adjusted_right_order =
> adjust_right_order(right_order, left_len)?;
> if let Some(left_order) = maybe_left_order {
> adjusted_right_order.extend_from_slice(left_order);
> }
> Some(adjusted_right_order)
> }
> ```
>
> Since the function is changed into `calculate_join_output_ordering` into `calculate_join_output_order` in a previous PR, this function is not currently in main. However, the new function is also adding left order in case of the inner join.
>
> ```rust
> (false, true) => {
> // Special case, we can prefix ordering of left side with the ordering of right side.
> if join_type == JoinType::Inner && probe_side == Some(JoinSide::Right) {
> merge_vectors(&right_ordering, left_ordering)
> } else {
> right_ordering
> }
> }
> ```
I know this changes about `calculate_join_output_ordering`.
If we don't consider the special case
```
if join_type == JoinType::Inner && probe_side == Some(JoinSide::Right) {
merge_vectors(&right_ordering, left_ordering)
```
Does we can get the right result?
@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] liukun4515 commented on a diff in pull request #7155: HashJoin order fixing
Posted by "liukun4515 (via GitHub)" <gi...@apache.org>.
liukun4515 commented on code in PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#discussion_r1280292355
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -757,7 +757,7 @@ pub fn build_equal_condition_join_indices(
let mut build_indices = UInt64BufferBuilder::new(0);
let mut probe_indices = UInt32BufferBuilder::new(0);
// Visit all of the probe rows
- for (row, hash_value) in hash_values.iter().enumerate() {
+ for (row, hash_value) in hash_values.iter().enumerate().rev() {
Review Comment:
Sorry for this issue https://github.com/apache/arrow-datafusion/issues/7113
I don't know why this issue is a bug?
Does it get the error result for the hash join?
@Dandandan @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] liukun4515 commented on pull request #7155: HashJoin order fixing
Posted by "liukun4515 (via GitHub)" <gi...@apache.org>.
liukun4515 commented on PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#issuecomment-1661865079
> Thanks @metesynnada and @ozankabak for the extra review.
>
> I felt certain that this is the correct change so went ahead with the merge. @liukun4515 let us know if you have any worries.
In this issue https://github.com/apache/arrow-datafusion/issues/7113
@metesynnada describe the issue
```
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.
```
But I review the code of `calculate_join_output_ordering`, and find the build side are not preserved the order
Does we need to preserve the order for the build side?
From the implementation of `calculate_join_output_ordering`, I think we should just maintain the order of the probe side.
Does I miss something?
@Dandandan
@ozankabak
--
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 a diff in pull request #7155: HashJoin order fixing
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #7155:
URL: https://github.com/apache/arrow-datafusion/pull/7155#discussion_r1280392875
##########
datafusion/core/src/physical_plan/joins/hash_join.rs:
##########
@@ -757,7 +757,7 @@ pub fn build_equal_condition_join_indices(
let mut build_indices = UInt64BufferBuilder::new(0);
let mut probe_indices = UInt32BufferBuilder::new(0);
// Visit all of the probe rows
- for (row, hash_value) in hash_values.iter().enumerate() {
+ for (row, hash_value) in hash_values.iter().enumerate().rev() {
Review Comment:
So there seems there was no test for checking the ordering of the hash join results (only for the matching rows to be correct) @metesynnada changed one to test this. This is important if the execution plan depends on the output ordering (and doesn't add extra sort).
The matching rows themselves are correct even before this PR.
--
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