Skip to content

Commit ab1e94a

Browse files
alambjayzhan211claude
authored
[branch-56] fix: SanityCheckPlan error when a per-partition constant leads an ordering (backport #27191) (#27368)
## Which issue does this PR close? - part of #24461 - Backport of #27191 to `branch-56` - Related to #26762. Co-authored-by: Jay Zhan <[email protected]> Co-authored-by: Claude Fable 5.1 <[email protected]>
1 parent cbd63d9 commit ab1e94a

5 files changed

Lines changed: 890 additions & 27 deletions

File tree

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

Lines changed: 93 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -353,7 +353,8 @@ impl EquivalenceProperties {
353353
}
354354
}
355355

356-
/// Adds new orderings into the existing ordering equivalence class.
356+
/// Adds new orderings into the existing ordering equivalence class, along
357+
/// with the orderings they imply through known equalities.
357358
pub fn add_orderings(
358359
&mut self,
359360
orderings: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
@@ -365,14 +366,32 @@ impl EquivalenceProperties {
365366
.cloned()
366367
.filter_map(|o| self.normalize_sort_exprs(o))
367368
.collect();
368-
if !normal_orderings.is_empty() {
369-
self.oeq_class.extend(orderings);
370-
// Normalize given orderings to update the cache:
371-
self.oeq_cache.normal_cls.extend(normal_orderings);
372-
// TODO: If no ordering is found to be redundant during extension, we
373-
// can use a shortcut algorithm to update the leading map.
374-
self.oeq_cache.update_map();
369+
if normal_orderings.is_empty() {
370+
return;
375371
}
372+
// `add_constants` and `add_equal_conditions` discover implied orderings
373+
// too, and whether an ordering is satisfied must not depend on which of
374+
// them ran last. Deriving one fails only on an expression that does not
375+
// match the schema; that ordering is then not implied, which can cost a
376+
// sort but not a wrong result.
377+
let mut implied: Vec<LexOrdering> = vec![];
378+
for ordering in &normal_orderings {
379+
// Two orderings can imply the same one; expand it only once:
380+
for ordering in self.implied_by(ordering).unwrap_or_default() {
381+
if !implied.contains(&ordering) {
382+
implied.push(ordering);
383+
}
384+
}
385+
}
386+
self.oeq_class.extend(orderings);
387+
// Normalize given orderings to update the cache:
388+
self.oeq_cache.normal_cls.extend(normal_orderings);
389+
// TODO: If no ordering is found to be redundant during extension, we
390+
// can use a shortcut algorithm to update the leading map.
391+
self.oeq_cache.update_map();
392+
// Each implied ordering is shorter than the one implying it, so this
393+
// terminates:
394+
self.add_orderings(implied);
376395
}
377396

378397
/// Adds a single ordering to the existing ordering equivalence class.
@@ -479,15 +498,76 @@ impl EquivalenceProperties {
479498
let mut new_orderings = vec![];
480499
for idx in ordering_idxs {
481500
let ordering = &self.oeq_cache.normal_cls[*idx];
482-
new_orderings
483-
.extend(self.implied_ordering(&ordering[0], ordering[1..].iter())?);
484-
}
485-
if !new_orderings.is_empty() {
486-
self.add_orderings(new_orderings);
501+
// As in `add_orderings`, an ordering that cannot be derived is
502+
// not implied, so the result does not depend on the call order:
503+
new_orderings.extend(self.implied_by(ordering).unwrap_or_default());
487504
}
505+
self.add_orderings(new_orderings);
488506
Ok(())
489507
}
490508

509+
/// Returns the orderings that the normal ordering `ordering` implies
510+
/// through known equalities: for each key that is a function of the keys
511+
/// after it (see [`Self::implied_ordering`]), `ordering` without that key.
512+
///
513+
/// # Example: a key that is a function of the keys after it
514+
///
515+
/// * Ordering: `[k ASC, a ASC, c ASC]`
516+
/// * Equality: `a = CAST(c AS DATE)`
517+
/// * Returns: `[k ASC, c ASC]`
518+
///
519+
/// Among the rows that tie on `k`, the rows are sorted by `a`, and the
520+
/// rows that also tie on `a` are sorted by `c`. `a` is the date of `c`, so
521+
/// a row with an earlier `a` also has an earlier `c`, and the rows that
522+
/// tie on `k` are sorted by `c` alone:
523+
///
524+
/// ```text
525+
/// ┌───┬────────────┬──────────────────┐
526+
/// │ k │ a │ c │
527+
/// ├───┼────────────┼──────────────────┤
528+
/// │ x │ 2026-01-01 │ 2026-01-01 09:00 │
529+
/// │ x │ 2026-01-02 │ 2026-01-02 01:00 │
530+
/// │ x │ 2026-01-02 │ 2026-01-02 05:00 │
531+
/// │ y │ 2026-01-01 │ 2026-01-01 03:00 │
532+
/// └───┴────────────┴──────────────────┘
533+
/// ```
534+
///
535+
/// # Example: a constant that differs between partitions
536+
///
537+
/// * Ordering: `[k ASC, a ASC, c ASC]`, where `k` is a constant whose value
538+
/// differs between partitions
539+
/// * Equality: `a = CAST(c AS DATE)`
540+
/// * Returns: `[c ASC]`
541+
///
542+
/// A normal ordering can keep such a constant (see
543+
/// `EquivalenceGroup::normalize_sort_exprs`). Within a partition `k` has
544+
/// one value, so it is left out of the keys and of the result.
545+
///
546+
/// # Example: directions that differ
547+
///
548+
/// * Ordering: `[a ASC, c DESC]`
549+
/// * Equality: `a = CAST(c AS DATE)`
550+
/// * Returns: nothing
551+
///
552+
/// `c` descends within a date but ascends across dates, so the rows are
553+
/// not sorted by `c` in either direction.
554+
fn implied_by(&self, ordering: &LexOrdering) -> Result<Vec<LexOrdering>> {
555+
let keys: Vec<_> = ordering
556+
.iter()
557+
.filter(|sort_expr| self.eq_group.is_expr_constant(&sort_expr.expr).is_none())
558+
.collect();
559+
let mut implied = vec![];
560+
for (idx, key) in keys.iter().enumerate() {
561+
if let Some(rest) =
562+
self.implied_ordering(key, keys[idx + 1..].iter().copied())?
563+
{
564+
let prefix = keys[..idx].iter().copied().cloned();
565+
implied.extend(LexOrdering::new(prefix.chain(rest)));
566+
}
567+
}
568+
Ok(implied)
569+
}
570+
491571
/// Returns the ordering that the normal ordering `[leading, rest..]`
492572
/// implies through an equality on its leading expression, if any.
493573
///

0 commit comments

Comments
 (0)