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
// 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.

//! Install replace certain `Get` operators with their `Let` value.
//!
//! Some `Let` bindings are not useful, for example when they bind
//! a `Get` as their value, or when there is a single corresponding
//! `Get` statement in their body. These cases can be inlined without
//! harming planning.

use crate::TransformArgs;
use mz_expr::visit::{Visit, VisitChildren};
use mz_expr::{Id, LocalId, MirRelationExpr, RECURSION_LIMIT};
use mz_ore::stack::{CheckedRecursion, RecursionGuard};

/// Install replace certain `Get` operators with their `Let` value.
#[derive(Debug)]
pub struct InlineLet {
    /// If `true`, inline MFPs around a Get.
    ///
    /// We want this value to be true for the InlineLet call that comes right
    /// before [crate::join_implementation::JoinImplementation] runs because
    /// [crate::join_implementation::JoinImplementation] cannot lift MFPs
    /// through a Let.
    ///
    /// Generally, though, we prefer to be more conservative in our inlining in
    /// order to be able to better detect CSEs.
    pub inline_mfp: bool,
    /// A [`RecursionGuard`] to be used by the [`CheckedRecursion`] implementation.
    recursion_guard: RecursionGuard,
}

impl InlineLet {
    /// Construct a new [`InlineLet`] instance with the given `inline_mfp`
    /// where `recursion_guard` is initialized with [`RECURSION_LIMIT`] as limit.
    pub fn new(inline_mfp: bool) -> InlineLet {
        InlineLet {
            inline_mfp,
            recursion_guard: RecursionGuard::with_limit(RECURSION_LIMIT),
        }
    }
}

impl CheckedRecursion for InlineLet {
    fn recursion_guard(&self) -> &RecursionGuard {
        &self.recursion_guard
    }
}

impl crate::Transform for InlineLet {
    #[tracing::instrument(
        target = "optimizer"
        level = "trace",
        skip_all,
        fields(path.segment = "inline_let")
    )]
    fn transform(
        &self,
        relation: &mut MirRelationExpr,
        _: TransformArgs,
    ) -> Result<(), crate::TransformError> {
        let result = self.transform_without_trace(relation);
        mz_repr::explain_new::trace_plan(&*relation);
        result
    }
}

impl InlineLet {
    /// Performs the `InlineLet` transformation without tracing the result.
    pub fn transform_without_trace(
        &self,
        relation: &mut MirRelationExpr,
    ) -> Result<(), crate::TransformError> {
        let mut lets = vec![];
        self.action(relation, &mut lets)?;
        for (id, value) in lets.into_iter().rev() {
            *relation = MirRelationExpr::Let {
                id,
                value: Box::new(value),
                body: Box::new(relation.take_dangerous()),
            };
        }
        Ok(())
    }

    /// Install replace certain `Get` operators with their `Let` value.
    ///
    /// IMPORTANT: This transform is used for cleaning up after `RelationCSE`, which
    /// adds `Let` operators pretty aggressively, leading to very deep dataflows. Nothing
    /// in this transform should lead to expensive recursive traversal of the subgraph,
    /// such as the one in `MirRelationExpr::typ`, since that may result in a stack
    /// overflow.
    pub fn action(
        &self,
        relation: &mut MirRelationExpr,
        lets: &mut Vec<(LocalId, MirRelationExpr)>,
    ) -> Result<(), crate::TransformError> {
        self.checked_recur(|_| {
            if let MirRelationExpr::Let { id, value, body } = relation {
                self.action(value, lets)?;

                let mut num_gets = 0;
                body.try_visit_mut_pre::<_, crate::TransformError>(
                    &mut |relation| match relation {
                        MirRelationExpr::Get { id: get_id, .. } if Id::Local(*id) == *get_id => {
                            num_gets += 1;
                            Ok(())
                        }
                        _ => Ok(()),
                    },
                )?;

                let stripped_value = if self.inline_mfp {
                    mz_expr::MapFilterProject::extract_non_errors_from_expr(&**value).1
                } else {
                    &**value
                };
                let inlinable = match stripped_value {
                    MirRelationExpr::Get { .. } | MirRelationExpr::Constant { .. } => true,
                    _ => num_gets <= 1,
                };

                if inlinable {
                    // if only used once, just inline it
                    body.try_visit_mut_pre::<_, crate::TransformError>(&mut |relation| {
                        match relation {
                            MirRelationExpr::Get { id: get_id, .. }
                                if Id::Local(*id) == *get_id =>
                            {
                                *relation = (**value).clone();
                                Ok(())
                            }
                            _ => Ok(()),
                        }
                    })?;
                } else {
                    // otherwise lift it to the top so it's out of the way
                    lets.push((*id, value.take_dangerous()));
                }

                *relation = body.take_dangerous();
                // might be another Let in the body so have to recur here
                self.action(relation, lets)
            } else {
                relation.try_visit_mut_children(|child| self.action(child, lets))
            }
        })
    }
}