You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "comphead (via GitHub)" <gi...@apache.org> on 2024/03/29 00:59:00 UTC
[I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
comphead opened a new issue, #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846
### Is your feature request related to a problem or challenge?
Hi all
I was going through SMJ implementation and suddenly stepped on the comments
```
// Sort-Merge join support currently is experimental
```
https://github.com/apache/arrow-datafusion/blob/81c96fc3db0ea35638278f32df066be63b745a51/datafusion/core/src/physical_planner.rs#L1141
I think it would be nice to revisit it and understand if Sort Merge Join Exec is still experimental.
And if so is there any strategies to make it stable, or to run benchmarks to prove the join is stable?
### Describe the solution you'd like
_No response_
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2028459854
I believe we can add fuzz tests for SMJ to ensure it is robust.
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2034917073
we shouldn't be comparing HJ vs SMJ 1:1, but the performance has to be quite close? What I'm trying to solve is to find a strategy to remove the experimental flag from SMJ and prove it is stable.
btw I found the fuzz tests are in place https://github.com/apache/arrow-datafusion/blob/daf182dc789230dbd9cf21ca2e975789213a5365/datafusion/core/tests/fuzz_cases/join_fuzz.rs#L128
--
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
Re: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2571713705
> > Is there a rule of thumb for choosing SMJ over HJ?
>
> Is there any plan on re-iterating on the SMJ heuristics ? For example, a use-case of mine would be: input data is pre-sorted + `target_partitions = 1` to use a single CPU core (wonder if there are better knobs that `target_partitions` for this btw).
>
> This couldn't use SMJ with current heuristics:
>
> https://github.com/apache/datafusion/blob/f3b1141d0f417e9d9e6c0ada03592c9d9ec60cd4/datafusion/core/src/physical_planner.rs#L1114-L1116
Sounds like that would probably be a good choice. Besides adding a knob / changing the default to do this, I think we will need some examples /benchmarks showing preferring SMJ over hash join in certain situations will improve performance and thus is a sane default.
--
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: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "milenkovicm (via GitHub)" <gi...@apache.org>.
milenkovicm commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2571716342
> > Is there a rule of thumb for choosing SMJ over HJ?
>
>
>
> Is there any plan on re-iterating on the SMJ heuristics ?
>
> For example, a use-case of mine would be: input data is pre-sorted + `target_partitions = 1` to use a single CPU core (wonder if there are better knobs that `target_partitions` for this btw).
>
>
>
> This couldn't use SMJ with current heuristics:
>
> https://github.com/apache/datafusion/blob/f3b1141d0f417e9d9e6c0ada03592c9d9ec60cd4/datafusion/core/src/physical_planner.rs#L1114-L1116
Until new configuration option is added I believe you could add your own optimiser rule to switch join implementation.
--
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: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "metesynnada (via GitHub)" <gi...@apache.org>.
metesynnada commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2034290998
Is there a rule of thumb for choosing SMJ over HJ?
--
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
Re: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-3319037522
I filed a ticket to discuss a potentially more general approach to join ordering and access path selection
- https://github.com/apache/datafusion/issues/17718
--
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: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2026415279
@alamb @ozankabak @viirya @mustafasrepo @berkaysynnada @metesynnada appreciate your inputs.
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2059436942
Seems like a good reason to keep it marked as experimental
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2027075183
From my experience, I have never seen SortMergeJoin used in any plan I looked at in DataFusion, so therefore I think it is still "experimental" or at least "not used by datafusion by default" (which maybe is the same thing)
It looks like there was some past interest in SortMergeJoin -- https://github.com/apache/arrow-datafusion/issues?q=is%3Aissue+is%3Aopen+sortmergejoin
Also the people interested in that operator seem to be the people focused on Spark
--
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
Re: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "16pierre (via GitHub)" <gi...@apache.org>.
16pierre commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2589918623
> Adjusting heuristics will likely just make some people's plans better but others worse
Yes, what I had in mind was to stay behind the `!prefer_hash_join` flag to use SMJ.
My blocker was rather the conditions `session_state.config().target_partitions() > 1 && session_state.config().repartition_joins()`, which I guess are required today to guarantee that data is pre-sorted correctly, whereas there may be other ways to infer that data is pre-sorted. But this probably not high priority, it's feasible to work-around as suggested in this thread.
--
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: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "16pierre (via GitHub)" <gi...@apache.org>.
16pierre commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2566568654
> Is there a rule of thumb for choosing SMJ over HJ?
Is there any plan on re-iterating on the SMJ heuristics ?
For example, a use-case of mine would be: input data is pre-sorted + `target_partitions = 1` to use a single CPU core (wonder if there are better knobs that `target_partitions` for this btw).
This couldn't use SMJ with current heuristics:
https://github.com/apache/datafusion/blob/f3b1141d0f417e9d9e6c0ada03592c9d9ec60cd4/datafusion/core/src/physical_planner.rs#L1114-L1116
--
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: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2571745238
The SMJ still needs some work to be done before we can enable it like supporting RightSemi/RightAnti. Also the issue was reported with small/empty batches in https://github.com/apache/datafusion-comet/pull/1211#issuecomment-2569564363
--
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: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2057999488
I ran TPCH benchmarks for SMJ and got
```
thread 'tokio-runtime-worker' panicked at datafusion/physical-plan/src/joins/sort_merge_join.rs:1357:22:
index out of bounds: the len is 0 but the index is 1
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
thread 'tokio-runtime-worker' panicked at datafusion/physical-plan/src/joins/sort_merge_join.rs:1357:22:
index out of bounds: the len is 0 but the index is 1
thread 'tokio-runtime-worker' panicked at datafusion/physical-plan/src/joins/sort_merge_join.rs:1357:22:
index out of bounds: the len is 0 but the index is 1
thread 'tokio-runtime-worker' panicked at datafusion/physical-plan/src/joins/sort_merge_join.rs:1357:22:
index out of bounds: the len is 0 but the index is 1
Error: Context("Join Error", External(JoinError::Panic(Id(88693), ...)))
```
--
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
Re: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9846:
URL: https://github.com/apache/datafusion/issues/9846#issuecomment-2571703716
> This couldn't use SMJ with current heuristics:
In my opinion, we should make more / better knobs for this kind of tuning (to make it easier to choose what types of joins, etc to use). Adjusting heuristics will likely just make some people's plans better but others worse
--
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: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2027426584
it is used if next conditions met https://github.com/apache/arrow-datafusion/blob/81c96fc3db0ea35638278f32df066be63b745a51/datafusion/core/src/physical_planner.rs#L1136
There is also a small set of tests introduced in `sort_merge_join.slt`. And the plans there shows SMJ
To enforce SMJ its needed to set
```
set datafusion.optimizer.prefer_hash_join = false;
```
Probably we can revisit tests and run some benchmarks with SMJ enforced to make a decision?
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2059458523
> Seems like a good reason to keep it marked as experimental
I'll create a separate issue on it.
Once TPCH passed we can get back on SMJ status
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2034369728
> Is there a rule of thumb for choosing SMJ over HJ?
I wonder how SMJ in DataFusion compares against HJ at the moment.
Some ideas for when SMJ could be chosen over HJ:
- When input data is already sorted on relevant keys, it is likely faster/requires less memory to plan a SMJ than HJ.
- HJ might require more memory than SMJ, so whenever e.g. data skew is expected one might choose sort merge over hash 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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2034578501
> Is there a rule of thumb for choosing SMJ over HJ?
I believe current state of the art in query processing is
1. If the data is already sorted by join keys, use MergeJoin (as @Dandandan says)
2. If the data is not already sorted on join key, use HashJoin
3. If HashJoin runs out of memory building the hash table, spill the table to disk (possibly switching to merge join internally)
The only benefit SMJ has over HJ at the moment in Datafusion is that we could plausibly join relations that are larger than memory using SMJ (using the fact that we can spill the inputs) -- this may be what @Dandandan is saying in https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2034369728
I think it is close to impossible to make MJ beat HJ for performance
--
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
Re: [I] [DISCUSSION] Sort Merge Join Experimental status [arrow-datafusion]
Posted by "comphead (via GitHub)" <gi...@apache.org>.
comphead commented on issue #9846:
URL: https://github.com/apache/arrow-datafusion/issues/9846#issuecomment-2032976999
I'm thinking if its enough to add fuzz tests, prob we also need to run benchmarks on top of SMJ? Afaik now benchmarks are on top of the HJ?
--
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
Re: [I] [Epic] Remove Sort Merge Join Experimental status [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #9846: [Epic] Remove Sort Merge Join Experimental status
URL: https://github.com/apache/datafusion/issues/9846
--
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