mz_transform/
lib.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//! Transformations for relation expressions.
11//!
12//! This crate contains traits, types, and methods suitable for transforming
13//! `MirRelationExpr` types in ways that preserve semantics and improve performance.
14//! The core trait is `Transform`, and many implementors of this trait can be
15//! boxed and iterated over. Some common transformation patterns are wrapped
16//! as `Transform` implementors themselves.
17//!
18//! The crate also contains the beginnings of whole-dataflow optimization,
19//! which uses the same analyses but spanning multiple dataflow elements.
20
21#![warn(missing_docs)]
22#![warn(missing_debug_implementations)]
23
24use std::collections::BTreeMap;
25use std::error::Error;
26use std::panic::AssertUnwindSafe;
27use std::sync::Arc;
28use std::{fmt, iter};
29
30use mz_expr::{MirRelationExpr, MirScalarExpr};
31use mz_ore::id_gen::IdGen;
32use mz_ore::stack::RecursionLimitError;
33use mz_ore::{soft_assert_or_log, soft_panic_or_log};
34use mz_repr::GlobalId;
35use mz_repr::optimize::OptimizerFeatures;
36use mz_sql::optimizer_metrics::OptimizerMetrics;
37use tracing::error;
38
39use crate::canonicalize_mfp::CanonicalizeMfp;
40use crate::column_knowledge::ColumnKnowledge;
41use crate::dataflow::DataflowMetainfo;
42use crate::demand::Demand;
43use crate::equivalence_propagation::EquivalencePropagation;
44use crate::fold_constants::FoldConstants;
45use crate::join_implementation::JoinImplementation;
46use crate::literal_constraints::LiteralConstraints;
47use crate::literal_lifting::LiteralLifting;
48use crate::movement::ProjectionPushdown;
49use crate::non_null_requirements::NonNullRequirements;
50use crate::normalize_lets::NormalizeLets;
51use crate::normalize_ops::NormalizeOps;
52use crate::predicate_pushdown::PredicatePushdown;
53use crate::reduce_elision::ReduceElision;
54use crate::reduce_reduction::ReduceReduction;
55use crate::reduction_pushdown::ReductionPushdown;
56use crate::redundant_join::RedundantJoin;
57use crate::semijoin_idempotence::SemijoinIdempotence;
58use crate::threshold_elision::ThresholdElision;
59use crate::typecheck::{SharedContext, Typecheck};
60use crate::union_cancel::UnionBranchCancellation;
61use crate::will_distinct::WillDistinct;
62
63pub use dataflow::optimize_dataflow;
64
65pub mod analysis;
66pub mod canonicalization;
67pub mod canonicalize_mfp;
68pub mod column_knowledge;
69pub mod compound;
70pub mod cse;
71pub mod dataflow;
72pub mod demand;
73pub mod equivalence_propagation;
74pub mod fold_constants;
75pub mod fusion;
76pub mod join_implementation;
77pub mod literal_constraints;
78pub mod literal_lifting;
79pub mod monotonic;
80pub mod movement;
81pub mod non_null_requirements;
82pub mod normalize_lets;
83pub mod normalize_ops;
84pub mod notice;
85pub mod ordering;
86pub mod predicate_pushdown;
87pub mod reduce_elision;
88pub mod reduce_reduction;
89pub mod reduction_pushdown;
90pub mod redundant_join;
91pub mod semijoin_idempotence;
92pub mod threshold_elision;
93pub mod typecheck;
94pub mod union_cancel;
95pub mod will_distinct;
96
97/// Compute the conjunction of a variadic number of expressions.
98#[macro_export]
99macro_rules! all {
100    ($x:expr) => ($x);
101    ($($x:expr,)+) => ( $($x)&&+ )
102}
103
104/// Compute the disjunction of a variadic number of expressions.
105#[macro_export]
106macro_rules! any {
107    ($x:expr) => ($x);
108    ($($x:expr,)+) => ( $($x)||+ )
109}
110
111/// Arguments that get threaded through all transforms, plus a `DataflowMetainfo` that can be
112/// manipulated by the transforms.
113#[derive(Debug)]
114pub struct TransformCtx<'a> {
115    /// The global ID for this query (if it exists).
116    pub global_id: Option<GlobalId>,
117    /// The indexes accessible.
118    pub indexes: &'a dyn IndexOracle,
119    /// Statistical estimates.
120    pub stats: &'a dyn StatisticsOracle,
121    /// Features passed to the enclosing `Optimizer`.
122    pub features: &'a OptimizerFeatures,
123    /// Typechecking context.
124    pub typecheck_ctx: &'a SharedContext,
125    /// Transforms can use this field to communicate information outside the result plans.
126    pub df_meta: &'a mut DataflowMetainfo,
127    /// Metrics for the optimizer.
128    pub metrics: Option<&'a OptimizerMetrics>,
129    /// The last hash of the query, if known.
130    pub last_hash: BTreeMap<GlobalId, u64>,
131}
132
133const FOLD_CONSTANTS_LIMIT: usize = 10000;
134
135impl<'a> TransformCtx<'a> {
136    /// Generates a [`TransformCtx`] instance for the local MIR optimization
137    /// stage.
138    ///
139    /// Used to call [`Optimizer::optimize`] on a
140    /// [`Optimizer::logical_optimizer`] in order to transform a stand-alone
141    /// [`MirRelationExpr`].
142    pub fn local(
143        features: &'a OptimizerFeatures,
144        typecheck_ctx: &'a SharedContext,
145        df_meta: &'a mut DataflowMetainfo,
146        metrics: Option<&'a OptimizerMetrics>,
147        global_id: Option<GlobalId>,
148    ) -> Self {
149        Self {
150            indexes: &EmptyIndexOracle,
151            stats: &EmptyStatisticsOracle,
152            global_id,
153            features,
154            typecheck_ctx,
155            df_meta,
156            metrics,
157            last_hash: Default::default(),
158        }
159    }
160
161    /// Generates a [`TransformCtx`] instance for the global MIR optimization
162    /// stage.
163    ///
164    /// Used to call [`optimize_dataflow`].
165    pub fn global(
166        indexes: &'a dyn IndexOracle,
167        stats: &'a dyn StatisticsOracle,
168        features: &'a OptimizerFeatures,
169        typecheck_ctx: &'a SharedContext,
170        df_meta: &'a mut DataflowMetainfo,
171        metrics: Option<&'a OptimizerMetrics>,
172    ) -> Self {
173        Self {
174            indexes,
175            stats,
176            global_id: None,
177            features,
178            df_meta,
179            typecheck_ctx,
180            metrics,
181            last_hash: Default::default(),
182        }
183    }
184
185    fn typecheck(&self) -> SharedContext {
186        Arc::clone(self.typecheck_ctx)
187    }
188
189    /// Lets self know the id of the object that is being optimized.
190    pub fn set_global_id(&mut self, global_id: GlobalId) {
191        self.global_id = Some(global_id);
192    }
193
194    fn reset_global_id(&mut self) {
195        self.global_id = None;
196    }
197
198    /// Updates `last_hash` with the hash of the given MIR plan for the id `self.global_id`.
199    /// Returns the hash.
200    fn update_last_hash(&mut self, plan: &MirRelationExpr) -> u64 {
201        let hash = plan.hash_to_u64();
202        if let Some(id) = self.global_id {
203            self.last_hash.insert(id, hash);
204        }
205        hash
206    }
207}
208
209/// Types capable of transforming relation expressions.
210pub trait Transform: fmt::Debug {
211    /// Transforms a relation into a functionally equivalent relation.
212    ///
213    /// This is a wrapper around `actually_perform_transform` that also
214    /// measures the time taken and updates the optimizer metrics.
215    fn transform(
216        &self,
217        relation: &mut MirRelationExpr,
218        args: &mut TransformCtx,
219    ) -> Result<(), TransformError> {
220        let hash_before = args
221            .global_id
222            .and_then(|id| args.last_hash.get(&id).copied())
223            .unwrap_or_else(|| relation.hash_to_u64());
224
225        mz_ore::soft_assert_eq_no_log!(hash_before, relation.hash_to_u64(), "cached hash clash");
226        // actually run the transform, recording the time taken
227        let start = std::time::Instant::now();
228        let res = self.actually_perform_transform(relation, args);
229        let duration = start.elapsed();
230
231        let hash_after = args.update_last_hash(relation);
232        if let Some(metrics) = args.metrics {
233            let transform_name = self.name();
234            metrics.observe_transform_time(transform_name, duration);
235            metrics.inc_transform(hash_before != hash_after, transform_name);
236        }
237
238        res
239    }
240
241    /// Transform a relation into a functionally equivalent relation.
242    ///
243    /// You transform should implement this method, but users should call
244    /// `transform` instead.
245    fn actually_perform_transform(
246        &self,
247        relation: &mut MirRelationExpr,
248        ctx: &mut TransformCtx,
249    ) -> Result<(), TransformError>;
250
251    /// A string describing the transform.
252    ///
253    /// This is useful mainly when iterating through many `Box<Transform>`
254    /// and one wants to judge progress before some defect occurs.
255    fn debug(&self) -> String {
256        format!("{:?}", self)
257    }
258
259    /// A short string naming the transform, as it will be reported in metrics.
260    fn name(&self) -> &'static str;
261}
262
263/// Errors that can occur during a transformation.
264#[derive(Debug, Clone)]
265pub enum TransformError {
266    /// An unstructured error.
267    Internal(String),
268    /// A reference to an apparently unbound identifier.
269    IdentifierMissing(mz_expr::LocalId),
270    /// Notify the caller to panic with the given message.
271    ///
272    /// This is used to bypass catch_unwind-wrapped calls of the optimizer and
273    /// support `SELECT mz_unsafe.mz_panic(<literal>)` statements as a mechanism to kill
274    /// environmentd in various tests.
275    CallerShouldPanic(String),
276}
277
278impl fmt::Display for TransformError {
279    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
280        match self {
281            TransformError::Internal(msg) => write!(f, "internal transform error: {}", msg),
282            TransformError::IdentifierMissing(i) => {
283                write!(f, "apparently unbound identifier: {:?}", i)
284            }
285            TransformError::CallerShouldPanic(msg) => {
286                write!(f, "caller should panic with message: {}", msg)
287            }
288        }
289    }
290}
291
292impl Error for TransformError {}
293
294impl From<RecursionLimitError> for TransformError {
295    fn from(error: RecursionLimitError) -> Self {
296        TransformError::Internal(error.to_string())
297    }
298}
299
300/// Implemented by error types that sometimes want to indicate that an error should cause a panic
301/// even in a `catch_unwind` context. Useful for implementing `mz_unsafe.mz_panic('forced panic')`.
302pub trait MaybeShouldPanic {
303    /// Whether the error means that we want a panic. If yes, then returns the error msg.
304    fn should_panic(&self) -> Option<String>;
305}
306
307impl MaybeShouldPanic for TransformError {
308    fn should_panic(&self) -> Option<String> {
309        match self {
310            TransformError::CallerShouldPanic(msg) => Some(msg.to_string()),
311            _ => None,
312        }
313    }
314}
315
316/// Catch panics in the given optimization, and demote them to [`TransformError::Internal`] error.
317///
318/// Additionally, if the result of the optimization is an error (not a panic) that indicates we
319/// should panic, then panic.
320pub fn catch_unwind_optimize<Opt, To, E>(optimization: Opt) -> Result<To, E>
321where
322    Opt: FnOnce() -> Result<To, E>,
323    E: From<TransformError> + MaybeShouldPanic,
324{
325    match mz_ore::panic::catch_unwind_str(AssertUnwindSafe(optimization)) {
326        Ok(Err(e)) if e.should_panic().is_some() => {
327            // Promote a `CallerShouldPanic` error from the result to a proper panic. This is
328            // needed in order to ensure that `mz_unsafe.mz_panic('forced panic')` calls still
329            // panic the caller.
330            panic!("{}", e.should_panic().expect("checked above"));
331        }
332        Ok(result) => result.map_err(|e| e),
333        Err(panic) => {
334            // A panic during optimization is always a bug; log an error so we learn about it.
335            // TODO(teskje): collect and log a backtrace from the panic site
336            tracing::error!("caught a panic during query optimization: {panic}");
337
338            let msg = format!("unexpected panic during query optimization: {panic}");
339            Err(TransformError::Internal(msg).into())
340        }
341    }
342}
343
344/// A trait for a type that can answer questions about what indexes exist.
345pub trait IndexOracle: fmt::Debug {
346    /// Returns an iterator over the indexes that exist on the identified
347    /// collection.
348    ///
349    /// Each index is described by the list of key expressions. If no indexes
350    /// exist for the identified collection, or if the identified collection
351    /// is unknown, the returned iterator will be empty.
352    ///
353    // NOTE(benesch): The allocation here is unfortunate, but on the other hand
354    // you need only allocate when you actually look for an index. Can we do
355    // better somehow? Making the entire optimizer generic over this iterator
356    // type doesn't presently seem worthwhile.
357    fn indexes_on(
358        &self,
359        id: GlobalId,
360    ) -> Box<dyn Iterator<Item = (GlobalId, &[MirScalarExpr])> + '_>;
361}
362
363/// An [`IndexOracle`] that knows about no indexes.
364#[derive(Debug)]
365pub struct EmptyIndexOracle;
366
367impl IndexOracle for EmptyIndexOracle {
368    fn indexes_on(
369        &self,
370        _id: GlobalId,
371    ) -> Box<dyn Iterator<Item = (GlobalId, &[MirScalarExpr])> + '_> {
372        Box::new(iter::empty())
373    }
374}
375
376/// A trait for a type that can estimate statistics about a given `GlobalId`
377pub trait StatisticsOracle: fmt::Debug + Send {
378    /// Returns a cardinality estimate for the given identifier
379    ///
380    /// Returning `None` means "no estimate"; returning `Some(0)` means estimating that the shard backing `id` is empty
381    fn cardinality_estimate(&self, id: GlobalId) -> Option<usize>;
382
383    /// Returns a map from identifiers to sizes
384    fn as_map(&self) -> BTreeMap<GlobalId, usize>;
385}
386
387/// A [`StatisticsOracle`] that knows nothing and can give no estimates.
388#[derive(Debug)]
389pub struct EmptyStatisticsOracle;
390
391impl StatisticsOracle for EmptyStatisticsOracle {
392    fn cardinality_estimate(&self, _: GlobalId) -> Option<usize> {
393        None
394    }
395
396    fn as_map(&self) -> BTreeMap<GlobalId, usize> {
397        BTreeMap::new()
398    }
399}
400
401/// A sequence of transformations iterated some number of times.
402#[derive(Debug)]
403pub struct Fixpoint {
404    name: &'static str,
405    transforms: Vec<Box<dyn Transform>>,
406    limit: usize,
407}
408
409impl Fixpoint {
410    /// Run a single iteration of the [`Fixpoint`] transform by iterating
411    /// through all transforms.
412    #[mz_ore::instrument(
413        target = "optimizer",
414        level = "debug",
415        fields(path.segment = iter_name)
416    )]
417    fn apply_transforms(
418        &self,
419        relation: &mut MirRelationExpr,
420        ctx: &mut TransformCtx,
421        iter_name: String,
422    ) -> Result<(), TransformError> {
423        for transform in self.transforms.iter() {
424            transform.transform(relation, ctx)?;
425        }
426        mz_repr::explain::trace_plan(relation);
427        Ok(())
428    }
429}
430
431impl Transform for Fixpoint {
432    fn name(&self) -> &'static str {
433        self.name
434    }
435
436    #[mz_ore::instrument(
437        target = "optimizer",
438        level = "debug",
439        fields(path.segment = self.name)
440    )]
441    fn actually_perform_transform(
442        &self,
443        relation: &mut MirRelationExpr,
444        ctx: &mut TransformCtx,
445    ) -> Result<(), TransformError> {
446        // The number of iterations for a relation to settle depends on the
447        // number of nodes in the relation. Instead of picking an arbitrary
448        // hard limit on the number of iterations, we use a soft limit and
449        // check whether the relation has become simpler after reaching it.
450        // If so, we perform another pass of transforms. Otherwise, there is
451        // a bug somewhere that prevents the relation from settling on a
452        // stable shape.
453        let mut iter_no = 0;
454        let mut seen = BTreeMap::new();
455        seen.insert(relation.hash_to_u64(), iter_no);
456        let original = relation.clone();
457        loop {
458            let prev_size = relation.size();
459            for i in iter_no..iter_no + self.limit {
460                let prev = relation.clone();
461                self.apply_transforms(relation, ctx, format!("{i:04}"))?;
462                if *relation == prev {
463                    if prev_size > 100000 {
464                        tracing::warn!(%prev_size, "Very big MIR plan");
465                    }
466                    mz_repr::explain::trace_plan(relation);
467                    return Ok(());
468                }
469                let seen_i = seen.insert(relation.hash_to_u64(), i);
470                if let Some(seen_i) = seen_i {
471                    // Let's see whether this is just a hash collision, or a real loop: Run the
472                    // whole thing from the beginning up until `seen_i`, and compare all the plans
473                    // to the current plan from the outer `for`.
474                    // (It would not be enough to compare only the plan at `seen_i`, because
475                    // then we could miss a real loop if there is also a hash collision somewhere
476                    // in the middle of the loop, because then we'd compare the last plan of the
477                    // loop not with its actual match, but with the colliding plan.)
478                    let mut again = original.clone();
479                    // The `+2` is because:
480                    // - one `+1` is to finally get to the plan at `seen_i`,
481                    // - another `+1` is because we are comparing to `relation` only _before_
482                    //   calling `apply_transforms`.
483                    for j in 0..(seen_i + 2) {
484                        if again == *relation {
485                            // We really got into an infinite loop (e.g., we are oscillating between
486                            // two plans). This is not catastrophic, because we can just say we are
487                            // done now, but it would be great to eventually find a way to prevent
488                            // these loops from happening in the first place. We have several
489                            // relevant issues, see
490                            // https://github.com/MaterializeInc/database-issues/issues/8197#issuecomment-2200172227
491                            mz_repr::explain::trace_plan(relation);
492                            error!(
493                                "Fixpoint `{}` detected a loop of length {} after {} iterations",
494                                self.name,
495                                i - seen_i,
496                                i
497                            );
498                            return Ok(());
499                        }
500                        ctx.update_last_hash(&again);
501                        self.apply_transforms(
502                            &mut again,
503                            ctx,
504                            format!("collision detection {j:04}"),
505                        )?;
506                    }
507                    // If we got here, then this was just a hash collision! Just continue as if
508                    // nothing happened.
509                }
510            }
511            let current_size = relation.size();
512
513            iter_no += self.limit;
514
515            if current_size < prev_size {
516                tracing::warn!(
517                    "Fixpoint {} ran for {} iterations \
518                     without reaching a fixpoint but reduced the relation size; \
519                     current_size ({}) < prev_size ({}); \
520                     continuing for {} more iterations",
521                    self.name,
522                    iter_no,
523                    current_size,
524                    prev_size,
525                    self.limit
526                );
527            } else {
528                // We failed to reach a fixed point, or find a sufficiently short cycle.
529                // This is not catastrophic, because we can just say we are done now,
530                // but it would be great to eventually find a way to prevent these loops from
531                // happening in the first place. We have several relevant issues, see
532                // https://github.com/MaterializeInc/database-issues/issues/8197#issuecomment-2200172227
533                mz_repr::explain::trace_plan(relation);
534                soft_panic_or_log!(
535                    "Fixpoint {} failed to reach a fixed point, or cycle of length at most {}",
536                    self.name,
537                    self.limit,
538                );
539                return Ok(());
540            }
541        }
542    }
543}
544
545/// Convenience macro for guarding transforms behind a feature flag.
546///
547/// If you have a code block like
548///
549/// ```ignore
550/// vec![
551///     Box::new(Foo::default()),
552///     Box::new(Bar::default()),
553///     Box::new(Baz::default()),
554/// ]
555/// ```
556///
557/// and you want to guard `Bar` behind a feature flag `enable_bar`, you can
558/// write
559///
560/// ```ignore
561/// transforms![
562///     Box::new(Foo::default()),
563///     Box::new(Bar::default()); if ctx.features.enable_bar,
564///     Box::new(Baz::default()),
565/// ]
566/// ```
567///
568/// as a shorthand and in order to minimize your code diff.
569#[allow(unused_macros)]
570macro_rules! transforms {
571    // Internal rule. Matches lines with a guard: `$transform; if $cond`.
572    (@op fill $buf:ident with $transform:expr; if $cond:expr, $($transforms:tt)*) => {
573        if $cond {
574            $buf.push($transform);
575        }
576        transforms!(@op fill $buf with $($transforms)*);
577    };
578    // Internal rule. Matches lines without a guard: `$transform`.
579    (@op fill $buf:ident with $transform:expr, $($transforms:tt)*) => {
580        $buf.push($transform);
581        transforms!(@op fill $buf with $($transforms)*);
582    };
583    // Internal rule: matches the empty $transforms TokenTree (terminal case).
584    (@op fill $buf:ident with) => {
585        // do nothing
586    };
587    ($($transforms:tt)*) => {{
588        #[allow(clippy::vec_init_then_push)]
589        {
590            let mut __buf = Vec::<Box<dyn Transform>>::new();
591            transforms!(@op fill __buf with $($transforms)*);
592            __buf
593        }
594    }};
595}
596
597/// A sequence of transformations that simplify the `MirRelationExpr`
598#[derive(Debug)]
599pub struct FuseAndCollapse {
600    transforms: Vec<Box<dyn Transform>>,
601}
602
603impl Default for FuseAndCollapse {
604    fn default() -> Self {
605        Self {
606            // TODO: The relative orders of the transforms have not been
607            // determined except where there are comments.
608            // TODO (database-issues#2036): All the transforms here except for `ProjectionLifting`
609            //  and `RedundantJoin` can be implemented as free functions.
610            transforms: vec![
611                Box::new(canonicalization::ProjectionExtraction),
612                Box::new(movement::ProjectionLifting::default()),
613                Box::new(fusion::Fusion),
614                Box::new(canonicalization::FlatMapElimination),
615                Box::new(fusion::join::Join),
616                Box::new(NormalizeLets::new(false)),
617                Box::new(fusion::reduce::Reduce),
618                Box::new(WillDistinct),
619                Box::new(compound::UnionNegateFusion),
620                // This goes after union fusion so we can cancel out
621                // more branches at a time.
622                Box::new(UnionBranchCancellation),
623                // This should run before redundant join to ensure that key info
624                // is correct.
625                Box::new(NormalizeLets::new(false)),
626                // Removes redundant inputs from joins.
627                // Note that this eliminates one redundant input per join,
628                // so it is necessary to run this section in a loop.
629                Box::new(RedundantJoin::default()),
630                // As a final logical action, convert any constant expression to a constant.
631                // Some optimizations fight against this, and we want to be sure to end as a
632                // `MirRelationExpr::Constant` if that is the case, so that subsequent use can
633                // clearly see this.
634                Box::new(fold_constants_fixpoint()),
635            ],
636        }
637    }
638}
639
640impl Transform for FuseAndCollapse {
641    fn name(&self) -> &'static str {
642        "FuseAndCollapse"
643    }
644
645    #[mz_ore::instrument(
646        target = "optimizer",
647        level = "debug",
648        fields(path.segment = "fuse_and_collapse")
649    )]
650    fn actually_perform_transform(
651        &self,
652        relation: &mut MirRelationExpr,
653        ctx: &mut TransformCtx,
654    ) -> Result<(), TransformError> {
655        for transform in self.transforms.iter() {
656            transform.transform(relation, ctx)?;
657        }
658        mz_repr::explain::trace_plan(&*relation);
659        Ok(())
660    }
661}
662
663/// Run the [`FuseAndCollapse`] transforms in a fixpoint.
664pub fn fuse_and_collapse_fixpoint() -> Fixpoint {
665    Fixpoint {
666        name: "fuse_and_collapse_fixpoint",
667        limit: 100,
668        transforms: FuseAndCollapse::default().transforms,
669    }
670}
671
672/// Does constant folding to a fixpoint: An expression all of whose leaves are constants, of size
673/// small enough to be inlined and folded should reach a single `MirRelationExpr::Constant`.
674///
675/// This needs to call `FoldConstants` together with `NormalizeLets` in a fixpoint loop, because
676/// currently `FoldConstants` doesn't inline CTEs, so these two need to alternate until fixpoint.
677///
678/// Also note that `FoldConstants` can break the normalized form by removing all references to a
679/// Let.
680///
681/// We also call `ReduceScalars`, because that does constant folding inside scalar expressions.
682pub fn fold_constants_fixpoint() -> Fixpoint {
683    Fixpoint {
684        name: "fold_constants_fixpoint",
685        limit: 100,
686        transforms: vec![
687            Box::new(FoldConstants {
688                limit: Some(FOLD_CONSTANTS_LIMIT),
689            }),
690            Box::new(canonicalization::ReduceScalars),
691            Box::new(NormalizeLets::new(false)),
692        ],
693    }
694}
695
696/// Construct a normalizing transform that runs transforms that normalize the
697/// structure of the tree until a fixpoint.
698///
699/// Care needs to be taken to ensure that the fixpoint converges for every
700/// possible input tree. If this is not the case, there are two possibilities:
701/// 1. The rewrite loop runs enters an oscillating cycle.
702/// 2. The expression grows without bound.
703pub fn normalize() -> Fixpoint {
704    Fixpoint {
705        name: "normalize",
706        limit: 100,
707        transforms: vec![Box::new(NormalizeLets::new(false)), Box::new(NormalizeOps)],
708    }
709}
710
711/// A naive optimizer for relation expressions.
712///
713/// The optimizer currently applies only peep-hole optimizations, from a limited
714/// set that were sufficient to get some of TPC-H up and working. It is worth a
715/// review at some point to improve the quality, coverage, and architecture of
716/// the optimizations.
717#[derive(Debug)]
718pub struct Optimizer {
719    /// A logical name identifying this optimizer instance.
720    pub name: &'static str,
721    /// The list of transforms to apply to an input relation.
722    pub transforms: Vec<Box<dyn Transform>>,
723}
724
725impl Optimizer {
726    /// Builds a logical optimizer that only performs logical transformations.
727    #[deprecated = "Create an Optimize instance and call `optimize` instead."]
728    pub fn logical_optimizer(ctx: &mut TransformCtx) -> Self {
729        let transforms: Vec<Box<dyn Transform>> = vec![
730            Box::new(Typecheck::new(ctx.typecheck()).strict_join_equivalences()),
731            // 1. Structure-agnostic cleanup
732            Box::new(normalize()),
733            Box::new(NonNullRequirements::default()),
734            // 2. Collapse constants, joins, unions, and lets as much as possible.
735            // TODO: lift filters/maps to maximize ability to collapse
736            // things down?
737            Box::new(fuse_and_collapse_fixpoint()),
738            // 3. Needs to happen before LiteralLifting, EquivalencePropagation
739            // make (literal) filters look more complicated than what the NonNegative Analysis can
740            // recognize.
741            Box::new(ThresholdElision),
742            // 4. Move predicate information up and down the tree.
743            //    This also fixes the shape of joins in the plan.
744            Box::new(Fixpoint {
745                name: "fixpoint_logical_01",
746                limit: 100,
747                transforms: vec![
748                    // Predicate pushdown sets the equivalence classes of joins.
749                    Box::new(PredicatePushdown::default()),
750                    Box::new(EquivalencePropagation::default()),
751                    // Lifts the information `col1 = col2`
752                    Box::new(Demand::default()),
753                    Box::new(FuseAndCollapse::default()),
754                ],
755            }),
756            // 5. Reduce/Join simplifications.
757            Box::new(Fixpoint {
758                name: "fixpoint_logical_02",
759                limit: 100,
760                transforms: vec![
761                    Box::new(SemijoinIdempotence::default()),
762                    // Pushes aggregations down
763                    Box::new(ReductionPushdown),
764                    // Replaces reduces with maps when the group keys are
765                    // unique with maps
766                    Box::new(ReduceElision),
767                    // Rips complex reduces apart.
768                    Box::new(ReduceReduction),
769                    // Converts `Cross Join {Constant(Literal) + Input}` to
770                    // `Map {Cross Join (Input, Constant()), Literal}`.
771                    // Join fusion will clean this up to `Map{Input, Literal}`
772                    Box::new(LiteralLifting::default()),
773                    // Identifies common relation subexpressions.
774                    Box::new(cse::relation_cse::RelationCSE::new(false)),
775                    Box::new(FuseAndCollapse::default()),
776                ],
777            }),
778            Box::new(
779                Typecheck::new(ctx.typecheck())
780                    .disallow_new_globals()
781                    .strict_join_equivalences(),
782            ),
783        ];
784        Self {
785            name: "logical",
786            transforms,
787        }
788    }
789
790    /// Builds a physical optimizer.
791    ///
792    /// Performs logical transformations followed by all physical ones.
793    /// This is meant to be used for optimizing each view within a dataflow
794    /// once view inlining has already happened, right before dataflow
795    /// rendering.
796    pub fn physical_optimizer(ctx: &mut TransformCtx) -> Self {
797        // Implementation transformations
798        let transforms: Vec<Box<dyn Transform>> = transforms![
799            Box::new(
800                Typecheck::new(ctx.typecheck())
801                    .disallow_new_globals()
802                    .strict_join_equivalences(),
803            ),
804            // Considerations for the relationship between JoinImplementation and other transforms:
805            // - there should be a run of LiteralConstraints before JoinImplementation lifts away
806            //   the Filters from the Gets;
807            // - there should be no RelationCSE between this LiteralConstraints and
808            //   JoinImplementation, because that could move an IndexedFilter behind a Get.
809            // - The last RelationCSE before JoinImplementation should be with inline_mfp = true.
810            // - Currently, JoinImplementation can't be before LiteralLifting because the latter
811            //   sometimes creates `Unimplemented` joins (despite LiteralLifting already having been
812            //   run in the logical optimizer).
813            // - Not running EquivalencePropagation in the same fixpoint loop with JoinImplementation
814            //   is slightly hurting our plans. However, I'd say we should fix these problems by
815            //   making EquivalencePropagation (and/or JoinImplementation) smarter (database-issues#5289), rather than
816            //   having them in the same fixpoint loop. If they would be in the same fixpoint loop,
817            //   then we either run the risk of EquivalencePropagation invalidating a join plan (database-issues#5260),
818            //   or we would have to run JoinImplementation an unbounded number of times, which is
819            //   also not good database-issues#4639.
820            //   (The same is true for FoldConstants, Demand, and LiteralLifting to a lesser
821            //   extent.)
822            //
823            // Also note that FoldConstants and LiteralLifting are not confluent. They can
824            // oscillate between e.g.:
825            //         Constant
826            //           - (4)
827            // and
828            //         Map (4)
829            //           Constant
830            //             - ()
831            Box::new(Fixpoint {
832                name: "fixpoint_physical_01",
833                limit: 100,
834                transforms: vec![
835                    Box::new(EquivalencePropagation::default()),
836                    Box::new(fold_constants_fixpoint()),
837                    Box::new(Demand::default()),
838                    // Demand might have introduced dummies, so let's also do a ProjectionPushdown.
839                    Box::new(ProjectionPushdown::default()),
840                    Box::new(LiteralLifting::default()),
841                ],
842            }),
843            Box::new(LiteralConstraints),
844            Box::new(Fixpoint {
845                name: "fixpoint_join_impl",
846                limit: 100,
847                transforms: vec![Box::new(JoinImplementation::default())],
848            }),
849            Box::new(CanonicalizeMfp),
850            // Identifies common relation subexpressions.
851            Box::new(cse::relation_cse::RelationCSE::new(false)),
852            // `RelationCSE` can create new points of interest for `ProjectionPushdown`: If an MFP
853            // is cut in half by `RelationCSE`, then we'd like to push projections behind the new
854            // Get as much as possible. This is because a fork in the plan involves copying the
855            // data. (But we need `ProjectionPushdown` to skip joins, because it can't deal with
856            // filled in JoinImplementations.)
857            Box::new(ProjectionPushdown::skip_joins()); if ctx.features.enable_projection_pushdown_after_relation_cse,
858            // Plans look nicer if we tidy MFPs again after ProjectionPushdown.
859            Box::new(CanonicalizeMfp); if ctx.features.enable_projection_pushdown_after_relation_cse,
860            // Do a last run of constant folding. Importantly, this also runs `NormalizeLets`!
861            // We need `NormalizeLets` at the end of the MIR pipeline for various reasons:
862            // - The rendering expects some invariants about Let/LetRecs.
863            // - `CollectIndexRequests` needs a normalized plan.
864            //   https://github.com/MaterializeInc/database-issues/issues/6371
865            Box::new(fold_constants_fixpoint()),
866            Box::new(
867                Typecheck::new(ctx.typecheck())
868                    .disallow_new_globals()
869                    .disallow_dummy(),
870            ),
871        ];
872        Self {
873            name: "physical",
874            transforms,
875        }
876    }
877
878    /// Contains the logical optimizations that should run after cross-view
879    /// transformations run.
880    ///
881    /// Set `allow_new_globals` when you will use these as the first passes.
882    /// The first instance of the typechecker in an optimizer pipeline should
883    /// allow new globals (or it will crash when it encounters them).
884    pub fn logical_cleanup_pass(ctx: &mut TransformCtx, allow_new_globals: bool) -> Self {
885        let mut typechecker = Typecheck::new(ctx.typecheck()).strict_join_equivalences();
886
887        if !allow_new_globals {
888            typechecker = typechecker.disallow_new_globals();
889        }
890
891        let transforms: Vec<Box<dyn Transform>> = vec![
892            Box::new(typechecker),
893            // Delete unnecessary maps.
894            Box::new(fusion::Fusion),
895            Box::new(Fixpoint {
896                name: "fixpoint_logical_cleanup_pass_01",
897                limit: 100,
898                transforms: vec![
899                    Box::new(CanonicalizeMfp),
900                    // Remove threshold operators which have no effect.
901                    Box::new(ThresholdElision),
902                    // Projection pushdown may unblock fusing joins and unions.
903                    Box::new(fusion::join::Join),
904                    // Predicate pushdown required to tidy after join fusion.
905                    Box::new(PredicatePushdown::default()),
906                    Box::new(RedundantJoin::default()),
907                    // Redundant join produces projects that need to be fused.
908                    Box::new(fusion::Fusion),
909                    Box::new(compound::UnionNegateFusion),
910                    // This goes after union fusion so we can cancel out
911                    // more branches at a time.
912                    Box::new(UnionBranchCancellation),
913                    // The last RelationCSE before JoinImplementation should be with
914                    // inline_mfp = true.
915                    Box::new(cse::relation_cse::RelationCSE::new(true)),
916                    Box::new(fold_constants_fixpoint()),
917                ],
918            }),
919            Box::new(
920                Typecheck::new(ctx.typecheck())
921                    .disallow_new_globals()
922                    .strict_join_equivalences(),
923            ),
924        ];
925        Self {
926            name: "logical_cleanup",
927            transforms,
928        }
929    }
930
931    /// Builds a tiny optimizer, which is only suitable for optimizing fast-path queries.
932    pub fn fast_path_optimizer(_ctx: &mut TransformCtx) -> Self {
933        let transforms: Vec<Box<dyn Transform>> = vec![
934            Box::new(canonicalization::ReduceScalars),
935            Box::new(LiteralConstraints),
936            Box::new(CanonicalizeMfp),
937            // We might have arrived at a constant, e.g., due to contradicting literal constraints.
938            Box::new(Fixpoint {
939                name: "fast_path_fold_constants_fixpoint",
940                limit: 100,
941                transforms: vec![
942                    Box::new(FoldConstants {
943                        limit: Some(FOLD_CONSTANTS_LIMIT),
944                    }),
945                    Box::new(canonicalization::ReduceScalars),
946                ],
947            }),
948        ];
949        Self {
950            name: "fast_path_optimizer",
951            transforms,
952        }
953    }
954
955    /// Builds a tiny optimizer, which just folds constants. For more details, see
956    /// [fold_constants_fixpoint].
957    pub fn constant_optimizer(_ctx: &mut TransformCtx) -> Self {
958        Self {
959            name: "fast_path_optimizer",
960            transforms: vec![Box::new(fold_constants_fixpoint())],
961        }
962    }
963
964    /// Optimizes the supplied relation expression.
965    ///
966    /// These optimizations are performed with no information about available arrangements,
967    /// which makes them suitable for pre-optimization before dataflow deployment.
968    #[mz_ore::instrument(
969        target = "optimizer",
970        level = "debug",
971        fields(path.segment = self.name)
972    )]
973    pub fn optimize(
974        &self,
975        mut relation: MirRelationExpr,
976        ctx: &mut TransformCtx,
977    ) -> Result<mz_expr::OptimizedMirRelationExpr, TransformError> {
978        let transform_result = self.transform(&mut relation, ctx);
979
980        // Make sure we are not swallowing any notice.
981        // TODO: we should actually wire up notices that come from here. This is not urgent, because
982        // currently notices can only come from the physical MIR optimizer (specifically,
983        // `LiteralConstraints`), and callers of this method are running the logical MIR optimizer.
984        soft_assert_or_log!(
985            ctx.df_meta.optimizer_notices.is_empty(),
986            "logical MIR optimization unexpectedly produced notices"
987        );
988
989        match transform_result {
990            Ok(_) => {
991                mz_repr::explain::trace_plan(&relation);
992                Ok(mz_expr::OptimizedMirRelationExpr(relation))
993            }
994            Err(e) => {
995                // Without this, the dropping of `relation` (which happens automatically when
996                // returning from this function) might run into a stack overflow, see
997                // https://github.com/MaterializeInc/database-issues/issues/4043
998                relation.destroy_carefully();
999                error!("Optimizer::optimize(): {}", e);
1000                Err(e)
1001            }
1002        }
1003    }
1004
1005    /// Optimizes the supplied relation expression in place, using available arrangements.
1006    ///
1007    /// This method should only be called with non-empty `indexes` when optimizing a dataflow,
1008    /// as the optimizations may lock in the use of arrangements that may cease to exist.
1009    fn transform(
1010        &self,
1011        relation: &mut MirRelationExpr,
1012        args: &mut TransformCtx,
1013    ) -> Result<(), TransformError> {
1014        args.update_last_hash(relation);
1015
1016        for transform in self.transforms.iter() {
1017            transform.transform(relation, args)?;
1018        }
1019
1020        Ok(())
1021    }
1022}