Struct mz_transform::union_cancel::UnionBranchCancellation

pub struct UnionBranchCancellation;

Detects an input being unioned with its negation and cancels them out

UnionBranchCancellation is recursion-safe, but this is not immediately trivial: It relies on the equality of certain MirRelationExprs, which is a scary thing in a WMR context, because Get x can mean not-equal things in different Let bindings. However, this problematic case can’t happen here, because when UnionBranchCancellation is looking at two Gets to the same Id, then these have to be under the same Let binding. This is because the recursion of compare_branches starts from two things in the same Let binding (from two inputs of a Union), and then we don’t make any compare_branches call where relation and other are in different Let bindings.

Implementations

impl UnionBranchCancellation

pub fn action( &self, relation: &mut MirRelationExpr, ) -> Result<(), TransformError>

Detects an input being unioned with its negation and cancels them out

fn branch_sign(branch: &MirRelationExpr) -> bool

Returns the sign of a given union branch. The sign is true if the branch contains an odd number of Negate operators within a chain of Map, Filter and Project operators, and false otherwise.

This sign is pre-computed for all union branches in order to avoid performing expensive comparisons of branches with the same sign since they can’t possibly cancel each other.

fn compare_branches( relation: &MirRelationExpr, other: &MirRelationExpr, ) -> BranchCmp

Compares two branches to check whether they produce the same results but with negated row count values, ie. one of them contains an extra Negate operator. Negate operators may appear interleaved with Map, Filter and Project operators, but these operators must appear in the same order in both branches.

Trait Implementations

impl Debug for UnionBranchCancellation

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Transform for UnionBranchCancellation

fn transform( &self, relation: &mut MirRelationExpr, _: &mut TransformCtx<'_>, ) -> Result<(), TransformError>

Transform a relation into a functionally equivalent relation.

fn debug(&self) -> String

A string describing the transform.