Module mz_transform::equivalence_propagation

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

• EquivalencePropagation
  Pulls up and pushes down predicate information represented as equivalences