mz_transform/analysis/
monotonic.rs

1// Copyright Materialize, Inc. and contributors. All rights reserved.
2//
3// Use of this software is governed by the Business Source License
4// included in the LICENSE file.
5//
6// As of the Change Date specified in that file, in accordance with
7// the Business Source License, use of this software will be governed
8// by the Apache License, Version 2.0.
9
10//! Analysis that determines the logical monotonicity of an expression.
11//!
12//! Expressions are logically monotonic if their inputs are monotonic, and they
13//! do not introduce any retractions.
14
15use std::collections::BTreeSet;
16
17use mz_expr::{Id, MirRelationExpr};
18use mz_repr::GlobalId;
19
20use crate::analysis::common_lattice::BoolLattice;
21use crate::analysis::{Analysis, Derived, Lattice};
22
23/// Determines the logical monotonicity of an expression.
24#[derive(Debug)]
25pub struct Monotonic {
26    global_monotonic_ids: BTreeSet<GlobalId>,
27}
28
29impl Monotonic {
30    /// A monotonicity analyser provided with the set of Global IDs that are known to be monotonic.
31    pub fn new(global_monotonic_ids: BTreeSet<GlobalId>) -> Self {
32        Self {
33            global_monotonic_ids,
34        }
35    }
36
37    #[inline]
38    fn has_monotonic_children(
39        expr: &MirRelationExpr,
40        index: usize,
41        results: &[bool],
42        depends: &Derived,
43    ) -> bool {
44        depends
45            .children_of_rev(index, expr.children().count())
46            .fold(true, |acc, child| acc && results[child])
47    }
48}
49
50impl Analysis for Monotonic {
51    type Value = bool;
52
53    fn derive(
54        &self,
55        expr: &MirRelationExpr,
56        index: usize,
57        results: &[Self::Value],
58        depends: &Derived,
59    ) -> Self::Value {
60        use Id::*;
61        match expr {
62            MirRelationExpr::Get { id: Global(id), .. } => self.global_monotonic_ids.contains(id),
63            MirRelationExpr::Get { id: Local(id), .. } => {
64                let index = *depends
65                    .bindings()
66                    .get(id)
67                    .expect("Dependency info not found");
68                *results.get(index).unwrap_or(&false)
69            }
70            // Monotonic iff their input is.
71            MirRelationExpr::Project { .. }
72            | MirRelationExpr::Map { .. }
73            | MirRelationExpr::ArrangeBy { .. }
74            | MirRelationExpr::Threshold { .. }
75            | MirRelationExpr::Let { .. }
76            | MirRelationExpr::LetRec { .. } => results[index - 1],
77            // Monotonic iff all inputs are.
78            MirRelationExpr::Union { .. } | MirRelationExpr::Join { .. } => {
79                Self::has_monotonic_children(expr, index, results, depends)
80            }
81            // Any set limit or offset can result in retractions when input data arrive.
82            // If neither limit nor offset are set, the TopK stage will eventually be optimized out.
83            MirRelationExpr::TopK { .. } => false,
84            MirRelationExpr::Negate { .. } => false,
85            MirRelationExpr::Filter { predicates, .. } => {
86                let is_monotonic = results[index - 1];
87                // Temporal predicates can introduce non-monotonicity, as they
88                // can result in the future removal of records.
89                // TODO: this could be improved to only restrict if upper bounds
90                // are present, as temporal lower bounds only delay introduction.
91                is_monotonic && !predicates.iter().any(|p| p.contains_temporal())
92            }
93            MirRelationExpr::Reduce { aggregates, .. } => {
94                // Reduce is monotonic iff its input is, and it is a "distinct"
95                // with no aggregate values; otherwise it may need to retract.
96                results[index - 1] && aggregates.is_empty()
97            }
98            MirRelationExpr::FlatMap { func, .. } => {
99                results[index - 1] && func.preserves_monotonicity()
100            }
101            MirRelationExpr::Constant { rows: Ok(rows), .. } => {
102                rows.iter().all(|(_, diff)| diff.is_positive())
103            }
104            // TODO: database-issues#8337 (Investigate if constant expressions with error rows can be marked monotonic)
105            MirRelationExpr::Constant { rows: Err(_), .. } => false,
106        }
107    }
108
109    fn lattice() -> Option<Box<dyn Lattice<Self::Value>>> {
110        Some(Box::new(BoolLattice))
111    }
112}
mz_transform/analysis/monotonic.rs

mz_transform/analysis/
monotonic.rs
