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(true)),
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/// If `limit` is false, it does constant folding even on large constants.
676///
677/// This needs to call `FoldConstants` together with `NormalizeLets` in a fixpoint loop, because
678/// currently `FoldConstants` doesn't inline CTEs, so these two need to alternate until fixpoint.
679///
680/// Also note that `FoldConstants` can break the normalized form by removing all references to a
681/// Let.
682///
683/// We also call `ReduceScalars`, because that does constant folding inside scalar expressions.
684pub fn fold_constants_fixpoint(limit: bool) -> Fixpoint {
685 Fixpoint {
686 name: "fold_constants_fixpoint",
687 limit: 100,
688 transforms: vec![
689 Box::new(FoldConstants {
690 limit: if limit {
691 Some(FOLD_CONSTANTS_LIMIT)
692 } else {
693 None
694 },
695 }),
696 Box::new(canonicalization::ReduceScalars),
697 Box::new(NormalizeLets::new(false)),
698 ],
699 }
700}
701
702/// Construct a normalizing transform that runs transforms that normalize the
703/// structure of the tree until a fixpoint.
704///
705/// Care needs to be taken to ensure that the fixpoint converges for every
706/// possible input tree. If this is not the case, there are two possibilities:
707/// 1. The rewrite loop runs enters an oscillating cycle.
708/// 2. The expression grows without bound.
709pub fn normalize() -> Fixpoint {
710 Fixpoint {
711 name: "normalize",
712 limit: 100,
713 transforms: vec![Box::new(NormalizeLets::new(false)), Box::new(NormalizeOps)],
714 }
715}
716
717/// A naive optimizer for relation expressions.
718///
719/// The optimizer currently applies only peep-hole optimizations, from a limited
720/// set that were sufficient to get some of TPC-H up and working. It is worth a
721/// review at some point to improve the quality, coverage, and architecture of
722/// the optimizations.
723#[derive(Debug)]
724pub struct Optimizer {
725 /// A logical name identifying this optimizer instance.
726 pub name: &'static str,
727 /// The list of transforms to apply to an input relation.
728 pub transforms: Vec<Box<dyn Transform>>,
729}
730
731impl Optimizer {
732 /// Builds a logical optimizer that only performs logical transformations.
733 #[deprecated = "Create an Optimize instance and call `optimize` instead."]
734 pub fn logical_optimizer(ctx: &mut TransformCtx) -> Self {
735 let transforms: Vec<Box<dyn Transform>> = vec![
736 Box::new(Typecheck::new(ctx.typecheck()).strict_join_equivalences()),
737 // 1. Structure-agnostic cleanup
738 Box::new(normalize()),
739 Box::new(NonNullRequirements::default()),
740 // 2. Collapse constants, joins, unions, and lets as much as possible.
741 // TODO: lift filters/maps to maximize ability to collapse
742 // things down?
743 Box::new(fuse_and_collapse_fixpoint()),
744 // 3. Needs to happen before LiteralLifting, EquivalencePropagation
745 // make (literal) filters look more complicated than what the NonNegative Analysis can
746 // recognize.
747 Box::new(ThresholdElision),
748 // 4. Move predicate information up and down the tree.
749 // This also fixes the shape of joins in the plan.
750 Box::new(Fixpoint {
751 name: "fixpoint_logical_01",
752 limit: 100,
753 transforms: vec![
754 // Predicate pushdown sets the equivalence classes of joins.
755 Box::new(PredicatePushdown::default()),
756 Box::new(EquivalencePropagation::default()),
757 // Lifts the information `col1 = col2`
758 Box::new(Demand::default()),
759 Box::new(FuseAndCollapse::default()),
760 ],
761 }),
762 // 5. Reduce/Join simplifications.
763 Box::new(Fixpoint {
764 name: "fixpoint_logical_02",
765 limit: 100,
766 transforms: vec![
767 Box::new(SemijoinIdempotence::default()),
768 // Pushes aggregations down
769 Box::new(ReductionPushdown),
770 // Replaces reduces with maps when the group keys are
771 // unique with maps
772 Box::new(ReduceElision),
773 // Rips complex reduces apart.
774 Box::new(ReduceReduction),
775 // Converts `Cross Join {Constant(Literal) + Input}` to
776 // `Map {Cross Join (Input, Constant()), Literal}`.
777 // Join fusion will clean this up to `Map{Input, Literal}`
778 Box::new(LiteralLifting::default()),
779 // Identifies common relation subexpressions.
780 Box::new(cse::relation_cse::RelationCSE::new(false)),
781 Box::new(FuseAndCollapse::default()),
782 ],
783 }),
784 Box::new(
785 Typecheck::new(ctx.typecheck())
786 .disallow_new_globals()
787 .strict_join_equivalences(),
788 ),
789 ];
790 Self {
791 name: "logical",
792 transforms,
793 }
794 }
795
796 /// Builds a physical optimizer.
797 ///
798 /// Performs logical transformations followed by all physical ones.
799 /// This is meant to be used for optimizing each view within a dataflow
800 /// once view inlining has already happened, right before dataflow
801 /// rendering.
802 pub fn physical_optimizer(ctx: &mut TransformCtx) -> Self {
803 // Implementation transformations
804 let transforms: Vec<Box<dyn Transform>> = transforms![
805 Box::new(
806 Typecheck::new(ctx.typecheck())
807 .disallow_new_globals()
808 .strict_join_equivalences(),
809 ),
810 // Considerations for the relationship between JoinImplementation and other transforms:
811 // - there should be a run of LiteralConstraints before JoinImplementation lifts away
812 // the Filters from the Gets;
813 // - there should be no RelationCSE between this LiteralConstraints and
814 // JoinImplementation, because that could move an IndexedFilter behind a Get.
815 // - The last RelationCSE before JoinImplementation should be with inline_mfp = true.
816 // - Currently, JoinImplementation can't be before LiteralLifting because the latter
817 // sometimes creates `Unimplemented` joins (despite LiteralLifting already having been
818 // run in the logical optimizer).
819 // - Not running EquivalencePropagation in the same fixpoint loop with JoinImplementation
820 // is slightly hurting our plans. However, I'd say we should fix these problems by
821 // making EquivalencePropagation (and/or JoinImplementation) smarter (database-issues#5289), rather than
822 // having them in the same fixpoint loop. If they would be in the same fixpoint loop,
823 // then we either run the risk of EquivalencePropagation invalidating a join plan (database-issues#5260),
824 // or we would have to run JoinImplementation an unbounded number of times, which is
825 // also not good database-issues#4639.
826 // (The same is true for FoldConstants, Demand, and LiteralLifting to a lesser
827 // extent.)
828 //
829 // Also note that FoldConstants and LiteralLifting are not confluent. They can
830 // oscillate between e.g.:
831 // Constant
832 // - (4)
833 // and
834 // Map (4)
835 // Constant
836 // - ()
837 Box::new(Fixpoint {
838 name: "fixpoint_physical_01",
839 limit: 100,
840 transforms: vec![
841 Box::new(EquivalencePropagation::default()),
842 Box::new(fold_constants_fixpoint(true)),
843 Box::new(Demand::default()),
844 // Demand might have introduced dummies, so let's also do a ProjectionPushdown.
845 Box::new(ProjectionPushdown::default()),
846 Box::new(LiteralLifting::default()),
847 ],
848 }),
849 Box::new(LiteralConstraints),
850 Box::new(Fixpoint {
851 name: "fixpoint_join_impl",
852 limit: 100,
853 transforms: vec![Box::new(JoinImplementation::default())],
854 }),
855 Box::new(CanonicalizeMfp),
856 // Identifies common relation subexpressions.
857 Box::new(cse::relation_cse::RelationCSE::new(false)),
858 // `RelationCSE` can create new points of interest for `ProjectionPushdown`: If an MFP
859 // is cut in half by `RelationCSE`, then we'd like to push projections behind the new
860 // Get as much as possible. This is because a fork in the plan involves copying the
861 // data. (But we need `ProjectionPushdown` to skip joins, because it can't deal with
862 // filled in JoinImplementations.)
863 Box::new(ProjectionPushdown::skip_joins()); if ctx.features.enable_projection_pushdown_after_relation_cse,
864 // Plans look nicer if we tidy MFPs again after ProjectionPushdown.
865 Box::new(CanonicalizeMfp); if ctx.features.enable_projection_pushdown_after_relation_cse,
866 // Do a last run of constant folding. Importantly, this also runs `NormalizeLets`!
867 // We need `NormalizeLets` at the end of the MIR pipeline for various reasons:
868 // - The rendering expects some invariants about Let/LetRecs.
869 // - `CollectIndexRequests` needs a normalized plan.
870 // https://github.com/MaterializeInc/database-issues/issues/6371
871 Box::new(fold_constants_fixpoint(true)),
872 Box::new(
873 Typecheck::new(ctx.typecheck())
874 .disallow_new_globals()
875 .disallow_dummy(),
876 ),
877 ];
878 Self {
879 name: "physical",
880 transforms,
881 }
882 }
883
884 /// Contains the logical optimizations that should run after cross-view
885 /// transformations run.
886 ///
887 /// Set `allow_new_globals` when you will use these as the first passes.
888 /// The first instance of the typechecker in an optimizer pipeline should
889 /// allow new globals (or it will crash when it encounters them).
890 pub fn logical_cleanup_pass(ctx: &mut TransformCtx, allow_new_globals: bool) -> Self {
891 let mut typechecker = Typecheck::new(ctx.typecheck()).strict_join_equivalences();
892
893 if !allow_new_globals {
894 typechecker = typechecker.disallow_new_globals();
895 }
896
897 let transforms: Vec<Box<dyn Transform>> = vec![
898 Box::new(typechecker),
899 // Delete unnecessary maps.
900 Box::new(fusion::Fusion),
901 Box::new(Fixpoint {
902 name: "fixpoint_logical_cleanup_pass_01",
903 limit: 100,
904 transforms: vec![
905 Box::new(CanonicalizeMfp),
906 // Remove threshold operators which have no effect.
907 Box::new(ThresholdElision),
908 // Projection pushdown may unblock fusing joins and unions.
909 Box::new(fusion::join::Join),
910 // Predicate pushdown required to tidy after join fusion.
911 Box::new(PredicatePushdown::default()),
912 Box::new(RedundantJoin::default()),
913 // Redundant join produces projects that need to be fused.
914 Box::new(fusion::Fusion),
915 Box::new(compound::UnionNegateFusion),
916 // This goes after union fusion so we can cancel out
917 // more branches at a time.
918 Box::new(UnionBranchCancellation),
919 // The last RelationCSE before JoinImplementation should be with
920 // inline_mfp = true.
921 Box::new(cse::relation_cse::RelationCSE::new(true)),
922 Box::new(fold_constants_fixpoint(true)),
923 ],
924 }),
925 Box::new(
926 Typecheck::new(ctx.typecheck())
927 .disallow_new_globals()
928 .strict_join_equivalences(),
929 ),
930 ];
931 Self {
932 name: "logical_cleanup",
933 transforms,
934 }
935 }
936
937 /// Builds a tiny optimizer, which is only suitable for optimizing fast-path queries.
938 pub fn fast_path_optimizer(_ctx: &mut TransformCtx) -> Self {
939 let transforms: Vec<Box<dyn Transform>> = vec![
940 Box::new(canonicalization::ReduceScalars),
941 Box::new(LiteralConstraints),
942 Box::new(CanonicalizeMfp),
943 // We might have arrived at a constant, e.g., due to contradicting literal constraints.
944 Box::new(Fixpoint {
945 name: "fast_path_fold_constants_fixpoint",
946 limit: 100,
947 transforms: vec![
948 Box::new(FoldConstants {
949 limit: Some(FOLD_CONSTANTS_LIMIT),
950 }),
951 Box::new(canonicalization::ReduceScalars),
952 ],
953 }),
954 ];
955 Self {
956 name: "fast_path_optimizer",
957 transforms,
958 }
959 }
960
961 /// Builds a tiny optimizer, which just folds constants. For more details, see
962 /// [fold_constants_fixpoint].
963 pub fn constant_optimizer(_ctx: &mut TransformCtx, limit: bool) -> Self {
964 Self {
965 name: "fast_path_optimizer",
966 transforms: vec![Box::new(fold_constants_fixpoint(limit))],
967 }
968 }
969
970 /// Optimizes the supplied relation expression.
971 ///
972 /// These optimizations are performed with no information about available arrangements,
973 /// which makes them suitable for pre-optimization before dataflow deployment.
974 #[mz_ore::instrument(
975 target = "optimizer",
976 level = "debug",
977 fields(path.segment = self.name)
978 )]
979 pub fn optimize(
980 &self,
981 mut relation: MirRelationExpr,
982 ctx: &mut TransformCtx,
983 ) -> Result<mz_expr::OptimizedMirRelationExpr, TransformError> {
984 let transform_result = self.transform(&mut relation, ctx);
985
986 // Make sure we are not swallowing any notice.
987 // TODO: we should actually wire up notices that come from here. This is not urgent, because
988 // currently notices can only come from the physical MIR optimizer (specifically,
989 // `LiteralConstraints`), and callers of this method are running the logical MIR optimizer.
990 soft_assert_or_log!(
991 ctx.df_meta.optimizer_notices.is_empty(),
992 "logical MIR optimization unexpectedly produced notices"
993 );
994
995 match transform_result {
996 Ok(_) => {
997 mz_repr::explain::trace_plan(&relation);
998 Ok(mz_expr::OptimizedMirRelationExpr(relation))
999 }
1000 Err(e) => {
1001 // Without this, the dropping of `relation` (which happens automatically when
1002 // returning from this function) might run into a stack overflow, see
1003 // https://github.com/MaterializeInc/database-issues/issues/4043
1004 relation.destroy_carefully();
1005 error!("Optimizer::optimize(): {}", e);
1006 Err(e)
1007 }
1008 }
1009 }
1010
1011 /// Optimizes the supplied relation expression in place, using available arrangements.
1012 ///
1013 /// This method should only be called with non-empty `indexes` when optimizing a dataflow,
1014 /// as the optimizations may lock in the use of arrangements that may cease to exist.
1015 fn transform(
1016 &self,
1017 relation: &mut MirRelationExpr,
1018 args: &mut TransformCtx,
1019 ) -> Result<(), TransformError> {
1020 args.update_last_hash(relation);
1021
1022 for transform in self.transforms.iter() {
1023 transform.transform(relation, args)?;
1024 }
1025
1026 Ok(())
1027 }
1028}