## Coverage Report

#### Created: 2025-11-22 06:00

next uncovered line (L), next uncovered region (R), next uncovered branch (B)

    /Users/andrewlamb/Software/datafusion/datafusion/physical-expr/src/equivalence/properties/dependency.rs

    Line
    Count
    Source
    1
    // Licensed to the Apache Software Foundation (ASF) under one
    2
    // or more contributor license agreements.  See the NOTICE file
    3
    // distributed with this work for additional information
    4
    // regarding copyright ownership.  The ASF licenses this file
    5
    // to you under the Apache License, Version 2.0 (the
    6
    // "License"); you may not use this file except in compliance
    7
    // with the License.  You may obtain a copy of the License at
    8
    //
    9
    //   http://www.apache.org/licenses/LICENSE-2.0
    10
    //
    11
    // Unless required by applicable law or agreed to in writing,
    12
    // software distributed under the License is distributed on an
    13
    // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
    14
    // KIND, either express or implied.  See the License for the
    15
    // specific language governing permissions and limitations
    16
    // under the License.
    17
    18
    use std::fmt::{self, Display};
    19
    use std::ops::{Deref, DerefMut};
    20
    use std::sync::Arc;
    21
    22
    use super::expr_refers;
    23
    use crate::{LexOrdering, PhysicalSortExpr};
    24
    25
    use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
    26
    27
    use indexmap::{IndexMap, IndexSet};
    28
    use itertools::Itertools;
    29
    30
    // A list of sort expressions that can be calculated from a known set of
    31
    /// dependencies.
    32
    #[derive(Debug, Default, Clone, PartialEq, Eq)]
    33
    pub struct Dependencies {
    34
        sort_exprs: IndexSet<PhysicalSortExpr>,
    35
    }
    36
    37
    impl Display for Dependencies {
    38
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    39
    0
            write!(f, "[")?;
    40
    0
            let mut iter = self.sort_exprs.iter();
    41
    0
            if let Some(dep) = iter.next() {
    42
    0
                write!(f, "{dep}")?;
    43
    0
            }
    44
    0
            for dep in iter {
    45
    0
                write!(f, ", {dep}")?;
    46
            }
    47
    0
            write!(f, "]")
    48
    0
        }
    49
    }
    50
    51
    impl Dependencies {
    52
        // Creates a new `Dependencies` instance from the given sort expressions.
    53
    0
        pub fn new(sort_exprs: impl IntoIterator<Item = PhysicalSortExpr>) -> Self {
    54
    0
            Self {
    55
    0
                sort_exprs: sort_exprs.into_iter().collect(),
    56
    0
            }
    57
    0
        }
    58
    }
    59
    60
    impl Deref for Dependencies {
    61
        type Target = IndexSet<PhysicalSortExpr>;
    62
    63
    0
        fn deref(&self) -> &Self::Target {
    64
    0
            &self.sort_exprs
    65
    0
        }
    66
    }
    67
    68
    impl DerefMut for Dependencies {
    69
    0
        fn deref_mut(&mut self) -> &mut Self::Target {
    70
    0
            &mut self.sort_exprs
    71
    0
        }
    72
    }
    73
    74
    impl IntoIterator for Dependencies {
    75
        type Item = PhysicalSortExpr;
    76
        type IntoIter = <IndexSet<PhysicalSortExpr> as IntoIterator>::IntoIter;
    77
    78
    0
        fn into_iter(self) -> Self::IntoIter {
    79
    0
            self.sort_exprs.into_iter()
    80
    0
        }
    81
    }
    82
    83
    /// Contains a mapping of all dependencies we have processed for each sort expr
    84
    pub struct DependencyEnumerator<'a> {
    85
        /// Maps `expr` --> `[exprs]` that have previously been processed
    86
        seen: IndexMap<&'a PhysicalSortExpr, IndexSet<&'a PhysicalSortExpr>>,
    87
    }
    88
    89
    impl<'a> DependencyEnumerator<'a> {
    90
    0
        pub fn new() -> Self {
    91
    0
            Self {
    92
    0
                seen: IndexMap::new(),
    93
    0
            }
    94
    0
        }
    95
    96
        /// Insert a new dependency,
    97
        ///
    98
        /// returns false if the dependency was already in the map
    99
        /// returns true if the dependency was newly inserted
    100
    0
        fn insert(
    101
    0
            &mut self,
    102
    0
            target: &'a PhysicalSortExpr,
    103
    0
            dep: &'a PhysicalSortExpr,
    104
    0
        ) -> bool {
    105
    0
            self.seen.entry(target).or_default().insert(dep)
    106
    0
        }
    107
    108
        /// This function recursively analyzes the dependencies of the given sort
    109
        /// expression within the given dependency map to construct lexicographical
    110
        /// orderings that include the sort expression and its dependencies.
    111
        ///
    112
        /// # Parameters
    113
        ///
    114
        /// - `referred_sort_expr`: A reference to the sort expression (`PhysicalSortExpr`)
    115
        ///   for which lexicographical orderings satisfying its dependencies are to be
    116
        ///   constructed.
    117
        /// - `dependency_map`: A reference to the `DependencyMap` that contains
    118
        ///   dependencies for different `PhysicalSortExpr`s.
    119
        ///
    120
        /// # Returns
    121
        ///
    122
        /// A vector of lexicographical orderings (`Vec<LexOrdering>`) based on the given
    123
        /// sort expression and its dependencies.
    124
    0
        pub fn construct_orderings(
    125
    0
            &mut self,
    126
    0
            referred_sort_expr: &'a PhysicalSortExpr,
    127
    0
            dependency_map: &'a DependencyMap,
    128
    0
        ) -> Vec<LexOrdering> {
    129
    0
            let node = dependency_map
    130
    0
                .get(referred_sort_expr)
    131
    0
                .expect("`referred_sort_expr` should be inside `dependency_map`");
    132
            // Since we work on intermediate nodes, we are sure `node.target` exists.
    133
    0
            let target = node.target.as_ref().unwrap();
    134
            // An empty dependency means the referred_sort_expr represents a global ordering.
    135
            // Return its projected version, which is the target_expression.
    136
    0
            if node.dependencies.is_empty() {
    137
    0
                return vec![[target.clone()].into()];
    138
    0
            };
    139
    140
    0
            node.dependencies
    141
    0
                .iter()
    142
    0
                .flat_map(|dep| {
    143
    0
                    let mut orderings = if self.insert(target, dep) {
    144
    0
                        self.construct_orderings(dep, dependency_map)
    145
                    } else {
    146
    0
                        vec![]
    147
                    };
    148
    149
    0
                    for ordering in orderings.iter_mut() {
    150
    0
                        ordering.push(target.clone());
    151
    0
                    }
    152
    0
                    orderings
    153
    0
                })
    154
    0
                .collect()
    155
    0
        }
    156
    }
    157
    158
    /// Maps an expression --> DependencyNode
    159
    ///
    160
    /// # Debugging / deplaying `DependencyMap`
    161
    ///
    162
    /// This structure implements `Display` to assist debugging. For example:
    163
    ///
    164
    /// ```text
    165
    /// DependencyMap: {
    166
    ///   a@0 ASC --> (target: a@0 ASC, dependencies: [[]])
    167
    ///   b@1 ASC --> (target: b@1 ASC, dependencies: [[a@0 ASC, c@2 ASC]])
    168
    ///   c@2 ASC --> (target: c@2 ASC, dependencies: [[b@1 ASC, a@0 ASC]])
    169
    ///   d@3 ASC --> (target: d@3 ASC, dependencies: [[c@2 ASC, b@1 ASC]])
    170
    /// }
    171
    /// ```
    172
    ///
    173
    /// # Note on IndexMap Rationale
    174
    ///
    175
    /// Using `IndexMap` (which preserves insert order) to ensure consistent results
    176
    /// across different executions for the same query. We could have used `HashSet`
    177
    /// and `HashMap` instead without any loss of functionality.
    178
    ///
    179
    /// As an example, if existing orderings are
    180
    /// 1. `[a ASC, b ASC]`
    181
    /// 2. `[c ASC]`
    182
    ///
    183
    /// Then both the following output orderings are valid
    184
    /// 1. `[a ASC, b ASC, c ASC]`
    185
    /// 2. `[c ASC, a ASC, b ASC]`
    186
    ///
    187
    /// These are both valid as they are concatenated versions of the alternative
    188
    /// orderings. Had we used `HashSet`/`HashMap`, we couldn't guarantee to generate
    189
    /// the same result among the possible two results in the example above.
    190
    #[derive(Debug, Default)]
    191
    pub struct DependencyMap {
    192
        map: IndexMap<PhysicalSortExpr, DependencyNode>,
    193
    }
    194
    195
    impl DependencyMap {
    196
        /// Insert a new dependency of `sort_expr` (i.e. `dependency`) into the map
    197
        /// along with its target sort expression.
    198
    0
        pub fn insert(
    199
    0
            &mut self,
    200
    0
            sort_expr: PhysicalSortExpr,
    201
    0
            target_sort_expr: Option<PhysicalSortExpr>,
    202
    0
            dependency: Option<PhysicalSortExpr>,
    203
    0
        ) {
    204
    0
            let entry = self.map.entry(sort_expr);
    205
    0
            let node = entry.or_insert_with(|| DependencyNode {
    206
    0
                target: target_sort_expr,
    207
    0
                dependencies: Dependencies::default(),
    208
    0
            });
    209
    0
            node.dependencies.extend(dependency);
    210
    0
        }
    211
    }
    212
    213
    impl Deref for DependencyMap {
    214
        type Target = IndexMap<PhysicalSortExpr, DependencyNode>;
    215
    216
    0
        fn deref(&self) -> &Self::Target {
    217
    0
            &self.map
    218
    0
        }
    219
    }
    220
    221
    impl Display for DependencyMap {
    222
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    223
    0
            writeln!(f, "DependencyMap: {{")?;
    224
    0
            for (sort_expr, node) in self.map.iter() {
    225
    0
                writeln!(f, "  {sort_expr} --> {node}")?;
    226
            }
    227
    0
            writeln!(f, "}}")
    228
    0
        }
    229
    }
    230
    231
    /// Represents a node in the dependency map used to construct projected orderings.
    232
    ///
    233
    /// A `DependencyNode` contains information about a particular sort expression,
    234
    /// including its target sort expression and a set of dependencies on other sort
    235
    /// expressions.
    236
    ///
    237
    /// # Fields
    238
    ///
    239
    /// - `target`: An optional `PhysicalSortExpr` representing the target sort
    240
    ///   expression associated with the node. It is `None` if the sort expression
    241
    ///   cannot be projected.
    242
    /// - `dependencies`: A [`Dependencies`] containing dependencies on other sort
    243
    ///   expressions that are referred to by the target sort expression.
    244
    #[derive(Debug, Clone, PartialEq, Eq)]
    245
    pub struct DependencyNode {
    246
        pub(crate) target: Option<PhysicalSortExpr>,
    247
        pub(crate) dependencies: Dependencies,
    248
    }
    249
    250
    impl Display for DependencyNode {
    251
    0
        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    252
    0
            if let Some(target) = &self.target {
    253
    0
                write!(f, "(target: {target}, ")?;
    254
            } else {
    255
    0
                write!(f, "(")?;
    256
            }
    257
    0
            write!(f, "dependencies: [{}])", self.dependencies)
    258
    0
        }
    259
    }
    260
    261
    /// This function analyzes the dependency map to collect referred dependencies for
    262
    /// a given source expression.
    263
    ///
    264
    /// # Parameters
    265
    ///
    266
    /// - `dependency_map`: A reference to the `DependencyMap` where each
    267
    ///   `PhysicalSortExpr` is associated with a `DependencyNode`.
    268
    /// - `source`: A reference to the source expression (`Arc<dyn PhysicalExpr>`)
    269
    ///   for which relevant dependencies need to be identified.
    270
    ///
    271
    /// # Returns
    272
    ///
    273
    /// A `Vec<Dependencies>` containing the dependencies for the given source
    274
    /// expression. These dependencies are expressions that are referred to by
    275
    /// the source expression based on the provided dependency map.
    276
    0
    pub fn referred_dependencies(
    277
    0
        dependency_map: &DependencyMap,
    278
    0
        source: &Arc<dyn PhysicalExpr>,
    279
    0
    ) -> Vec<Dependencies> {
    280
        // Associate `PhysicalExpr`s with `PhysicalSortExpr`s that contain them:
    281
    0
        let mut expr_to_sort_exprs = IndexMap::<_, Dependencies>::new();
    282
    0
        for sort_expr in dependency_map
    283
    0
            .keys()
    284
    0
            .filter(|sort_expr| expr_refers(source, &sort_expr.expr))
    285
    0
        {
    286
    0
            let key = Arc::clone(&sort_expr.expr);
    287
    0
            expr_to_sort_exprs
    288
    0
                .entry(key)
    289
    0
                .or_default()
    290
    0
                .insert(sort_expr.clone());
    291
    0
        }
    292
    293
        // Generate all valid dependencies for the source. For example, if the source
    294
        // is `a + b` and the map is `[a -> (a ASC, a DESC), b -> (b ASC)]`, we get
    295
        // `vec![HashSet(a ASC, b ASC), HashSet(a DESC, b ASC)]`.
    296
    0
        expr_to_sort_exprs
    297
    0
            .into_values()
    298
    0
            .multi_cartesian_product()
    299
    0
            .map(Dependencies::new)
    300
    0
            .collect()
    301
    0
    }
    302
    303
    /// This function retrieves the dependencies of the given relevant sort expression
    304
    /// from the given dependency map. It then constructs prefix orderings by recursively
    305
    /// analyzing the dependencies and include them in the orderings.
    306
    ///
    307
    /// # Parameters
    308
    ///
    309
    /// - `relevant_sort_expr`: A reference to the relevant sort expression
    310
    ///   (`PhysicalSortExpr`) for which prefix orderings are to be constructed.
    311
    /// - `dependency_map`: A reference to the `DependencyMap` containing dependencies.
    312
    ///
    313
    /// # Returns
    314
    ///
    315
    /// A vector of prefix orderings (`Vec<LexOrdering>`) based on the given relevant
    316
    /// sort expression and its dependencies.
    317
    0
    pub fn construct_prefix_orderings(
    318
    0
        relevant_sort_expr: &PhysicalSortExpr,
    319
    0
        dependency_map: &DependencyMap,
    320
    0
    ) -> Vec<LexOrdering> {
    321
    0
        let mut dep_enumerator = DependencyEnumerator::new();
    322
    0
        dependency_map
    323
    0
            .get(relevant_sort_expr)
    324
    0
            .expect("no relevant sort expr found")
    325
    0
            .dependencies
    326
    0
            .iter()
    327
    0
            .flat_map(|dep| dep_enumerator.construct_orderings(dep, dependency_map))
    328
    0
            .collect()
    329
    0
    }
    330
    331
    /// Generates all possible orderings where dependencies are satisfied for the
    332
    /// current projection expression.
    333
    ///
    334
    /// # Example
    335
    ///  If `dependencies` is `a + b ASC` and the dependency map holds dependencies
    336
    ///  * `a ASC` --> `[c ASC]`
    337
    ///  * `b ASC` --> `[d DESC]`,
    338
    ///
    339
    /// This function generates these two sort orders
    340
    /// * `[c ASC, d DESC, a + b ASC]`
    341
    /// * `[d DESC, c ASC, a + b ASC]`
    342
    ///
    343
    /// # Parameters
    344
    ///
    345
    /// * `dependencies` - Set of relevant expressions.
    346
    /// * `dependency_map` - Map of dependencies for expressions that may appear in
    347
    ///   `dependencies`.
    348
    ///
    349
    /// # Returns
    350
    ///
    351
    /// A vector of lexical orderings (`Vec<LexOrdering>`) representing all valid
    352
    /// orderings based on the given dependencies.
    353
    0
    pub fn generate_dependency_orderings(
    354
    0
        dependencies: &Dependencies,
    355
    0
        dependency_map: &DependencyMap,
    356
    0
    ) -> Vec<LexOrdering> {
    357
        // Construct all the valid prefix orderings for each expression appearing
    358
        // in the projection. Note that if relevant prefixes are empty, there is no
    359
        // dependency, meaning that dependent is a leading ordering.
    360
    0
        dependencies
    361
    0
            .iter()
    362
    0
            .filter_map(|dep| {
    363
    0
                let prefixes = construct_prefix_orderings(dep, dependency_map);
    364
    0
                (!prefixes.is_empty()).then_some(prefixes)
    365
    0
            })
    366
            // Generate all possible valid orderings:
    367
    0
            .multi_cartesian_product()
    368
    0
            .flat_map(|prefix_orderings| {
    369
    0
                let length = prefix_orderings.len();
    370
    0
                prefix_orderings
    371
    0
                    .into_iter()
    372
    0
                    .permutations(length)
    373
    0
                    .filter_map(|prefixes| {
    374
    0
                        prefixes.into_iter().reduce(|mut acc, ordering| {
    375
    0
                            acc.extend(ordering);
    376
    0
                            acc
    377
    0
                        })
    378
    0
                    })
    379
    0
            })
    380
    0
            .collect()
    381
    0
    }
    382
    383
    #[cfg(test)]
    384
    mod tests {
    385
        use std::ops::Not;
    386
        use std::sync::Arc;
    387
    388
        use super::*;
    389
        use crate::equivalence::tests::{
    390
            convert_to_sort_reqs, create_test_params, create_test_schema, parse_sort_expr,
    391
        };
    392
        use crate::equivalence::{convert_to_sort_exprs, ProjectionMapping};
    393
        use crate::expressions::{col, BinaryExpr, CastExpr, Column};
    394
        use crate::projection::tests::output_schema;
    395
        use crate::{ConstExpr, EquivalenceProperties, ScalarFunctionExpr};
    396
    397
        use arrow::compute::SortOptions;
    398
        use arrow::datatypes::{DataType, Field, Schema, TimeUnit};
    399
        use datafusion_common::config::ConfigOptions;
    400
        use datafusion_common::{Constraint, Constraints, Result};
    401
        use datafusion_expr::sort_properties::SortProperties;
    402
        use datafusion_expr::Operator;
    403
        use datafusion_functions::string::concat;
    404
        use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
    405
        use datafusion_physical_expr_common::sort_expr::{
    406
            LexRequirement, PhysicalSortRequirement,
    407
        };
    408
    409
        #[test]
    410
    0
        fn project_equivalence_properties_test() -> Result<()> {
    411
    0
            let input_schema = Arc::new(Schema::new(vec![
    412
    0
                Field::new("a", DataType::Int64, true),
    413
    0
                Field::new("b", DataType::Int64, true),
    414
    0
                Field::new("c", DataType::Int64, true),
    415
            ]));
    416
    417
    0
            let input_properties = EquivalenceProperties::new(Arc::clone(&input_schema));
    418
    0
            let col_a = col("a", &input_schema)?;
    419
    420
            // a as a1, a as a2, a as a3, a as a3
    421
    0
            let proj_exprs = vec![
    422
    0
                (Arc::clone(&col_a), "a1".to_string()),
    423
    0
                (Arc::clone(&col_a), "a2".to_string()),
    424
    0
                (Arc::clone(&col_a), "a3".to_string()),
    425
    0
                (Arc::clone(&col_a), "a4".to_string()),
    426
            ];
    427
    0
            let projection_mapping = ProjectionMapping::try_new(proj_exprs, &input_schema)?;
    428
    429
    0
            let out_schema = output_schema(&projection_mapping, &input_schema)?;
    430
            // a as a1, a as a2, a as a3, a as a3
    431
    0
            let proj_exprs = vec![
    432
    0
                (Arc::clone(&col_a), "a1".to_string()),
    433
    0
                (Arc::clone(&col_a), "a2".to_string()),
    434
    0
                (Arc::clone(&col_a), "a3".to_string()),
    435
    0
                (Arc::clone(&col_a), "a4".to_string()),
    436
            ];
    437
    0
            let projection_mapping = ProjectionMapping::try_new(proj_exprs, &input_schema)?;
    438
    439
            // a as a1, a as a2, a as a3, a as a3
    440
    0
            let col_a1 = &col("a1", &out_schema)?;
    441
    0
            let col_a2 = &col("a2", &out_schema)?;
    442
    0
            let col_a3 = &col("a3", &out_schema)?;
    443
    0
            let col_a4 = &col("a4", &out_schema)?;
    444
    0
            let out_properties = input_properties.project(&projection_mapping, out_schema);
    445
    446
            // At the output a1=a2=a3=a4
    447
    0
            assert_eq!(out_properties.eq_group().len(), 1);
    448
    0
            let eq_class = out_properties.eq_group().iter().next().unwrap();
    449
    0
            assert_eq!(eq_class.len(), 4);
    450
    0
            assert!(eq_class.contains(col_a1));
    451
    0
            assert!(eq_class.contains(col_a2));
    452
    0
            assert!(eq_class.contains(col_a3));
    453
    0
            assert!(eq_class.contains(col_a4));
    454
    455
    0
            Ok(())
    456
    0
        }
    457
    458
        #[test]
    459
    0
        fn project_equivalence_properties_test_multi() -> Result<()> {
    460
            // test multiple input orderings with equivalence properties
    461
    0
            let input_schema = Arc::new(Schema::new(vec![
    462
    0
                Field::new("a", DataType::Int64, true),
    463
    0
                Field::new("b", DataType::Int64, true),
    464
    0
                Field::new("c", DataType::Int64, true),
    465
    0
                Field::new("d", DataType::Int64, true),
    466
            ]));
    467
    468
    0
            let mut input_properties = EquivalenceProperties::new(Arc::clone(&input_schema));
    469
            // add equivalent ordering [a, b, c, d]
    470
    0
            input_properties.add_ordering([
    471
    0
                parse_sort_expr("a", &input_schema),
    472
    0
                parse_sort_expr("b", &input_schema),
    473
    0
                parse_sort_expr("c", &input_schema),
    474
    0
                parse_sort_expr("d", &input_schema),
    475
    0
            ]);
    476
    477
            // add equivalent ordering [a, c, b, d]
    478
    0
            input_properties.add_ordering([
    479
    0
                parse_sort_expr("a", &input_schema),
    480
    0
                parse_sort_expr("c", &input_schema),
    481
    0
                parse_sort_expr("b", &input_schema), // NB b and c are swapped
    482
    0
                parse_sort_expr("d", &input_schema),
    483
    0
            ]);
    484
    485
            // simply project all the columns in order
    486
    0
            let proj_exprs = vec![
    487
    0
                (col("a", &input_schema)?, "a".to_string()),
    488
    0
                (col("b", &input_schema)?, "b".to_string()),
    489
    0
                (col("c", &input_schema)?, "c".to_string()),
    490
    0
                (col("d", &input_schema)?, "d".to_string()),
    491
            ];
    492
    0
            let projection_mapping = ProjectionMapping::try_new(proj_exprs, &input_schema)?;
    493
    0
            let out_properties = input_properties.project(&projection_mapping, input_schema);
    494
    495
    0
            assert_eq!(
    496
    0
                out_properties.to_string(),
    497
                "order: [[a@0 ASC, c@2 ASC, b@1 ASC, d@3 ASC], [a@0 ASC, b@1 ASC, c@2 ASC, d@3 ASC]]"
    498
            );
    499
    500
    0
            Ok(())
    501
    0
        }
    502
    503
        #[test]
    504
    0
        fn test_normalize_ordering_equivalence_classes() -> Result<()> {
    505
    0
            let schema = Schema::new(vec![
    506
    0
                Field::new("a", DataType::Int32, true),
    507
    0
                Field::new("b", DataType::Int32, true),
    508
    0
                Field::new("c", DataType::Int32, true),
    509
            ]);
    510
    0
            let col_a_expr = col("a", &schema)?;
    511
    0
            let col_b_expr = col("b", &schema)?;
    512
    0
            let col_c_expr = col("c", &schema)?;
    513
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::new(schema.clone()));
    514
    515
    0
            eq_properties.add_equal_conditions(col_a_expr, Arc::clone(&col_c_expr))?;
    516
    0
            eq_properties.add_orderings([
    517
    0
                vec![PhysicalSortExpr::new_default(Arc::clone(&col_b_expr))],
    518
    0
                vec![PhysicalSortExpr::new_default(Arc::clone(&col_c_expr))],
    519
    0
            ]);
    520
    521
    0
            let mut expected_eqs = EquivalenceProperties::new(Arc::new(schema));
    522
    0
            expected_eqs.add_orderings([
    523
    0
                vec![PhysicalSortExpr::new_default(col_b_expr)],
    524
    0
                vec![PhysicalSortExpr::new_default(col_c_expr)],
    525
    0
            ]);
    526
    527
    0
            assert!(eq_properties.oeq_class().eq(expected_eqs.oeq_class()));
    528
    0
            Ok(())
    529
    0
        }
    530
    531
        #[test]
    532
    0
        fn test_get_indices_of_matching_sort_exprs_with_order_eq() -> Result<()> {
    533
    0
            let sort_options = SortOptions::default();
    534
    0
            let sort_options_not = SortOptions::default().not();
    535
    536
    0
            let schema = Schema::new(vec![
    537
    0
                Field::new("a", DataType::Int32, true),
    538
    0
                Field::new("b", DataType::Int32, true),
    539
            ]);
    540
    0
            let col_a = col("a", &schema)?;
    541
    0
            let col_b = col("b", &schema)?;
    542
    0
            let required_columns = [Arc::clone(&col_b), Arc::clone(&col_a)];
    543
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::new(schema));
    544
    0
            eq_properties.add_ordering([
    545
    0
                PhysicalSortExpr::new(Arc::new(Column::new("b", 1)), sort_options_not),
    546
    0
                PhysicalSortExpr::new(Arc::new(Column::new("a", 0)), sort_options),
    547
    0
            ]);
    548
    0
            let (result, idxs) = eq_properties.find_longest_permutation(&required_columns)?;
    549
    0
            assert_eq!(idxs, vec![0, 1]);
    550
    0
            assert_eq!(
    551
                result,
    552
    0
                vec![
    553
    0
                    PhysicalSortExpr::new(col_b, sort_options_not),
    554
    0
                    PhysicalSortExpr::new(col_a, sort_options),
    555
                ]
    556
            );
    557
    558
    0
            let schema = Schema::new(vec![
    559
    0
                Field::new("a", DataType::Int32, true),
    560
    0
                Field::new("b", DataType::Int32, true),
    561
    0
                Field::new("c", DataType::Int32, true),
    562
            ]);
    563
    0
            let col_a = col("a", &schema)?;
    564
    0
            let col_b = col("b", &schema)?;
    565
    0
            let required_columns = [Arc::clone(&col_b), Arc::clone(&col_a)];
    566
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::new(schema));
    567
    0
            eq_properties.add_orderings([
    568
    0
                vec![PhysicalSortExpr::new(
    569
    0
                    Arc::new(Column::new("c", 2)),
    570
    0
                    sort_options,
    571
    0
                )],
    572
    0
                vec![
    573
    0
                    PhysicalSortExpr::new(Arc::new(Column::new("b", 1)), sort_options_not),
    574
    0
                    PhysicalSortExpr::new(Arc::new(Column::new("a", 0)), sort_options),
    575
    0
                ],
    576
    0
            ]);
    577
    0
            let (result, idxs) = eq_properties.find_longest_permutation(&required_columns)?;
    578
    0
            assert_eq!(idxs, vec![0, 1]);
    579
    0
            assert_eq!(
    580
                result,
    581
    0
                vec![
    582
    0
                    PhysicalSortExpr::new(col_b, sort_options_not),
    583
    0
                    PhysicalSortExpr::new(col_a, sort_options),
    584
                ]
    585
            );
    586
    587
    0
            let required_columns = [
    588
    0
                Arc::new(Column::new("b", 1)) as _,
    589
    0
                Arc::new(Column::new("a", 0)) as _,
    590
    0
            ];
    591
    0
            let schema = Schema::new(vec![
    592
    0
                Field::new("a", DataType::Int32, true),
    593
    0
                Field::new("b", DataType::Int32, true),
    594
    0
                Field::new("c", DataType::Int32, true),
    595
            ]);
    596
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::new(schema));
    597
    598
            // not satisfied orders
    599
    0
            eq_properties.add_ordering([
    600
    0
                PhysicalSortExpr::new(Arc::new(Column::new("b", 1)), sort_options_not),
    601
    0
                PhysicalSortExpr::new(Arc::new(Column::new("c", 2)), sort_options),
    602
    0
                PhysicalSortExpr::new(Arc::new(Column::new("a", 0)), sort_options),
    603
    0
            ]);
    604
    0
            let (_, idxs) = eq_properties.find_longest_permutation(&required_columns)?;
    605
    0
            assert_eq!(idxs, vec![0]);
    606
    607
    0
            Ok(())
    608
    0
        }
    609
    610
        #[test]
    611
    0
        fn test_update_properties() -> Result<()> {
    612
    0
            let schema = Schema::new(vec![
    613
    0
                Field::new("a", DataType::Int32, true),
    614
    0
                Field::new("b", DataType::Int32, true),
    615
    0
                Field::new("c", DataType::Int32, true),
    616
    0
                Field::new("d", DataType::Int32, true),
    617
            ]);
    618
    619
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::new(schema.clone()));
    620
    0
            let col_a = col("a", &schema)?;
    621
    0
            let col_b = col("b", &schema)?;
    622
    0
            let col_c = col("c", &schema)?;
    623
    0
            let col_d = col("d", &schema)?;
    624
    0
            let option_asc = SortOptions {
    625
    0
                descending: false,
    626
    0
                nulls_first: false,
    627
    0
            };
    628
            // b=a (e.g they are aliases)
    629
    0
            eq_properties.add_equal_conditions(Arc::clone(&col_b), Arc::clone(&col_a))?;
    630
            // [b ASC], [d ASC]
    631
    0
            eq_properties.add_orderings([
    632
    0
                vec![PhysicalSortExpr::new(Arc::clone(&col_b), option_asc)],
    633
    0
                vec![PhysicalSortExpr::new(Arc::clone(&col_d), option_asc)],
    634
    0
            ]);
    635
    636
    0
            let test_cases = vec![
    637
                // d + b
    638
    0
                (
    639
    0
                    Arc::new(BinaryExpr::new(col_d, Operator::Plus, Arc::clone(&col_b))) as _,
    640
    0
                    SortProperties::Ordered(option_asc),
    641
    0
                ),
    642
                // b
    643
    0
                (col_b, SortProperties::Ordered(option_asc)),
    644
                // a
    645
    0
                (Arc::clone(&col_a), SortProperties::Ordered(option_asc)),
    646
                // a + c
    647
    0
                (
    648
    0
                    Arc::new(BinaryExpr::new(col_a, Operator::Plus, col_c)),
    649
    0
                    SortProperties::Unordered,
    650
    0
                ),
    651
            ];
    652
    0
            for (expr, expected) in test_cases {
    653
    0
                let leading_orderings = eq_properties
    654
    0
                    .oeq_class()
    655
    0
                    .iter()
    656
    0
                    .map(|ordering| ordering.first().clone())
    657
    0
                    .collect::<Vec<_>>();
    658
    0
                let expr_props = eq_properties.get_expr_properties(Arc::clone(&expr));
    659
    0
                let err_msg = format!(
    660
    0
                    "expr:{:?}, expected: {:?}, actual: {:?}, leading_orderings: {leading_orderings:?}",
    661
                    expr, expected, expr_props.sort_properties
    662
                );
    663
    0
                assert_eq!(expr_props.sort_properties, expected, "{err_msg}");
    664
            }
    665
    666
    0
            Ok(())
    667
    0
        }
    668
    669
        #[test]
    670
    0
        fn test_find_longest_permutation() -> Result<()> {
    671
            // Schema satisfies following orderings:
    672
            // [a ASC], [d ASC, b ASC], [e DESC, f ASC, g ASC]
    673
            // and
    674
            // Column [a=c] (e.g they are aliases).
    675
            // At below we add [d ASC, h DESC] also, for test purposes
    676
    0
            let (test_schema, mut eq_properties) = create_test_params()?;
    677
    0
            let col_a = &col("a", &test_schema)?;
    678
    0
            let col_b = &col("b", &test_schema)?;
    679
    0
            let col_c = &col("c", &test_schema)?;
    680
    0
            let col_d = &col("d", &test_schema)?;
    681
    0
            let col_e = &col("e", &test_schema)?;
    682
    0
            let col_f = &col("f", &test_schema)?;
    683
    0
            let col_h = &col("h", &test_schema)?;
    684
            // a + d
    685
    0
            let a_plus_d = Arc::new(BinaryExpr::new(
    686
    0
                Arc::clone(col_a),
    687
    0
                Operator::Plus,
    688
    0
                Arc::clone(col_d),
    689
    0
            )) as _;
    690
    691
    0
            let option_asc = SortOptions {
    692
    0
                descending: false,
    693
    0
                nulls_first: false,
    694
    0
            };
    695
    0
            let option_desc = SortOptions {
    696
    0
                descending: true,
    697
    0
                nulls_first: true,
    698
    0
            };
    699
            // [d ASC, h DESC] also satisfies schema.
    700
    0
            eq_properties.add_ordering([
    701
    0
                PhysicalSortExpr::new(Arc::clone(col_d), option_asc),
    702
    0
                PhysicalSortExpr::new(Arc::clone(col_h), option_desc),
    703
    0
            ]);
    704
    0
            let test_cases = vec![
    705
                // TEST CASE 1
    706
    0
                (vec![col_a], vec![(col_a, option_asc)]),
    707
                // TEST CASE 2
    708
    0
                (vec![col_c], vec![(col_c, option_asc)]),
    709
                // TEST CASE 3
    710
    0
                (
    711
    0
                    vec![col_d, col_e, col_b],
    712
    0
                    vec![
    713
    0
                        (col_d, option_asc),
    714
    0
                        (col_e, option_desc),
    715
    0
                        (col_b, option_asc),
    716
    0
                    ],
    717
    0
                ),
    718
                // TEST CASE 4
    719
    0
                (vec![col_b], vec![]),
    720
                // TEST CASE 5
    721
    0
                (vec![col_d], vec![(col_d, option_asc)]),
    722
                // TEST CASE 5
    723
    0
                (vec![&a_plus_d], vec![(&a_plus_d, option_asc)]),
    724
                // TEST CASE 6
    725
    0
                (
    726
    0
                    vec![col_b, col_d],
    727
    0
                    vec![(col_d, option_asc), (col_b, option_asc)],
    728
    0
                ),
    729
                // TEST CASE 6
    730
    0
                (
    731
    0
                    vec![col_c, col_e],
    732
    0
                    vec![(col_c, option_asc), (col_e, option_desc)],
    733
    0
                ),
    734
                // TEST CASE 7
    735
    0
                (
    736
    0
                    vec![col_d, col_h, col_e, col_f, col_b],
    737
    0
                    vec![
    738
    0
                        (col_d, option_asc),
    739
    0
                        (col_e, option_desc),
    740
    0
                        (col_h, option_desc),
    741
    0
                        (col_f, option_asc),
    742
    0
                        (col_b, option_asc),
    743
    0
                    ],
    744
    0
                ),
    745
                // TEST CASE 8
    746
    0
                (
    747
    0
                    vec![col_e, col_d, col_h, col_f, col_b],
    748
    0
                    vec![
    749
    0
                        (col_e, option_desc),
    750
    0
                        (col_d, option_asc),
    751
    0
                        (col_h, option_desc),
    752
    0
                        (col_f, option_asc),
    753
    0
                        (col_b, option_asc),
    754
    0
                    ],
    755
    0
                ),
    756
                // TEST CASE 9
    757
    0
                (
    758
    0
                    vec![col_e, col_d, col_b, col_h, col_f],
    759
    0
                    vec![
    760
    0
                        (col_e, option_desc),
    761
    0
                        (col_d, option_asc),
    762
    0
                        (col_b, option_asc),
    763
    0
                        (col_h, option_desc),
    764
    0
                        (col_f, option_asc),
    765
    0
                    ],
    766
    0
                ),
    767
            ];
    768
    0
            for (exprs, expected) in test_cases {
    769
    0
                let exprs = exprs.into_iter().cloned().collect::<Vec<_>>();
    770
    0
                let expected = convert_to_sort_exprs(&expected);
    771
    0
                let (actual, _) = eq_properties.find_longest_permutation(&exprs)?;
    772
    0
                assert_eq!(actual, expected);
    773
            }
    774
    775
    0
            Ok(())
    776
    0
        }
    777
    778
        #[test]
    779
    0
        fn test_find_longest_permutation2() -> Result<()> {
    780
            // Schema satisfies following orderings:
    781
            // [a ASC], [d ASC, b ASC], [e DESC, f ASC, g ASC]
    782
            // and
    783
            // Column [a=c] (e.g they are aliases).
    784
            // At below we add [d ASC, h DESC] also, for test purposes
    785
    0
            let (test_schema, mut eq_properties) = create_test_params()?;
    786
    0
            let col_h = &col("h", &test_schema)?;
    787
    788
            // Add column h as constant
    789
    0
            eq_properties.add_constants(vec![ConstExpr::from(Arc::clone(col_h))])?;
    790
    791
    0
            let test_cases = vec![
    792
                // TEST CASE 1
    793
                // ordering of the constants are treated as default ordering.
    794
                // This is the convention currently used.
    795
    0
                (vec![col_h], vec![(col_h, SortOptions::default())]),
    796
            ];
    797
    0
            for (exprs, expected) in test_cases {
    798
    0
                let exprs = exprs.into_iter().cloned().collect::<Vec<_>>();
    799
    0
                let expected = convert_to_sort_exprs(&expected);
    800
    0
                let (actual, _) = eq_properties.find_longest_permutation(&exprs)?;
    801
    0
                assert_eq!(actual, expected);
    802
            }
    803
    804
    0
            Ok(())
    805
    0
        }
    806
    807
        #[test]
    808
    0
        fn test_normalize_sort_reqs() -> Result<()> {
    809
            // Schema satisfies following properties
    810
            // a=c
    811
            // and following orderings are valid
    812
            // [a ASC], [d ASC, b ASC], [e DESC, f ASC, g ASC]
    813
    0
            let (test_schema, eq_properties) = create_test_params()?;
    814
    0
            let col_a = &col("a", &test_schema)?;
    815
    0
            let col_b = &col("b", &test_schema)?;
    816
    0
            let col_c = &col("c", &test_schema)?;
    817
    0
            let col_d = &col("d", &test_schema)?;
    818
    0
            let col_e = &col("e", &test_schema)?;
    819
    0
            let col_f = &col("f", &test_schema)?;
    820
    0
            let option_asc = SortOptions {
    821
    0
                descending: false,
    822
    0
                nulls_first: false,
    823
    0
            };
    824
    0
            let option_desc = SortOptions {
    825
    0
                descending: true,
    826
    0
                nulls_first: true,
    827
    0
            };
    828
            // First element in the tuple stores vector of requirement, second element is the expected return value for ordering_satisfy function
    829
    0
            let requirements = vec![
    830
    0
                (
    831
    0
                    vec![(col_a, Some(option_asc))],
    832
    0
                    vec![(col_a, Some(option_asc))],
    833
    0
                ),
    834
    0
                (
    835
    0
                    vec![(col_a, Some(option_desc))],
    836
    0
                    vec![(col_a, Some(option_desc))],
    837
    0
                ),
    838
    0
                (vec![(col_a, None)], vec![(col_a, None)]),
    839
                // Test whether equivalence works as expected
    840
    0
                (
    841
    0
                    vec![(col_c, Some(option_asc))],
    842
    0
                    vec![(col_a, Some(option_asc))],
    843
    0
                ),
    844
    0
                (vec![(col_c, None)], vec![(col_a, None)]),
    845
                // Test whether ordering equivalence works as expected
    846
    0
                (
    847
    0
                    vec![(col_d, Some(option_asc)), (col_b, Some(option_asc))],
    848
    0
                    vec![(col_d, Some(option_asc)), (col_b, Some(option_asc))],
    849
    0
                ),
    850
    0
                (
    851
    0
                    vec![(col_d, None), (col_b, None)],
    852
    0
                    vec![(col_d, None), (col_b, None)],
    853
    0
                ),
    854
    0
                (
    855
    0
                    vec![(col_e, Some(option_desc)), (col_f, Some(option_asc))],
    856
    0
                    vec![(col_e, Some(option_desc)), (col_f, Some(option_asc))],
    857
    0
                ),
    858
                // We should be able to normalize in compatible requirements also (not exactly equal)
    859
    0
                (
    860
    0
                    vec![(col_e, Some(option_desc)), (col_f, None)],
    861
    0
                    vec![(col_e, Some(option_desc)), (col_f, None)],
    862
    0
                ),
    863
    0
                (
    864
    0
                    vec![(col_e, None), (col_f, None)],
    865
    0
                    vec![(col_e, None), (col_f, None)],
    866
    0
                ),
    867
            ];
    868
    869
    0
            for (reqs, expected_normalized) in requirements.into_iter() {
    870
    0
                let req = convert_to_sort_reqs(&reqs);
    871
    0
                let expected_normalized = convert_to_sort_reqs(&expected_normalized);
    872
    873
    0
                assert_eq!(
    874
    0
                    eq_properties.normalize_sort_requirements(req).unwrap(),
    875
                    expected_normalized
    876
                );
    877
            }
    878
    879
    0
            Ok(())
    880
    0
        }
    881
    882
        #[test]
    883
    0
        fn test_schema_normalize_sort_requirement_with_equivalence() -> Result<()> {
    884
    0
            let option1 = SortOptions {
    885
    0
                descending: false,
    886
    0
                nulls_first: false,
    887
    0
            };
    888
            // Assume that column a and c are aliases.
    889
    0
            let (test_schema, eq_properties) = create_test_params()?;
    890
    0
            let col_a = &col("a", &test_schema)?;
    891
    0
            let col_c = &col("c", &test_schema)?;
    892
    0
            let col_d = &col("d", &test_schema)?;
    893
    894
            // Test cases for equivalence normalization
    895
            // First entry in the tuple is PhysicalSortRequirement, second entry in the tuple is
    896
            // expected PhysicalSortRequirement after normalization.
    897
    0
            let test_cases = vec![
    898
    0
                (vec![(col_a, Some(option1))], vec![(col_a, Some(option1))]),
    899
                // In the normalized version column c should be replace with column a
    900
    0
                (vec![(col_c, Some(option1))], vec![(col_a, Some(option1))]),
    901
    0
                (vec![(col_c, None)], vec![(col_a, None)]),
    902
    0
                (vec![(col_d, Some(option1))], vec![(col_d, Some(option1))]),
    903
            ];
    904
    0
            for (reqs, expected) in test_cases.into_iter() {
    905
    0
                let reqs = convert_to_sort_reqs(&reqs);
    906
    0
                let expected = convert_to_sort_reqs(&expected);
    907
    0
                let normalized = eq_properties
    908
    0
                    .normalize_sort_requirements(reqs.clone())
    909
    0
                    .unwrap();
    910
    0
                assert!(
    911
    0
                    expected.eq(&normalized),
    912
    0
                    "error in test: reqs: {reqs:?}, expected: {expected:?}, normalized: {normalized:?}"
    913
                );
    914
            }
    915
    916
    0
            Ok(())
    917
    0
        }
    918
    919
        #[test]
    920
    0
        fn test_eliminate_redundant_monotonic_sorts() -> Result<()> {
    921
    0
            let schema = Arc::new(Schema::new(vec![
    922
    0
                Field::new("a", DataType::Date32, true),
    923
    0
                Field::new("b", DataType::Utf8, true),
    924
    0
                Field::new("c", DataType::Timestamp(TimeUnit::Nanosecond, None), true),
    925
            ]));
    926
    0
            let mut base_properties = EquivalenceProperties::new(Arc::clone(&schema));
    927
    0
            base_properties.reorder(
    928
    0
                ["a", "b", "c"]
    929
    0
                    .into_iter()
    930
    0
                    .map(|c| PhysicalSortExpr::new_default(col(c, schema.as_ref()).unwrap())),
    931
    0
            )?;
    932
    933
            struct TestCase {
    934
                name: &'static str,
    935
                constants: Vec<Arc<dyn PhysicalExpr>>,
    936
                equal_conditions: Vec<[Arc<dyn PhysicalExpr>; 2]>,
    937
                sort_columns: &'static [&'static str],
    938
                should_satisfy_ordering: bool,
    939
            }
    940
    941
    0
            let col_a = col("a", schema.as_ref())?;
    942
    0
            let col_b = col("b", schema.as_ref())?;
    943
    0
            let col_c = col("c", schema.as_ref())?;
    944
    0
            let cast_c = Arc::new(CastExpr::new(col_c, DataType::Date32, None)) as _;
    945
    946
    0
            let cases = vec![
    947
    0
                TestCase {
    948
    0
                    name: "(a, b, c) -> (c)",
    949
    0
                    // b is constant, so it should be removed from the sort order
    950
    0
                    constants: vec![Arc::clone(&col_b)],
    951
    0
                    equal_conditions: vec![[Arc::clone(&cast_c), Arc::clone(&col_a)]],
    952
    0
                    sort_columns: &["c"],
    953
    0
                    should_satisfy_ordering: true,
    954
    0
                },
    955
                // Same test with above test, where equality order is swapped.
    956
                // Algorithm shouldn't depend on this order.
    957
    0
                TestCase {
    958
    0
                    name: "(a, b, c) -> (c)",
    959
    0
                    // b is constant, so it should be removed from the sort order
    960
    0
                    constants: vec![col_b],
    961
    0
                    equal_conditions: vec![[Arc::clone(&col_a), Arc::clone(&cast_c)]],
    962
    0
                    sort_columns: &["c"],
    963
    0
                    should_satisfy_ordering: true,
    964
    0
                },
    965
    0
                TestCase {
    966
    0
                    name: "not ordered because (b) is not constant",
    967
    0
                    // b is not constant anymore
    968
    0
                    constants: vec![],
    969
    0
                    // a and c are still compatible, but this is irrelevant since the original ordering is (a, b, c)
    970
    0
                    equal_conditions: vec![[Arc::clone(&cast_c), Arc::clone(&col_a)]],
    971
    0
                    sort_columns: &["c"],
    972
    0
                    should_satisfy_ordering: false,
    973
    0
                },
    974
            ];
    975
    976
    0
            for case in cases {
    977
                // Construct the equivalence properties in different orders
    978
                // to exercise different code paths
    979
                // (The resulting properties _should_ be the same)
    980
    0
                for properties in [
    981
                    // Equal conditions before constants
    982
                    {
    983
    0
                        let mut properties = base_properties.clone();
    984
    0
                        for [left, right] in case.equal_conditions.clone() {
    985
    0
                            properties.add_equal_conditions(left, right)?
    986
                        }
    987
    0
                        properties.add_constants(
    988
    0
                            case.constants.iter().cloned().map(ConstExpr::from),
    989
    0
                        )?;
    990
    0
                        properties
    991
                    },
    992
                    // Constants before equal conditions
    993
                    {
    994
    0
                        let mut properties = base_properties.clone();
    995
    0
                        properties.add_constants(
    996
    0
                            case.constants.iter().cloned().map(ConstExpr::from),
    997
    0
                        )?;
    998
    0
                        for [left, right] in case.equal_conditions {
    999
    0
                            properties.add_equal_conditions(left, right)?
    1000
                        }
    1001
    0
                        properties
    1002
                    },
    1003
                ] {
    1004
    0
                    let sort = case
    1005
    0
                        .sort_columns
    1006
    0
                        .iter()
    1007
    0
                        .map(|&name| col(name, &schema).map(PhysicalSortExpr::new_default))
    1008
    0
                        .collect::<Result<Vec<_>>>()?;
    1009
    1010
    0
                    assert_eq!(
    1011
    0
                        properties.ordering_satisfy(sort)?,
    1012
                        case.should_satisfy_ordering,
    1013
    0
                        "failed test '{}'",
    1014
                        case.name
    1015
                    );
    1016
                }
    1017
            }
    1018
    1019
    0
            Ok(())
    1020
    0
        }
    1021
    1022
        #[test]
    1023
    0
        fn test_ordering_equivalence_with_lex_monotonic_concat() -> Result<()> {
    1024
    0
            let schema = Arc::new(Schema::new(vec![
    1025
    0
                Field::new("a", DataType::Utf8, false),
    1026
    0
                Field::new("b", DataType::Utf8, false),
    1027
    0
                Field::new("c", DataType::Utf8, false),
    1028
            ]));
    1029
    1030
    0
            let col_a = col("a", &schema)?;
    1031
    0
            let col_b = col("b", &schema)?;
    1032
    0
            let col_c = col("c", &schema)?;
    1033
    1034
    0
            let a_concat_b: Arc<dyn PhysicalExpr> = Arc::new(ScalarFunctionExpr::new(
    1035
    0
                "concat",
    1036
    0
                concat(),
    1037
    0
                vec![Arc::clone(&col_a), Arc::clone(&col_b)],
    1038
    0
                Field::new("f", DataType::Utf8, true).into(),
    1039
    0
                Arc::new(ConfigOptions::default()),
    1040
    0
            ));
    1041
    1042
            // Assume existing ordering is [c ASC, a ASC, b ASC]
    1043
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1044
    1045
    0
            eq_properties.add_ordering([
    1046
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_c)).asc(),
    1047
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_a)).asc(),
    1048
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_b)).asc(),
    1049
    0
            ]);
    1050
    1051
            // Add equality condition c = concat(a, b)
    1052
    0
            eq_properties.add_equal_conditions(Arc::clone(&col_c), a_concat_b)?;
    1053
    1054
    0
            let orderings = eq_properties.oeq_class();
    1055
    1056
    0
            let expected_ordering1 = [PhysicalSortExpr::new_default(col_c).asc()].into();
    1057
    0
            let expected_ordering2 = [
    1058
    0
                PhysicalSortExpr::new_default(col_a).asc(),
    1059
    0
                PhysicalSortExpr::new_default(col_b).asc(),
    1060
    0
            ]
    1061
    0
            .into();
    1062
    1063
            // The ordering should be [c ASC] and [a ASC, b ASC]
    1064
    0
            assert_eq!(orderings.len(), 2);
    1065
    0
            assert!(orderings.contains(&expected_ordering1));
    1066
    0
            assert!(orderings.contains(&expected_ordering2));
    1067
    1068
    0
            Ok(())
    1069
    0
        }
    1070
    1071
        #[test]
    1072
    0
        fn test_ordering_equivalence_with_non_lex_monotonic_multiply() -> Result<()> {
    1073
    0
            let schema = Arc::new(Schema::new(vec![
    1074
    0
                Field::new("a", DataType::Int32, false),
    1075
    0
                Field::new("b", DataType::Int32, false),
    1076
    0
                Field::new("c", DataType::Int32, false),
    1077
            ]));
    1078
    1079
    0
            let col_a = col("a", &schema)?;
    1080
    0
            let col_b = col("b", &schema)?;
    1081
    0
            let col_c = col("c", &schema)?;
    1082
    1083
    0
            let a_times_b = Arc::new(BinaryExpr::new(
    1084
    0
                Arc::clone(&col_a),
    1085
    0
                Operator::Multiply,
    1086
    0
                Arc::clone(&col_b),
    1087
    0
            )) as _;
    1088
    1089
            // Assume existing ordering is [c ASC, a ASC, b ASC]
    1090
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1091
    1092
    0
            let initial_ordering: LexOrdering = [
    1093
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_c)).asc(),
    1094
    0
                PhysicalSortExpr::new_default(col_a).asc(),
    1095
    0
                PhysicalSortExpr::new_default(col_b).asc(),
    1096
    0
            ]
    1097
    0
            .into();
    1098
    1099
    0
            eq_properties.add_ordering(initial_ordering.clone());
    1100
    1101
            // Add equality condition c = a * b
    1102
    0
            eq_properties.add_equal_conditions(col_c, a_times_b)?;
    1103
    1104
    0
            let orderings = eq_properties.oeq_class();
    1105
    1106
            // The ordering should remain unchanged since multiplication is not lex-monotonic
    1107
    0
            assert_eq!(orderings.len(), 1);
    1108
    0
            assert!(orderings.contains(&initial_ordering));
    1109
    1110
    0
            Ok(())
    1111
    0
        }
    1112
    1113
        #[test]
    1114
    0
        fn test_ordering_equivalence_with_concat_equality() -> Result<()> {
    1115
    0
            let schema = Arc::new(Schema::new(vec![
    1116
    0
                Field::new("a", DataType::Utf8, false),
    1117
    0
                Field::new("b", DataType::Utf8, false),
    1118
    0
                Field::new("c", DataType::Utf8, false),
    1119
            ]));
    1120
    1121
    0
            let col_a = col("a", &schema)?;
    1122
    0
            let col_b = col("b", &schema)?;
    1123
    0
            let col_c = col("c", &schema)?;
    1124
    1125
    0
            let a_concat_b = Arc::new(ScalarFunctionExpr::new(
    1126
    0
                "concat",
    1127
    0
                concat(),
    1128
    0
                vec![Arc::clone(&col_a), Arc::clone(&col_b)],
    1129
    0
                Field::new("f", DataType::Utf8, true).into(),
    1130
    0
                Arc::new(ConfigOptions::default()),
    1131
    0
            )) as _;
    1132
    1133
            // Assume existing ordering is [concat(a, b) ASC, a ASC, b ASC]
    1134
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1135
    1136
    0
            eq_properties.add_ordering([
    1137
    0
                PhysicalSortExpr::new_default(Arc::clone(&a_concat_b)).asc(),
    1138
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_a)).asc(),
    1139
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_b)).asc(),
    1140
    0
            ]);
    1141
    1142
            // Add equality condition c = concat(a, b)
    1143
    0
            eq_properties.add_equal_conditions(col_c, Arc::clone(&a_concat_b))?;
    1144
    1145
    0
            let orderings = eq_properties.oeq_class();
    1146
    1147
    0
            let expected_ordering1 = [PhysicalSortExpr::new_default(a_concat_b).asc()].into();
    1148
    0
            let expected_ordering2 = [
    1149
    0
                PhysicalSortExpr::new_default(col_a).asc(),
    1150
    0
                PhysicalSortExpr::new_default(col_b).asc(),
    1151
    0
            ]
    1152
    0
            .into();
    1153
    1154
            // The ordering should be [c ASC] and [a ASC, b ASC]
    1155
    0
            assert_eq!(orderings.len(), 2);
    1156
    0
            assert!(orderings.contains(&expected_ordering1));
    1157
    0
            assert!(orderings.contains(&expected_ordering2));
    1158
    1159
    0
            Ok(())
    1160
    0
        }
    1161
    1162
        #[test]
    1163
    0
        fn test_requirements_compatible() -> Result<()> {
    1164
    0
            let schema = Arc::new(Schema::new(vec![
    1165
    0
                Field::new("a", DataType::Int32, true),
    1166
    0
                Field::new("b", DataType::Int32, true),
    1167
    0
                Field::new("c", DataType::Int32, true),
    1168
            ]));
    1169
    0
            let col_a = col("a", &schema)?;
    1170
    0
            let col_b = col("b", &schema)?;
    1171
    0
            let col_c = col("c", &schema)?;
    1172
    1173
    0
            let eq_properties = EquivalenceProperties::new(schema);
    1174
    0
            let lex_a: LexRequirement =
    1175
    0
                [PhysicalSortRequirement::new(Arc::clone(&col_a), None)].into();
    1176
    0
            let lex_a_b: LexRequirement = [
    1177
    0
                PhysicalSortRequirement::new(col_a, None),
    1178
    0
                PhysicalSortRequirement::new(col_b, None),
    1179
    0
            ]
    1180
    0
            .into();
    1181
    0
            let lex_c = [PhysicalSortRequirement::new(col_c, None)].into();
    1182
    1183
    0
            assert!(eq_properties.requirements_compatible(lex_a.clone(), lex_a.clone()));
    1184
    0
            assert!(!eq_properties.requirements_compatible(lex_a.clone(), lex_a_b.clone()));
    1185
    0
            assert!(eq_properties.requirements_compatible(lex_a_b, lex_a.clone()));
    1186
    0
            assert!(!eq_properties.requirements_compatible(lex_c, lex_a));
    1187
    1188
    0
            Ok(())
    1189
    0
        }
    1190
    1191
        #[test]
    1192
    0
        fn test_with_reorder_constant_filtering() -> Result<()> {
    1193
    0
            let schema = create_test_schema()?;
    1194
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1195
    1196
            // Setup constant columns
    1197
    0
            let col_a = col("a", &schema)?;
    1198
    0
            let col_b = col("b", &schema)?;
    1199
    0
            eq_properties.add_constants([ConstExpr::from(Arc::clone(&col_a))])?;
    1200
    1201
    0
            let sort_exprs = vec![
    1202
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_a)),
    1203
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_b)),
    1204
            ];
    1205
    1206
    0
            let change = eq_properties.reorder(sort_exprs)?;
    1207
    0
            assert!(change);
    1208
    1209
    0
            assert_eq!(eq_properties.oeq_class().len(), 1);
    1210
    0
            let ordering = eq_properties.oeq_class().iter().next().unwrap();
    1211
    0
            assert_eq!(ordering.len(), 2);
    1212
    0
            assert!(ordering[0].expr.eq(&col_a));
    1213
    0
            assert!(ordering[1].expr.eq(&col_b));
    1214
    1215
    0
            Ok(())
    1216
    0
        }
    1217
    1218
        #[test]
    1219
    0
        fn test_with_reorder_preserve_suffix() -> Result<()> {
    1220
    0
            let schema = create_test_schema()?;
    1221
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1222
    1223
    0
            let col_a = col("a", &schema)?;
    1224
    0
            let col_b = col("b", &schema)?;
    1225
    0
            let col_c = col("c", &schema)?;
    1226
    1227
    0
            let asc = SortOptions::default();
    1228
    0
            let desc = SortOptions {
    1229
    0
                descending: true,
    1230
    0
                nulls_first: true,
    1231
    0
            };
    1232
    1233
            // Initial ordering: [a ASC, b DESC, c ASC]
    1234
    0
            eq_properties.add_ordering([
    1235
    0
                PhysicalSortExpr::new(Arc::clone(&col_a), asc),
    1236
    0
                PhysicalSortExpr::new(Arc::clone(&col_b), desc),
    1237
    0
                PhysicalSortExpr::new(Arc::clone(&col_c), asc),
    1238
    0
            ]);
    1239
    1240
            // New ordering: [a ASC]
    1241
    0
            let new_order = vec![PhysicalSortExpr::new(Arc::clone(&col_a), asc)];
    1242
    1243
    0
            let change = eq_properties.reorder(new_order)?;
    1244
    0
            assert!(!change);
    1245
    1246
            // Should only contain [a ASC, b DESC, c ASC]
    1247
    0
            assert_eq!(eq_properties.oeq_class().len(), 1);
    1248
    0
            let ordering = eq_properties.oeq_class().iter().next().unwrap();
    1249
    0
            assert_eq!(ordering.len(), 3);
    1250
    0
            assert!(ordering[0].expr.eq(&col_a));
    1251
    0
            assert!(ordering[0].options.eq(&asc));
    1252
    0
            assert!(ordering[1].expr.eq(&col_b));
    1253
    0
            assert!(ordering[1].options.eq(&desc));
    1254
    0
            assert!(ordering[2].expr.eq(&col_c));
    1255
    0
            assert!(ordering[2].options.eq(&asc));
    1256
    1257
    0
            Ok(())
    1258
    0
        }
    1259
    1260
        #[test]
    1261
    0
        fn test_with_reorder_equivalent_expressions() -> Result<()> {
    1262
    0
            let schema = create_test_schema()?;
    1263
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1264
    1265
    0
            let col_a = col("a", &schema)?;
    1266
    0
            let col_b = col("b", &schema)?;
    1267
    0
            let col_c = col("c", &schema)?;
    1268
    1269
            // Make a and b equivalent
    1270
    0
            eq_properties.add_equal_conditions(Arc::clone(&col_a), Arc::clone(&col_b))?;
    1271
    1272
            // Initial ordering: [a ASC, c ASC]
    1273
    0
            eq_properties.add_ordering([
    1274
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_a)),
    1275
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_c)),
    1276
    0
            ]);
    1277
    1278
            // New ordering: [b ASC]
    1279
    0
            let new_order = vec![PhysicalSortExpr::new_default(Arc::clone(&col_b))];
    1280
    1281
    0
            let change = eq_properties.reorder(new_order)?;
    1282
    1283
    0
            assert!(!change);
    1284
            // Should only contain [a/b ASC, c ASC]
    1285
    0
            assert_eq!(eq_properties.oeq_class().len(), 1);
    1286
    1287
            // Verify orderings
    1288
    0
            let asc = SortOptions::default();
    1289
    0
            let ordering = eq_properties.oeq_class().iter().next().unwrap();
    1290
    0
            assert_eq!(ordering.len(), 2);
    1291
    0
            assert!(ordering[0].expr.eq(&col_a) || ordering[0].expr.eq(&col_b));
    1292
    0
            assert!(ordering[0].options.eq(&asc));
    1293
    0
            assert!(ordering[1].expr.eq(&col_c));
    1294
    0
            assert!(ordering[1].options.eq(&asc));
    1295
    1296
    0
            Ok(())
    1297
    0
        }
    1298
    1299
        #[test]
    1300
    0
        fn test_with_reorder_incompatible_prefix() -> Result<()> {
    1301
    0
            let schema = create_test_schema()?;
    1302
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1303
    1304
    0
            let col_a = col("a", &schema)?;
    1305
    0
            let col_b = col("b", &schema)?;
    1306
    1307
    0
            let asc = SortOptions::default();
    1308
    0
            let desc = SortOptions {
    1309
    0
                descending: true,
    1310
    0
                nulls_first: true,
    1311
    0
            };
    1312
    1313
            // Initial ordering: [a ASC, b DESC]
    1314
    0
            eq_properties.add_ordering([
    1315
    0
                PhysicalSortExpr::new(Arc::clone(&col_a), asc),
    1316
    0
                PhysicalSortExpr::new(Arc::clone(&col_b), desc),
    1317
    0
            ]);
    1318
    1319
            // New ordering: [a DESC]
    1320
    0
            let new_order = vec![PhysicalSortExpr::new(Arc::clone(&col_a), desc)];
    1321
    1322
    0
            let change = eq_properties.reorder(new_order.clone())?;
    1323
    1324
    0
            assert!(change);
    1325
            // Should only contain the new ordering since options don't match
    1326
    0
            assert_eq!(eq_properties.oeq_class().len(), 1);
    1327
    0
            let ordering = eq_properties.oeq_class().iter().next().unwrap();
    1328
    0
            assert_eq!(ordering.to_vec(), new_order);
    1329
    1330
    0
            Ok(())
    1331
    0
        }
    1332
    1333
        #[test]
    1334
    0
        fn test_with_reorder_comprehensive() -> Result<()> {
    1335
    0
            let schema = create_test_schema()?;
    1336
    0
            let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
    1337
    1338
    0
            let col_a = col("a", &schema)?;
    1339
    0
            let col_b = col("b", &schema)?;
    1340
    0
            let col_c = col("c", &schema)?;
    1341
    0
            let col_d = col("d", &schema)?;
    1342
    0
            let col_e = col("e", &schema)?;
    1343
    1344
            // Constants: c is constant
    1345
    0
            eq_properties.add_constants([ConstExpr::from(Arc::clone(&col_c))])?;
    1346
    1347
            // Equality: b = d
    1348
    0
            eq_properties.add_equal_conditions(Arc::clone(&col_b), Arc::clone(&col_d))?;
    1349
    1350
            // Orderings: [d ASC, a ASC], [e ASC]
    1351
    0
            eq_properties.add_orderings([
    1352
    0
                vec![
    1353
    0
                    PhysicalSortExpr::new_default(Arc::clone(&col_d)),
    1354
    0
                    PhysicalSortExpr::new_default(Arc::clone(&col_a)),
    1355
    0
                ],
    1356
    0
                vec![PhysicalSortExpr::new_default(Arc::clone(&col_e))],
    1357
    0
            ]);
    1358
    1359
            // New ordering: [b ASC, c ASC]
    1360
    0
            let new_order = vec![
    1361
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_b)),
    1362
    0
                PhysicalSortExpr::new_default(Arc::clone(&col_c)),
    1363
            ];
    1364
    1365
    0
            let old_orderings = eq_properties.oeq_class().clone();
    1366
    0
            let change = eq_properties.reorder(new_order)?;
    1367
            // Original orderings should be preserved:
    1368
    0
            assert!(!change);
    1369
    0
            assert_eq!(eq_properties.oeq_class, old_orderings);
    1370
    1371
    0
            Ok(())
    1372
    0
        }
    1373
    1374
        #[test]
    1375
    0
        fn test_ordering_satisfaction_with_key_constraints() -> Result<()> {
    1376
    0
            let pk_schema = Arc::new(Schema::new(vec![
    1377
    0
                Field::new("a", DataType::Int32, true),
    1378
    0
                Field::new("b", DataType::Int32, true),
    1379
    0
                Field::new("c", DataType::Int32, true),
    1380
    0
                Field::new("d", DataType::Int32, true),
    1381
            ]));
    1382
    1383
    0
            let unique_schema = Arc::new(Schema::new(vec![
    1384
    0
                Field::new("a", DataType::Int32, false),
    1385
    0
                Field::new("b", DataType::Int32, false),
    1386
    0
                Field::new("c", DataType::Int32, true),
    1387
    0
                Field::new("d", DataType::Int32, true),
    1388
            ]));
    1389
    1390
            // Test cases to run
    1391
    0
            let test_cases = vec![
    1392
                // (name, schema, constraint, base_ordering, satisfied_orderings, unsatisfied_orderings)
    1393
    0
                (
    1394
    0
                    "single column primary key",
    1395
    0
                    &pk_schema,
    1396
    0
                    vec![Constraint::PrimaryKey(vec![0])],
    1397
    0
                    vec!["a"], // base ordering
    1398
    0
                    vec![vec!["a", "b"], vec!["a", "c", "d"]],
    1399
    0
                    vec![vec!["b", "a"], vec!["c", "a"]],
    1400
    0
                ),
    1401
    0
                (
    1402
    0
                    "single column unique",
    1403
    0
                    &unique_schema,
    1404
    0
                    vec![Constraint::Unique(vec![0])],
    1405
    0
                    vec!["a"], // base ordering
    1406
    0
                    vec![vec!["a", "b"], vec!["a", "c", "d"]],
    1407
    0
                    vec![vec!["b", "a"], vec!["c", "a"]],
    1408
    0
                ),
    1409
    0
                (
    1410
    0
                    "multi-column primary key",
    1411
    0
                    &pk_schema,
    1412
    0
                    vec![Constraint::PrimaryKey(vec![0, 1])],
    1413
    0
                    vec!["a", "b"], // base ordering
    1414
    0
                    vec![vec!["a", "b", "c"], vec!["a", "b", "d"]],
    1415
    0
                    vec![vec!["b", "a"], vec!["a", "c", "b"]],
    1416
    0
                ),
    1417
    0
                (
    1418
    0
                    "multi-column unique",
    1419
    0
                    &unique_schema,
    1420
    0
                    vec![Constraint::Unique(vec![0, 1])],
    1421
    0
                    vec!["a", "b"], // base ordering
    1422
    0
                    vec![vec!["a", "b", "c"], vec!["a", "b", "d"]],
    1423
    0
                    vec![vec!["b", "a"], vec!["c", "a", "b"]],
    1424
    0
                ),
    1425
    0
                (
    1426
    0
                    "nullable unique",
    1427
    0
                    &unique_schema,
    1428
    0
                    vec![Constraint::Unique(vec![2, 3])],
    1429
    0
                    vec!["c", "d"], // base ordering
    1430
    0
                    vec![],
    1431
    0
                    vec![vec!["c", "d", "a"]],
    1432
    0
                ),
    1433
    0
                (
    1434
    0
                    "ordering with arbitrary column unique",
    1435
    0
                    &unique_schema,
    1436
    0
                    vec![Constraint::Unique(vec![0, 1])],
    1437
    0
                    vec!["a", "c", "b"], // base ordering
    1438
    0
                    vec![vec!["a", "c", "b", "d"]],
    1439
    0
                    vec![vec!["a", "b", "d"]],
    1440
    0
                ),
    1441
    0
                (
    1442
    0
                    "ordering with arbitrary column pk",
    1443
    0
                    &pk_schema,
    1444
    0
                    vec![Constraint::PrimaryKey(vec![0, 1])],
    1445
    0
                    vec!["a", "c", "b"], // base ordering
    1446
    0
                    vec![vec!["a", "c", "b", "d"]],
    1447
    0
                    vec![vec!["a", "b", "d"]],
    1448
    0
                ),
    1449
    0
                (
    1450
    0
                    "ordering with arbitrary column pk complex",
    1451
    0
                    &pk_schema,
    1452
    0
                    vec![Constraint::PrimaryKey(vec![3, 1])],
    1453
    0
                    vec!["b", "a", "d"], // base ordering
    1454
    0
                    vec![vec!["b", "a", "d", "c"]],
    1455
    0
                    vec![vec!["b", "c", "d", "a"], vec!["b", "a", "c", "d"]],
    1456
    0
                ),
    1457
            ];
    1458
    1459
            for (
    1460
    0
                name,
    1461
    0
                schema,
    1462
    0
                constraints,
    1463
    0
                base_order,
    1464
    0
                satisfied_orders,
    1465
    0
                unsatisfied_orders,
    1466
    0
            ) in test_cases
    1467
            {
    1468
    0
                let mut eq_properties = EquivalenceProperties::new(Arc::clone(schema));
    1469
    1470
                // Convert string column names to orderings
    1471
    0
                let satisfied_orderings: Vec<_> = satisfied_orders
    1472
    0
                    .iter()
    1473
    0
                    .map(|cols| {
    1474
    0
                        cols.iter()
    1475
    0
                            .map(|col_name| {
    1476
    0
                                PhysicalSortExpr::new_default(col(col_name, schema).unwrap())
    1477
    0
                            })
    1478
    0
                            .collect::<Vec<_>>()
    1479
    0
                    })
    1480
    0
                    .collect();
    1481
    1482
    0
                let unsatisfied_orderings: Vec<_> = unsatisfied_orders
    1483
    0
                    .iter()
    1484
    0
                    .map(|cols| {
    1485
    0
                        cols.iter()
    1486
    0
                            .map(|col_name| {
    1487
    0
                                PhysicalSortExpr::new_default(col(col_name, schema).unwrap())
    1488
    0
                            })
    1489
    0
                            .collect::<Vec<_>>()
    1490
    0
                    })
    1491
    0
                    .collect();
    1492
    1493
                // Test that orderings are not satisfied before adding constraints
    1494
    0
                for ordering in satisfied_orderings.clone() {
    1495
    0
                    let err_msg = format!(
    1496
    0
                        "{name}: ordering {ordering:?} should not be satisfied before adding constraints",
    1497
                    );
    1498
    0
                    assert!(!eq_properties.ordering_satisfy(ordering)?, "{err_msg}");
    1499
                }
    1500
    1501
                // Add base ordering
    1502
    0
                let base_ordering = base_order.iter().map(|col_name| PhysicalSortExpr {
    1503
    0
                    expr: col(col_name, schema).unwrap(),
    1504
    0
                    options: SortOptions::default(),
    1505
    0
                });
    1506
    0
                eq_properties.add_ordering(base_ordering);
    1507
    1508
                // Add constraints
    1509
    0
                eq_properties =
    1510
    0
                    eq_properties.with_constraints(Constraints::new_unverified(constraints));
    1511
    1512
                // Test that expected orderings are now satisfied
    1513
    0
                for ordering in satisfied_orderings {
    1514
    0
                    let err_msg = format!(
    1515
    0
                        "{name}: ordering {ordering:?} should be satisfied after adding constraints",
    1516
                    );
    1517
    0
                    assert!(eq_properties.ordering_satisfy(ordering)?, "{err_msg}");
    1518
                }
    1519
    1520
                // Test that unsatisfied orderings remain unsatisfied
    1521
    0
                for ordering in unsatisfied_orderings {
    1522
    0
                    let err_msg = format!(
    1523
    0
                        "{name}: ordering {ordering:?} should not be satisfied after adding constraints",
    1524
                    );
    1525
    0
                    assert!(!eq_properties.ordering_satisfy(ordering)?, "{err_msg}");
    1526
                }
    1527
            }
    1528
    1529
    0
            Ok(())
    1530
    0
        }
    1531
    }