You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "korowa (via GitHub)" <gi...@apache.org> on 2023/11/10 19:59:47 UTC
[I] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
korowa opened a new issue, #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130
### Is your feature request related to a problem or challenge?
The problem related to #8020
At this moment, [collect_left_input](https://github.com/apache/arrow-datafusion/blob/91c9d6f847eda0b5b1d01257b5c24459651d3926/datafusion/physical-plan/src/joins/hash_join.rs#L612) function in hash join implementation produces `JoinHasMap` which is optimized for reverse iteration -- for each `hash_value` the actual HashMap stores the index of the last row from the build-side, and remaining indices for same has are stored in `JoinHashMap.next` vector.
To keep maintaining inputs order in join output, `HashJoinStream` iterates over probe-batch in [reverse](https://github.com/apache/arrow-datafusion/blob/91c9d6f847eda0b5b1d01257b5c24459651d3926/datafusion/physical-plan/src/joins/hash_join.rs#L906) order, and after processing the whole batch, it, again, reverts order of matched [build](https://github.com/apache/arrow-datafusion/blob/91c9d6f847eda0b5b1d01257b5c24459651d3926/datafusion/physical-plan/src/joins/hash_join.rs#L940) and [probe](https://github.com/apache/arrow-datafusion/blob/91c9d6f847eda0b5b1d01257b5c24459651d3926/datafusion/physical-plan/src/joins/hash_join.rs#L941) indices.
The problem is that reverse iteration doesn't allow `HashJoinStream` to produce partial output batch (without having all matched indices for current probe batch) -- in this case join output order will be distorted.
### Describe the solution you'd like
Desired behaviour of `HashJoinStream` -- preserving natural order of probe + build side record, without intermediary inversion of indices -- to be ready to produce output batch in any moment.
This could be achieved by modifying `update_hash` to save "head" of hash chains in Map. It may also require to still track chain tails while building `JoinHashMap` in order to keep performance at the same level -- tails might be stored in `JoinHashMap` (probably not the best decision in terms of memory utilization), or in a separate data structure which will only exist during build-side collection and won't be as memory-greedy as one more integer in HashMap tuples.
### 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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on issue #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130#issuecomment-1808938777
Another option to achieve desired behaviour and not to affect left input collection performance (almost) at all -- is updating `JoinHashMap` in reverse order -- seems to be the most straightforward and simple solution for the issue.
--
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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130#issuecomment-1808944556
Tha
> Another option to achieve desired behaviour and not to affect left input collection performance (almost) at all -- is updating `JoinHashMap` in reverse order -- seems to be the most straightforward and simple solution for the issue.
Thanks @korowa -- I am not super familiar with this code; After I have done a bit more study I'll hopefully have a proposal to share
--
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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130#issuecomment-1809237585
I started hacking on this locally -- the basic structure I have in mind looks something like this (I need to sort out the OnceFuture stuff, which is awkward at the moment).
But the idea is to wrap up the state needed to build output into a separate enum like the following:
```
/// State machine for creating output for HashJoin
///
/// TODO Add memory reservation for intermediate rows
enum HashJoinOutput {
/// output phase has not yet started, input is
ReadingInput {
/// future which builds hash table from left side
left_fut: OnceFut<JoinLeftData>,
},
/// output phase has started, but have no probe batch
Ready {
// TODO make this into the proper state
left_fut: OnceFut<JoinLeftData>,
},
/// and output is being built from probe batches
Probing {
data: JoinLeftData,
},
/// emitting any final unmatched indices, if any (depending on the join type)
Unmatched {
//
data: JoinLeftData,
},
/// Input is complete, and output is complete
Done,
}
```
Then I think adding the logic to incrementally compute the matching indices is more tractable (though as you say @korowa we'll still have to protect against pathalogical cases where each input row in the probe batch matches all the rows in the hashtable).
I think this will take me a few days to code up realistically, and https://github.com/apache/arrow-datafusion/issues/8078 is higher priority for me. However, I think we'll be able to make this work
--
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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130#issuecomment-1809232758
Here are some small documentation PRs to start the process
* https://github.com/apache/arrow-datafusion/pull/8153
* https://github.com/apache/arrow-datafusion/pull/8154
--
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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb closed issue #8130: FIFO `JoinHashMap` for `HashJoin`
URL: https://github.com/apache/arrow-datafusion/issues/8130
--
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] FIFO `JoinHashMap` for `HashJoin` [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #8130:
URL: https://github.com/apache/arrow-datafusion/issues/8130#issuecomment-1808925637
I am going to try and study this code and see if I can find some way to structure 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