bert-beyondloops commented on PR #26261: URL: https://github.com/apache/datafusion/pull/26261#issuecomment-6189479270
@quwin Thanks for doing some benchmarks.
I adopted another strategy for the implementation:
`sort_merge_join_keys` in `physical_planner.rs` picks the join key order
and per-key SortOptions. It works as follows:
- Candidates.
- The start is the provided key order with default sort options.
- Further candidates come from each known ordering (oeq_class) of each
input. The ordering's entries that are join keys, normalized through the
equivalence group, become the leading keys, in that order and with those
options. The remaining keys follow in their provided order with default
options.
- Scoring. Each candidate is scored 0, 1 or 2: the number of inputs that
ordering_satisfy confirms are already sorted on it. The default wins ties, so
existing plans are unchanged, and the search stops as soon as a candidate
scores 2.
- Cost. There is nothing to do if neither input has an ordering. Otherwise
it costs one candidate per known ordering, each checked with two
ordering_satisfy calls.
Note on the approach. An earlier iteration of this PR searched all
combinations of sort options per key with backtracking, in the provided key
order, and adopted them only if both inputs agreed. This version replaces it
with
the candidate approach above, to avoid the exponential search and the CPU
cost. It also covers more cases:
- keys listed in a different order than the input ordering
- keys that are constant or equal to another column
- adopting the ordering of only one input, so that only the other side
needs a SortExec
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
