findepi commented on code in PR #17684:
URL: https://github.com/apache/datafusion/pull/17684#discussion_r2372930407
##########
datafusion/physical-plan/src/windows/mod.rs:
##########
@@ -371,18 +371,41 @@ pub(crate) fn window_equivalence_properties(
for (i, expr) in window_exprs.iter().enumerate() {
let partitioning_exprs = expr.partition_by();
let no_partitioning = partitioning_exprs.is_empty();
- // Collect columns defining partitioning, and construct all
`SortOptions`
- // variations for them. Then, we will check each one whether it
satisfies
- // the existing ordering provided by the input plan.
+
+ // Find "one" valid ordering for partition columns to avoid
exponential complexity.
let mut all_satisfied_lexs = vec![];
- for lex in partitioning_exprs
- .iter()
- .map(|pb_order|
sort_options_resolving_constant(Arc::clone(pb_order)))
- .multi_cartesian_product()
- .filter_map(LexOrdering::new)
- {
- if window_eq_properties.ordering_satisfy(lex.clone())? {
- all_satisfied_lexs.push(lex);
+ if !no_partitioning {
+ // Find a single valid ordering using a greedy approach
+ let mut ordering = vec![];
+ for partition_expr in partitioning_exprs.iter() {
+ let sort_options =
+
sort_options_resolving_constant(Arc::clone(partition_expr), true);
+
+ // Try each sort option and pick the first one that works
+ let mut found = false;
+ for sort_expr in sort_options.iter() {
+ let mut candidate_ordering = ordering.clone();
+ candidate_ordering.push(sort_expr.clone());
+
+ if let Some(lex) =
LexOrdering::new(candidate_ordering.clone()) {
+ if window_eq_properties.ordering_satisfy(lex)? {
Review Comment:
No doubt quadratic is so much better than exponential.
What could make turn valid partial ordering into an invalid, when extended
with a new expression?
Is it only about duplicates?
IIRC, `LexOrdering::new` checks for dups, so something we could easily do
O(n) overall. But I don't know yet what `window_eq_properties.ordering_satisfy`
does.
--
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]
