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

mz_expr/
explain.rs
