fn discover_new_orderings()

in datafusion/physical-expr/src/equivalence/properties/mod.rs [367:441]
60 lines of code
14 McCabe index (conditional complexity)

    fn discover_new_orderings(&mut self, expr: &Arc<dyn PhysicalExpr>) -> Result<()> {
        let normalized_expr = self.eq_group().normalize_expr(Arc::clone(expr));
        let eq_class = self
            .eq_group
            .iter()
            .find_map(|class| {
                class
                    .contains(&normalized_expr)
                    .then(|| class.clone().into_vec())
            })
            .unwrap_or_else(|| vec![Arc::clone(&normalized_expr)]);

        let mut new_orderings: Vec<LexOrdering> = vec![];
        for ordering in self.normalized_oeq_class().iter() {
            if !ordering[0].expr.eq(&normalized_expr) {
                continue;
            }

            let leading_ordering_options = ordering[0].options;

            for equivalent_expr in &eq_class {
                let children = equivalent_expr.children();
                if children.is_empty() {
                    continue;
                }

                // Check if all children match the next expressions in the ordering
                let mut all_children_match = true;
                let mut child_properties = vec![];

                // Build properties for each child based on the next expressions
                for (i, child) in children.iter().enumerate() {
                    if let Some(next) = ordering.get(i + 1) {
                        if !child.as_ref().eq(next.expr.as_ref()) {
                            all_children_match = false;
                            break;
                        }
                        child_properties.push(ExprProperties {
                            sort_properties: SortProperties::Ordered(next.options),
                            range: Interval::make_unbounded(
                                &child.data_type(&self.schema)?,
                            )?,
                            preserves_lex_ordering: true,
                        });
                    } else {
                        all_children_match = false;
                        break;
                    }
                }

                if all_children_match {
                    // Check if the expression is monotonic in all arguments
                    if let Ok(expr_properties) =
                        equivalent_expr.get_properties(&child_properties)
                    {
                        if expr_properties.preserves_lex_ordering
                            && SortProperties::Ordered(leading_ordering_options)
                                == expr_properties.sort_properties
                        {
                            // Assume existing ordering is [c ASC, a ASC, b ASC]
                            // When equality c = f(a,b) is given, if we know that given ordering `[a ASC, b ASC]`,
                            // ordering `[f(a,b) ASC]` is valid, then we can deduce that ordering `[a ASC, b ASC]` is also valid.
                            // Hence, ordering `[a ASC, b ASC]` can be added to the state as a valid ordering.
                            // (e.g. existing ordering where leading ordering is removed)
                            new_orderings.push(LexOrdering::new(ordering[1..].to_vec()));
                            break;
                        }
                    }
                }
            }
        }

        self.oeq_class.add_new_orderings(new_orderings);
        Ok(())
    }