mz_transform/equivalence_propagation.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//! Propagates expression equivalence from leaves to root, and back down again.
11//!
12//! Expression equivalences are `MirScalarExpr` replacements by simpler expressions.
13//! These equivalences derive from
14//! Filters: predicates must evaluate to `Datum::True`.
15//! Maps: new columns equal the expressions that define them.
16//! Joins: equated columns must be equal.
17//! Others: lots of other predicates we might learn (range constraints on aggregates; non-negativity)
18//!
19//! From leaf to root the equivalences are *enforced*, and communicate that the expression will not produce rows that do not satisfy the equivalence.
20//! From root to leaf the equivalences are *advised*, and communicate that the expression may discard any outputs that do not satisfy the equivalence.
21//!
22//! Importantly, in descent the operator *may not* assume any equivalence filtering will be applied to its results.
23//! It cannot therefore produce rows it would otherwise not, even rows that do not satisfy the equivalence.
24//! Operators *may* introduce filtering in descent, and they must do so to take further advantage of the equivalences.
25//!
26//! The subtlety is due to the expressions themselves causing the equivalences, and allowing more rows may invalidate equivalences.
27//! For example, we might learn that `Column(7)` equals `Literal(3)`, but must refrain from introducing that substitution in descent,
28//! because it is possible that the equivalence derives from restrictions in the expression we are visiting. Were we certain that the
29//! equivalence was independent of the expression (e.g. through a more nuanced expression traversal) we could imaging relaxing this.
30
31use std::collections::BTreeMap;
32
33use itertools::Itertools;
34use mz_expr::{Id, MirRelationExpr, MirScalarExpr};
35use mz_repr::Datum;
36use tracing::debug;
37
38use crate::analysis::equivalences::{
39 EqClassesImpl, EquivalenceClasses, EquivalenceClassesWithholdingErrors, Equivalences,
40 ExpressionReducer,
41};
42use crate::analysis::{Arity, DerivedView, SqlRelationType};
43
44use crate::{TransformCtx, TransformError};
45
46/// Pulls up and pushes down predicate information represented as equivalences
47#[derive(Debug, Default)]
48pub struct EquivalencePropagation;
49
50impl crate::Transform for EquivalencePropagation {
51 fn name(&self) -> &'static str {
52 "EquivalencePropagation"
53 }
54
55 #[mz_ore::instrument(
56 target = "optimizer"
57 level = "trace",
58 fields(path.segment = "equivalence_propagation")
59 )]
60 fn actually_perform_transform(
61 &self,
62 relation: &mut MirRelationExpr,
63 ctx: &mut TransformCtx,
64 ) -> Result<(), TransformError> {
65 // Perform bottom-up equivalence class analysis.
66 use crate::analysis::DerivedBuilder;
67 let mut builder = DerivedBuilder::new(ctx.features);
68 builder.require(Equivalences);
69 let derived = builder.visit(relation);
70 let derived = derived.as_view();
71
72 let prior = relation.clone();
73
74 let mut get_equivalences = BTreeMap::default();
75 self.apply(
76 relation,
77 derived,
78 EquivalenceClasses::default(),
79 &mut get_equivalences,
80 ctx,
81 );
82
83 // Trace the plan as the result of `equivalence_propagation` before potentially applying
84 // `ColumnKnowledge`. (If `ColumnKnowledge` runs, it will trace its own result.)
85 mz_repr::explain::trace_plan(&*relation);
86
87 if prior == *relation {
88 let ck = crate::ColumnKnowledge::default();
89 ck.transform(relation, ctx)?;
90 if prior != *relation {
91 // This used to be tracing::error, but it became too common with
92 // dequadratic_eqprop_map.
93 tracing::warn!(
94 ?ctx.global_id,
95 "ColumnKnowledge performed work after EquivalencePropagation",
96 );
97 }
98 }
99
100 Ok(())
101 }
102}
103
104impl EquivalencePropagation {
105 /// Provides the opportunity to mutate `relation` in response to equivalences enforced by others.
106 ///
107 /// Provides the opportunity to mutate `relation` in response to equivalences enforced by their children,
108 /// as presented in `derived`, and equivalences enforced of their output (by their ancestors), as presented
109 /// in `outer_equivalences` and `get_equivalences`.
110 ///
111 /// The mutations should never invalidate an equivalence the operator has been reported as providing, as that
112 /// information may have already been acted upon by others.
113 ///
114 /// The `expr_index` argument must equal `expr`s position in post-order, so that it can be used as a reference
115 /// into `derived`. The argument can be used with the `SubtreeSize` analysis to determine the range of values
116 /// associated with `expr`.
117 ///
118 /// After the call, `get_equivalences` will be populated with certainly equivalences that will be certainly
119 /// enforced for all uses of each identifier. The information can be harvested and propagated to the definitions
120 /// of those identifiers.
121 pub fn apply(
122 &self,
123 expr: &mut MirRelationExpr,
124 derived: DerivedView,
125 mut outer_equivalences: EquivalenceClasses,
126 get_equivalences: &mut BTreeMap<Id, EquivalenceClasses>,
127 ctx: &mut TransformCtx,
128 ) {
129 // TODO: The top-down traversal can be coded as a worklist, with arguments tupled and enqueued.
130 // This has the potential to do a lot more cloning (of `outer_equivalences`), and some care is needed
131 // for `get_equivalences` which would be scoped to the whole method rather than tupled and enqueued.
132
133 let expr_type = derived
134 .value::<SqlRelationType>()
135 .expect("SqlRelationType required");
136 assert!(expr_type.is_some());
137 let expr_equivalences = derived
138 .value::<Equivalences>()
139 .expect("Equivalences required");
140
141 // `None` analysis values indicate collections that can be pruned.
142 let expr_equivalences = if let Some(e) = expr_equivalences {
143 e
144 } else {
145 expr.take_safely_with_col_types(expr_type.clone().unwrap());
146 return;
147 };
148
149 // Optimize `outer_equivalences` in the context of `expr_type`.
150 // If it ends up unsatisfiable, we can replace `expr` with an empty constant of the same relation type.
151 let reducer = expr_equivalences.reducer();
152 for class in outer_equivalences.classes.iter_mut() {
153 for expr in class.iter_mut() {
154 reducer.reduce_expr(expr);
155 }
156 }
157
158 outer_equivalences.minimize(expr_type.as_ref().map(|x| &x[..]));
159 if outer_equivalences.unsatisfiable() {
160 expr.take_safely_with_col_types(expr_type.clone().unwrap());
161 return;
162 }
163
164 match expr {
165 MirRelationExpr::Constant { rows, typ: _ } => {
166 if let Ok(rows) = rows {
167 let mut datum_vec = mz_repr::DatumVec::new();
168 // Delete any rows that violate the equivalences.
169 // Do not delete rows that produce errors, as they are semantically important.
170 rows.retain(|(row, _count)| {
171 let temp_storage = mz_repr::RowArena::new();
172 let datums = datum_vec.borrow_with(row);
173 outer_equivalences.classes.iter().all(|class| {
174 // Any subset of `Ok` results must equate, or we can drop the row.
175 let mut oks = class
176 .iter()
177 .filter_map(|e| e.eval(&datums[..], &temp_storage).ok());
178 if let Some(e1) = oks.next() {
179 oks.all(|e2| e1 == e2)
180 } else {
181 true
182 }
183 })
184 });
185 }
186 }
187 MirRelationExpr::Get { id, .. } => {
188 // Install and intersect with other equivalences from other `Get` sites.
189 // These will be read out by the corresponding `Let` binding's `value`.
190 if let Some(equivs) = get_equivalences.get_mut(id) {
191 *equivs = equivs.union(&outer_equivalences);
192 } else {
193 get_equivalences.insert(*id, outer_equivalences);
194 }
195 }
196 MirRelationExpr::Let { id, .. } => {
197 let id = *id;
198 // Traverse `body` first to assemble equivalences to push to `value`.
199 // Descend without a key for `id`, treating the absence as the identity for union.
200 // `Get` nodes with identifier `id` will populate the equivalence classes with the intersection of their guarantees.
201 let mut children_rev = expr.children_mut().rev().zip_eq(derived.children_rev());
202
203 let body = children_rev.next().unwrap();
204 let value = children_rev.next().unwrap();
205
206 self.apply(
207 body.0,
208 body.1,
209 outer_equivalences.clone(),
210 get_equivalences,
211 ctx,
212 );
213
214 // We expect to find `id` in `get_equivalences`, as otherwise the binding is
215 // not referenced and can be removed.
216 if let Some(equivalences) = get_equivalences.get(&Id::Local(id)) {
217 self.apply(
218 value.0,
219 value.1,
220 equivalences.clone(),
221 get_equivalences,
222 ctx,
223 );
224 }
225 }
226 MirRelationExpr::LetRec { .. } => {
227 let mut child_iter = expr.children_mut().rev().zip_eq(derived.children_rev());
228 // Continue in `body` with the outer equivalences.
229 let (body, view) = child_iter.next().unwrap();
230 self.apply(body, view, outer_equivalences, get_equivalences, ctx);
231 // Continue recursively, but without the outer equivalences supplied to `body`.
232 for (child, view) in child_iter {
233 self.apply(
234 child,
235 view,
236 EquivalenceClasses::default(),
237 get_equivalences,
238 ctx,
239 );
240 }
241 }
242 MirRelationExpr::Project { input, outputs } => {
243 // Transform `outer_equivalences` to one relevant for `input`.
244 outer_equivalences.permute(outputs);
245 self.apply(
246 input,
247 derived.last_child(),
248 outer_equivalences,
249 get_equivalences,
250 ctx,
251 );
252 }
253 MirRelationExpr::Map { input, scalars } => {
254 // Optimize `scalars` with respect to input equivalences.
255 let input_equivalences = derived
256 .last_child()
257 .value::<Equivalences>()
258 .expect("Equivalences required");
259
260 if let Some(input_equivalences_orig) = input_equivalences {
261 // We clone `input_equivalences` only if we want to modify it, which is when
262 // `enable_dequadratic_eqprop_map` is off. Otherwise, we work with the original
263 // `input_equivalences`.
264 let mut input_equivalences_cloned = None;
265 if !ctx.features.enable_dequadratic_eqprop_map {
266 // We mutate them for variadic Maps if the feature flag is not set.
267 input_equivalences_cloned = Some(input_equivalences_orig.clone());
268 }
269 // Get all output types, to reveal a prefix to each scaler expr.
270 let input_types = derived
271 .value::<SqlRelationType>()
272 .expect("SqlRelationType required")
273 .as_ref()
274 .unwrap();
275 let input_arity = input_types.len() - scalars.len();
276 for (index, expr) in scalars.iter_mut().enumerate() {
277 let reducer = if !ctx.features.enable_dequadratic_eqprop_map {
278 input_equivalences_cloned
279 .as_ref()
280 .expect("always filled if feature flag is not set")
281 .reducer()
282 } else {
283 input_equivalences_orig.reducer()
284 };
285 let changed = reducer.reduce_expr(expr);
286 if changed || !ctx.features.enable_less_reduce_in_eqprop {
287 expr.reduce(&input_types[..(input_arity + index)]);
288 }
289 if !ctx.features.enable_dequadratic_eqprop_map {
290 // Unfortunately, we had to stop doing the following, because it
291 // was making the `Map` handling quadratic.
292 // TODO: Get back to this when we have e-graphs.
293 // https://github.com/MaterializeInc/database-issues/issues/9157
294 //
295 // Introduce the fact relating the mapped expression and corresponding
296 // column. This allows subsequent expressions to be optimized with this
297 // information.
298 input_equivalences_cloned
299 .as_mut()
300 .expect("always filled if feature flag is not set")
301 .classes
302 .push(vec![
303 expr.clone(),
304 MirScalarExpr::column(input_arity + index),
305 ]);
306 input_equivalences_cloned
307 .as_mut()
308 .expect("always filled if feature flag is not set")
309 .minimize(Some(input_types));
310 }
311 }
312 let input_arity = *derived
313 .last_child()
314 .value::<Arity>()
315 .expect("Arity required");
316 outer_equivalences.project(0..input_arity);
317 self.apply(
318 input,
319 derived.last_child(),
320 outer_equivalences,
321 get_equivalences,
322 ctx,
323 );
324 }
325 }
326 MirRelationExpr::FlatMap { input, exprs, .. } => {
327 // Transform `exprs` by guarantees from `input` *and* from `outer`???
328 let input_equivalences = derived
329 .last_child()
330 .value::<Equivalences>()
331 .expect("Equivalences required");
332
333 if let Some(input_equivalences) = input_equivalences {
334 let input_types = derived
335 .last_child()
336 .value::<SqlRelationType>()
337 .expect("SqlRelationType required");
338 let reducer = input_equivalences.reducer();
339 for expr in exprs.iter_mut() {
340 let changed = reducer.reduce_expr(expr);
341 if changed || !ctx.features.enable_less_reduce_in_eqprop {
342 expr.reduce(input_types.as_ref().unwrap());
343 }
344 }
345 let input_arity = *derived
346 .last_child()
347 .value::<Arity>()
348 .expect("Arity required");
349 outer_equivalences.project(0..input_arity);
350 self.apply(
351 input,
352 derived.last_child(),
353 outer_equivalences,
354 get_equivalences,
355 ctx,
356 );
357 }
358 }
359 MirRelationExpr::Filter { input, predicates } => {
360 // Transform `predicates` by guarantees from `input` *and* from `outer`???
361 // If we reduce based on `input` guarantees, we won't be able to push those
362 // constraints down into input, which may be fine but is worth considering.
363 let input_equivalences = derived
364 .last_child()
365 .value::<Equivalences>()
366 .expect("Equivalences required");
367 if let Some(input_equivalences) = input_equivalences {
368 let input_types = derived
369 .last_child()
370 .value::<SqlRelationType>()
371 .expect("SqlRelationType required");
372 let reducer = input_equivalences.reducer();
373 for expr in predicates.iter_mut() {
374 let changed = reducer.reduce_expr(expr);
375 if changed || !ctx.features.enable_less_reduce_in_eqprop {
376 expr.reduce(input_types.as_ref().unwrap());
377 }
378 }
379 // Incorporate `predicates` into `outer_equivalences`.
380 let mut class = predicates.clone();
381 class.push(MirScalarExpr::literal_ok(
382 Datum::True,
383 mz_repr::SqlScalarType::Bool,
384 ));
385 outer_equivalences.classes.push(class);
386 outer_equivalences.minimize(input_types.as_ref().map(|x| &x[..]));
387 self.apply(
388 input,
389 derived.last_child(),
390 outer_equivalences,
391 get_equivalences,
392 ctx,
393 );
394 }
395 }
396
397 MirRelationExpr::Join {
398 inputs,
399 equivalences,
400 ..
401 } => {
402 // Certain equivalences are ensured by each of the inputs.
403 // Other equivalences are imposed by parents of the expression.
404 // We must not weaken the properties provided by the expression to its parents,
405 // meaning we can optimize `equivalences` with respect to input guarantees,
406 // but not with respect to `outer_equivalences`.
407
408 // Each child can be presented with the integration of `join_equivalences`, `outer_equivalences`,
409 // and each input equivalence *other than* their own, projected onto the input's columns.
410
411 // Enumerate locations to find each child's analysis outputs.
412 let mut children: Vec<_> = derived.children_rev().collect::<Vec<_>>();
413 children.reverse();
414
415 // Assemble the appended input types, for use in expression minimization.
416 // Do not use `expr_types`, which may reflect nullability that does not hold for the inputs.
417 let mut input_types = Some(
418 children
419 .iter()
420 .flat_map(|c| {
421 c.value::<SqlRelationType>()
422 .expect("SqlRelationType required")
423 .as_ref()
424 .unwrap()
425 .iter()
426 .cloned()
427 })
428 .collect::<Vec<_>>(),
429 );
430
431 // For each child, assemble its equivalences using join-relative column numbers.
432 // Don't do anything with the children yet, as we'll want to revisit each with
433 // this information at hand.
434 let mut columns = 0;
435 let mut input_equivalences = Vec::with_capacity(children.len());
436 for child in children.iter() {
437 let child_arity = child.value::<Arity>().expect("Arity required");
438 let equivalences = child
439 .value::<Equivalences>()
440 .expect("Equivalences required")
441 .clone();
442
443 if let Some(mut equivalences) = equivalences {
444 let permutation = (columns..(columns + child_arity)).collect::<Vec<_>>();
445 equivalences.permute(&permutation);
446 equivalences.minimize(input_types.as_ref().map(|x| &x[..]));
447 input_equivalences.push(equivalences);
448 }
449 columns += child_arity;
450 }
451
452 // Form the equivalences we will use to replace `equivalences`.
453 let mut join_equivalences: EqClassesImpl =
454 if ctx.features.enable_eq_classes_withholding_errors {
455 EqClassesImpl::EquivalenceClassesWithholdingErrors(
456 EquivalenceClassesWithholdingErrors::default(),
457 )
458 } else {
459 EqClassesImpl::EquivalenceClasses(EquivalenceClasses::default())
460 };
461 join_equivalences.extend_equivalences(equivalences.clone());
462
463 // // Optionally, introduce `outer_equivalences` into `equivalences`.
464 // // This is not required, but it could be very helpful. To be seen.
465 // join_equivalences
466 // .classes
467 // .extend(outer_equivalences.classes.clone());
468
469 // Reduce join equivalences by the input equivalences.
470 for input_equivs in input_equivalences.iter() {
471 let reducer = input_equivs.reducer();
472 for class in join_equivalences
473 .equivalence_classes_mut()
474 .classes
475 .iter_mut()
476 {
477 for expr in class.iter_mut() {
478 // Semijoin elimination currently fails if you do more advanced simplification than
479 // literal substitution.
480 let old = expr.clone();
481 let changed = reducer.reduce_expr(expr);
482 let acceptable_sub = literal_domination(&old, expr);
483 if changed || !ctx.features.enable_less_reduce_in_eqprop {
484 expr.reduce(input_types.as_ref().unwrap());
485 }
486 if !acceptable_sub && !literal_domination(&old, expr)
487 || expr.contains_err()
488 {
489 expr.clone_from(&old);
490 }
491 }
492 }
493 }
494 // Remove nullability information, as it has already been incorporated from input equivalences,
495 // and if it was reduced out relative to input equivalences we don't want to re-introduce it.
496 if let Some(input_types) = input_types.as_mut() {
497 for col in input_types.iter_mut() {
498 col.nullable = true;
499 }
500 }
501 join_equivalences
502 .equivalence_classes_mut()
503 .minimize(input_types.as_ref().map(|x| &x[..]));
504
505 // Revisit each child, determining the information to present to it, and recurring.
506 let mut columns = 0;
507 for ((index, child), expr) in
508 children.into_iter().enumerate().zip_eq(inputs.iter_mut())
509 {
510 let child_arity = child.value::<Arity>().expect("Arity required");
511
512 let mut push_equivalences = join_equivalences.clone();
513 push_equivalences.extend_equivalences(outer_equivalences.classes.clone());
514
515 for (other, input_equivs) in input_equivalences.iter().enumerate() {
516 if index != other {
517 push_equivalences.extend_equivalences(input_equivs.classes.clone());
518 }
519 }
520 push_equivalences.project(columns..(columns + child_arity));
521 self.apply(
522 expr,
523 child,
524 push_equivalences.equivalence_classes().clone(),
525 get_equivalences,
526 ctx,
527 );
528
529 columns += child_arity;
530 }
531
532 let extracted_equivalences =
533 join_equivalences.extract_equivalences(input_types.as_ref().map(|x| &x[..]));
534
535 debug!(
536 ?inputs,
537 ?extracted_equivalences,
538 "Join equivalences extracted"
539 );
540 equivalences.clone_from(&extracted_equivalences);
541 }
542 MirRelationExpr::Reduce {
543 input,
544 group_key,
545 aggregates,
546 ..
547 } => {
548 // TODO: MIN, MAX, ANY, ALL aggregates pass through all certain properties of their columns.
549 // This may involve projection and permutation, to reposition the information appropriately.
550 // TODO: Non-null constraints likely push down into the support of the aggregate expressions.
551
552 // Apply any equivalences about the input to key and aggregate expressions.
553 let input_equivalences = derived
554 .last_child()
555 .value::<Equivalences>()
556 .expect("Equivalences required");
557 if let Some(input_equivalences) = input_equivalences {
558 let input_type = derived
559 .last_child()
560 .value::<SqlRelationType>()
561 .expect("SqlRelationType required");
562 let reducer = input_equivalences.reducer();
563 for key in group_key.iter_mut() {
564 // Semijoin elimination currently fails if you do more advanced simplification than
565 // literal substitution.
566 let old_key = key.clone();
567 let changed = reducer.reduce_expr(key);
568 let acceptable_sub = literal_domination(&old_key, key);
569 if changed || !ctx.features.enable_less_reduce_in_eqprop {
570 key.reduce(input_type.as_ref().unwrap());
571 }
572 if !acceptable_sub && !literal_domination(&old_key, key) {
573 key.clone_from(&old_key);
574 }
575 }
576 for aggr in aggregates.iter_mut() {
577 let changed = reducer.reduce_expr(&mut aggr.expr);
578 if changed || !ctx.features.enable_less_reduce_in_eqprop {
579 aggr.expr.reduce(input_type.as_ref().unwrap());
580 }
581 // A count expression over a non-null expression can discard the expression.
582 if aggr.func == mz_expr::AggregateFunc::Count && !aggr.distinct {
583 let mut probe = aggr.expr.clone().call_is_null();
584 reducer.reduce_expr(&mut probe);
585 if probe.is_literal_false() {
586 aggr.expr = MirScalarExpr::literal_true();
587 }
588 }
589 }
590 }
591
592 // To transform `outer_equivalences` to one about `input`, we will "pretend" to pre-pend all of
593 // the input columns, introduce equivalences about the evaluation of `group_key` on them
594 // and the key columns themselves, and then project onto these "input" columns.
595 let input_arity = *derived
596 .last_child()
597 .value::<Arity>()
598 .expect("Arity required");
599 let output_arity = *derived.value::<Arity>().expect("Arity required");
600
601 // Permute `outer_equivalences` to reference columns `input_arity` later.
602 let permutation = (input_arity..(input_arity + output_arity)).collect::<Vec<_>>();
603 outer_equivalences.permute(&permutation[..]);
604 for (index, group) in group_key.iter().enumerate() {
605 outer_equivalences.classes.push(vec![
606 MirScalarExpr::column(input_arity + index),
607 group.clone(),
608 ]);
609 }
610 outer_equivalences.project(0..input_arity);
611 self.apply(
612 input,
613 derived.last_child(),
614 outer_equivalences,
615 get_equivalences,
616 ctx,
617 );
618 }
619 MirRelationExpr::TopK {
620 input,
621 group_key,
622 limit,
623 ..
624 } => {
625 // We must be careful when updating `limit` to not install column references
626 // outside of `group_key`. We'll do this for now with `literal_domination`,
627 // which will ensure we only perform substitutions by a literal.
628 let input_equivalences = derived
629 .last_child()
630 .value::<Equivalences>()
631 .expect("Equivalences required");
632 if let Some(input_equivalences) = input_equivalences {
633 let input_types = derived
634 .last_child()
635 .value::<SqlRelationType>()
636 .expect("SqlRelationType required");
637 let reducer = input_equivalences.reducer();
638 if let Some(expr) = limit {
639 let old_expr = expr.clone();
640 let changed = reducer.reduce_expr(expr);
641 let acceptable_sub = literal_domination(&old_expr, expr);
642 if changed || !ctx.features.enable_less_reduce_in_eqprop {
643 expr.reduce(input_types.as_ref().unwrap());
644 }
645 if !acceptable_sub && !literal_domination(&old_expr, expr) {
646 expr.clone_from(&old_expr);
647 }
648 }
649 }
650
651 // Discard equivalences among non-key columns, as it is not correct that `input` may drop rows
652 // that violate constraints among non-key columns without affecting the result.
653 outer_equivalences.project(0..group_key.len());
654 self.apply(
655 input,
656 derived.last_child(),
657 outer_equivalences,
658 get_equivalences,
659 ctx,
660 );
661 }
662 MirRelationExpr::Negate { input } => {
663 self.apply(
664 input,
665 derived.last_child(),
666 outer_equivalences,
667 get_equivalences,
668 ctx,
669 );
670 }
671 MirRelationExpr::Threshold { input } => {
672 self.apply(
673 input,
674 derived.last_child(),
675 outer_equivalences,
676 get_equivalences,
677 ctx,
678 );
679 }
680 MirRelationExpr::Union { .. } => {
681 for (child, derived) in expr.children_mut().rev().zip_eq(derived.children_rev()) {
682 self.apply(
683 child,
684 derived,
685 outer_equivalences.clone(),
686 get_equivalences,
687 ctx,
688 );
689 }
690 }
691 MirRelationExpr::ArrangeBy { input, .. } => {
692 // TODO: Option to alter arrangement keys, though .. terrifying.
693 self.apply(
694 input,
695 derived.last_child(),
696 outer_equivalences,
697 get_equivalences,
698 ctx,
699 );
700 }
701 }
702 }
703}
704
705/// Logic encapsulating our willingness to accept an expression simplification.
706///
707/// For reasons of robustness, we cannot yet perform all recommended simplifications.
708/// Certain transforms expect idiomatic expressions, often around precise use of column
709/// identifiers, rather than equivalent identifiers.
710///
711/// The substitutions we are confident with are those that introduce literals for columns,
712/// or which replace column nullability checks with literals.
713fn literal_domination(old: &MirScalarExpr, new: &MirScalarExpr) -> bool {
714 let mut todo = vec![(old, new)];
715 while let Some((old, new)) = todo.pop() {
716 match (old, new) {
717 (_, MirScalarExpr::Literal(_, _)) => {
718 // Substituting a literal is always acceptable; we don't need to consult
719 // the result of the old expression to determine this.
720 }
721 (
722 MirScalarExpr::CallUnary { func: f0, expr: e0 },
723 MirScalarExpr::CallUnary { func: f1, expr: e1 },
724 ) => {
725 if f0 != f1 {
726 return false;
727 } else {
728 todo.push((&**e0, &**e1));
729 }
730 }
731 (
732 MirScalarExpr::CallBinary {
733 func: f0,
734 expr1: e01,
735 expr2: e02,
736 },
737 MirScalarExpr::CallBinary {
738 func: f1,
739 expr1: e11,
740 expr2: e12,
741 },
742 ) => {
743 if f0 != f1 {
744 return false;
745 } else {
746 todo.push((&**e01, &**e11));
747 todo.push((&**e02, &**e12));
748 }
749 }
750 (
751 MirScalarExpr::CallVariadic {
752 func: f0,
753 exprs: e0s,
754 },
755 MirScalarExpr::CallVariadic {
756 func: f1,
757 exprs: e1s,
758 },
759 ) => {
760 use itertools::Itertools;
761 if f0 != f1 || e0s.len() != e1s.len() {
762 return false;
763 } else {
764 todo.extend(e0s.iter().zip_eq(e1s));
765 }
766 }
767 (
768 MirScalarExpr::If {
769 cond: c0,
770 then: t0,
771 els: e0,
772 },
773 MirScalarExpr::If {
774 cond: c1,
775 then: t1,
776 els: e1,
777 },
778 ) => {
779 todo.push((&**c0, &**c1));
780 todo.push((&**t0, &**t1));
781 todo.push((&**e0, &**e1))
782 }
783 _ => {
784 if old != new {
785 return false;
786 }
787 }
788 }
789 }
790 true
791}