You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/06/05 09:24:55 UTC
[GitHub] [arrow-datafusion] korowa opened a new pull request, #2699: Sort preserving `SortMergeJoin`
korowa opened a new pull request, #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699
# Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #2698.
# Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
Defined ordering of `SortMergeJoin` output may be helpful for query planner/optimizer in general.
# What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
Now there is `StreamedBatch.output_indices` -- single structure for storing both streamed side indices with and without matches on buffered side, instead of two separate places as before (`StreamedBatch.null_joined` and `BufferedBatch.pair_joined`).
It allows to stage output indices in the order they appear as a result of `join_partial` calls (which generally is an order of streamed/outer input), and since `output_indices` now used for output batch creation, output batches are also ordered.
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
No
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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 merged pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
alamb merged PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699
--
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 pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699#issuecomment-1152640022
I put this on my weekend review list -- I want to ensure I have sufficient time to focus as this stuff is always tricky and I haven't found such time this week, sadly 😢
--
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] waynexia commented on pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
waynexia commented on PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699#issuecomment-1152484150
I have checked the test and think it's concrete :+1: Logic changes also look good to me but I'm not very confident.
--
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 a diff in pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699#discussion_r895637134
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1414,7 +1407,7 @@ mod tests {
"| 3 | 5 | 9 | 20 | 5 | 80 |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
I think it might be worth a note here explaining that the sort order of the output is important in case someone might try and change it in the future:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1489,7 +1482,7 @@ mod tests {
"| 1 | 1 | 8 | 1 | 1 | 80 |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1451,7 +1444,7 @@ mod tests {
"| 2 | 2 | 9 | 2 | 2 | 80 |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1619,7 +1611,7 @@ mod tests {
assert_eq!(batches.len(), 2);
assert_eq!(batches[0].num_rows(), 2);
assert_eq!(batches[1].num_rows(), 1);
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1650,7 +1642,7 @@ mod tests {
"| 3 | 7 | 9 | | | |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1774,7 +1766,7 @@ mod tests {
"| 2 | 5 | 8 |",
"+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1838,7 +1830,7 @@ mod tests {
"| 1970-01-04 | 2022-04-26 | 1970-01-10 | 1970-01-21 | 2022-04-26 | 1970-03-22 |",
"+------------+------------+------------+------------+------------+------------+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1743,7 +1735,7 @@ mod tests {
"| 5 | 7 | 11 |",
"+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1571,14 +1564,13 @@ mod tests {
"+----+----+----+----+----+----+",
"| a1 | b2 | c1 | a1 | b2 | c2 |",
"+----+----+----+----+----+----+",
- "| 1 | | 1 | 1 | | 10 |",
- "| 1 | 1 | | 1 | 1 | 70 |",
- "| 2 | 2 | 8 | 2 | 2 | 80 |",
"| 2 | 2 | 9 | 2 | 2 | 80 |",
+ "| 2 | 2 | 8 | 2 | 2 | 80 |",
+ "| 1 | 1 | | 1 | 1 | 70 |",
+ "| 1 | | 1 | 1 | | 10 |",
"+----+----+----+----+----+----+",
];
- //assert_eq!(batches.len(), 1);
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1526,7 +1519,7 @@ mod tests {
"| 2 | 2 | 9 | 2 | 2 | 80 |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1805,7 +1797,7 @@ mod tests {
"| 2 | 5 | 8 | 20 | 2 | 80 |",
"+---+---+---+----+---+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1676,12 +1668,12 @@ mod tests {
"+----+----+----+----+----+----+",
"| a1 | b1 | c1 | a2 | b1 | c2 |",
"+----+----+----+----+----+----+",
- "| | | | 30 | 6 | 90 |",
"| 1 | 4 | 7 | 10 | 4 | 70 |",
"| 2 | 5 | 8 | 20 | 5 | 80 |",
+ "| | | | 30 | 6 | 90 |",
"+----+----+----+----+----+----+",
];
- assert_batches_sorted_eq!(expected, &batches);
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1871,6 +1863,223 @@ mod tests {
"| 1970-01-01 | 2022-04-25 | 1970-01-01 | 1970-01-01 | 2022-04-25 | 1970-01-01 |",
"+------------+------------+------------+------------+------------+------------+",
];
+ assert_batches_eq!(expected, &batches);
Review Comment:
```suggestion
// The output order is important as SMJ preserves sortedness
assert_batches_eq!(expected, &batches);
```
##########
datafusion/core/src/physical_plan/sort_merge_join.rs:
##########
@@ -1871,6 +1863,223 @@ mod tests {
"| 1970-01-01 | 2022-04-25 | 1970-01-01 | 1970-01-01 | 2022-04-25 | 1970-01-01 |",
"+------------+------------+------------+------------+------------+------------+",
];
+ assert_batches_eq!(expected, &batches);
+ Ok(())
+ }
+
+ #[tokio::test]
+ async fn join_left_sort_order() -> Result<()> {
+ let left = build_table(
+ ("a1", &vec![0, 1, 2, 3, 4, 5]),
+ ("b1", &vec![3, 4, 5, 6, 6, 7]),
+ ("c1", &vec![4, 5, 6, 7, 8, 9]),
+ );
+ let right = build_table(
+ ("a2", &vec![0, 10, 20, 30, 40]),
+ ("b2", &vec![2, 4, 6, 6, 8]),
+ ("c2", &vec![50, 60, 70, 80, 90]),
+ );
+ let on = vec![(
+ Column::new_with_schema("b1", &left.schema())?,
+ Column::new_with_schema("b2", &right.schema())?,
+ )];
+
+ let (_, batches) = join_collect(left, right, on, JoinType::Left).await?;
+ let expected = vec![
+ "+----+----+----+----+----+----+",
+ "| a1 | b1 | c1 | a2 | b2 | c2 |",
+ "+----+----+----+----+----+----+",
+ "| 0 | 3 | 4 | | | |",
+ "| 1 | 4 | 5 | 10 | 4 | 60 |",
+ "| 2 | 5 | 6 | | | |",
+ "| 3 | 6 | 7 | 20 | 6 | 70 |",
+ "| 3 | 6 | 7 | 30 | 6 | 80 |",
+ "| 4 | 6 | 8 | 20 | 6 | 70 |",
+ "| 4 | 6 | 8 | 30 | 6 | 80 |",
+ "| 5 | 7 | 9 | | | |",
+ "+----+----+----+----+----+----+",
+ ];
+ assert_batches_eq!(expected, &batches);
+ Ok(())
+ }
+
+ #[tokio::test]
+ async fn join_right_sort_order() -> Result<()> {
+ let left = build_table(
+ ("a1", &vec![0, 1, 2, 3]),
+ ("b1", &vec![3, 4, 5, 7]),
+ ("c1", &vec![6, 7, 8, 9]),
+ );
+ let right = build_table(
+ ("a2", &vec![0, 10, 20, 30]),
+ ("b2", &vec![2, 4, 5, 6]),
+ ("c2", &vec![60, 70, 80, 90]),
+ );
+ let on = vec![(
+ Column::new_with_schema("b1", &left.schema())?,
+ Column::new_with_schema("b2", &right.schema())?,
+ )];
+
+ let (_, batches) = join_collect(left, right, on, JoinType::Right).await?;
+ let expected = vec![
+ "+----+----+----+----+----+----+",
+ "| a1 | b1 | c1 | a2 | b2 | c2 |",
+ "+----+----+----+----+----+----+",
+ "| | | | 0 | 2 | 60 |",
+ "| 1 | 4 | 7 | 10 | 4 | 70 |",
+ "| 2 | 5 | 8 | 20 | 5 | 80 |",
+ "| | | | 30 | 6 | 90 |",
+ "+----+----+----+----+----+----+",
+ ];
+ assert_batches_eq!(expected, &batches);
+ Ok(())
+ }
+
+ #[tokio::test]
+ async fn join_left_multiple_batches() -> Result<()> {
Review Comment:
👍
--
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 pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699#issuecomment-1155536508
Thanks again @korowa
--
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] codecov-commenter commented on pull request #2699: Sort preserving `SortMergeJoin`
Posted by GitBox <gi...@apache.org>.
codecov-commenter commented on PR #2699:
URL: https://github.com/apache/arrow-datafusion/pull/2699#issuecomment-1146775508
# [Codecov](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) Report
> Merging [#2699](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (ee55576) into [master](https://codecov.io/gh/apache/arrow-datafusion/commit/a690a28ec7d35e994c2e021c62c336a4af84209e?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) (a690a28) will **increase** coverage by `0.02%`.
> The diff coverage is `97.41%`.
```diff
@@ Coverage Diff @@
## master #2699 +/- ##
==========================================
+ Coverage 84.66% 84.68% +0.02%
==========================================
Files 270 270
Lines 46919 47006 +87
==========================================
+ Hits 39724 39808 +84
- Misses 7195 7198 +3
```
| [Impacted Files](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation) | Coverage Δ | |
|---|---|---|
| [...tafusion/core/src/physical\_plan/sort\_merge\_join.rs](https://codecov.io/gh/apache/arrow-datafusion/pull/2699/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-ZGF0YWZ1c2lvbi9jb3JlL3NyYy9waHlzaWNhbF9wbGFuL3NvcnRfbWVyZ2Vfam9pbi5ycw==) | `90.34% <97.41%> (+0.73%)` | :arrow_up: |
| [datafusion/expr/src/window\_frame.rs](https://codecov.io/gh/apache/arrow-datafusion/pull/2699/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-ZGF0YWZ1c2lvbi9leHByL3NyYy93aW5kb3dfZnJhbWUucnM=) | `92.43% <0.00%> (-0.85%)` | :arrow_down: |
| [datafusion/core/src/physical\_plan/metrics/value.rs](https://codecov.io/gh/apache/arrow-datafusion/pull/2699/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-ZGF0YWZ1c2lvbi9jb3JlL3NyYy9waHlzaWNhbF9wbGFuL21ldHJpY3MvdmFsdWUucnM=) | `86.93% <0.00%> (-0.51%)` | :arrow_down: |
| [datafusion/expr/src/logical\_plan/plan.rs](https://codecov.io/gh/apache/arrow-datafusion/pull/2699/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-ZGF0YWZ1c2lvbi9leHByL3NyYy9sb2dpY2FsX3BsYW4vcGxhbi5ycw==) | `68.21% <0.00%> (ø)` | |
| [datafusion/optimizer/src/utils.rs](https://codecov.io/gh/apache/arrow-datafusion/pull/2699/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation#diff-ZGF0YWZ1c2lvbi9vcHRpbWl6ZXIvc3JjL3V0aWxzLnJz) | `32.79% <0.00%> (+1.07%)` | :arrow_up: |
------
[Continue to review full report at Codecov](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Last update [a690a28...ee55576](https://codecov.io/gh/apache/arrow-datafusion/pull/2699?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=The+Apache+Software+Foundation).
--
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