# Module mz_transform::equivalence_propagation

source · ## Expand description

Propagates expression equivalence from leaves to root, and back down again.

Expression equivalences are `MirScalarExpr`

replacements by simpler expressions.
These equivalences derive from
Filters: predicates must evaluate to `Datum::True`

.
Maps: new columns equal the expressions that define them.
Joins: equated columns must be equal.
Others: lots of other predicates we might learn (range constraints on aggregates; non-negativity)

From leaf to root the equivalences are *enforced*, and communicate that the expression will not produce rows that do not satisfy the equivalence.
From root to leaf the equivalences are *advised*, and communicate that the expression may discard any outputs that do not satisfy the equivalence.

Importantly, in descent the operator *may not* assume any equivalence filtering will be applied to its results.
It cannot therefore produce rows it would otherwise not, even rows that do not satisfy the equivalence.
Operators *may* introduce filtering in descent, and they must do so to take further advantage of the equivalences.

The subtlety is due to the expressions themselves causing the equivalences, and allowing more rows may invalidate equivalences.
For example, we might learn that `Column(7)`

equals `Literal(3)`

, but must refrain from introducing that substitution in descent,
because it is possible that the equivalence derives from restrictions in the expression we are visiting. Were we certain that the
equivalence was independent of the expression (e.g. through a more nuanced expression traversal) we could imaging relaxing this.

## Structs§

- Pulls up and pushes down predicate information represented as equivalences