Skip to content

Commit c777864

Browse files
committed
fix: discover implied orderings when an ordering is added
1 parent 6e6a8ae commit c777864

3 files changed

Lines changed: 90 additions & 0 deletions

File tree

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

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -392,12 +392,27 @@ impl EquivalenceProperties {
392392
.filter_map(|o| self.normalize_sort_exprs(o))
393393
.collect();
394394
if !normal_orderings.is_empty() {
395+
// What the new orderings imply through known equalities. `add_constants`
396+
// and `add_equal_conditions` discover this too, and whether an ordering
397+
// is satisfied must not depend on which of them ran last. If it cannot
398+
// be derived, nothing is implied.
399+
let implied: Vec<_> = normal_orderings
400+
.iter()
401+
.filter_map(|ordering| {
402+
self.implied_ordering(&ordering[0], ordering[1..].iter())
403+
.ok()
404+
.flatten()
405+
})
406+
.collect();
395407
self.oeq_class.extend(orderings);
396408
// Normalize given orderings to update the cache:
397409
self.oeq_cache.normal_cls.extend(normal_orderings);
398410
// TODO: If no ordering is found to be redundant during extension, we
399411
// can use a shortcut algorithm to update the leading map.
400412
self.oeq_cache.update_map();
413+
// Each implied ordering is shorter than the one implying it, so this
414+
// terminates:
415+
self.add_orderings(implied);
401416
}
402417
}
403418

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

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -352,6 +352,40 @@ mod tests {
352352
};
353353
use datafusion_expr::{ColumnarValue, Operator, Volatility, create_udf};
354354

355+
/// With `CAST(c AS DATE) = a`, the ordering `[a, c]` implies `[c]`, whether
356+
/// the ordering or the equality comes first.
357+
#[test]
358+
fn implied_ordering_does_not_depend_on_call_order() -> Result<()> {
359+
let schema = Arc::new(Schema::new(vec![
360+
Field::new("a", DataType::Date32, true),
361+
Field::new("c", DataType::Timestamp(TimeUnit::Nanosecond, None), true),
362+
]));
363+
let [a, c] = ["a", "c"].map(|name| col(name, &schema).unwrap());
364+
let cast_c = Arc::new(CastExpr::new_with_target_field(
365+
Arc::clone(&c),
366+
Arc::new(Field::new("c", DataType::Date32, true)),
367+
None,
368+
)) as Arc<dyn PhysicalExpr>;
369+
let ordering =
370+
[&a, &c].map(|expr| PhysicalSortExpr::new_default(Arc::clone(expr)));
371+
372+
let mut equality_first = EquivalenceProperties::new(Arc::clone(&schema));
373+
equality_first.add_equal_conditions(Arc::clone(&cast_c), Arc::clone(&a))?;
374+
equality_first.add_ordering(ordering.clone());
375+
376+
let mut ordering_first = EquivalenceProperties::new(Arc::clone(&schema));
377+
ordering_first.add_ordering(ordering);
378+
ordering_first.add_equal_conditions(cast_c, Arc::clone(&a))?;
379+
380+
for properties in [equality_first, ordering_first] {
381+
assert!(
382+
properties
383+
.ordering_satisfy([PhysicalSortExpr::new_default(Arc::clone(&c))])?
384+
);
385+
}
386+
Ok(())
387+
}
388+
355389
/// A normal ordering keeps a constant whose value differs between
356390
/// partitions (`AcrossPartitions::Heterogeneous`), and such a constant
357391
/// can lead it. Within a partition the constant has one value, so it is

‎datafusion/sqllogictest/test_files/window.slt‎

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7926,6 +7926,47 @@ a 2026-01-02T01:00:00 2
79267926
a 2026-01-02T05:00:00 3
79277927
b 2026-01-03T01:00:00 4
79287928

7929+
# An ordering that a sort adds implies other orderings through known equalities,
7930+
# as it does when the equality comes after the sort: `[a, c]` with
7931+
# `a = CAST(c AS DATE)` has `[c]`.
7932+
query DPI
7933+
SELECT a, c, ROW_NUMBER() OVER (ORDER BY c) AS r
7934+
FROM (SELECT a, c FROM ordered_through_cast WHERE a = CAST(c AS DATE) ORDER BY a, c LIMIT 10)
7935+
ORDER BY r;
7936+
----
7937+
2026-01-01 2026-01-01T09:00:00 1
7938+
2026-01-02 2026-01-02T01:00:00 2
7939+
2026-01-02 2026-01-02T05:00:00 3
7940+
2026-01-03 2026-01-03T01:00:00 4
7941+
7942+
# The same with a per-partition constant leading the sort.
7943+
query TDPI
7944+
SELECT k, a, c, ROW_NUMBER() OVER (ORDER BY c) AS r
7945+
FROM (SELECT lower(k) AS k, a, c FROM ordered_through_cast WHERE k = 'a' AND a = CAST(c AS DATE) ORDER BY k, a, c LIMIT 10)
7946+
ORDER BY r;
7947+
----
7948+
a 2026-01-01 2026-01-01T09:00:00 1
7949+
a 2026-01-02 2026-01-02T01:00:00 2
7950+
a 2026-01-02 2026-01-02T05:00:00 3
7951+
7952+
# And when a merge of partitions is added above the sort, which keeps only its
7953+
# merge key.
7954+
statement ok
7955+
set datafusion.execution.target_partitions = 4;
7956+
7957+
query DPI
7958+
SELECT a, c, ROW_NUMBER() OVER (ORDER BY c) AS r
7959+
FROM (SELECT a, c FROM ordered_through_cast WHERE a = CAST(c AS DATE) ORDER BY a, c LIMIT 10)
7960+
ORDER BY r;
7961+
----
7962+
2026-01-01 2026-01-01T09:00:00 1
7963+
2026-01-02 2026-01-02T01:00:00 2
7964+
2026-01-02 2026-01-02T05:00:00 3
7965+
2026-01-03 2026-01-03T01:00:00 4
7966+
7967+
statement ok
7968+
set datafusion.execution.target_partitions = 1;
7969+
79297970
statement ok
79307971
DROP TABLE ordered_through_cast;
79317972

0 commit comments

Comments
 (0)