mz_expr/
explain.rs

Help
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//! `EXPLAIN` support for structures defined in this crate.
11
12use std::collections::BTreeMap;
13use std::fmt::Formatter;
14use std::time::Duration;
15
16use mz_ore::str::{Indent, IndentLike, separated};
17use mz_repr::GlobalId;
18use mz_repr::explain::ExplainError::LinearChainsPlusRecursive;
19use mz_repr::explain::text::DisplayText;
20use mz_repr::explain::{
21    AnnotatedPlan, Explain, ExplainConfig, ExplainError, ExprHumanizer, ScalarOps,
22    UnsupportedFormat, UsedIndexes,
23};
24use mz_repr::optimize::OptimizerFeatures;
25
26use crate::interpret::{Interpreter, MfpEval, Trace};
27use crate::visit::Visit;
28use crate::{
29    AccessStrategy, Id, LocalId, MapFilterProject, MirRelationExpr, MirScalarExpr, RowSetFinishing,
30};
31
32pub use crate::explain::text::{
33    HumanizedExplain, HumanizedExpr, HumanizedNotice, HumanizerMode, fmt_text_constant_rows,
34};
35
36mod json;
37mod text;
38
39/// Explain context shared by all [`mz_repr::explain::Explain`]
40/// implementations in this crate.
41#[derive(Debug)]
42pub struct ExplainContext<'a> {
43    pub config: &'a ExplainConfig,
44    pub features: &'a OptimizerFeatures,
45    pub humanizer: &'a dyn ExprHumanizer,
46    pub cardinality_stats: BTreeMap<GlobalId, usize>,
47    pub used_indexes: UsedIndexes,
48    pub finishing: Option<RowSetFinishing>,
49    pub duration: Duration,
50    // Cluster against which the explained plan is optimized.
51    pub target_cluster: Option<&'a str>,
52    // This is a String so that we don't have to move `OptimizerNotice` to `mz-expr`. We can revisit
53    // this decision if we want to every make this print in the json output in a machine readable
54    // way.
55    pub optimizer_notices: Vec<String>,
56}
57
58/// A structure produced by the `explain_$format` methods in
59/// [`mz_repr::explain::Explain`] implementations for points
60/// in the optimization pipeline identified with a single plan of
61/// type `T`.
62#[allow(missing_debug_implementations)]
63pub struct ExplainSinglePlan<'a, T> {
64    pub context: &'a ExplainContext<'a>,
65    pub plan: AnnotatedPlan<'a, T>,
66}
67
68/// Carries metadata about the possibility of MFP pushdown for a source.
69/// (Likely to change, and only emitted when a context flag is enabled.)
70#[allow(missing_debug_implementations)]
71pub struct PushdownInfo<'a> {
72    /// Pushdown-able filters in the source, by index.
73    pub pushdown: Vec<&'a MirScalarExpr>,
74}
75
76impl<'a, C, M> DisplayText<C> for HumanizedExpr<'a, PushdownInfo<'a>, M>
77where
78    C: AsMut<Indent>,
79    M: HumanizerMode,
80{
81    fn fmt_text(&self, f: &mut Formatter<'_>, ctx: &mut C) -> std::fmt::Result {
82        let PushdownInfo { pushdown } = self.expr;
83
84        if !pushdown.is_empty() {
85            let pushdown = pushdown.iter().map(|e| self.mode.expr(*e, self.cols));
86            let pushdown = separated(" AND ", pushdown);
87            writeln!(f, "{}pushdown=({})", ctx.as_mut(), pushdown)?;
88        }
89
90        Ok(())
91    }
92}
93
94#[allow(missing_debug_implementations)]
95pub struct ExplainSource<'a> {
96    pub id: GlobalId,
97    pub op: Option<&'a MapFilterProject>,
98    pub pushdown_info: Option<PushdownInfo<'a>>,
99}
100
101impl<'a> ExplainSource<'a> {
102    pub fn new(
103        id: GlobalId,
104        op: Option<&'a MapFilterProject>,
105        filter_pushdown: bool,
106    ) -> ExplainSource<'a> {
107        let pushdown_info = if filter_pushdown {
108            op.map(|op| {
109                let mfp_mapped = MfpEval::new(&Trace, op.input_arity, &op.expressions);
110                let pushdown = op
111                    .predicates
112                    .iter()
113                    .filter(|(_, e)| mfp_mapped.expr(e).pushdownable())
114                    .map(|(_, e)| e)
115                    .collect();
116                PushdownInfo { pushdown }
117            })
118        } else {
119            None
120        };
121
122        ExplainSource {
123            id,
124            op,
125            pushdown_info,
126        }
127    }
128
129    #[inline]
130    pub fn is_identity(&self) -> bool {
131        match self.op {
132            Some(op) => op.is_identity(),
133            None => false,
134        }
135    }
136}
137
138impl<'a, 'h, C, M> DisplayText<C> for HumanizedExpr<'a, ExplainSource<'a>, M>
139where
140    C: AsMut<Indent> + AsRef<&'h dyn ExprHumanizer>,
141    M: HumanizerMode,
142{
143    fn fmt_text(&self, f: &mut std::fmt::Formatter<'_>, ctx: &mut C) -> std::fmt::Result {
144        let id = ctx
145            .as_ref()
146            .humanize_id(self.expr.id)
147            .unwrap_or_else(|| self.expr.id.to_string());
148        writeln!(f, "{}Source {}", ctx.as_mut(), id)?;
149        ctx.indented(|ctx| {
150            if let Some(op) = self.expr.op {
151                self.child(op).fmt_text(f, ctx)?;
152            }
153            if let Some(pushdown_info) = &self.expr.pushdown_info {
154                self.child(pushdown_info).fmt_text(f, ctx)?;
155            }
156            Ok(())
157        })
158    }
159}
160
161/// A structure produced by the `explain_$format` methods in
162/// [`mz_repr::explain::Explain`] implementations at points
163/// in the optimization pipeline identified with a
164/// `DataflowDescription` instance with plans of type `T`.
165#[allow(missing_debug_implementations)]
166pub struct ExplainMultiPlan<'a, T> {
167    pub context: &'a ExplainContext<'a>,
168    // Maps the names of the sources to the linear operators that will be
169    // on them.
170    pub sources: Vec<ExplainSource<'a>>,
171    // elements of the vector are in topological order
172    pub plans: Vec<(String, AnnotatedPlan<'a, T>)>,
173}
174
175impl<'a> Explain<'a> for MirRelationExpr {
176    type Context = ExplainContext<'a>;
177
178    type Text = ExplainSinglePlan<'a, MirRelationExpr>;
179
180    type VerboseText = ExplainSinglePlan<'a, MirRelationExpr>;
181
182    type Json = ExplainSinglePlan<'a, MirRelationExpr>;
183
184    type Dot = UnsupportedFormat;
185
186    fn explain_text(&'a mut self, context: &'a Self::Context) -> Result<Self::Text, ExplainError> {
187        self.as_explain_single_plan(context)
188    }
189
190    fn explain_verbose_text(
191        &'a mut self,
192        context: &'a Self::Context,
193    ) -> Result<Self::VerboseText, ExplainError> {
194        self.as_explain_single_plan(context)
195    }
196
197    fn explain_json(&'a mut self, context: &'a Self::Context) -> Result<Self::Json, ExplainError> {
198        self.as_explain_single_plan(context)
199    }
200}
201
202impl<'a> MirRelationExpr {
203    fn as_explain_single_plan(
204        &'a mut self,
205        context: &'a ExplainContext<'a>,
206    ) -> Result<ExplainSinglePlan<'a, MirRelationExpr>, ExplainError> {
207        // normalize the representation as linear chains
208        // (this implies !context.config.raw_plans by construction)
209        if context.config.linear_chains {
210            enforce_linear_chains(self)?;
211        };
212
213        let plan = AnnotatedPlan {
214            plan: self,
215            annotations: BTreeMap::default(),
216        };
217
218        Ok(ExplainSinglePlan { context, plan })
219    }
220}
221
222/// Normalize the way inputs of multi-input variants are rendered.
223///
224/// After the transform is applied, non-trival inputs `$input` of variants with
225/// more than one input are wrapped in a `let $x = $input in $x` blocks.
226///
227/// If these blocks are subsequently pulled up by `NormalizeLets`,
228/// the rendered version of the resulting tree will only have linear chains.
229pub fn enforce_linear_chains(expr: &mut MirRelationExpr) -> Result<(), ExplainError> {
230    use MirRelationExpr::{Constant, Get, Join, Union};
231
232    if expr.is_recursive() {
233        // `linear_chains` is not implemented for WMR, see
234        // https://github.com/MaterializeInc/database-issues/issues/5631
235        return Err(LinearChainsPlusRecursive);
236    }
237
238    // helper struct: a generator of fresh local ids
239    let mut id_gen = id_gen(expr).peekable();
240
241    let mut wrap_in_let = |input: &mut MirRelationExpr| {
242        match input {
243            Constant { .. } | Get { .. } => (),
244            input => {
245                // generate fresh local id
246                // let id = id_cnt
247                //     .next()
248                //     .map(|id| LocalId::new(1000_u64 + u64::cast_from(id_map.len()) + id))
249                //     .unwrap();
250                let id = id_gen.next().unwrap();
251                let value = input.take_safely(None);
252                // generate a `let $fresh_id = $body in $fresh_id` to replace this input
253                let mut binding = MirRelationExpr::Let {
254                    id,
255                    value: Box::new(value),
256                    body: Box::new(Get {
257                        id: Id::Local(id.clone()),
258                        typ: input.typ(),
259                        access_strategy: AccessStrategy::UnknownOrLocal,
260                    }),
261                };
262                // swap the current body with the replacement
263                std::mem::swap(input, &mut binding);
264            }
265        }
266    };
267
268    expr.try_visit_mut_post(&mut |expr: &mut MirRelationExpr| {
269        match expr {
270            Join { inputs, .. } => {
271                for input in inputs {
272                    wrap_in_let(input);
273                }
274            }
275            Union { base, inputs } => {
276                wrap_in_let(base);
277                for input in inputs {
278                    wrap_in_let(input);
279                }
280            }
281            _ => (),
282        }
283        Ok(())
284    })
285}
286
287// Create an [`Iterator`] for [`LocalId`] values that are guaranteed to be
288// fresh within the scope of the given [`MirRelationExpr`].
289fn id_gen(expr: &MirRelationExpr) -> impl Iterator<Item = LocalId> + use<> {
290    let mut max_id = 0_u64;
291
292    expr.visit_pre(|expr| {
293        match expr {
294            MirRelationExpr::Let { id, .. } => max_id = std::cmp::max(max_id, id.into()),
295            _ => (),
296        };
297    });
298
299    (max_id + 1..).map(LocalId::new)
300}
301
302impl ScalarOps for MirScalarExpr {
303    fn match_col_ref(&self) -> Option<usize> {
304        match self {
305            MirScalarExpr::Column(c) => Some(*c),
306            _ => None,
307        }
308    }
309
310    fn references(&self, column: usize) -> bool {
311        match self {
312            MirScalarExpr::Column(c) => *c == column,
313            _ => false,
314        }
315    }
316}
mz_expr/explain.rs

mz_expr/
explain.rs
