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}