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

mz_transform/
monotonic.rs
