findepi commented on code in PR #17684:
URL: https://github.com/apache/datafusion/pull/17684#discussion_r2366142279
##########
datafusion/physical-plan/src/windows/mod.rs:
##########
@@ -371,18 +371,46 @@ 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.
+
+ // Use incremental approach to avoid O(4^n) exponential complexity:
+ // Instead of generating all combinations upfront via
multi_cartesian_product,
+ // we build orderings incrementally and prune invalid paths early.
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 {
Review Comment:
This condition looks redundant.
##########
datafusion/physical-plan/src/windows/mod.rs:
##########
@@ -371,18 +371,46 @@ 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.
+
+ // Use incremental approach to avoid O(4^n) exponential complexity:
+ // Instead of generating all combinations upfront via
multi_cartesian_product,
+ // we build orderings incrementally and prune invalid paths early.
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 {
+ // Start with empty orderings that we'll extend incrementally
+ let mut current_orderings = vec![vec![]];
+ for partition_expr in partitioning_exprs.iter() {
+ let mut next_orderings = vec![];
+
+ let sort_options =
+
sort_options_resolving_constant(Arc::clone(partition_expr), true);
+
+ // For each current partial ordering, try extending with each
sort option
+ for current in current_orderings.iter() {
+ for sort_expr in sort_options.iter() {
+ let mut extended = current.clone();
+ extended.push(sort_expr.clone());
Review Comment:
Does this look potentially expensive?
##########
datafusion/physical-plan/src/windows/mod.rs:
##########
@@ -371,18 +371,46 @@ 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.
+
+ // Use incremental approach to avoid O(4^n) exponential complexity:
+ // Instead of generating all combinations upfront via
multi_cartesian_product,
+ // we build orderings incrementally and prune invalid paths early.
Review Comment:
❤️
##########
datafusion/physical-plan/src/windows/mod.rs:
##########
@@ -471,7 +501,7 @@ pub(crate) fn window_equivalence_properties(
.get_aggregate_expr()
.expressions()
.into_iter()
- .map(sort_options_resolving_constant)
+ .map(|expr| sort_options_resolving_constant(expr,
false))
.multi_cartesian_product();
Review Comment:
this looks exponential still. when is this code path taken?
--
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-unsubscr...@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscr...@datafusion.apache.org
For additional commands, e-mail: github-h...@datafusion.apache.org
