mz_transform/
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 to identify monotonic collections, especially TopK inputs.
11
12use std::collections::BTreeSet;
13
14use itertools::Itertools;
15use mz_expr::MirRelationExpr;
16use mz_repr::GlobalId;
17
18use crate::TransformCtx;
19use crate::analysis::DerivedBuilder;
20use crate::analysis::monotonic::Monotonic;
21
22/// A struct to apply expression optimizations based on the [`Monotonic`] analysis.
23#[derive(Debug, Default)]
24pub struct MonotonicFlag;
25
26impl MonotonicFlag {
27    /// Transforms `expr` by propagating information about monotonicity through operators,
28    /// using [`mz_repr::optimize::OptimizerFeatures`] from `ctx` and global monotonic ids.
29    pub fn transform(
30        &self,
31        expr: &mut MirRelationExpr,
32        ctx: &mut TransformCtx,
33        global_monotonic_ids: &BTreeSet<GlobalId>,
34    ) -> Result<(), crate::RecursionLimitError> {
35        let mut builder = DerivedBuilder::new(ctx.features);
36        builder.require(Monotonic::new(global_monotonic_ids.clone()));
37        let derived = builder.visit(&*expr);
38
39        let mut todo = vec![(&mut *expr, derived.as_view())];
40        while let Some((expr, view)) = todo.pop() {
41            match expr {
42                MirRelationExpr::Reduce { monotonic, .. }
43                | MirRelationExpr::TopK { monotonic, .. } => {
44                    *monotonic = *view
45                        .last_child()
46                        .value::<Monotonic>()
47                        .expect("Monotonic required");
48                }
49                _ => {}
50            }
51            todo.extend(expr.children_mut().rev().zip_eq(view.children_rev()))
52        }
53
54        mz_repr::explain::trace_plan(&*expr);
55        Ok(())
56    }
57}
mz_transform/monotonic.rs

mz_transform/
monotonic.rs
