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