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

mz_expr/
explain.rs
