jayzhan211 commented on issue #27267:
URL: https://github.com/apache/datafusion/issues/27267#issuecomment-6874775656

   @itang06 thanks for trying it. I'd keep the optimization. The cause is that 
the window declares its ordering with NULLs on the wrong end, so fixing that 
end fixes the bug without a nullability special case:
   
   - With a growing frame (`UNBOUNDED PRECEDING AND ...`), `MAX`/`MIN`/`SUM` 
stay NULL until the first non-NULL input, so NULLs come **first**. 
`get_result_ordering` in `physical-expr/src/aggregate.rs` always says NULLS 
LAST.
   - With a shrinking frame (`... AND UNBOUNDED FOLLOWING`), NULLs come 
**last**. `window_equivalence_properties` in `physical-plan/src/windows/mod.rs` 
says NULLS FIRST.
   
   Swapping those fixes all three queries in the issue, and the sort is still 
removed when the query asks for the NULL placement that really holds.
   
   For the `SUM` test you mentioned (window.slt:3206, `c9` is `NOT NULL`): when 
every argument is NOT NULL, there is no `FILTER`, and the frame contains the 
current row, the result can't be NULL, so the ordering holds with NULLs at 
either end and both can be added. With both changes every sqllogictest file 
passes unchanged. Both rules assume a set-monotonic aggregate is NULL only 
before it has seen a non-NULL input, which would be worth one sentence in the 
`SetMonotonicity` docs.
   
   Sliding frames (`N PRECEDING AND CURRENT ROW`) use a third rule with its own 
bugs; I filed that as #27422, so this fix doesn't need to cover it.
   
   Could you take this approach in your PR? The patch I tried and three more 
queries that return the wrong order on main are below.
   
   <details><summary>Patch I tried on main, and the 5 snapshots it 
changes</summary>
   
   ```diff
   diff --git a/datafusion/physical-expr/src/aggregate.rs 
b/datafusion/physical-expr/src/aggregate.rs
   index 4b6af0a434..1d31239f16 100644
   --- a/datafusion/physical-expr/src/aggregate.rs
   +++ b/datafusion/physical-expr/src/aggregate.rs
   @@ -1126,8 +1126,9 @@ impl AggregateFunctionExpr {
                return None;
            }
            let expr = Arc::new(Column::new(self.name(), aggr_func_idx));
   -        let options =
   -            SortOptions::new(monotonicity == SetMonotonicity::Decreasing, 
false);
   +        // The frame only grows, so the result is NULL until the first
   +        // non-NULL input enters it and never NULL after: NULLs come first.
   +        let options = SortOptions::new(monotonicity == 
SetMonotonicity::Decreasing, true);
            Some(PhysicalSortExpr { expr, options })
        }
    }
   diff --git a/datafusion/physical-expr/src/window/aggregate.rs 
b/datafusion/physical-expr/src/window/aggregate.rs
   index f57d70dd24..43359aa596 100644
   --- a/datafusion/physical-expr/src/window/aggregate.rs
   +++ b/datafusion/physical-expr/src/window/aggregate.rs
   @@ -121,6 +121,16 @@ impl PlainAggregateWindowExpr {
                .get_aggregate_expr()
                .get_result_ordering(window_expr_index)
            {
   +            if result_never_null(self, eq_properties.schema()) {
   +                // No NULLs, so the ordering holds with NULLs at either end.
   +                let mut flipped = expr.clone();
   +                flipped.options.nulls_first = !flipped.options.nulls_first;
   +                add_new_ordering_expr_with_partition_by(
   +                    eq_properties,
   +                    flipped,
   +                    &self.partition_by,
   +                )?;
   +            }
                add_new_ordering_expr_with_partition_by(
                    eq_properties,
                    expr,
   @@ -290,3 +300,27 @@ impl AggregateWindowExpr for PlainAggregateWindowExpr {
            self.is_constant_in_partition
        }
    }
   +
   +/// Returns true if a set-monotonic window aggregate never returns NULL:
   +/// every argument is NOT NULL, there is no FILTER, and the frame always
   +/// contains the current row. COUNT, SUM, MIN and MAX return a non-NULL
   +/// value for any non-empty set of non-NULL inputs.
   +pub fn result_never_null(
   +    expr: &dyn AggregateWindowExpr,
   +    schema: &arrow::datatypes::Schema,
   +) -> bool {
   +    let frame = expr.get_window_frame();
   +    let frame_has_current_row = matches!(
   +        frame.start_bound,
   +        WindowFrameBound::Preceding(_) | WindowFrameBound::CurrentRow
   +    ) && matches!(
   +        frame.end_bound,
   +        WindowFrameBound::CurrentRow | WindowFrameBound::Following(_)
   +    );
   +    expr.filter_expr().is_none()
   +        && frame_has_current_row
   +        && expr
   +            .expressions()
   +            .iter()
   +            .all(|arg| matches!(arg.nullable(schema), Ok(false)))
   +}
   diff --git a/datafusion/physical-expr/src/window/mod.rs 
b/datafusion/physical-expr/src/window/mod.rs
   index 0fe416d45b..64924f429e 100644
   --- a/datafusion/physical-expr/src/window/mod.rs
   +++ b/datafusion/physical-expr/src/window/mod.rs
   @@ -8,7 +8,7 @@ mod standard;
    mod standard_window_function_expr;
    mod window_expr;
    
   -pub use aggregate::PlainAggregateWindowExpr;
   +pub use aggregate::{PlainAggregateWindowExpr, result_never_null};
    pub use sliding_aggregate::SlidingAggregateWindowExpr;
    pub use standard::StandardWindowExpr;
    pub use standard_window_function_expr::StandardWindowFunctionExpr;
   diff --git a/datafusion/physical-plan/src/windows/mod.rs 
b/datafusion/physical-plan/src/windows/mod.rs
   index 404f225387..7d814f09d6 100644
   --- a/datafusion/physical-plan/src/windows/mod.rs
   +++ b/datafusion/physical-plan/src/windows/mod.rs
   @@ -31,7 +31,7 @@ use 
datafusion_functions_window_common::partition::PartitionEvaluatorArgs;
    use datafusion_physical_expr::aggregate::{AggregateExprBuilder, 
AggregateFunctionExpr};
    use datafusion_physical_expr::expressions::Column;
    use datafusion_physical_expr::window::{
   -    SlidingAggregateWindowExpr, StandardWindowFunctionExpr,
   +    SlidingAggregateWindowExpr, StandardWindowFunctionExpr, 
result_never_null,
    };
    use datafusion_physical_expr::{ConstExpr, EquivalenceProperties};
    use datafusion_physical_expr_common::sort_expr::{
   @@ -481,22 +481,33 @@ pub(crate) fn window_equivalence_properties(
                    // monotonicity, we can utilize it to introduce new 
orderings.
                    let frame = sliding_expr.get_window_frame();
                    if frame.end_bound.is_unbounded() {
   +                    // The frame only shrinks, so once it holds no non-NULL
   +                    // input the result stays NULL: NULLs come last.
                        let increasing = 
set_monotonicity.eq(&SetMonotonicity::Increasing);
                        let window_col = Column::new(expr.name(), i + 
input_schema_len);
   -                    if no_partitioning {
   -                        // Reverse set-monotonic cases with no partitioning:
   -                        
window_eq_properties.add_ordering([PhysicalSortExpr::new(
   -                            Arc::new(window_col),
   -                            SortOptions::new(increasing, true),
   -                        )]);
   +                    // No NULLs, so the ordering holds with NULLs at either 
end.
   +                    let nulls_first_options = if 
result_never_null(sliding_expr, schema) {
   +                        vec![false, true]
                        } else {
   -                        // Reverse set-monotonic cases for all orderings:
   -                        for mut lex in all_satisfied_lexs.into_iter() {
   -                            lex.push(PhysicalSortExpr::new(
   +                        vec![false]
   +                    };
   +                    for nulls_first in nulls_first_options {
   +                        let options = SortOptions::new(increasing, 
nulls_first);
   +                        if no_partitioning {
   +                            // Reverse set-monotonic cases with no 
partitioning:
   +                            
window_eq_properties.add_ordering([PhysicalSortExpr::new(
                                    Arc::new(window_col.clone()),
   -                                SortOptions::new(increasing, true),
   -                            ));
   -                            window_eq_properties.add_ordering(lex);
   +                                options,
   +                            )]);
   +                        } else {
   +                            // Reverse set-monotonic cases for all 
orderings:
   +                            for mut lex in 
all_satisfied_lexs.clone().into_iter() {
   +                                lex.push(PhysicalSortExpr::new(
   +                                    Arc::new(window_col.clone()),
   +                                    options,
   +                                ));
   +                                window_eq_properties.add_ordering(lex);
   +                            }
                            }
                        }
                    }
   ```
   
   Snapshots that change in `enforce_sorting_monotonicity.rs`:
   - cases 17, 18: the sort is now kept (main removed it with NULLs on the 
wrong end)
   - cases 22, 38: the sort is now removed
   - case 34: the sort is now kept; a running `MIN` over input sorted by its 
own argument is constant, which neither rule knows
   </details>
   
   <details><summary>Three more queries that return the wrong order on main 
(correct with the patch)</summary>
   
   ```sql
   set datafusion.execution.target_partitions = 1;
   CREATE TABLE n(ts INT NOT NULL, x INT NOT NULL) AS VALUES (1, 1), (2, 3), 
(3, 2), (4, 5);
   
   -- FILTER: ts=1 has m NULL and comes first; expected last
   SELECT ts, m FROM (SELECT ts, MAX(x) FILTER (WHERE x > 2) OVER (ORDER BY ts) 
AS m FROM n) ORDER BY m ASC NULLS LAST;
   
   -- frame skips the current row: ts=1 has m NULL and comes first; expected 
last
   SELECT ts, m FROM (SELECT ts, MAX(x) OVER (ORDER BY ts ROWS BETWEEN 
UNBOUNDED PRECEDING AND 1 PRECEDING) AS m FROM n) ORDER BY m ASC NULLS LAST;
   
   -- shrinking frame after the current row: ts=4 has m NULL and comes last; 
expected first
   SELECT ts, m FROM (SELECT ts, MAX(x) OVER (ORDER BY ts ROWS BETWEEN 1 
FOLLOWING AND UNBOUNDED FOLLOWING) AS m FROM n) ORDER BY m DESC NULLS FIRST;
   ```
   </details>
   


-- 
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]

Reply via email to