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}