mz_transform/
canonicalize_mfp.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//! Canonicalizes MFPs, e.g., performs CSE on the scalar expressions, eliminates identity MFPs.
11//!
12//! Also calls `canonicalize_predicates` through `fusion::filter`.
13//!
14//! This transform takes a sequence of Maps, Filters, and Projects and
15//! canonicalizes it to a sequence like this:
16//! | Map
17//! | Filter
18//! | Project
19//!
20//! As part of canonicalizing, this transform looks at the Map-Filter-Project
21//! subsequence and identifies common `ScalarExpr` expressions across and within
22//! expressions that are arguments to the Map-Filter-Project. It reforms the
23//! `Map-Filter-Project` subsequence to build each distinct expression at most
24//! once and to re-use expressions instead of re-evaluating them.
25//!
26//! The re-use policy at the moment is severe and re-uses everything.
27//! It may be worth considering relations of this if it results in more
28//! busywork and less efficiency, but the wins can be substantial when
29//! expressions re-use complex subexpressions.
30
31use mz_expr::visit::VisitChildren;
32use mz_expr::{MapFilterProject, MirRelationExpr};
33
34use crate::TransformCtx;
35
36/// Canonicalizes MFPs and performs common sub-expression elimination.
37#[derive(Debug)]
38pub struct CanonicalizeMfp;
39
40impl crate::Transform for CanonicalizeMfp {
41    fn name(&self) -> &'static str {
42        "CanonicalizeMfp"
43    }
44
45    #[mz_ore::instrument(
46        target = "optimizer",
47        level = "debug",
48        fields(path.segment = "canonicalize_mfp")
49    )]
50    fn actually_perform_transform(
51        &self,
52        relation: &mut MirRelationExpr,
53        _: &mut TransformCtx,
54    ) -> Result<(), crate::TransformError> {
55        let result = self.action(relation);
56        mz_repr::explain::trace_plan(&*relation);
57        result
58    }
59}
60
61impl CanonicalizeMfp {
62    /// Extract and optimize MFPs.
63    pub fn action(&self, relation: &mut MirRelationExpr) -> Result<(), crate::TransformError> {
64        let mut mfp = MapFilterProject::extract_non_errors_from_expr_mut(relation);
65        // Optimize MFP, e.g., perform CSE Push MFPs through `Negate` operators,
66        // if encountered. This is a first steps toward a `CanonicalizeLinear`,
67        // which puts linear operators in a canonical representation.
68        mfp.optimize();
69        if let MirRelationExpr::Negate { input } = relation {
70            Self::rebuild_mfp(mfp, &mut **input);
71            relation.try_visit_mut_children(|e| self.action(e))?;
72        } else {
73            relation.try_visit_mut_children(|e| self.action(e))?;
74            Self::rebuild_mfp(mfp, relation);
75        }
76        Ok(())
77    }
78
79    /// Canonicalize the MapFilterProject to Map-Filter-Project, in that order.
80    pub fn rebuild_mfp(mfp: MapFilterProject, relation: &mut MirRelationExpr) {
81        if !mfp.is_identity() {
82            let (map, filter, project) = mfp.as_map_filter_project();
83            let total_arity = mfp.input_arity + map.len();
84            if !map.is_empty() {
85                *relation = relation.take_dangerous().map(map);
86            }
87            if !filter.is_empty() {
88                *relation = relation.take_dangerous().filter(filter);
89                crate::fusion::filter::Filter::action(relation);
90            }
91            if project.len() != total_arity || !project.iter().enumerate().all(|(i, o)| i == *o) {
92                *relation = relation.take_dangerous().project(project);
93            }
94        }
95    }
96}
mz_transform/canonicalize_mfp.rs

mz_transform/
canonicalize_mfp.rs
