Skip to content

Commit 11c0878

Browse files
committed
refactor: check partial constants as a sort direction plus its reverse
1 parent 751e171 commit 11c0878

2 files changed

Lines changed: 88 additions & 42 deletions

File tree

‎datafusion/physical-expr/src/equivalence/ordering.rs‎

Lines changed: 87 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ use crate::{LexOrdering, PhysicalExpr, add_offset_to_physical_sort_exprs};
2525

2626
use arrow::compute::SortOptions;
2727
use arrow::datatypes::SchemaRef;
28-
use datafusion_common::{HashSet, Result};
28+
use datafusion_common::Result;
2929
use 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`].
261256
pub(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

286272
impl 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
}

‎datafusion/physical-expr/src/equivalence/properties/walk.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -260,7 +260,7 @@ impl<'a> Walk<'a> {
260260
}
261261

262262
/// The head of each ordering that has one.
263-
fn heads(&self) -> impl Iterator<Item = &PhysicalSortExpr> {
263+
fn heads(&self) -> impl Iterator<Item = &PhysicalSortExpr> + Clone {
264264
let orderings = self.props.oeq_cache.normal_cls.iter().chain(&self.implied);
265265
orderings.enumerate().filter_map(|(idx, ordering)| {
266266
ordering.get(self.head_idxs.get(idx).copied().unwrap_or(0))

0 commit comments

Comments
 (0)