You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "jonathanc-n (via GitHub)" <gi...@apache.org> on 2024/11/04 17:53:15 UTC
[PR] feat: RightMark Join [datafusion]
jonathanc-n opened a new pull request, #13252:
URL: https://github.com/apache/datafusion/pull/13252
## 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 #13138 .
## 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.
-->
## 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.
-->
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "eejbyfeldt (via GitHub)" <gi...@apache.org>.
eejbyfeldt commented on code in PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#discussion_r1828317857
##########
datafusion/optimizer/src/optimize_projections/mod.rs:
##########
@@ -682,7 +682,8 @@ fn split_join_requirements(
| JoinType::Left
| JoinType::Right
| JoinType::Full
- | JoinType::LeftMark => {
+ | JoinType::LeftMark
+ | JoinType::RightMark => {
// Decrease right side indices by `left_len` so that they point to valid
// positions within the right child:
indices.split_off(left_len)
Review Comment:
Is this really correct? Feels like we will assign the wrong indices to the left here for `RightMark`? Should `RightMark` be moved to `RightSemi` and `RightAnti`. Maybe we should for `LeftMark` as well for clarity (and maybe that also fixes some edge case?)
##########
datafusion/substrait/src/logical_plan/producer.rs:
##########
@@ -726,7 +726,7 @@ fn to_substrait_jointype(join_type: JoinType) -> join_rel::JoinType {
JoinType::LeftAnti => join_rel::JoinType::LeftAnti,
JoinType::LeftSemi => join_rel::JoinType::LeftSemi,
JoinType::LeftMark => join_rel::JoinType::LeftMark,
- JoinType::RightAnti | JoinType::RightSemi => {
+ JoinType::RightAnti | JoinType::RightSemi | JoinType::RightMark => {
Review Comment:
Why can we not turn it into `join_rel::JoinType::RightMark` here?
##########
datafusion/proto-common/src/generated/pbjson.rs:
##########
@@ -3911,6 +3913,7 @@ impl<'de> serde::Deserialize<'de> for JoinType {
"RIGHTSEMI" => Ok(JoinType::Rightsemi),
"RIGHTANTI" => Ok(JoinType::Rightanti),
"LEFTMARK" => Ok(JoinType::Leftmark),
+ "RIGHTMARK" => Ok(JoinTYpe::Rightmark),
Review Comment:
This is causing CI failures. I belive this file should be generated by running: https://github.com/apache/datafusion/blob/main/datafusion/proto-common/regen.sh
```suggestion
"RIGHTMARK" => Ok(JoinType::Rightmark),
```
##########
datafusion/physical-plan/src/joins/symmetric_hash_join.rs:
##########
@@ -731,6 +731,22 @@ where
.collect();
(build_indices, probe_indices)
}
+ (JoinSide::Right, JoinType::RightMark) => {
+ let probe_indices = (0..prune_length)
+ .map(R::Native::from_usize)
+ .collect::<PrimitiveArray<R>>();
+ let build_indices = (0..prune_length)
+ .map(|idx| {
+ // For mark join we output a dummy index 0 to indicate the row had a match
+ if visited_rows.contains(&(idx + deleted_offset)) {
+ Some(L::Native::from_usize(0).unwrap())
+ } else {
+ None
+ }
+ })
+ .collect();
+ (build_indices, probe_indices)
Review Comment:
This looks very similar to what we do or the `LeftMark` could we move this code into a function and call it for both?
##########
datafusion/sql/src/unparser/plan.rs:
##########
@@ -866,7 +866,7 @@ impl Unparser<'_> {
JoinType::LeftSemi => ast::JoinOperator::LeftSemi(constraint),
JoinType::RightAnti => ast::JoinOperator::RightAnti(constraint),
JoinType::RightSemi => ast::JoinOperator::RightSemi(constraint),
- JoinType::LeftMark => unimplemented!("Unparsing of Left Mark join type"),
+ JoinType::LeftMark | JoinType::RightMark => unimplemented!("Unparsing of Left Mark join type"),
Review Comment:
```suggestion
JoinType::LeftMark | JoinType::RightMark => unimplemented!("Unparsing of mark join type"),
```
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -689,6 +690,16 @@ pub fn build_join_schema(
left_fields().chain(right_field).unzip()
}
JoinType::RightSemi | JoinType::RightAnti => right_fields().unzip(),
+ JoinType::RightMark => {
+ let left_field = once((
+ Field::new("mark", arrow_schema::DataType::Boolean, false),
+ ColumnIndex {
+ index: 0, // 'mark' is not associated with either side
+ side: JoinSide::None,
+ },
+ ));
Review Comment:
Maybe this could also be moved to a function that is used for both `LeftMark` and `RightMark`.
##########
datafusion/core/src/physical_optimizer/join_selection.rs:
##########
@@ -136,6 +136,9 @@ fn swap_join_type(join_type: JoinType) -> JoinType {
JoinType::LeftMark => {
unreachable!("LeftMark join type does not support swapping")
}
+ JoinType::RightMark => {
+ unreachable!("RightMark join type does not support swapping")
Review Comment:
Yeah, supporting swap is partly why we are adding RightMark. So would be good to have that fixed in 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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#issuecomment-2458236706
@eejbyfeldt I implemented the swapping, would be nice to see if I did that correctly.
I made a change to `adjust_indices_by_join_type` and combined the logic for the right join and rightmark join for indices:
```
JoinType::Right | JoinType::RightMark => {
// combine the matched and unmatched right result together
append_right_indices(
left_indices,
right_indices,
adjust_range,
preserve_order_for_right,
)
}```
`join_right_mark` test had previously not given any results and is now giving a table with values. However, it is marking all the values as true and I cannot seem to track the issue down. Would you be able to look into this?
Instead of this:
```
"+----+----+----+-------+",
"| a2 | b1 | c2 | mark |",
"+----+----+----+-------+",
"| 10 | 4 | 70 | true |",
"| 20 | 5 | 80 | true |",
"| 30 | 6 | 90 | false |",
"+----+----+----+-------+",
it is giving this:
"+----+----+----+-------+",
"| a2 | b1 | c2 | mark |",
"+----+----+----+-------+",
"| 10 | 4 | 70 | true |",
"| 20 | 5 | 80 | true |",
"| 30 | 6 | 90 | true |",
"+----+----+----+-------+",
```
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#issuecomment-2455356839
@eejbyfeldt Just leaving it as a draft for now, if you have any pointers feel free to add on.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n closed pull request #13252: feat: add RightMark Join
URL: https://github.com/apache/datafusion/pull/13252
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#discussion_r1828275851
##########
datafusion/core/src/physical_optimizer/join_selection.rs:
##########
@@ -136,6 +136,9 @@ fn swap_join_type(join_type: JoinType) -> JoinType {
JoinType::LeftMark => {
unreachable!("LeftMark join type does not support swapping")
}
+ JoinType::RightMark => {
+ unreachable!("RightMark join type does not support swapping")
Review Comment:
I think we can support it now, I think this should be relatively easy.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "eejbyfeldt (via GitHub)" <gi...@apache.org>.
eejbyfeldt commented on PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#issuecomment-2464127994
I think the logic here:
https://github.com/jonathanc-n/datafusion/blob/feac9714a172fd7dd96c18b724363bdad8e0d155/datafusion/physical-plan/src/joins/utils.rs#L1289-L1290
is probably not correct when there is both `LeftMark` and `RightMark`. For `RightMark` I would expect us to to need to `compute::is_not_null(build_indices)` instead. So we might need to pass the join_type to that function in order to implement that.
I also suspect we might need do more changes in `adjust_indices_by_join_type`. I don't think we can just do the same as `JoinType::Right` when we have multiple matches. The `Right` will for that case produce multiple rows per row from the right side, while the `RightMark` should follow similar logic to the `RightSemi` where we remove duplicates. But of course we need the unmatched rows like the `Right` join so we might need our own adjustment logic.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#discussion_r1834871623
##########
datafusion/proto-common/src/generated/pbjson.rs:
##########
@@ -3911,6 +3913,7 @@ impl<'de> serde::Deserialize<'de> for JoinType {
"RIGHTSEMI" => Ok(JoinType::Rightsemi),
"RIGHTANTI" => Ok(JoinType::Rightanti),
"LEFTMARK" => Ok(JoinType::Leftmark),
+ "RIGHTMARK" => Ok(JoinTYpe::Rightmark),
Review Comment:
Yeah I can probably open a pr to add this later.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n commented on code in PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#discussion_r1829870288
##########
datafusion/proto-common/src/generated/pbjson.rs:
##########
@@ -3911,6 +3913,7 @@ impl<'de> serde::Deserialize<'de> for JoinType {
"RIGHTSEMI" => Ok(JoinType::Rightsemi),
"RIGHTANTI" => Ok(JoinType::Rightanti),
"LEFTMARK" => Ok(JoinType::Leftmark),
+ "RIGHTMARK" => Ok(JoinTYpe::Rightmark),
Review Comment:
Is this included in the docs?
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "jonathanc-n (via GitHub)" <gi...@apache.org>.
jonathanc-n closed pull request #13252: feat: add RightMark Join
URL: https://github.com/apache/datafusion/pull/13252
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "eejbyfeldt (via GitHub)" <gi...@apache.org>.
eejbyfeldt commented on code in PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#discussion_r1833904787
##########
datafusion/proto-common/src/generated/pbjson.rs:
##########
@@ -3911,6 +3913,7 @@ impl<'de> serde::Deserialize<'de> for JoinType {
"RIGHTSEMI" => Ok(JoinType::Rightsemi),
"RIGHTANTI" => Ok(JoinType::Rightanti),
"LEFTMARK" => Ok(JoinType::Leftmark),
+ "RIGHTMARK" => Ok(JoinTYpe::Rightmark),
Review Comment:
There is some documentation here: https://github.com/eejbyfeldt/datafusion/blob/2e52580b0f10c35b36d02c6f44e13a460de771c9/datafusion/proto/CONTRIBUTING.md?plain=1#L20-L32 But I am sure it could be improved.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] feat: add RightMark Join [datafusion]
Posted by "eejbyfeldt (via GitHub)" <gi...@apache.org>.
eejbyfeldt commented on PR #13252:
URL: https://github.com/apache/datafusion/pull/13252#issuecomment-2464133596
@eejbyfeldt I implemented the swapping, would be nice to see if I did that correctly.
The swapping looks correct as far as I can tell. But will run some more tests when we fixed the other implementation issues.
--
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@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org