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

mz_expr/
explain.rs
