## 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/utils/guarantee.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
    //! [`LiteralGuarantee`] predicate analysis to determine if a column is a
    19
    //! constant.
    20
    21
    use crate::utils::split_disjunction;
    22
    use crate::{split_conjunction, PhysicalExpr};
    23
    use datafusion_common::{Column, HashMap, ScalarValue};
    24
    use datafusion_expr::Operator;
    25
    use std::collections::HashSet;
    26
    use std::fmt::{self, Display, Formatter};
    27
    use std::sync::Arc;
    28
    29
    /// Represents a guarantee that must be true for a boolean expression to
    30
    /// evaluate to `true`.
    31
    ///
    32
    /// The guarantee takes the form of a column and a set of literal (constant)
    33
    /// [`ScalarValue`]s. For the expression to evaluate to `true`, the column *must
    34
    /// satisfy* the guarantee(s).
    35
    ///
    36
    /// To satisfy the guarantee, depending on [`Guarantee`], the values in the
    37
    /// column must either:
    38
    ///
    39
    /// 1. be ONLY one of that set
    40
    /// 2. NOT be ANY of that set
    41
    ///
    42
    /// # Uses `LiteralGuarantee`s
    43
    ///
    44
    /// `LiteralGuarantee`s can be used to simplify filter expressions and skip data
    45
    /// files (e.g. row groups in parquet files) by proving expressions can not
    46
    /// possibly evaluate to `true`. For example, if we have a guarantee that `a`
    47
    /// must be in (`1`) for a filter to evaluate to `true`, then we can skip any
    48
    /// partition where we know that `a` never has the value of `1`.
    49
    ///
    50
    /// **Important**: If a `LiteralGuarantee` is not satisfied, the relevant
    51
    /// expression is *guaranteed* to evaluate to `false` or `null`. **However**,
    52
    /// the opposite does not hold. Even if all `LiteralGuarantee`s are satisfied,
    53
    /// that does **not** guarantee that the predicate will actually evaluate to
    54
    /// `true`: it may still evaluate to `true`, `false` or `null`.
    55
    ///
    56
    /// # Creating `LiteralGuarantee`s
    57
    ///
    58
    /// Use [`LiteralGuarantee::analyze`] to extract literal guarantees from a
    59
    /// filter predicate.
    60
    ///
    61
    /// # Details
    62
    /// A guarantee can be one of two forms:
    63
    ///
    64
    /// 1. The column must be one the values for the predicate to be `true`. If the
    65
    ///    column takes on any other value, the predicate can not evaluate to `true`.
    66
    ///    For example,
    67
    ///    `(a = 1)`, `(a = 1 OR a = 2)` or `a IN (1, 2, 3)`
    68
    ///
    69
    /// 2. The column must NOT be one of the values for the predicate to be `true`.
    70
    ///    If the column can ONLY take one of these values, the predicate can not
    71
    ///    evaluate to `true`. For example,
    72
    ///    `(a != 1)`, `(a != 1 AND a != 2)` or `a NOT IN (1, 2, 3)`
    73
    #[derive(Debug, Clone, PartialEq)]
    74
    pub struct LiteralGuarantee {
    75
        pub column: Column,
    76
        pub guarantee: Guarantee,
    77
        pub literals: HashSet<ScalarValue>,
    78
    }
    79
    80
    /// What is guaranteed about the values for a [`LiteralGuarantee`]?
    81
    #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
    82
    pub enum Guarantee {
    83
        /// Guarantee that the expression is `true` if `column` is one of the values. If
    84
        /// `column` is not one of the values, the expression can not be `true`.
    85
        In,
    86
        /// Guarantee that the expression is `true` if `column` is not ANY of the
    87
        /// values. If `column` only takes one of these values, the expression can
    88
        /// not be `true`.
    89
        NotIn,
    90
    }
    91
    92
    impl LiteralGuarantee {
    93
        /// Create a new instance of the guarantee if the provided operator is
    94
        /// supported. Returns None otherwise. See [`LiteralGuarantee::analyze`] to
    95
        /// create these structures from an predicate (boolean expression).
    96
    0
        fn new<'a>(
    97
    0
            column_name: impl Into<String>,
    98
    0
            guarantee: Guarantee,
    99
    0
            literals: impl IntoIterator<Item = &'a ScalarValue>,
    100
    0
        ) -> Self {
    101
    0
            let literals: HashSet<_> = literals.into_iter().cloned().collect();
    102
    103
    0
            Self {
    104
    0
                column: Column::from_name(column_name),
    105
    0
                guarantee,
    106
    0
                literals,
    107
    0
            }
    108
    0
        }
    109
    110
        /// Return a list of [`LiteralGuarantee`]s that must be satisfied for `expr`
    111
        /// to evaluate to `true`.
    112
        ///
    113
        /// If more than one `LiteralGuarantee` is returned, they must **all** hold
    114
        /// for the expression to possibly be `true`. If any is not satisfied, the
    115
        /// expression is guaranteed to be `null` or `false`.
    116
        ///
    117
        /// # Notes:
    118
        /// 1. `expr` must be a boolean expression or inlist expression.
    119
        /// 2. `expr` is not simplified prior to analysis.
    120
    0
        pub fn analyze(expr: &Arc<dyn PhysicalExpr>) -> Vec<LiteralGuarantee> {
    121
            // split conjunction: <expr> AND <expr> AND ...
    122
    0
            split_conjunction(expr)
    123
    0
                .into_iter()
    124
                // for an `AND` conjunction to be true, all terms individually must be true
    125
    0
                .fold(GuaranteeBuilder::new(), |builder, expr| {
    126
    0
                    if let Some(cel) = ColOpLit::try_new(expr) {
    127
    0
                        builder.aggregate_conjunct(&cel)
    128
    0
                    } else if let Some(inlist) = expr
    129
    0
                        .as_any()
    130
    0
                        .downcast_ref::<crate::expressions::InListExpr>()
    131
                    {
    132
    0
                        if let Some(inlist) = ColInList::try_new(inlist) {
    133
    0
                            builder.aggregate_multi_conjunct(
    134
    0
                                inlist.col,
    135
    0
                                inlist.guarantee,
    136
    0
                                inlist.list.iter().map(|lit| lit.value()),
    137
                            )
    138
                        } else {
    139
    0
                            builder
    140
                        }
    141
                    } else {
    142
                        // split disjunction: <expr> OR <expr> OR ...
    143
    0
                        let disjunctions = split_disjunction(expr);
    144
    145
                        // We are trying to add a guarantee that a column must be
    146
                        // in/not in a particular set of values for the expression
    147
                        // to evaluate to true.
    148
                        //
    149
                        // A disjunction is true, if at least one of the terms is be
    150
                        // true.
    151
                        //
    152
                        // Thus, we can infer a guarantee if all terms are of the
    153
                        // form `(col <op> literal) OR (col <op> literal) OR ...`.
    154
                        //
    155
                        // For example, we can infer that `a = 1 OR a = 2 OR a = 3`
    156
                        // is guaranteed to be true ONLY if a is in (`1`, `2` or `3`).
    157
                        //
    158
                        // However, for something like  `a = 1 OR a = 2 OR a < 0` we
    159
                        // **can't** guarantee that the predicate is only true if a
    160
                        // is in (`1`, `2`), as it could also be true if `a` were less
    161
                        // than zero.
    162
    0
                        let terms = disjunctions
    163
    0
                            .iter()
    164
    0
                            .filter_map(|expr| ColOpLit::try_new(expr))
    165
    0
                            .collect::<Vec<_>>();
    166
    167
                        // if all terms are 'col <op> literal' with the same column
    168
                        // and operation we can infer any guarantees
    169
                        //
    170
                        // For those like (a != foo AND (a != bar OR a != baz)).
    171
                        // We can't combine the (a != bar OR a != baz) part, but
    172
                        // it also doesn't invalidate our knowledge that a !=
    173
                        // foo is required for the expression to be true.
    174
                        // So we can only create a multi value guarantee for `=`
    175
                        // (or a single value). (e.g. ignore `a != foo OR a != bar`)
    176
    0
                        let first_term = terms.first();
    177
    0
                        if !terms.is_empty()
    178
    0
                            && terms.len() == disjunctions.len()
    179
    0
                            && terms.iter().all(|term| {
    180
    0
                                term.col.name() == first_term.unwrap().col.name()
    181
    0
                                    && term.guarantee == Guarantee::In
    182
    0
                            })
    183
                        {
    184
    0
                            builder.aggregate_multi_conjunct(
    185
    0
                                first_term.unwrap().col,
    186
    0
                                Guarantee::In,
    187
    0
                                terms.iter().map(|term| term.lit.value()),
    188
                            )
    189
                        } else {
    190
                            // Handle disjunctions with conjunctions like (a = 1 AND b = 2) OR (a = 2 AND b = 3)
    191
                            // Extract termsets from each disjunction
    192
                            // if in each termset, they have same column, and the guarantee is In,
    193
                            // we can infer a guarantee for the column
    194
                            // e.g. (a = 1 AND b = 2) OR (a = 2 AND b = 3) is `a IN (1, 2) AND b IN (2, 3)`
    195
                            // otherwise, we can't infer a guarantee
    196
    0
                            let termsets: Vec<Vec<ColOpLitOrInList>> = disjunctions
    197
    0
                                .iter()
    198
    0
                                .map(|expr| {
    199
    0
                                    split_conjunction(expr)
    200
    0
                                        .into_iter()
    201
    0
                                        .filter_map(ColOpLitOrInList::try_new)
    202
    0
                                        .filter(|term| term.guarantee() == Guarantee::In)
    203
    0
                                        .collect()
    204
    0
                                })
    205
    0
                                .collect();
    206
    207
                            // Early return if any termset is empty (can't infer guarantees)
    208
    0
                            if termsets.iter().any(|terms| terms.is_empty()) {
    209
    0
                                return builder;
    210
    0
                            }
    211
    212
                            // Find columns that appear in all termsets
    213
    0
                            let common_cols = find_common_columns(&termsets);
    214
    0
                            if common_cols.is_empty() {
    215
    0
                                return builder;
    216
    0
                            }
    217
    218
                            // Build guarantees for common columns
    219
    0
                            let mut builder = builder;
    220
    0
                            for col in common_cols {
    221
    0
                                let literals: Vec<_> = termsets
    222
    0
                                    .iter()
    223
    0
                                    .filter_map(|terms| {
    224
    0
                                        terms.iter().find(|term| term.col() == col).map(
    225
    0
                                            |term| {
    226
    0
                                                term.lits().into_iter().map(|lit| lit.value())
    227
    0
                                            },
    228
                                        )
    229
    0
                                    })
    230
    0
                                    .flatten()
    231
    0
                                    .collect();
    232
    233
    0
                                builder = builder.aggregate_multi_conjunct(
    234
    0
                                    col,
    235
    0
                                    Guarantee::In,
    236
    0
                                    literals.into_iter(),
    237
                                );
    238
                            }
    239
    240
    0
                            builder
    241
                        }
    242
                    }
    243
    0
                })
    244
    0
                .build()
    245
    0
        }
    246
    }
    247
    248
    impl Display for LiteralGuarantee {
    249
    0
        fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
    250
    0
            let mut sorted_literals: Vec<_> =
    251
    0
                self.literals.iter().map(|lit| lit.to_string()).collect();
    252
    0
            sorted_literals.sort();
    253
    0
            match self.guarantee {
    254
    0
                Guarantee::In => write!(
    255
    0
                    f,
    256
    0
                    "{} in ({})",
    257
                    self.column.name,
    258
    0
                    sorted_literals.join(", ")
    259
                ),
    260
    0
                Guarantee::NotIn => write!(
    261
    0
                    f,
    262
    0
                    "{} not in ({})",
    263
                    self.column.name,
    264
    0
                    sorted_literals.join(", ")
    265
                ),
    266
            }
    267
    0
        }
    268
    }
    269
    270
    /// Combines conjuncts (aka terms `AND`ed together) into [`LiteralGuarantee`]s,
    271
    /// preserving insert order
    272
    #[derive(Debug, Default)]
    273
    struct GuaranteeBuilder<'a> {
    274
        /// List of guarantees that have been created so far
    275
        /// if we have determined a subsequent conjunct invalidates a guarantee
    276
        /// e.g. `a = foo AND a = bar` then the relevant guarantee will be None
    277
        guarantees: Vec<Option<LiteralGuarantee>>,
    278
    279
        /// Key is the (column name, guarantee type)
    280
        /// Value is the index into `guarantees`
    281
        map: HashMap<(&'a crate::expressions::Column, Guarantee), usize>,
    282
    }
    283
    284
    impl<'a> GuaranteeBuilder<'a> {
    285
    0
        fn new() -> Self {
    286
    0
            Default::default()
    287
    0
        }
    288
    289
        /// Aggregate a new single `AND col <op> literal` term to this builder
    290
        /// combining with existing guarantees if possible.
    291
        ///
    292
        /// # Examples
    293
        /// * `AND (a = 1)`: `a` is guaranteed to be 1
    294
        /// * `AND (a != 1)`: a is guaranteed to not be 1
    295
    0
        fn aggregate_conjunct(self, col_op_lit: &ColOpLit<'a>) -> Self {
    296
    0
            self.aggregate_multi_conjunct(
    297
    0
                col_op_lit.col,
    298
    0
                col_op_lit.guarantee,
    299
    0
                [col_op_lit.lit.value()],
    300
            )
    301
    0
        }
    302
    303
        /// Aggregates a new single column, multi literal term to this builder
    304
        /// combining with previously known guarantees if possible.
    305
        ///
    306
        /// # Examples
    307
        /// For the following examples, we can guarantee the expression is `true` if:
    308
        /// * `AND (a = 1 OR a = 2 OR a = 3)`: a is in (1, 2, or 3)
    309
        /// * `AND (a IN (1,2,3))`: a is in (1, 2, or 3)
    310
        /// * `AND (a != 1 OR a != 2 OR a != 3)`: a is not in (1, 2, or 3)
    311
        /// * `AND (a NOT IN (1,2,3))`: a is not in (1, 2, or 3)
    312
    0
        fn aggregate_multi_conjunct(
    313
    0
            mut self,
    314
    0
            col: &'a crate::expressions::Column,
    315
    0
            guarantee: Guarantee,
    316
    0
            new_values: impl IntoIterator<Item = &'a ScalarValue>,
    317
    0
        ) -> Self {
    318
    0
            let key = (col, guarantee);
    319
    0
            if let Some(index) = self.map.get(&key) {
    320
                // already have a guarantee for this column
    321
    0
                let entry = &mut self.guarantees[*index];
    322
    323
    0
                let Some(existing) = entry else {
    324
                    // determined the previous guarantee for this column has been
    325
                    // invalidated, nothing to do
    326
    0
                    return self;
    327
                };
    328
    329
                // Combine conjuncts if we have `a != foo AND a != bar`. `a = foo
    330
                // AND a = bar` doesn't make logical sense so we don't optimize this
    331
                // case
    332
    0
                match existing.guarantee {
    333
                    // knew that the column could not be a set of values
    334
                    //
    335
                    // For example, if we previously had `a != 5` and now we see
    336
                    // another `AND a != 6` we know that a must not be either 5 or 6
    337
                    // for the expression to be true
    338
    0
                    Guarantee::NotIn => {
    339
    0
                        let new_values: HashSet<_> = new_values.into_iter().collect();
    340
    0
                        existing.literals.extend(new_values.into_iter().cloned());
    341
    0
                    }
    342
                    Guarantee::In => {
    343
    0
                        let intersection = new_values
    344
    0
                            .into_iter()
    345
    0
                            .filter(|new_value| existing.literals.contains(*new_value))
    346
    0
                            .collect::<Vec<_>>();
    347
                        // for an In guarantee, if the intersection is not empty,  we can extend the guarantee
    348
                        // e.g. `a IN (1,2,3) AND a IN (2,3,4)` is `a IN (2,3)`
    349
                        // otherwise, we invalidate the guarantee
    350
                        // e.g. `a IN (1,2,3) AND a IN (4,5,6)` is `a IN ()`, which is invalid
    351
    0
                        if !intersection.is_empty() {
    352
    0
                            existing.literals = intersection.into_iter().cloned().collect();
    353
    0
                        } else {
    354
    0
                            // at least one was not, so invalidate the guarantee
    355
    0
                            *entry = None;
    356
    0
                        }
    357
                    }
    358
                }
    359
    0
            } else {
    360
    0
                // This is a new guarantee
    361
    0
                let new_values: HashSet<_> = new_values.into_iter().collect();
    362
    0
    363
    0
                let guarantee = LiteralGuarantee::new(col.name(), guarantee, new_values);
    364
    0
                // add it to the list of guarantees
    365
    0
                self.guarantees.push(Some(guarantee));
    366
    0
                self.map.insert(key, self.guarantees.len() - 1);
    367
    0
            }
    368
    369
    0
            self
    370
    0
        }
    371
    372
        /// Return all guarantees that have been created so far
    373
    0
        fn build(self) -> Vec<LiteralGuarantee> {
    374
            // filter out any guarantees that have been invalidated
    375
    0
            self.guarantees.into_iter().flatten().collect()
    376
    0
        }
    377
    }
    378
    379
    /// Represents a single `col [not]in literal` expression
    380
    struct ColOpLit<'a> {
    381
        col: &'a crate::expressions::Column,
    382
        guarantee: Guarantee,
    383
        lit: &'a crate::expressions::Literal,
    384
    }
    385
    386
    impl<'a> ColOpLit<'a> {
    387
        /// Returns Some(ColOpLit) if the expression is either:
    388
        /// 1. `col <op> literal`
    389
        /// 2. `literal <op> col`
    390
        /// 3. operator is `=` or `!=`
    391
        ///
    392
        /// Returns None otherwise
    393
    0
        fn try_new(expr: &'a Arc<dyn PhysicalExpr>) -> Option<Self> {
    394
    0
            let binary_expr = expr
    395
    0
                .as_any()
    396
    0
                .downcast_ref::<crate::expressions::BinaryExpr>()?;
    397
    398
    0
            let (left, op, right) = (
    399
    0
                binary_expr.left().as_any(),
    400
    0
                binary_expr.op(),
    401
    0
                binary_expr.right().as_any(),
    402
    0
            );
    403
    0
            let guarantee = match op {
    404
    0
                Operator::Eq => Guarantee::In,
    405
    0
                Operator::NotEq => Guarantee::NotIn,
    406
    0
                _ => return None,
    407
            };
    408
            // col <op> literal
    409
    0
            if let (Some(col), Some(lit)) = (
    410
    0
                left.downcast_ref::<crate::expressions::Column>(),
    411
    0
                right.downcast_ref::<crate::expressions::Literal>(),
    412
            ) {
    413
    0
                Some(Self {
    414
    0
                    col,
    415
    0
                    guarantee,
    416
    0
                    lit,
    417
    0
                })
    418
            }
    419
            // literal <op> col
    420
    0
            else if let (Some(lit), Some(col)) = (
    421
    0
                left.downcast_ref::<crate::expressions::Literal>(),
    422
    0
                right.downcast_ref::<crate::expressions::Column>(),
    423
            ) {
    424
    0
                Some(Self {
    425
    0
                    col,
    426
    0
                    guarantee,
    427
    0
                    lit,
    428
    0
                })
    429
            } else {
    430
    0
                None
    431
            }
    432
    0
        }
    433
    }
    434
    435
    /// Represents a single `col [not]in literal` expression
    436
    struct ColInList<'a> {
    437
        col: &'a crate::expressions::Column,
    438
        guarantee: Guarantee,
    439
        list: Vec<&'a crate::expressions::Literal>,
    440
    }
    441
    442
    impl<'a> ColInList<'a> {
    443
        /// Returns Some(ColInList) if the expression is either:
    444
        /// 1. `col <op> (literal1, literal2, ...)`
    445
        /// 3. operator is `in` or `not in`
    446
        ///
    447
        /// Returns None otherwise
    448
    0
        fn try_new(inlist: &'a crate::expressions::InListExpr) -> Option<Self> {
    449
            // Only support single-column inlist currently, multi-column inlist is not supported
    450
    0
            let col = inlist
    451
    0
                .expr()
    452
    0
                .as_any()
    453
    0
                .downcast_ref::<crate::expressions::Column>()?;
    454
    455
    0
            let literals = inlist
    456
    0
                .list()
    457
    0
                .iter()
    458
    0
                .map(|e| e.as_any().downcast_ref::<crate::expressions::Literal>())
    459
    0
                .collect::<Option<Vec<_>>>()?;
    460
    461
    0
            let guarantee = if inlist.negated() {
    462
    0
                Guarantee::NotIn
    463
            } else {
    464
    0
                Guarantee::In
    465
            };
    466
    467
    0
            Some(Self {
    468
    0
                col,
    469
    0
                guarantee,
    470
    0
                list: literals,
    471
    0
            })
    472
    0
        }
    473
    }
    474
    475
    /// Represents a single `col [not]in literal` expression or a single `col <op> literal` expression
    476
    enum ColOpLitOrInList<'a> {
    477
        ColOpLit(ColOpLit<'a>),
    478
        ColInList(ColInList<'a>),
    479
    }
    480
    481
    impl<'a> ColOpLitOrInList<'a> {
    482
    0
        fn try_new(expr: &'a Arc<dyn PhysicalExpr>) -> Option<Self> {
    483
    0
            match expr
    484
    0
                .as_any()
    485
    0
                .downcast_ref::<crate::expressions::InListExpr>()
    486
            {
    487
    0
                Some(inlist) => Some(Self::ColInList(ColInList::try_new(inlist)?)),
    488
    0
                None => ColOpLit::try_new(expr).map(Self::ColOpLit),
    489
            }
    490
    0
        }
    491
    492
    0
        fn guarantee(&self) -> Guarantee {
    493
    0
            match self {
    494
    0
                Self::ColOpLit(col_op_lit) => col_op_lit.guarantee,
    495
    0
                Self::ColInList(col_in_list) => col_in_list.guarantee,
    496
            }
    497
    0
        }
    498
    499
    0
        fn col(&self) -> &'a crate::expressions::Column {
    500
    0
            match self {
    501
    0
                Self::ColOpLit(col_op_lit) => col_op_lit.col,
    502
    0
                Self::ColInList(col_in_list) => col_in_list.col,
    503
            }
    504
    0
        }
    505
    506
    0
        fn lits(&self) -> Vec<&'a crate::expressions::Literal> {
    507
    0
            match self {
    508
    0
                Self::ColOpLit(col_op_lit) => vec![col_op_lit.lit],
    509
    0
                Self::ColInList(col_in_list) => col_in_list.list.clone(),
    510
            }
    511
    0
        }
    512
    }
    513
    514
    /// Find columns that appear in all termsets
    515
    0
    fn find_common_columns<'a>(
    516
    0
        termsets: &[Vec<ColOpLitOrInList<'a>>],
    517
    0
    ) -> Vec<&'a crate::expressions::Column> {
    518
    0
        if termsets.is_empty() {
    519
    0
            return Vec::new();
    520
    0
        }
    521
    522
        // Start with columns from the first termset
    523
    0
        let mut common_cols: HashSet<_> = termsets[0].iter().map(|term| term.col()).collect();
    524
    525
        // check if any common_col in one termset occur many times
    526
        // e.g. (a = 1 AND a = 2) OR (a = 2 AND b = 3), should not infer a guarantee
    527
        // TODO: for above case, we can infer a IN (2) AND b IN (3)
    528
    0
        if common_cols.len() != termsets[0].len() {
    529
    0
            return Vec::new();
    530
    0
        }
    531
    532
        // Intersect with columns from remaining termsets
    533
    0
        for termset in termsets.iter().skip(1) {
    534
    0
            let termset_cols: HashSet<_> = termset.iter().map(|term| term.col()).collect();
    535
    0
            if termset_cols.len() != termset.len() {
    536
    0
                return Vec::new();
    537
    0
            }
    538
    0
            common_cols = common_cols.intersection(&termset_cols).cloned().collect();
    539
        }
    540
    541
    0
        common_cols.into_iter().collect()
    542
    0
    }
    543
    544
    #[cfg(test)]
    545
    mod test {
    546
        use std::sync::LazyLock;
    547
    548
        use super::*;
    549
        use crate::planner::logical2physical;
    550
    551
        use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
    552
        use datafusion_expr::expr_fn::*;
    553
        use datafusion_expr::{lit, Expr};
    554
    555
        use itertools::Itertools;
    556
    557
        #[test]
    558
    0
        fn test_literal() {
    559
            // a single literal offers no guarantee
    560
    0
            test_analyze(lit(true), vec![])
    561
    0
        }
    562
    563
        #[test]
    564
    0
        fn test_single() {
    565
            // a = "foo"
    566
    0
            test_analyze(col("a").eq(lit("foo")), vec![in_guarantee("a", ["foo"])]);
    567
            // "foo" = a
    568
    0
            test_analyze(lit("foo").eq(col("a")), vec![in_guarantee("a", ["foo"])]);
    569
            // a != "foo"
    570
    0
            test_analyze(
    571
    0
                col("a").not_eq(lit("foo")),
    572
    0
                vec![not_in_guarantee("a", ["foo"])],
    573
            );
    574
            // "foo" != a
    575
    0
            test_analyze(
    576
    0
                lit("foo").not_eq(col("a")),
    577
    0
                vec![not_in_guarantee("a", ["foo"])],
    578
            );
    579
    0
        }
    580
    581
        #[test]
    582
    0
        fn test_conjunction_single_column() {
    583
            // b = 1 AND b = 2. This is impossible. Ideally this expression could be simplified to false
    584
    0
            test_analyze(col("b").eq(lit(1)).and(col("b").eq(lit(2))), vec![]);
    585
            // b = 1 AND b != 2 . In theory, this could be simplified to `b = 1`.
    586
    0
            test_analyze(
    587
    0
                col("b").eq(lit(1)).and(col("b").not_eq(lit(2))),
    588
    0
                vec![
    589
                    // can only be true of b is 1 and b is not 2 (even though it is redundant)
    590
    0
                    in_guarantee("b", [1]),
    591
    0
                    not_in_guarantee("b", [2]),
    592
                ],
    593
            );
    594
            // b != 1 AND b = 2. In theory, this could be simplified to `b = 2`.
    595
    0
            test_analyze(
    596
    0
                col("b").not_eq(lit(1)).and(col("b").eq(lit(2))),
    597
    0
                vec![
    598
                    // can only be true of b is not 1 and b is 2 (even though it is redundant)
    599
    0
                    not_in_guarantee("b", [1]),
    600
    0
                    in_guarantee("b", [2]),
    601
                ],
    602
            );
    603
            // b != 1 AND b != 2
    604
    0
            test_analyze(
    605
    0
                col("b").not_eq(lit(1)).and(col("b").not_eq(lit(2))),
    606
    0
                vec![not_in_guarantee("b", [1, 2])],
    607
            );
    608
            // b != 1 AND b != 2 and b != 3
    609
    0
            test_analyze(
    610
    0
                col("b")
    611
    0
                    .not_eq(lit(1))
    612
    0
                    .and(col("b").not_eq(lit(2)))
    613
    0
                    .and(col("b").not_eq(lit(3))),
    614
    0
                vec![not_in_guarantee("b", [1, 2, 3])],
    615
            );
    616
            // b != 1 AND b = 2 and b != 3. Can only be true if b is 2 and b is not in (1, 3)
    617
    0
            test_analyze(
    618
    0
                col("b")
    619
    0
                    .not_eq(lit(1))
    620
    0
                    .and(col("b").eq(lit(2)))
    621
    0
                    .and(col("b").not_eq(lit(3))),
    622
    0
                vec![not_in_guarantee("b", [1, 3]), in_guarantee("b", [2])],
    623
            );
    624
            // b != 1 AND b != 2 and b = 3 (in theory could determine b = 3)
    625
    0
            test_analyze(
    626
    0
                col("b")
    627
    0
                    .not_eq(lit(1))
    628
    0
                    .and(col("b").not_eq(lit(2)))
    629
    0
                    .and(col("b").eq(lit(3))),
    630
    0
                vec![not_in_guarantee("b", [1, 2]), in_guarantee("b", [3])],
    631
            );
    632
            // b != 1 AND b != 2 and b > 3 (to be true, b can't be either 1 or 2
    633
    0
            test_analyze(
    634
    0
                col("b")
    635
    0
                    .not_eq(lit(1))
    636
    0
                    .and(col("b").not_eq(lit(2)))
    637
    0
                    .and(col("b").gt(lit(3))),
    638
    0
                vec![not_in_guarantee("b", [1, 2])],
    639
            );
    640
    0
        }
    641
    642
        #[test]
    643
    0
        fn test_conjunction_multi_column() {
    644
            // a = "foo" AND b = 1
    645
    0
            test_analyze(
    646
    0
                col("a").eq(lit("foo")).and(col("b").eq(lit(1))),
    647
    0
                vec![
    648
                    // should find both column guarantees
    649
    0
                    in_guarantee("a", ["foo"]),
    650
    0
                    in_guarantee("b", [1]),
    651
                ],
    652
            );
    653
            // a != "foo" AND b != 1
    654
    0
            test_analyze(
    655
    0
                col("a").not_eq(lit("foo")).and(col("b").not_eq(lit(1))),
    656
                // should find both column guarantees
    657
    0
                vec![not_in_guarantee("a", ["foo"]), not_in_guarantee("b", [1])],
    658
            );
    659
            // a = "foo" AND a = "bar"
    660
    0
            test_analyze(
    661
    0
                col("a").eq(lit("foo")).and(col("a").eq(lit("bar"))),
    662
                // this predicate is impossible ( can't be both foo and bar),
    663
    0
                vec![],
    664
            );
    665
            // a = "foo" AND b != "bar"
    666
    0
            test_analyze(
    667
    0
                col("a").eq(lit("foo")).and(col("a").not_eq(lit("bar"))),
    668
    0
                vec![in_guarantee("a", ["foo"]), not_in_guarantee("a", ["bar"])],
    669
            );
    670
            // a != "foo" AND a != "bar"
    671
    0
            test_analyze(
    672
    0
                col("a").not_eq(lit("foo")).and(col("a").not_eq(lit("bar"))),
    673
                // know it isn't "foo" or "bar"
    674
    0
                vec![not_in_guarantee("a", ["foo", "bar"])],
    675
            );
    676
            // a != "foo" AND a != "bar" and a != "baz"
    677
    0
            test_analyze(
    678
    0
                col("a")
    679
    0
                    .not_eq(lit("foo"))
    680
    0
                    .and(col("a").not_eq(lit("bar")))
    681
    0
                    .and(col("a").not_eq(lit("baz"))),
    682
                // know it isn't "foo" or "bar" or "baz"
    683
    0
                vec![not_in_guarantee("a", ["foo", "bar", "baz"])],
    684
            );
    685
            // a = "foo" AND a = "foo"
    686
    0
            let expr = col("a").eq(lit("foo"));
    687
    0
            test_analyze(expr.clone().and(expr), vec![in_guarantee("a", ["foo"])]);
    688
            // b > 5 AND b = 10 (should get an b = 10 guarantee)
    689
    0
            test_analyze(
    690
    0
                col("b").gt(lit(5)).and(col("b").eq(lit(10))),
    691
    0
                vec![in_guarantee("b", [10])],
    692
            );
    693
            // b > 10 AND b = 10 (this is impossible)
    694
    0
            test_analyze(
    695
    0
                col("b").gt(lit(10)).and(col("b").eq(lit(10))),
    696
    0
                vec![
    697
                    //  if b isn't 10, it can not be true (though the expression actually can never be true)
    698
    0
                    in_guarantee("b", [10]),
    699
                ],
    700
            );
    701
            // a != "foo" and (a != "bar" OR a != "baz")
    702
    0
            test_analyze(
    703
    0
                col("a")
    704
    0
                    .not_eq(lit("foo"))
    705
    0
                    .and(col("a").not_eq(lit("bar")).or(col("a").not_eq(lit("baz")))),
    706
                // a is not foo (we can't represent other knowledge about a)
    707
    0
                vec![not_in_guarantee("a", ["foo"])],
    708
            );
    709
    0
        }
    710
    711
        #[test]
    712
    0
        fn test_conjunction_and_disjunction_single_column() {
    713
            // b != 1 AND (b > 2)
    714
    0
            test_analyze(
    715
    0
                col("b").not_eq(lit(1)).and(col("b").gt(lit(2))),
    716
    0
                vec![
    717
                    // for the expression to be true, b can not be one
    718
    0
                    not_in_guarantee("b", [1]),
    719
                ],
    720
            );
    721
    722
            // b = 1 AND (b = 2 OR b = 3). Could be simplified to false.
    723
    0
            test_analyze(
    724
    0
                col("b")
    725
    0
                    .eq(lit(1))
    726
    0
                    .and(col("b").eq(lit(2)).or(col("b").eq(lit(3)))),
    727
    0
                vec![
    728
                    // in theory, b must be 1 and one of 2,3 for this expression to be true
    729
                    // which is a logical contradiction
    730
                ],
    731
            );
    732
    0
        }
    733
    734
        #[test]
    735
    0
        fn test_disjunction_single_column() {
    736
            // b = 1 OR b = 2
    737
    0
            test_analyze(
    738
    0
                col("b").eq(lit(1)).or(col("b").eq(lit(2))),
    739
    0
                vec![in_guarantee("b", [1, 2])],
    740
            );
    741
            // b != 1 OR b = 2
    742
    0
            test_analyze(col("b").not_eq(lit(1)).or(col("b").eq(lit(2))), vec![]);
    743
            // b = 1 OR b != 2
    744
    0
            test_analyze(col("b").eq(lit(1)).or(col("b").not_eq(lit(2))), vec![]);
    745
            // b != 1 OR b != 2
    746
    0
            test_analyze(col("b").not_eq(lit(1)).or(col("b").not_eq(lit(2))), vec![]);
    747
            // b != 1 OR b != 2 OR b = 3 -- in theory could guarantee that b = 3
    748
    0
            test_analyze(
    749
    0
                col("b")
    750
    0
                    .not_eq(lit(1))
    751
    0
                    .or(col("b").not_eq(lit(2)))
    752
    0
                    .or(lit("b").eq(lit(3))),
    753
    0
                vec![],
    754
            );
    755
            // b = 1 OR b = 2 OR b = 3
    756
    0
            test_analyze(
    757
    0
                col("b")
    758
    0
                    .eq(lit(1))
    759
    0
                    .or(col("b").eq(lit(2)))
    760
    0
                    .or(col("b").eq(lit(3))),
    761
    0
                vec![in_guarantee("b", [1, 2, 3])],
    762
            );
    763
            // b = 1 OR b = 2 OR b > 3 -- can't guarantee that the expression is only true if a is in (1, 2)
    764
    0
            test_analyze(
    765
    0
                col("b")
    766
    0
                    .eq(lit(1))
    767
    0
                    .or(col("b").eq(lit(2)))
    768
    0
                    .or(lit("b").eq(lit(3))),
    769
    0
                vec![],
    770
            );
    771
    0
        }
    772
    773
        #[test]
    774
    0
        fn test_disjunction_multi_column() {
    775
            // a = "foo" OR b = 1
    776
    0
            test_analyze(
    777
    0
                col("a").eq(lit("foo")).or(col("b").eq(lit(1))),
    778
                // no can't have a single column guarantee (if a = "foo" then b != 1) etc
    779
    0
                vec![],
    780
            );
    781
            // a != "foo" OR b != 1
    782
    0
            test_analyze(
    783
    0
                col("a").not_eq(lit("foo")).or(col("b").not_eq(lit(1))),
    784
                // No single column guarantee
    785
    0
                vec![],
    786
            );
    787
            // a = "foo" OR a = "bar"
    788
    0
            test_analyze(
    789
    0
                col("a").eq(lit("foo")).or(col("a").eq(lit("bar"))),
    790
    0
                vec![in_guarantee("a", ["foo", "bar"])],
    791
            );
    792
            // a = "foo" OR a = "foo"
    793
    0
            test_analyze(
    794
    0
                col("a").eq(lit("foo")).or(col("a").eq(lit("foo"))),
    795
    0
                vec![in_guarantee("a", ["foo"])],
    796
            );
    797
            // a != "foo" OR a != "bar"
    798
    0
            test_analyze(
    799
    0
                col("a").not_eq(lit("foo")).or(col("a").not_eq(lit("bar"))),
    800
                // can't represent knowledge about a in this case
    801
    0
                vec![],
    802
            );
    803
            // a = "foo" OR a = "bar" OR a = "baz"
    804
    0
            test_analyze(
    805
    0
                col("a")
    806
    0
                    .eq(lit("foo"))
    807
    0
                    .or(col("a").eq(lit("bar")))
    808
    0
                    .or(col("a").eq(lit("baz"))),
    809
    0
                vec![in_guarantee("a", ["foo", "bar", "baz"])],
    810
            );
    811
            // (a = "foo" OR a = "bar") AND (a = "baz)"
    812
    0
            test_analyze(
    813
    0
                (col("a").eq(lit("foo")).or(col("a").eq(lit("bar"))))
    814
    0
                    .and(col("a").eq(lit("baz"))),
    815
                // this could potentially be represented as 2 constraints with a more
    816
                // sophisticated analysis
    817
    0
                vec![],
    818
            );
    819
            // (a = "foo" OR a = "bar") AND (b = 1)
    820
    0
            test_analyze(
    821
    0
                (col("a").eq(lit("foo")).or(col("a").eq(lit("bar"))))
    822
    0
                    .and(col("b").eq(lit(1))),
    823
    0
                vec![in_guarantee("a", ["foo", "bar"]), in_guarantee("b", [1])],
    824
            );
    825
            // (a = "foo" OR a = "bar") OR (b = 1)
    826
    0
            test_analyze(
    827
    0
                col("a")
    828
    0
                    .eq(lit("foo"))
    829
    0
                    .or(col("a").eq(lit("bar")))
    830
    0
                    .or(col("b").eq(lit(1))),
    831
                // can't represent knowledge about a or b in this case
    832
    0
                vec![],
    833
            );
    834
    0
        }
    835
    836
        #[test]
    837
    0
        fn test_single_inlist() {
    838
            // b IN (1, 2, 3)
    839
    0
            test_analyze(
    840
    0
                col("b").in_list(vec![lit(1), lit(2), lit(3)], false),
    841
    0
                vec![in_guarantee("b", [1, 2, 3])],
    842
            );
    843
            // b NOT IN (1, 2, 3)
    844
    0
            test_analyze(
    845
    0
                col("b").in_list(vec![lit(1), lit(2), lit(3)], true),
    846
    0
                vec![not_in_guarantee("b", [1, 2, 3])],
    847
            );
    848
            // b IN (1,2,3,4...24)
    849
    0
            test_analyze(
    850
    0
                col("b").in_list((1..25).map(lit).collect_vec(), false),
    851
    0
                vec![in_guarantee("b", 1..25)],
    852
            );
    853
    0
        }
    854
    855
        #[test]
    856
    0
        fn test_inlist_conjunction() {
    857
            // b IN (1, 2, 3) AND b IN (2, 3, 4)
    858
    0
            test_analyze(
    859
    0
                col("b")
    860
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    861
    0
                    .and(col("b").in_list(vec![lit(2), lit(3), lit(4)], false)),
    862
    0
                vec![in_guarantee("b", [2, 3])],
    863
            );
    864
            // b NOT IN (1, 2, 3) AND b IN (2, 3, 4)
    865
    0
            test_analyze(
    866
    0
                col("b")
    867
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], true)
    868
    0
                    .and(col("b").in_list(vec![lit(2), lit(3), lit(4)], false)),
    869
    0
                vec![
    870
    0
                    not_in_guarantee("b", [1, 2, 3]),
    871
    0
                    in_guarantee("b", [2, 3, 4]),
    872
                ],
    873
            );
    874
            // b NOT IN (1, 2, 3) AND b NOT IN (2, 3, 4)
    875
    0
            test_analyze(
    876
    0
                col("b")
    877
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], true)
    878
    0
                    .and(col("b").in_list(vec![lit(2), lit(3), lit(4)], true)),
    879
    0
                vec![not_in_guarantee("b", [1, 2, 3, 4])],
    880
            );
    881
            // b IN (1, 2, 3) AND b = 4
    882
    0
            test_analyze(
    883
    0
                col("b")
    884
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    885
    0
                    .and(col("b").eq(lit(4))),
    886
    0
                vec![],
    887
            );
    888
            // b IN (1, 2, 3) AND b = 2
    889
    0
            test_analyze(
    890
    0
                col("b")
    891
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    892
    0
                    .and(col("b").eq(lit(2))),
    893
    0
                vec![in_guarantee("b", [2])],
    894
            );
    895
            // b IN (1, 2, 3) AND b != 2
    896
    0
            test_analyze(
    897
    0
                col("b")
    898
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    899
    0
                    .and(col("b").not_eq(lit(2))),
    900
    0
                vec![in_guarantee("b", [1, 2, 3]), not_in_guarantee("b", [2])],
    901
            );
    902
            // b NOT IN (1, 2, 3) AND b != 4
    903
    0
            test_analyze(
    904
    0
                col("b")
    905
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], true)
    906
    0
                    .and(col("b").not_eq(lit(4))),
    907
    0
                vec![not_in_guarantee("b", [1, 2, 3, 4])],
    908
            );
    909
            // b NOT IN (1, 2, 3) AND b != 2
    910
    0
            test_analyze(
    911
    0
                col("b")
    912
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], true)
    913
    0
                    .and(col("b").not_eq(lit(2))),
    914
    0
                vec![not_in_guarantee("b", [1, 2, 3])],
    915
            );
    916
    0
        }
    917
    918
        #[test]
    919
    0
        fn test_inlist_with_disjunction() {
    920
            // b IN (1, 2, 3) AND (b = 3 OR b = 4)
    921
    0
            test_analyze(
    922
    0
                col("b")
    923
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    924
    0
                    .and(col("b").eq(lit(3)).or(col("b").eq(lit(4)))),
    925
    0
                vec![in_guarantee("b", [3])],
    926
            );
    927
            // b IN (1, 2, 3) AND (b = 4 OR b = 5)
    928
    0
            test_analyze(
    929
    0
                col("b")
    930
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    931
    0
                    .and(col("b").eq(lit(4)).or(col("b").eq(lit(5)))),
    932
    0
                vec![],
    933
            );
    934
            // b NOT IN (1, 2, 3) AND (b = 3 OR b = 4)
    935
    0
            test_analyze(
    936
    0
                col("b")
    937
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], true)
    938
    0
                    .and(col("b").eq(lit(3)).or(col("b").eq(lit(4)))),
    939
    0
                vec![not_in_guarantee("b", [1, 2, 3]), in_guarantee("b", [3, 4])],
    940
            );
    941
            // b IN (1, 2, 3) OR b = 2
    942
    0
            test_analyze(
    943
    0
                col("b")
    944
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    945
    0
                    .or(col("b").eq(lit(2))),
    946
    0
                vec![in_guarantee("b", [1, 2, 3])],
    947
            );
    948
            // b IN (1, 2, 3) OR b != 3
    949
    0
            test_analyze(
    950
    0
                col("b")
    951
    0
                    .in_list(vec![lit(1), lit(2), lit(3)], false)
    952
    0
                    .or(col("b").not_eq(lit(3))),
    953
    0
                vec![],
    954
            );
    955
    0
        }
    956
    957
        #[test]
    958
    0
        fn test_disjunction_and_conjunction_multi_column() {
    959
            // (a = "foo" AND b = 1) OR (a = "bar" AND b = 2)
    960
    0
            test_analyze(
    961
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    962
    0
                    .or(col("a").eq(lit("bar")).and(col("b").eq(lit(2)))),
    963
    0
                vec![in_guarantee("a", ["foo", "bar"]), in_guarantee("b", [1, 2])],
    964
            );
    965
            // (a = "foo" AND b = 1) OR (a = "bar" AND b = 2) OR (b = 3)
    966
    0
            test_analyze(
    967
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    968
    0
                    .or(col("a").eq(lit("bar")).and(col("b").eq(lit(2))))
    969
    0
                    .or(col("b").eq(lit(3))),
    970
    0
                vec![in_guarantee("b", [1, 2, 3])],
    971
            );
    972
            // (a = "foo" AND b = 1) OR (a = "bar" AND b = 2) OR (c = 3)
    973
    0
            test_analyze(
    974
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    975
    0
                    .or(col("a").eq(lit("bar")).and(col("b").eq(lit(2))))
    976
    0
                    .or(col("c").eq(lit(3))),
    977
    0
                vec![],
    978
            );
    979
            // (a = "foo" AND b > 1) OR (a = "bar" AND b = 2)
    980
    0
            test_analyze(
    981
    0
                (col("a").eq(lit("foo")).and(col("b").gt(lit(1))))
    982
    0
                    .or(col("a").eq(lit("bar")).and(col("b").eq(lit(2)))),
    983
    0
                vec![in_guarantee("a", ["foo", "bar"])],
    984
            );
    985
            // (a = "foo" AND b = 1) OR (b = 1 AND c = 2) OR (c = 3 AND a = "bar")
    986
    0
            test_analyze(
    987
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    988
    0
                    .or(col("b").eq(lit(1)).and(col("c").eq(lit(2))))
    989
    0
                    .or(col("c").eq(lit(3)).and(col("a").eq(lit("bar")))),
    990
    0
                vec![],
    991
            );
    992
            // (a = "foo" AND a = "bar") OR (a = "good" AND b = 1)
    993
            // TODO: this should be `a IN ("good") AND b IN (1)`
    994
    0
            test_analyze(
    995
    0
                (col("a").eq(lit("foo")).and(col("a").eq(lit("bar"))))
    996
    0
                    .or(col("a").eq(lit("good")).and(col("b").eq(lit(1)))),
    997
    0
                vec![],
    998
            );
    999
            // (a = "foo" AND a = "foo") OR (a = "good" AND b = 1)
    1000
            // TODO: this should be `a IN ("foo", "good")`
    1001
    0
            test_analyze(
    1002
    0
                (col("a").eq(lit("foo")).and(col("a").eq(lit("foo"))))
    1003
    0
                    .or(col("a").eq(lit("good")).and(col("b").eq(lit(1)))),
    1004
    0
                vec![],
    1005
            );
    1006
            // (a = "foo" AND b = 3) OR (b = 4 AND b = 1) OR (b = 2 AND a = "bar")
    1007
    0
            test_analyze(
    1008
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(3))))
    1009
    0
                    .or(col("b").eq(lit(4)).and(col("b").eq(lit(1))))
    1010
    0
                    .or(col("b").eq(lit(2)).and(col("a").eq(lit("bar")))),
    1011
    0
                vec![],
    1012
            );
    1013
            // (b = 1 AND b > 3) OR (a = "foo" AND b = 4)
    1014
    0
            test_analyze(
    1015
    0
                (col("b").eq(lit(1)).and(col("b").gt(lit(3))))
    1016
    0
                    .or(col("a").eq(lit("foo")).and(col("b").eq(lit(4)))),
    1017
                // if b isn't 1 or 4, it can not be true (though the expression actually can never be true)
    1018
    0
                vec![in_guarantee("b", [1, 4])],
    1019
            );
    1020
            // (a = "foo" AND b = 1) OR (a != "bar" AND b = 2)
    1021
    0
            test_analyze(
    1022
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    1023
    0
                    .or(col("a").not_eq(lit("bar")).and(col("b").eq(lit(2)))),
    1024
    0
                vec![in_guarantee("b", [1, 2])],
    1025
            );
    1026
            // (a = "foo" AND b = 1) OR (a LIKE "%bar" AND b = 2)
    1027
    0
            test_analyze(
    1028
    0
                (col("a").eq(lit("foo")).and(col("b").eq(lit(1))))
    1029
    0
                    .or(col("a").like(lit("%bar")).and(col("b").eq(lit(2)))),
    1030
    0
                vec![in_guarantee("b", [1, 2])],
    1031
            );
    1032
            // (a IN ("foo", "bar") AND b = 5) OR (a IN ("foo", "bar") AND b = 6)
    1033
    0
            test_analyze(
    1034
    0
                (col("a")
    1035
    0
                    .in_list(vec![lit("foo"), lit("bar")], false)
    1036
    0
                    .and(col("b").eq(lit(5))))
    1037
    0
                .or(col("a")
    1038
    0
                    .in_list(vec![lit("foo"), lit("bar")], false)
    1039
    0
                    .and(col("b").eq(lit(6)))),
    1040
    0
                vec![in_guarantee("a", ["foo", "bar"]), in_guarantee("b", [5, 6])],
    1041
            );
    1042
            // (a IN ("foo", "bar") AND b = 5) OR (a IN ("foo") AND b = 6)
    1043
    0
            test_analyze(
    1044
    0
                (col("a")
    1045
    0
                    .in_list(vec![lit("foo"), lit("bar")], false)
    1046
    0
                    .and(col("b").eq(lit(5))))
    1047
    0
                .or(col("a")
    1048
    0
                    .in_list(vec![lit("foo")], false)
    1049
    0
                    .and(col("b").eq(lit(6)))),
    1050
    0
                vec![in_guarantee("a", ["foo", "bar"]), in_guarantee("b", [5, 6])],
    1051
            );
    1052
            // (a NOT IN ("foo", "bar") AND b = 5) OR (a NOT IN ("foo") AND b = 6)
    1053
    0
            test_analyze(
    1054
    0
                (col("a")
    1055
    0
                    .in_list(vec![lit("foo"), lit("bar")], true)
    1056
    0
                    .and(col("b").eq(lit(5))))
    1057
    0
                .or(col("a")
    1058
    0
                    .in_list(vec![lit("foo")], true)
    1059
    0
                    .and(col("b").eq(lit(6)))),
    1060
    0
                vec![in_guarantee("b", [5, 6])],
    1061
            );
    1062
    0
        }
    1063
    1064
        /// Tests that analyzing expr results in the expected guarantees
    1065
    0
        fn test_analyze(expr: Expr, expected: Vec<LiteralGuarantee>) {
    1066
    0
            println!("Begin analyze of {expr}");
    1067
    0
            let schema = schema();
    1068
    0
            let physical_expr = logical2physical(&expr, &schema);
    1069
    1070
    0
            let actual = LiteralGuarantee::analyze(&physical_expr)
    1071
    0
                .into_iter()
    1072
    0
                .sorted_by_key(|g| g.column.name().to_string())
    1073
    0
                .collect::<Vec<_>>();
    1074
    0
            assert_eq!(
    1075
                expected, actual,
    1076
    0
                "expr: {expr}\
    1077
    0
                   \n\nexpected: {expected:#?}\
    1078
    0
                   \n\nactual: {actual:#?}\
    1079
    0
                   \n\nexpr: {expr:#?}\
    1080
    0
                   \n\nphysical_expr: {physical_expr:#?}"
    1081
            );
    1082
    0
        }
    1083
    1084
        /// Guarantee that the expression is true if the column is one of the specified values
    1085
    0
        fn in_guarantee<'a, I, S>(column: &str, literals: I) -> LiteralGuarantee
    1086
    0
        where
    1087
    0
            I: IntoIterator<Item = S>,
    1088
    0
            S: Into<ScalarValue> + 'a,
    1089
        {
    1090
    0
            let literals: Vec<_> = literals.into_iter().map(|s| s.into()).collect();
    1091
    0
            LiteralGuarantee::new(column, Guarantee::In, literals.iter())
    1092
    0
        }
    1093
    1094
        /// Guarantee that the expression is true if the column is NOT any of the specified values
    1095
    0
        fn not_in_guarantee<'a, I, S>(column: &str, literals: I) -> LiteralGuarantee
    1096
    0
        where
    1097
    0
            I: IntoIterator<Item = S>,
    1098
    0
            S: Into<ScalarValue> + 'a,
    1099
        {
    1100
    0
            let literals: Vec<_> = literals.into_iter().map(|s| s.into()).collect();
    1101
    0
            LiteralGuarantee::new(column, Guarantee::NotIn, literals.iter())
    1102
    0
        }
    1103
    1104
        // Schema for testing
    1105
    0
        fn schema() -> SchemaRef {
    1106
    0
            static SCHEMA: LazyLock<SchemaRef> = LazyLock::new(|| {
    1107
    0
                Arc::new(Schema::new(vec![
    1108
    0
                    Field::new("a", DataType::Utf8, false),
    1109
    0
                    Field::new("b", DataType::Int32, false),
    1110
    0
                    Field::new("c", DataType::Int32, false),
    1111
                ]))
    1112
    0
            });
    1113
    0
            Arc::clone(&SCHEMA)
    1114
    0
        }
    1115
    }