## 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/ordering.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::Display;
    19
    use std::ops::Deref;
    20
    use std::sync::Arc;
    21
    use std::vec::IntoIter;
    22
    23
    use crate::expressions::with_new_schema;
    24
    use crate::{add_offset_to_physical_sort_exprs, LexOrdering, PhysicalExpr};
    25
    26
    use arrow::compute::SortOptions;
    27
    use arrow::datatypes::SchemaRef;
    28
    use datafusion_common::{HashSet, Result};
    29
    use datafusion_physical_expr_common::sort_expr::PhysicalSortExpr;
    30
    31
    /// An `OrderingEquivalenceClass` keeps track of distinct alternative orderings
    32
    /// than can describe a table. For example, consider the following table:
    33
    ///
    34
    /// ```text
    35
    /// ┌───┬───┬───┬───┐
    36
    /// │ a │ b │ c │ d │
    37
    /// ├───┼───┼───┼───┤
    38
    /// │ 1 │ 4 │ 3 │ 1 │
    39
    /// │ 2 │ 3 │ 3 │ 2 │
    40
    /// │ 3 │ 1 │ 2 │ 2 │
    41
    /// │ 3 │ 2 │ 1 │ 3 │
    42
    /// └───┴───┴───┴───┘
    43
    /// ```
    44
    ///
    45
    /// Here, both `[a ASC, b ASC]` and `[c DESC, d ASC]` describe the table
    46
    /// ordering. In this case, we say that these orderings are equivalent.
    47
    ///
    48
    /// An `OrderingEquivalenceClass` is a set of such equivalent orderings, which
    49
    /// is represented by a vector of `LexOrdering`s. The set does not store any
    50
    /// redundant information by enforcing the invariant that no suffix of an
    51
    /// ordering in the equivalence class is a prefix of another ordering in the
    52
    /// equivalence class. The set can be empty, which means that there are no
    53
    /// orderings that describe the table.
    54
    #[derive(Clone, Debug, Default, Eq, PartialEq)]
    55
    pub struct OrderingEquivalenceClass {
    56
        orderings: Vec<LexOrdering>,
    57
    }
    58
    59
    impl OrderingEquivalenceClass {
    60
        /// Clears (empties) this ordering equivalence class.
    61
    0
        pub fn clear(&mut self) {
    62
    0
            self.orderings.clear();
    63
    0
        }
    64
    65
        /// Creates a new ordering equivalence class from the given orderings
    66
        /// and removes any redundant entries (if given).
    67
    0
        pub fn new(
    68
    0
            orderings: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
    69
    0
        ) -> Self {
    70
    0
            let mut result = Self {
    71
    0
                orderings: orderings.into_iter().filter_map(LexOrdering::new).collect(),
    72
    0
            };
    73
    0
            result.remove_redundant_entries();
    74
    0
            result
    75
    0
        }
    76
    77
        /// Extend this ordering equivalence class with the given orderings.
    78
    0
        pub fn extend(&mut self, orderings: impl IntoIterator<Item = LexOrdering>) {
    79
    0
            self.orderings.extend(orderings);
    80
            // Make sure that there are no redundant orderings:
    81
    0
            self.remove_redundant_entries();
    82
    0
        }
    83
    84
        /// Adds new orderings into this ordering equivalence class.
    85
    0
        pub fn add_orderings(
    86
    0
            &mut self,
    87
    0
            sort_exprs: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
    88
    0
        ) {
    89
    0
            self.orderings
    90
    0
                .extend(sort_exprs.into_iter().filter_map(LexOrdering::new));
    91
            // Make sure that there are no redundant orderings:
    92
    0
            self.remove_redundant_entries();
    93
    0
        }
    94
    95
        /// Removes redundant orderings from this ordering equivalence class.
    96
        ///
    97
        /// For instance, if we already have the ordering `[a ASC, b ASC, c DESC]`,
    98
        /// then there is no need to keep ordering `[a ASC, b ASC]` in the state.
    99
    0
        fn remove_redundant_entries(&mut self) {
    100
    0
            let mut work = true;
    101
    0
            while work {
    102
    0
                work = false;
    103
    0
                let mut idx = 0;
    104
    0
                'outer: while idx < self.orderings.len() {
    105
    0
                    let mut ordering_idx = idx + 1;
    106
    0
                    while ordering_idx < self.orderings.len() {
    107
    0
                        if let Some(remove) = self.resolve_overlap(idx, ordering_idx) {
    108
    0
                            work = true;
    109
    0
                            if remove {
    110
    0
                                self.orderings.swap_remove(idx);
    111
    0
                                continue 'outer;
    112
    0
                            }
    113
    0
                        }
    114
    0
                        if let Some(remove) = self.resolve_overlap(ordering_idx, idx) {
    115
    0
                            work = true;
    116
    0
                            if remove {
    117
    0
                                self.orderings.swap_remove(ordering_idx);
    118
    0
                                continue;
    119
    0
                            }
    120
    0
                        }
    121
    0
                        ordering_idx += 1;
    122
                    }
    123
    0
                    idx += 1;
    124
                }
    125
            }
    126
    0
        }
    127
    128
        /// Trims `orderings[idx]` if some suffix of it overlaps with a prefix of
    129
        /// `orderings[pre_idx]`. If there is any overlap, returns a `Some(true)`
    130
        /// if any trimming took place, and `Some(false)` otherwise. If there is
    131
        /// no overlap, returns `None`.
    132
        ///
    133
        /// For example, if `orderings[idx]` is `[a ASC, b ASC, c DESC]` and
    134
        /// `orderings[pre_idx]` is `[b ASC, c DESC]`, then the function will trim
    135
        /// `orderings[idx]` to `[a ASC]`.
    136
    0
        fn resolve_overlap(&mut self, idx: usize, pre_idx: usize) -> Option<bool> {
    137
    0
            let length = self.orderings[idx].len();
    138
    0
            let other_length = self.orderings[pre_idx].len();
    139
    0
            for overlap in 1..=length.min(other_length) {
    140
    0
                if self.orderings[idx][length - overlap..]
    141
    0
                    == self.orderings[pre_idx][..overlap]
    142
                {
    143
    0
                    return Some(!self.orderings[idx].truncate(length - overlap));
    144
    0
                }
    145
            }
    146
    0
            None
    147
    0
        }
    148
    149
        /// Returns the concatenation of all the orderings. This enables merge
    150
        /// operations to preserve all equivalent orderings simultaneously.
    151
    0
        pub fn output_ordering(&self) -> Option<LexOrdering> {
    152
    0
            self.orderings.iter().cloned().reduce(|mut cat, o| {
    153
    0
                cat.extend(o);
    154
    0
                cat
    155
    0
            })
    156
    0
        }
    157
    158
        // Append orderings in `other` to all existing orderings in this ordering
    159
        // equivalence class.
    160
    0
        pub fn join_suffix(mut self, other: &Self) -> Self {
    161
    0
            let n_ordering = self.orderings.len();
    162
            // Replicate entries before cross product:
    163
    0
            let n_cross = std::cmp::max(n_ordering, other.len() * n_ordering);
    164
    0
            self.orderings = self.orderings.into_iter().cycle().take(n_cross).collect();
    165
            // Append sort expressions of `other` to the current orderings:
    166
    0
            for (outer_idx, ordering) in other.iter().enumerate() {
    167
    0
                let base = outer_idx * n_ordering;
    168
                // Use the cross product index:
    169
    0
                for idx in base..(base + n_ordering) {
    170
    0
                    self.orderings[idx].extend(ordering.iter().cloned());
    171
    0
                }
    172
            }
    173
    0
            self
    174
    0
        }
    175
    176
        /// Adds `offset` value to the index of each expression inside this
    177
        /// ordering equivalence class.
    178
    0
        pub fn add_offset(&mut self, offset: isize) -> Result<()> {
    179
    0
            let orderings = std::mem::take(&mut self.orderings);
    180
    0
            for ordering_result in orderings
    181
    0
                .into_iter()
    182
    0
                .map(|o| add_offset_to_physical_sort_exprs(o, offset))
    183
            {
    184
    0
                self.orderings.extend(LexOrdering::new(ordering_result?));
    185
            }
    186
    0
            Ok(())
    187
    0
        }
    188
    189
        /// Transforms this `OrderingEquivalenceClass` by mapping columns in the
    190
        /// original schema to columns in the new schema by index. The new schema
    191
        /// and the original schema needs to be aligned; i.e. they should have the
    192
        /// same number of columns, and fields at the same index have the same type
    193
        /// in both schemas.
    194
    0
        pub fn with_new_schema(mut self, schema: &SchemaRef) -> Result<Self> {
    195
    0
            self.orderings = self
    196
    0
                .orderings
    197
    0
                .into_iter()
    198
    0
                .map(|ordering| {
    199
    0
                    ordering
    200
    0
                        .into_iter()
    201
    0
                        .map(|mut sort_expr| {
    202
    0
                            sort_expr.expr = with_new_schema(sort_expr.expr, schema)?;
    203
    0
                            Ok(sort_expr)
    204
    0
                        })
    205
    0
                        .collect::<Result<Vec<_>>>()
    206
                        // The following `unwrap` is safe because the vector will always
    207
                        // be non-empty.
    208
    0
                        .map(|v| LexOrdering::new(v).unwrap())
    209
    0
                })
    210
    0
                .collect::<Result<_>>()?;
    211
    0
            Ok(self)
    212
    0
        }
    213
    214
        /// Gets sort options associated with this expression if it is a leading
    215
        /// ordering expression. Otherwise, returns `None`.
    216
    0
        pub fn get_options(&self, expr: &Arc<dyn PhysicalExpr>) -> Option<SortOptions> {
    217
    0
            for ordering in self.iter() {
    218
    0
                let leading_ordering = &ordering[0];
    219
    0
                if leading_ordering.expr.eq(expr) {
    220
    0
                    return Some(leading_ordering.options);
    221
    0
                }
    222
            }
    223
    0
            None
    224
    0
        }
    225
    226
        /// Checks whether the given expression is partially constant according to
    227
        /// this ordering equivalence class.
    228
        ///
    229
        /// This function determines whether `expr` appears in at least one combination
    230
        /// of `descending` and `nulls_first` options that indicate partial constantness
    231
        /// in a lexicographical ordering. Specifically, an expression is considered
    232
        /// a partial constant in this context if its `SortOptions` satisfies either
    233
        /// of the following conditions:
    234
        /// - It is `descending` with `nulls_first` and _also_ `ascending` with
    235
        ///   `nulls_last`, OR
    236
        /// - It is `descending` with `nulls_last` and _also_ `ascending` with
    237
        ///   `nulls_first`.
    238
        ///
    239
        /// The equivalence mechanism primarily uses `ConstExpr`s to represent globally
    240
        /// constant expressions. However, some expressions may only be partially
    241
        /// constant within a lexicographical ordering. This function helps identify
    242
        /// such cases. If an expression is constant within a prefix ordering, it is
    243
        /// added as a constant during `ordering_satisfy_requirement()` iterations
    244
        /// after the corresponding prefix requirement is satisfied.
    245
        ///
    246
        /// ### Future Improvements
    247
        ///
    248
        /// This function may become unnecessary if any of the following improvements
    249
        /// are implemented:
    250
        /// 1. `SortOptions` supports encoding constantness information.
    251
        /// 2. `EquivalenceProperties` gains `FunctionalDependency` awareness, eliminating
    252
        ///    the need for `Constant` and `Constraints`.
    253
    0
        pub fn is_expr_partial_const(&self, expr: &Arc<dyn PhysicalExpr>) -> bool {
    254
    0
            let mut constantness_defining_pairs = [
    255
    0
                HashSet::from([(false, false), (true, true)]),
    256
    0
                HashSet::from([(false, true), (true, false)]),
    257
    0
            ];
    258
    259
    0
            for ordering in self.iter() {
    260
    0
                let leading_ordering = ordering.first();
    261
    0
                if leading_ordering.expr.eq(expr) {
    262
    0
                    let opt = (
    263
    0
                        leading_ordering.options.descending,
    264
    0
                        leading_ordering.options.nulls_first,
    265
    0
                    );
    266
    0
                    constantness_defining_pairs[0].remove(&opt);
    267
    0
                    constantness_defining_pairs[1].remove(&opt);
    268
    0
                }
    269
            }
    270
    271
    0
            constantness_defining_pairs
    272
    0
                .iter()
    273
    0
                .any(|pair| pair.is_empty())
    274
    0
        }
    275
    }
    276
    277
    impl Deref for OrderingEquivalenceClass {
    278
        type Target = [LexOrdering];
    279
    280
    0
        fn deref(&self) -> &Self::Target {
    281
    0
            self.orderings.as_slice()
    282
    0
        }
    283
    }
    284
    285
    impl From<Vec<LexOrdering>> for OrderingEquivalenceClass {
    286
    0
        fn from(orderings: Vec<LexOrdering>) -> Self {
    287
    0
            let mut result = Self { orderings };
    288
    0
            result.remove_redundant_entries();
    289
    0
            result
    290
    0
        }
    291
    }
    292
    293
    /// Convert the `OrderingEquivalenceClass` into an iterator of `LexOrdering`s.
    294
    impl IntoIterator for OrderingEquivalenceClass {
    295
        type Item = LexOrdering;
    296
        type IntoIter = IntoIter<Self::Item>;
    297
    298
    0
        fn into_iter(self) -> Self::IntoIter {
    299
    0
            self.orderings.into_iter()
    300
    0
        }
    301
    }
    302
    303
    impl Display for OrderingEquivalenceClass {
    304
    0
        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
    305
    0
            write!(f, "[")?;
    306
    0
            let mut iter = self.orderings.iter();
    307
    0
            if let Some(ordering) = iter.next() {
    308
    0
                write!(f, "[{ordering}]")?;
    309
    0
            }
    310
    0
            for ordering in iter {
    311
    0
                write!(f, ", [{ordering}]")?;
    312
            }
    313
    0
            write!(f, "]")
    314
    0
        }
    315
    }
    316
    317
    impl From<OrderingEquivalenceClass> for Vec<LexOrdering> {
    318
    0
        fn from(oeq_class: OrderingEquivalenceClass) -> Self {
    319
    0
            oeq_class.orderings
    320
    0
        }
    321
    }
    322
    323
    #[cfg(test)]
    324
    mod tests {
    325
        use std::sync::Arc;
    326
    327
        use crate::equivalence::tests::create_test_schema;
    328
        use crate::equivalence::{
    329
            convert_to_orderings, convert_to_sort_exprs, EquivalenceClass, EquivalenceGroup,
    330
            EquivalenceProperties, OrderingEquivalenceClass,
    331
        };
    332
        use crate::expressions::{col, BinaryExpr, Column};
    333
        use crate::utils::tests::TestScalarUDF;
    334
        use crate::{
    335
            AcrossPartitions, ConstExpr, PhysicalExpr, PhysicalExprRef, PhysicalSortExpr,
    336
            ScalarFunctionExpr,
    337
        };
    338
    339
        use arrow::compute::SortOptions;
    340
        use arrow::datatypes::{DataType, Field, Schema};
    341
        use datafusion_common::config::ConfigOptions;
    342
        use datafusion_common::Result;
    343
        use datafusion_expr::{Operator, ScalarUDF};
    344
    345
        #[test]
    346
    0
        fn test_ordering_satisfy() -> Result<()> {
    347
    0
            let input_schema = Arc::new(Schema::new(vec![
    348
    0
                Field::new("a", DataType::Int64, true),
    349
    0
                Field::new("b", DataType::Int64, true),
    350
            ]));
    351
    0
            let crude = vec![PhysicalSortExpr {
    352
    0
                expr: Arc::new(Column::new("a", 0)),
    353
    0
                options: SortOptions::default(),
    354
    0
            }];
    355
    0
            let finer = vec![
    356
    0
                PhysicalSortExpr {
    357
    0
                    expr: Arc::new(Column::new("a", 0)),
    358
    0
                    options: SortOptions::default(),
    359
    0
                },
    360
    0
                PhysicalSortExpr {
    361
    0
                    expr: Arc::new(Column::new("b", 1)),
    362
    0
                    options: SortOptions::default(),
    363
    0
                },
    364
            ];
    365
            // finer ordering satisfies, crude ordering should return true
    366
    0
            let eq_properties_finer = EquivalenceProperties::new_with_orderings(
    367
    0
                Arc::clone(&input_schema),
    368
    0
                [finer.clone()],
    369
            );
    370
    0
            assert!(eq_properties_finer.ordering_satisfy(crude.clone())?);
    371
    372
            // Crude ordering doesn't satisfy finer ordering. should return false
    373
    0
            let eq_properties_crude =
    374
    0
                EquivalenceProperties::new_with_orderings(Arc::clone(&input_schema), [crude]);
    375
    0
            assert!(!eq_properties_crude.ordering_satisfy(finer)?);
    376
    0
            Ok(())
    377
    0
        }
    378
    379
        #[test]
    380
    0
        fn test_ordering_satisfy_with_equivalence2() -> Result<()> {
    381
    0
            let test_schema = create_test_schema()?;
    382
    0
            let col_a = &col("a", &test_schema)?;
    383
    0
            let col_b = &col("b", &test_schema)?;
    384
    0
            let col_c = &col("c", &test_schema)?;
    385
    0
            let col_d = &col("d", &test_schema)?;
    386
    0
            let col_e = &col("e", &test_schema)?;
    387
    0
            let col_f = &col("f", &test_schema)?;
    388
    0
            let test_fun = Arc::new(ScalarUDF::new_from_impl(TestScalarUDF::new()));
    389
    390
    0
            let floor_a = Arc::new(ScalarFunctionExpr::try_new(
    391
    0
                Arc::clone(&test_fun),
    392
    0
                vec![Arc::clone(col_a)],
    393
    0
                &test_schema,
    394
    0
                Arc::new(ConfigOptions::default()),
    395
    0
            )?) as PhysicalExprRef;
    396
    0
            let floor_f = Arc::new(ScalarFunctionExpr::try_new(
    397
    0
                Arc::clone(&test_fun),
    398
    0
                vec![Arc::clone(col_f)],
    399
    0
                &test_schema,
    400
    0
                Arc::new(ConfigOptions::default()),
    401
    0
            )?) as PhysicalExprRef;
    402
    0
            let exp_a = Arc::new(ScalarFunctionExpr::try_new(
    403
    0
                Arc::clone(&test_fun),
    404
    0
                vec![Arc::clone(col_a)],
    405
    0
                &test_schema,
    406
    0
                Arc::new(ConfigOptions::default()),
    407
    0
            )?) as PhysicalExprRef;
    408
    409
    0
            let a_plus_b = Arc::new(BinaryExpr::new(
    410
    0
                Arc::clone(col_a),
    411
    0
                Operator::Plus,
    412
    0
                Arc::clone(col_b),
    413
    0
            )) as Arc<dyn PhysicalExpr>;
    414
    0
            let options = SortOptions {
    415
    0
                descending: false,
    416
    0
                nulls_first: false,
    417
    0
            };
    418
    419
    0
            let test_cases = vec![
    420
                // ------------ TEST CASE 1 ------------
    421
    0
                (
    422
    0
                    // orderings
    423
    0
                    vec![
    424
    0
                        // [a ASC, d ASC, b ASC]
    425
    0
                        vec![(col_a, options), (col_d, options), (col_b, options)],
    426
    0
                        // [c ASC]
    427
    0
                        vec![(col_c, options)],
    428
    0
                    ],
    429
    0
                    // equivalence classes
    430
    0
                    vec![vec![col_a, col_f]],
    431
    0
                    // constants
    432
    0
                    vec![col_e],
    433
    0
                    // requirement [a ASC, b ASC], requirement is not satisfied.
    434
    0
                    vec![(col_a, options), (col_b, options)],
    435
    0
                    // expected: requirement is not satisfied.
    436
    0
                    false,
    437
    0
                ),
    438
                // ------------ TEST CASE 2 ------------
    439
    0
                (
    440
    0
                    // orderings
    441
    0
                    vec![
    442
    0
                        // [a ASC, c ASC, b ASC]
    443
    0
                        vec![(col_a, options), (col_c, options), (col_b, options)],
    444
    0
                        // [d ASC]
    445
    0
                        vec![(col_d, options)],
    446
    0
                    ],
    447
    0
                    // equivalence classes
    448
    0
                    vec![vec![col_a, col_f]],
    449
    0
                    // constants
    450
    0
                    vec![col_e],
    451
    0
                    // requirement [floor(a) ASC],
    452
    0
                    vec![(&floor_a, options)],
    453
    0
                    // expected: requirement is satisfied.
    454
    0
                    true,
    455
    0
                ),
    456
                // ------------ TEST CASE 2.1 ------------
    457
    0
                (
    458
    0
                    // orderings
    459
    0
                    vec![
    460
    0
                        // [a ASC, c ASC, b ASC]
    461
    0
                        vec![(col_a, options), (col_c, options), (col_b, options)],
    462
    0
                        // [d ASC]
    463
    0
                        vec![(col_d, options)],
    464
    0
                    ],
    465
    0
                    // equivalence classes
    466
    0
                    vec![vec![col_a, col_f]],
    467
    0
                    // constants
    468
    0
                    vec![col_e],
    469
    0
                    // requirement [floor(f) ASC], (Please note that a=f)
    470
    0
                    vec![(&floor_f, options)],
    471
    0
                    // expected: requirement is satisfied.
    472
    0
                    true,
    473
    0
                ),
    474
                // ------------ TEST CASE 3 ------------
    475
    0
                (
    476
    0
                    // orderings
    477
    0
                    vec![
    478
    0
                        // [a ASC, c ASC, b ASC]
    479
    0
                        vec![(col_a, options), (col_c, options), (col_b, options)],
    480
    0
                        // [d ASC]
    481
    0
                        vec![(col_d, options)],
    482
    0
                    ],
    483
    0
                    // equivalence classes
    484
    0
                    vec![vec![col_a, col_f]],
    485
    0
                    // constants
    486
    0
                    vec![col_e],
    487
    0
                    // requirement [a ASC, c ASC, a+b ASC],
    488
    0
                    vec![(col_a, options), (col_c, options), (&a_plus_b, options)],
    489
    0
                    // expected: requirement is satisfied.
    490
    0
                    true,
    491
    0
                ),
    492
                // ------------ TEST CASE 4 ------------
    493
    0
                (
    494
    0
                    // orderings
    495
    0
                    vec![
    496
    0
                        // [a ASC, b ASC, c ASC, d ASC]
    497
    0
                        vec![
    498
    0
                            (col_a, options),
    499
    0
                            (col_b, options),
    500
    0
                            (col_c, options),
    501
    0
                            (col_d, options),
    502
    0
                        ],
    503
    0
                    ],
    504
    0
                    // equivalence classes
    505
    0
                    vec![vec![col_a, col_f]],
    506
    0
                    // constants
    507
    0
                    vec![col_e],
    508
    0
                    // requirement [floor(a) ASC, a+b ASC],
    509
    0
                    vec![(&floor_a, options), (&a_plus_b, options)],
    510
    0
                    // expected: requirement is satisfied.
    511
    0
                    false,
    512
    0
                ),
    513
                // ------------ TEST CASE 5 ------------
    514
    0
                (
    515
    0
                    // orderings
    516
    0
                    vec![
    517
    0
                        // [a ASC, b ASC, c ASC, d ASC]
    518
    0
                        vec![
    519
    0
                            (col_a, options),
    520
    0
                            (col_b, options),
    521
    0
                            (col_c, options),
    522
    0
                            (col_d, options),
    523
    0
                        ],
    524
    0
                    ],
    525
    0
                    // equivalence classes
    526
    0
                    vec![vec![col_a, col_f]],
    527
    0
                    // constants
    528
    0
                    vec![col_e],
    529
    0
                    // requirement [exp(a) ASC, a+b ASC],
    530
    0
                    vec![(&exp_a, options), (&a_plus_b, options)],
    531
    0
                    // expected: requirement is not satisfied.
    532
    0
                    // TODO: If we know that exp function is 1-to-1 function.
    533
    0
                    //  we could have deduced that above requirement is satisfied.
    534
    0
                    false,
    535
    0
                ),
    536
                // ------------ TEST CASE 6 ------------
    537
    0
                (
    538
    0
                    // orderings
    539
    0
                    vec![
    540
    0
                        // [a ASC, d ASC, b ASC]
    541
    0
                        vec![(col_a, options), (col_d, options), (col_b, options)],
    542
    0
                        // [c ASC]
    543
    0
                        vec![(col_c, options)],
    544
    0
                    ],
    545
    0
                    // equivalence classes
    546
    0
                    vec![vec![col_a, col_f]],
    547
    0
                    // constants
    548
    0
                    vec![col_e],
    549
    0
                    // requirement [a ASC, d ASC, floor(a) ASC],
    550
    0
                    vec![(col_a, options), (col_d, options), (&floor_a, options)],
    551
    0
                    // expected: requirement is satisfied.
    552
    0
                    true,
    553
    0
                ),
    554
                // ------------ TEST CASE 7 ------------
    555
    0
                (
    556
    0
                    // orderings
    557
    0
                    vec![
    558
    0
                        // [a ASC, c ASC, b ASC]
    559
    0
                        vec![(col_a, options), (col_c, options), (col_b, options)],
    560
    0
                        // [d ASC]
    561
    0
                        vec![(col_d, options)],
    562
    0
                    ],
    563
    0
                    // equivalence classes
    564
    0
                    vec![vec![col_a, col_f]],
    565
    0
                    // constants
    566
    0
                    vec![col_e],
    567
    0
                    // requirement [a ASC, floor(a) ASC, a + b ASC],
    568
    0
                    vec![(col_a, options), (&floor_a, options), (&a_plus_b, options)],
    569
    0
                    // expected: requirement is not satisfied.
    570
    0
                    false,
    571
    0
                ),
    572
                // ------------ TEST CASE 8 ------------
    573
    0
                (
    574
    0
                    // orderings
    575
    0
                    vec![
    576
    0
                        // [a ASC, b ASC, c ASC]
    577
    0
                        vec![(col_a, options), (col_b, options), (col_c, options)],
    578
    0
                        // [d ASC]
    579
    0
                        vec![(col_d, options)],
    580
    0
                    ],
    581
    0
                    // equivalence classes
    582
    0
                    vec![vec![col_a, col_f]],
    583
    0
                    // constants
    584
    0
                    vec![col_e],
    585
    0
                    // requirement [a ASC, c ASC, floor(a) ASC, a + b ASC],
    586
    0
                    vec![
    587
    0
                        (col_a, options),
    588
    0
                        (col_c, options),
    589
    0
                        (&floor_a, options),
    590
    0
                        (&a_plus_b, options),
    591
    0
                    ],
    592
    0
                    // expected: requirement is not satisfied.
    593
    0
                    false,
    594
    0
                ),
    595
                // ------------ TEST CASE 9 ------------
    596
    0
                (
    597
    0
                    // orderings
    598
    0
                    vec![
    599
    0
                        // [a ASC, b ASC, c ASC, d ASC]
    600
    0
                        vec![
    601
    0
                            (col_a, options),
    602
    0
                            (col_b, options),
    603
    0
                            (col_c, options),
    604
    0
                            (col_d, options),
    605
    0
                        ],
    606
    0
                    ],
    607
    0
                    // equivalence classes
    608
    0
                    vec![vec![col_a, col_f]],
    609
    0
                    // constants
    610
    0
                    vec![col_e],
    611
    0
                    // requirement [a ASC, b ASC, c ASC, floor(a) ASC],
    612
    0
                    vec![
    613
    0
                        (col_a, options),
    614
    0
                        (col_b, options),
    615
    0
                        (col_c, options),
    616
    0
                        (&floor_a, options),
    617
    0
                    ],
    618
    0
                    // expected: requirement is satisfied.
    619
    0
                    true,
    620
    0
                ),
    621
                // ------------ TEST CASE 10 ------------
    622
    0
                (
    623
    0
                    // orderings
    624
    0
                    vec![
    625
    0
                        // [d ASC, b ASC]
    626
    0
                        vec![(col_d, options), (col_b, options)],
    627
    0
                        // [c ASC, a ASC]
    628
    0
                        vec![(col_c, options), (col_a, options)],
    629
    0
                    ],
    630
    0
                    // equivalence classes
    631
    0
                    vec![vec![col_a, col_f]],
    632
    0
                    // constants
    633
    0
                    vec![col_e],
    634
    0
                    // requirement [c ASC, d ASC, a + b ASC],
    635
    0
                    vec![(col_c, options), (col_d, options), (&a_plus_b, options)],
    636
    0
                    // expected: requirement is satisfied.
    637
    0
                    true,
    638
    0
                ),
    639
            ];
    640
    641
    0
            for (orderings, eq_group, constants, reqs, expected) in test_cases {
    642
    0
                let err_msg =
    643
    0
                    format!("error in test orderings: {orderings:?}, eq_group: {eq_group:?}, constants: {constants:?}, reqs: {reqs:?}, expected: {expected:?}");
    644
    0
                let mut eq_properties = EquivalenceProperties::new(Arc::clone(&test_schema));
    645
    0
                let orderings = convert_to_orderings(&orderings);
    646
    0
                eq_properties.add_orderings(orderings);
    647
    0
                let classes = eq_group
    648
    0
                    .into_iter()
    649
    0
                    .map(|eq_class| EquivalenceClass::new(eq_class.into_iter().cloned()));
    650
    0
                let eq_group = EquivalenceGroup::new(classes);
    651
    0
                eq_properties.add_equivalence_group(eq_group)?;
    652
    653
    0
                let constants = constants.into_iter().map(|expr| {
    654
    0
                    ConstExpr::new(Arc::clone(expr), AcrossPartitions::Uniform(None))
    655
    0
                });
    656
    0
                eq_properties.add_constants(constants)?;
    657
    658
    0
                let reqs = convert_to_sort_exprs(&reqs);
    659
    0
                assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
    660
            }
    661
    662
    0
            Ok(())
    663
    0
        }
    664
    665
        #[test]
    666
    0
        fn test_ordering_satisfy_different_lengths() -> Result<()> {
    667
    0
            let test_schema = create_test_schema()?;
    668
    0
            let col_a = &col("a", &test_schema)?;
    669
    0
            let col_b = &col("b", &test_schema)?;
    670
    0
            let col_c = &col("c", &test_schema)?;
    671
    0
            let col_d = &col("d", &test_schema)?;
    672
    0
            let col_e = &col("e", &test_schema)?;
    673
    0
            let col_f = &col("f", &test_schema)?;
    674
    0
            let options = SortOptions {
    675
    0
                descending: false,
    676
    0
                nulls_first: false,
    677
    0
            };
    678
            // a=c (e.g they are aliases).
    679
    0
            let mut eq_properties = EquivalenceProperties::new(test_schema);
    680
    0
            eq_properties.add_equal_conditions(Arc::clone(col_a), Arc::clone(col_c))?;
    681
    682
    0
            let orderings = vec![
    683
    0
                vec![(col_a, options)],
    684
    0
                vec![(col_e, options)],
    685
    0
                vec![(col_d, options), (col_f, options)],
    686
            ];
    687
    0
            let orderings = convert_to_orderings(&orderings);
    688
    689
            // Column [a ASC], [e ASC], [d ASC, f ASC] are all valid orderings for the schema.
    690
    0
            eq_properties.add_orderings(orderings);
    691
    692
            // First entry in the tuple is required ordering, second entry is the expected flag
    693
            // that indicates whether this required ordering is satisfied.
    694
            // ([a ASC], true) indicate a ASC requirement is already satisfied by existing orderings.
    695
    0
            let test_cases = vec![
    696
                // [c ASC, a ASC, e ASC], expected represents this requirement is satisfied
    697
    0
                (
    698
    0
                    vec![(col_c, options), (col_a, options), (col_e, options)],
    699
    0
                    true,
    700
    0
                ),
    701
    0
                (vec![(col_c, options), (col_b, options)], false),
    702
    0
                (vec![(col_c, options), (col_d, options)], true),
    703
    0
                (
    704
    0
                    vec![(col_d, options), (col_f, options), (col_b, options)],
    705
    0
                    false,
    706
    0
                ),
    707
    0
                (vec![(col_d, options), (col_f, options)], true),
    708
            ];
    709
    710
    0
            for (reqs, expected) in test_cases {
    711
    0
                let err_msg =
    712
    0
                    format!("error in test reqs: {reqs:?}, expected: {expected:?}",);
    713
    0
                let reqs = convert_to_sort_exprs(&reqs);
    714
    0
                assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
    715
            }
    716
    717
    0
            Ok(())
    718
    0
        }
    719
    720
        #[test]
    721
    0
        fn test_remove_redundant_entries_oeq_class() -> Result<()> {
    722
    0
            let schema = create_test_schema()?;
    723
    0
            let col_a = &col("a", &schema)?;
    724
    0
            let col_b = &col("b", &schema)?;
    725
    0
            let col_c = &col("c", &schema)?;
    726
    0
            let col_d = &col("d", &schema)?;
    727
    0
            let col_e = &col("e", &schema)?;
    728
    729
    0
            let option_asc = SortOptions {
    730
    0
                descending: false,
    731
    0
                nulls_first: false,
    732
    0
            };
    733
    0
            let option_desc = SortOptions {
    734
    0
                descending: true,
    735
    0
                nulls_first: true,
    736
    0
            };
    737
    738
            // First entry in the tuple is the given orderings for the table
    739
            // Second entry is the simplest version of the given orderings that is functionally equivalent.
    740
    0
            let test_cases = vec![
    741
                // ------- TEST CASE 1 ---------
    742
    0
                (
    743
    0
                    // ORDERINGS GIVEN
    744
    0
                    vec![
    745
    0
                        // [a ASC, b ASC]
    746
    0
                        vec![(col_a, option_asc), (col_b, option_asc)],
    747
    0
                    ],
    748
    0
                    // EXPECTED orderings that is succinct.
    749
    0
                    vec![
    750
    0
                        // [a ASC, b ASC]
    751
    0
                        vec![(col_a, option_asc), (col_b, option_asc)],
    752
    0
                    ],
    753
    0
                ),
    754
                // ------- TEST CASE 2 ---------
    755
    0
                (
    756
    0
                    // ORDERINGS GIVEN
    757
    0
                    vec![
    758
    0
                        // [a ASC, b ASC]
    759
    0
                        vec![(col_a, option_asc), (col_b, option_asc)],
    760
    0
                        // [a ASC, b ASC, c ASC]
    761
    0
                        vec![
    762
    0
                            (col_a, option_asc),
    763
    0
                            (col_b, option_asc),
    764
    0
                            (col_c, option_asc),
    765
    0
                        ],
    766
    0
                    ],
    767
    0
                    // EXPECTED orderings that is succinct.
    768
    0
                    vec![
    769
    0
                        // [a ASC, b ASC, c ASC]
    770
    0
                        vec![
    771
    0
                            (col_a, option_asc),
    772
    0
                            (col_b, option_asc),
    773
    0
                            (col_c, option_asc),
    774
    0
                        ],
    775
    0
                    ],
    776
    0
                ),
    777
                // ------- TEST CASE 3 ---------
    778
    0
                (
    779
    0
                    // ORDERINGS GIVEN
    780
    0
                    vec![
    781
    0
                        // [a ASC, b DESC]
    782
    0
                        vec![(col_a, option_asc), (col_b, option_desc)],
    783
    0
                        // [a ASC]
    784
    0
                        vec![(col_a, option_asc)],
    785
    0
                        // [a ASC, c ASC]
    786
    0
                        vec![(col_a, option_asc), (col_c, option_asc)],
    787
    0
                    ],
    788
    0
                    // EXPECTED orderings that is succinct.
    789
    0
                    vec![
    790
    0
                        // [a ASC, b DESC]
    791
    0
                        vec![(col_a, option_asc), (col_b, option_desc)],
    792
    0
                        // [a ASC, c ASC]
    793
    0
                        vec![(col_a, option_asc), (col_c, option_asc)],
    794
    0
                    ],
    795
    0
                ),
    796
                // ------- TEST CASE 4 ---------
    797
    0
                (
    798
    0
                    // ORDERINGS GIVEN
    799
    0
                    vec![
    800
    0
                        // [a ASC, b ASC]
    801
    0
                        vec![(col_a, option_asc), (col_b, option_asc)],
    802
    0
                        // [a ASC, b ASC, c ASC]
    803
    0
                        vec![
    804
    0
                            (col_a, option_asc),
    805
    0
                            (col_b, option_asc),
    806
    0
                            (col_c, option_asc),
    807
    0
                        ],
    808
    0
                        // [a ASC]
    809
    0
                        vec![(col_a, option_asc)],
    810
    0
                    ],
    811
    0
                    // EXPECTED orderings that is succinct.
    812
    0
                    vec![
    813
    0
                        // [a ASC, b ASC, c ASC]
    814
    0
                        vec![
    815
    0
                            (col_a, option_asc),
    816
    0
                            (col_b, option_asc),
    817
    0
                            (col_c, option_asc),
    818
    0
                        ],
    819
    0
                    ],
    820
    0
                ),
    821
                // ------- TEST CASE 5 ---------
    822
                // Empty ordering
    823
    0
                (
    824
    0
                    vec![],
    825
    0
                    // No ordering in the state (empty ordering is ignored).
    826
    0
                    vec![],
    827
    0
                ),
    828
                // ------- TEST CASE 6 ---------
    829
    0
                (
    830
    0
                    // ORDERINGS GIVEN
    831
    0
                    vec![
    832
    0
                        // [a ASC, b ASC]
    833
    0
                        vec![(col_a, option_asc), (col_b, option_asc)],
    834
    0
                        // [b ASC]
    835
    0
                        vec![(col_b, option_asc)],
    836
    0
                    ],
    837
    0
                    // EXPECTED orderings that is succinct.
    838
    0
                    vec![
    839
    0
                        // [a ASC]
    840
    0
                        vec![(col_a, option_asc)],
    841
    0
                        // [b ASC]
    842
    0
                        vec![(col_b, option_asc)],
    843
    0
                    ],
    844
    0
                ),
    845
                // ------- TEST CASE 7 ---------
    846
                // b, a
    847
                // c, a
    848
                // d, b, c
    849
    0
                (
    850
    0
                    // ORDERINGS GIVEN
    851
    0
                    vec![
    852
    0
                        // [b ASC, a ASC]
    853
    0
                        vec![(col_b, option_asc), (col_a, option_asc)],
    854
    0
                        // [c ASC, a ASC]
    855
    0
                        vec![(col_c, option_asc), (col_a, option_asc)],
    856
    0
                        // [d ASC, b ASC, c ASC]
    857
    0
                        vec![
    858
    0
                            (col_d, option_asc),
    859
    0
                            (col_b, option_asc),
    860
    0
                            (col_c, option_asc),
    861
    0
                        ],
    862
    0
                    ],
    863
    0
                    // EXPECTED orderings that is succinct.
    864
    0
                    vec![
    865
    0
                        // [b ASC, a ASC]
    866
    0
                        vec![(col_b, option_asc), (col_a, option_asc)],
    867
    0
                        // [c ASC, a ASC]
    868
    0
                        vec![(col_c, option_asc), (col_a, option_asc)],
    869
    0
                        // [d ASC]
    870
    0
                        vec![(col_d, option_asc)],
    871
    0
                    ],
    872
    0
                ),
    873
                // ------- TEST CASE 8 ---------
    874
                // b, e
    875
                // c, a
    876
                // d, b, e, c, a
    877
    0
                (
    878
    0
                    // ORDERINGS GIVEN
    879
    0
                    vec![
    880
    0
                        // [b ASC, e ASC]
    881
    0
                        vec![(col_b, option_asc), (col_e, option_asc)],
    882
    0
                        // [c ASC, a ASC]
    883
    0
                        vec![(col_c, option_asc), (col_a, option_asc)],
    884
    0
                        // [d ASC, b ASC, e ASC, c ASC, a ASC]
    885
    0
                        vec![
    886
    0
                            (col_d, option_asc),
    887
    0
                            (col_b, option_asc),
    888
    0
                            (col_e, option_asc),
    889
    0
                            (col_c, option_asc),
    890
    0
                            (col_a, option_asc),
    891
    0
                        ],
    892
    0
                    ],
    893
    0
                    // EXPECTED orderings that is succinct.
    894
    0
                    vec![
    895
    0
                        // [b ASC, e ASC]
    896
    0
                        vec![(col_b, option_asc), (col_e, option_asc)],
    897
    0
                        // [c ASC, a ASC]
    898
    0
                        vec![(col_c, option_asc), (col_a, option_asc)],
    899
    0
                        // [d ASC]
    900
    0
                        vec![(col_d, option_asc)],
    901
    0
                    ],
    902
    0
                ),
    903
                // ------- TEST CASE 9 ---------
    904
                // b
    905
                // a, b, c
    906
                // d, a, b
    907
    0
                (
    908
    0
                    // ORDERINGS GIVEN
    909
    0
                    vec![
    910
    0
                        // [b ASC]
    911
    0
                        vec![(col_b, option_asc)],
    912
    0
                        // [a ASC, b ASC, c ASC]
    913
    0
                        vec![
    914
    0
                            (col_a, option_asc),
    915
    0
                            (col_b, option_asc),
    916
    0
                            (col_c, option_asc),
    917
    0
                        ],
    918
    0
                        // [d ASC, a ASC, b ASC]
    919
    0
                        vec![
    920
    0
                            (col_d, option_asc),
    921
    0
                            (col_a, option_asc),
    922
    0
                            (col_b, option_asc),
    923
    0
                        ],
    924
    0
                    ],
    925
    0
                    // EXPECTED orderings that is succinct.
    926
    0
                    vec![
    927
    0
                        // [b ASC]
    928
    0
                        vec![(col_b, option_asc)],
    929
    0
                        // [a ASC, b ASC, c ASC]
    930
    0
                        vec![
    931
    0
                            (col_a, option_asc),
    932
    0
                            (col_b, option_asc),
    933
    0
                            (col_c, option_asc),
    934
    0
                        ],
    935
    0
                        // [d ASC]
    936
    0
                        vec![(col_d, option_asc)],
    937
    0
                    ],
    938
    0
                ),
    939
            ];
    940
    0
            for (orderings, expected) in test_cases {
    941
    0
                let orderings = convert_to_orderings(&orderings);
    942
    0
                let expected = convert_to_orderings(&expected);
    943
    0
                let actual = OrderingEquivalenceClass::from(orderings.clone());
    944
    0
                let err_msg = format!(
    945
    0
                    "orderings: {orderings:?}, expected: {expected:?}, actual :{actual:?}"
    946
                );
    947
    0
                assert_eq!(actual.len(), expected.len(), "{err_msg}");
    948
    0
                for elem in actual {
    949
    0
                    assert!(expected.contains(&elem), "{}", err_msg);
    950
                }
    951
            }
    952
    953
    0
            Ok(())
    954
    0
        }
    955
    }