@@ -25,7 +25,7 @@ use crate::{LexOrdering, PhysicalExpr, add_offset_to_physical_sort_exprs};
2525
2626use arrow:: compute:: SortOptions ;
2727use arrow:: datatypes:: SchemaRef ;
28- use datafusion_common:: { HashSet , Result } ;
28+ use datafusion_common:: Result ;
2929use datafusion_physical_expr_common:: sort_expr:: PhysicalSortExpr ;
3030
3131/// An `OrderingEquivalenceClass` keeps track of distinct alternative orderings
@@ -223,25 +223,19 @@ impl OrderingEquivalenceClass {
223223 None
224224 }
225225
226- /// Checks whether the given expression is partially constant according to
227- /// this ordering equivalence class.
226+ /// Checks whether `expr` has a single value according to this ordering
227+ /// equivalence class: whether one ordering starts with `expr` in some
228+ /// direction and another starts with it in the exact reverse, such as
229+ /// `ASC NULLS LAST` and `DESC NULLS FIRST`. Rows sorted both ways all have
230+ /// the same value (or are all null).
228231 ///
229- /// This function determines whether `expr` appears in at least one combination
230- /// of `descending` and `nulls_first` options that indicate partial constantness
231- /// in a lexicographical ordering. Specifically, an expression is considered
232- /// a partial constant in this context if its `SortOptions` satisfies either
233- /// of the following conditions:
234- /// - It is `descending` with `nulls_first` and _also_ `ascending` with
235- /// `nulls_last`, OR
236- /// - It is `descending` with `nulls_last` and _also_ `ascending` with
237- /// `nulls_first`.
238- ///
239- /// The equivalence mechanism primarily uses `ConstExpr`s to represent globally
240- /// constant expressions. However, some expressions may only be partially
241- /// constant within a lexicographical ordering. This function helps identify
242- /// such cases. If an expression is constant within a prefix ordering, it is
243- /// pinned during `ordering_satisfy_requirement()` iterations after the
244- /// corresponding prefix requirement is satisfied.
232+ /// This is how a value that is constant only within groups of rows is
233+ /// recorded, since a `ConstExpr` is constant across all rows. For example,
234+ /// `SUM(x) OVER (PARTITION BY k)` has one value per `k`, so the window adds
235+ /// `[k, w]` once for each of the four directions of `w`. Sort requirement
236+ /// checks look at the orderings past the keys they have satisfied, so once
237+ /// `k` is satisfied they see `w` in opposite directions, and `w` counts as
238+ /// constant.
245239 ///
246240 /// ### Future Improvements
247241 ///
@@ -255,32 +249,24 @@ impl OrderingEquivalenceClass {
255249 }
256250}
257251
258- /// Checks whether `expr` is partially constant according to the given leading
259- /// sort expressions of some orderings. See
252+ /// Checks whether `expr` has a single value according to the leading sort
253+ /// expressions of some orderings: whether `expr` leads one of them in some
254+ /// direction and another in the exact reverse. See
260255/// [`OrderingEquivalenceClass::is_expr_partial_const`].
261256pub ( crate ) fn is_partial_const < ' a > (
262- leading : impl IntoIterator < Item = & ' a PhysicalSortExpr > ,
257+ leading : impl Iterator < Item = & ' a PhysicalSortExpr > + Clone ,
263258 expr : & Arc < dyn PhysicalExpr > ,
264259) -> bool {
265- let mut constantness_defining_pairs = [
266- HashSet :: from ( [ ( false , false ) , ( true , true ) ] ) ,
267- HashSet :: from ( [ ( false , true ) , ( true , false ) ] ) ,
268- ] ;
269-
270- for leading_ordering in leading {
271- if leading_ordering. expr . eq ( expr) {
272- let opt = (
273- leading_ordering. options . descending ,
274- leading_ordering. options . nulls_first ,
275- ) ;
276- constantness_defining_pairs[ 0 ] . remove ( & opt) ;
277- constantness_defining_pairs[ 1 ] . remove ( & opt) ;
278- }
279- }
280-
281- constantness_defining_pairs
282- . iter ( )
283- . any ( |pair| pair. is_empty ( ) )
260+ let leads_in = move |options : SortOptions | {
261+ leading
262+ . clone ( )
263+ . any ( |sort_expr| sort_expr. options == options && sort_expr. expr . eq ( expr) )
264+ } ;
265+ // `!` gives the exact reverse, e.g. `DESC NULLS FIRST` for `ASC NULLS LAST`.
266+ let asc_nulls_first = SortOptions :: default ( ) . asc ( ) . nulls_first ( ) ;
267+ let asc_nulls_last = SortOptions :: default ( ) . asc ( ) . nulls_last ( ) ;
268+ ( leads_in ( asc_nulls_first) && leads_in ( !asc_nulls_first) )
269+ || ( leads_in ( asc_nulls_last) && leads_in ( !asc_nulls_last) )
284270}
285271
286272impl Deref for OrderingEquivalenceClass {
@@ -1000,4 +986,64 @@ mod tests {
1000986
1001987 Ok ( ( ) )
1002988 }
989+
990+ #[ test]
991+ fn test_is_expr_partial_const ( ) -> Result < ( ) > {
992+ let schema = create_test_schema ( ) ?;
993+ let col_a = & col ( "a" , & schema) ?;
994+ let col_b = & col ( "b" , & schema) ?;
995+ let [
996+ asc_nulls_last,
997+ asc_nulls_first,
998+ desc_nulls_last,
999+ desc_nulls_first,
1000+ ] = [ ( false , false ) , ( false , true ) , ( true , false ) , ( true , true ) ] . map (
1001+ |( descending, nulls_first) | SortOptions {
1002+ descending,
1003+ nulls_first,
1004+ } ,
1005+ ) ;
1006+
1007+ // The leading sort expression of each ordering, and whether `a` has a
1008+ // single value according to them.
1009+ let test_cases = vec ! [
1010+ // A direction and its exact reverse:
1011+ (
1012+ vec![ ( col_a, asc_nulls_last) , ( col_a, desc_nulls_first) ] ,
1013+ true ,
1014+ ) ,
1015+ (
1016+ vec![ ( col_a, asc_nulls_first) , ( col_a, desc_nulls_last) ] ,
1017+ true ,
1018+ ) ,
1019+ // Nulls first both ways, e.g. `NULL, NULL, 5, 5`:
1020+ (
1021+ vec![ ( col_a, asc_nulls_first) , ( col_a, desc_nulls_first) ] ,
1022+ false ,
1023+ ) ,
1024+ // Nulls last both ways, e.g. `5, 5, NULL, NULL`:
1025+ (
1026+ vec![ ( col_a, asc_nulls_last) , ( col_a, desc_nulls_last) ] ,
1027+ false ,
1028+ ) ,
1029+ ( vec![ ( col_a, asc_nulls_last) ] , false ) ,
1030+ // The reverse direction belongs to another expression:
1031+ (
1032+ vec![ ( col_a, asc_nulls_last) , ( col_b, desc_nulls_first) ] ,
1033+ false ,
1034+ ) ,
1035+ ] ;
1036+ for ( leading, expected) in test_cases {
1037+ let oeq_class = OrderingEquivalenceClass :: new ( leading. into_iter ( ) . map (
1038+ |( expr, options) | [ PhysicalSortExpr :: new ( Arc :: clone ( expr) , options) ] ,
1039+ ) ) ;
1040+ assert_eq ! (
1041+ oeq_class. is_expr_partial_const( col_a) ,
1042+ expected,
1043+ "{oeq_class}"
1044+ ) ;
1045+ }
1046+
1047+ Ok ( ( ) )
1048+ }
10031049}
0 commit comments