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}