berkaysynnada commented on code in PR #17684:
URL: https://github.com/apache/datafusion/pull/17684#discussion_r2372481541
##########
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:
Yes, it's quadratic as we validate orderings of length 1, 2, 3, n. But
that's unavoidable since we need to check that each partial ordering stays
valid as we extend it.
Still way better than before. Old version is O(4^n), the new one is O(n^2 *
4)
The quadratic cost is the price of correctness
--
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]
