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