korowa commented on PR #8020: URL: https://github.com/apache/arrow-datafusion/pull/8020#issuecomment-1804360056
@metesynnada , @alamb, thank you! To be honest, item#2 -- `HashJoin` refactoring seems like too massive task for me (at least in short/reasonable period of time) -- so, I would be awesome to get some help with it. Regarding FIFO `JoinHashMap`, @metesynnada > brief explanation of how you maintain the lexical order on the build side? That has given me a following thought: 1) the only two cases when DataFusion cares about build-side output ordering -- are inner joins [1](https://github.com/apache/arrow-datafusion/blob/93af4401d77e9761ca3d187cdc56aa245f7aa7aa/datafusion/physical-plan/src/joins/utils.rs#L189) and [2](https://github.com/apache/arrow-datafusion/blob/93af4401d77e9761ca3d187cdc56aa245f7aa7aa/datafusion/physical-plan/src/joins/utils.rs#L202) 2) actually ordering in plan doesn't care about "natural" order (the order in which records were fetched from the source, and which actually is inverted/broken in this PR for build-side). The only important thing is lexical order -- which is still fine, cause `HashJoinStream` keeps maintaining it for probe-side. Due to these couple of facts -- it doesn't seem to me that FIFO `HashJoinMap` is required, cause for inner joins both probe and build sides will keep their lexicographical order (if they both were ordered by join-key columns -- otherwise build-side order will anyway be distorted). Example for current implementation would be like following (for `build inner join probe using (key)`) ``` Probe Build Output ┌───────┬───────┐ ┌───────┬───────┐ ┌─────────┬─────────┬─────┐ │ idx │ key │ │ idx │ key │ │probe_idx│build_idx│ key │ ├───────┼───────┤ ├───────┼───────┤ ├─────────┼─────────┼─────┤ │ 0 │ 1 │ │ 0 │ 1 │ │ 0 │ 1 │ 1 │ │ │ │ │ │ │ │ │ │ │ │ 1 │ 2 │ │ 1 │ 1 │ │ 0 │ 0 │ 1 │ │ │ │ │ │ │ │ │ │ │ │ 2 │ 3 │ │ 2 │ 2 │ │ 1 │ 3 │ 2 │ │ │ │ │ │ │ │ │ │ │ │ 3 │ 4 │ │ 3 │ 2 │ │ 1 │ 2 │ 2 │ │ │ │ │ │ │ │ │ │ │ │ 4 │ 5 │ │ 4 │ 5 │ │ 4 │ 4 │ 5 │ └───────┴───────┘ └───────┴───────┘ └─────────┴─────────┴─────┘ ``` index-based order of build side has changed, but lexicographically -- it is still correct. So, I guess, there is no need for `JoinHashMap` modification, and all we need now -- is to use separate `build_equal_condition_join_indices ` for SHJ. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
