1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
// Copyright Materialize, Inc. and contributors. All rights reserved.
//
// Use of this software is governed by the Business Source License
// included in the LICENSE file.
//
// As of the Change Date specified in that file, in accordance with
// the Business Source License, use of this software will be governed
// by the Apache License, Version 2.0.

//! Detects an input being unioned with its negation and cancels them out

use crate::{TransformArgs, TransformError};
use itertools::Itertools;
use mz_expr::visit::Visit;
use mz_expr::MirRelationExpr;

/// Detects an input being unioned with its negation and cancels them out
#[derive(Debug)]
pub struct UnionBranchCancellation;

impl crate::Transform for UnionBranchCancellation {
    fn transform(
        &self,
        relation: &mut MirRelationExpr,
        _: TransformArgs,
    ) -> Result<(), TransformError> {
        relation.try_visit_mut_post(&mut |e| self.action(e))
    }
}

/// Result of the comparison of two branches of a union for cancellation
/// purposes.
enum BranchCmp {
    /// The two branches are equivalent in the sense the the produce the
    /// same exact results.
    Equivalent,
    /// The two branches are equivalent, but one of them produces negated
    /// row count values, and hence, they cancel each other.
    Inverse,
    /// The two branches are not equivalent in any way.
    Distinct,
}

impl BranchCmp {
    /// Modify the result of the comparison when a Negate operator is
    /// found at the top of one the branches just compared.
    fn inverse(self) -> Self {
        match self {
            BranchCmp::Equivalent => BranchCmp::Inverse,
            BranchCmp::Inverse => BranchCmp::Equivalent,
            BranchCmp::Distinct => BranchCmp::Distinct,
        }
    }
}

impl UnionBranchCancellation {
    /// Detects an input being unioned with its negation and cancels them out
    pub fn action(&self, relation: &mut MirRelationExpr) -> Result<(), TransformError> {
        if let MirRelationExpr::Union { base, inputs } = relation {
            // Compares a union branch against the remaining branches in the union
            // with opposite sign until it finds a branch that cancels the given one
            // and returns its position.
            let matching_negation = |input: &MirRelationExpr,
                                     sign: bool,
                                     inputs: &[MirRelationExpr],
                                     input_signs: &[bool],
                                     start_idx: usize|
             -> Option<usize> {
                for i in start_idx..inputs.len() {
                    // Only compare branches with opposite signs
                    if sign != input_signs[i] {
                        if let BranchCmp::Inverse = Self::compare_branches(input, &inputs[i]) {
                            return Some(i);
                        }
                    }
                }
                None
            };

            let base_sign = Self::branch_sign(base);
            let input_signs = inputs.iter().map(Self::branch_sign).collect_vec();

            // Compare branches if there is at least a negated branch
            if std::iter::once(&base_sign).chain(&input_signs).any(|x| *x) {
                if let Some(j) = matching_negation(&*base, base_sign, inputs, &input_signs, 0) {
                    let relation_typ = base.typ();
                    **base = MirRelationExpr::constant(vec![], relation_typ.clone());
                    inputs[j] = MirRelationExpr::constant(vec![], relation_typ);
                }

                for i in 0..inputs.len() {
                    if let Some(j) =
                        matching_negation(&inputs[i], input_signs[i], inputs, &input_signs, i + 1)
                    {
                        let relation_typ = inputs[i].typ();
                        inputs[i] = MirRelationExpr::constant(vec![], relation_typ.clone());
                        inputs[j] = MirRelationExpr::constant(vec![], relation_typ);
                    }
                }
            }
        }
        Ok(())
    }

    /// Returns the sign of a given union branch. The sign is `true` if the branch contains
    /// an odd number of Negate operators within a chain of Map, Filter and Project
    /// operators, and `false` otherwise.
    ///
    /// This sign is pre-computed for all union branches in order to avoid performing
    /// expensive comparisons of branches with the same sign since they can't possibly
    /// cancel each other.
    fn branch_sign(branch: &MirRelationExpr) -> bool {
        let mut relation = branch;
        let mut sign = false;
        loop {
            match relation {
                MirRelationExpr::Negate { input } => {
                    sign ^= true;
                    relation = &**input;
                }
                MirRelationExpr::Map { input, .. }
                | MirRelationExpr::Filter { input, .. }
                | MirRelationExpr::Project { input, .. } => {
                    relation = &**input;
                }
                _ => return sign,
            }
        }
    }

    /// Compares two branches to check whether they produce the same results but
    /// with negated row count values, ie. one of them contains an extra Negate operator.
    /// Negate operators may appear interleaved with Map, Filter and Project
    /// operators, but these operators must appear in the same order in both branches.
    fn compare_branches(relation: &MirRelationExpr, other: &MirRelationExpr) -> BranchCmp {
        match (relation, other) {
            (
                MirRelationExpr::Negate { input: input1 },
                MirRelationExpr::Negate { input: input2 },
            ) => Self::compare_branches(&*input1, &*input2),
            (r, MirRelationExpr::Negate { input }) | (MirRelationExpr::Negate { input }, r) => {
                Self::compare_branches(&*input, r).inverse()
            }
            (
                MirRelationExpr::Map {
                    input: input1,
                    scalars: scalars1,
                },
                MirRelationExpr::Map {
                    input: input2,
                    scalars: scalars2,
                },
            ) => {
                if scalars1 == scalars2 {
                    Self::compare_branches(&*input1, &*input2)
                } else {
                    BranchCmp::Distinct
                }
            }
            (
                MirRelationExpr::Filter {
                    input: input1,
                    predicates: predicates1,
                },
                MirRelationExpr::Filter {
                    input: input2,
                    predicates: predicates2,
                },
            ) => {
                if predicates1 == predicates2 {
                    Self::compare_branches(&*input1, &*input2)
                } else {
                    BranchCmp::Distinct
                }
            }
            (
                MirRelationExpr::Project {
                    input: input1,
                    outputs: outputs1,
                },
                MirRelationExpr::Project {
                    input: input2,
                    outputs: outputs2,
                },
            ) => {
                if outputs1 == outputs2 {
                    Self::compare_branches(&*input1, &*input2)
                } else {
                    BranchCmp::Distinct
                }
            }
            _ => {
                if relation == other {
                    BranchCmp::Equivalent
                } else {
                    BranchCmp::Distinct
                }
            }
        }
    }
}