Struct mz_transform::analysis::equivalences::EquivalenceClasses

pub struct EquivalenceClasses {
    pub classes: Vec<Vec<MirScalarExpr>>,
    remap: BTreeMap<MirScalarExpr, MirScalarExpr>,
}

A compact representation of classes of expressions that must be equivalent.

Each “class” contains a list of expressions, each of which must be Eq::eq equal. Ideally, the first element is the “simplest”, e.g. a literal or column reference, and any other element of that list can be replaced by it.

The classes are meant to be minimized, with each expression as reduced as it can be, and all classes sharing an element merged.

Fields

classes: Vec<Vec<MirScalarExpr>>

Multiple lists of equivalent expressions, each representing an equivalence class.

The first element should be the “canonical” simplest element, that any other element can be replaced by. These classes are unified whenever possible, to minimize the number of classes. They are only guaranteed to form an equivalence relation after a call to minimize, which refreshes both self.classes and self.remap.

remap: BTreeMap<MirScalarExpr, MirScalarExpr>

An expression simplification map.

This map reflects an equivalence relation based on a prior version of self.classes. As users may add to self.classes, self.remap may become stale. We refresh remap only in self.refresh(), to the equivalence relation that derives from self.classes.

It is important to self.remap.clear() if you invalidate it by mutating rather than appending to self.classes. This will be corrected in the next call to self.refresh(), but until then remap could be arbitrarily wrong. This should be improved in the future.

Implementations

impl EquivalenceClasses

pub fn mir_scalar_expr_complexity( e1: &MirScalarExpr, e2: &MirScalarExpr, ) -> Ordering

Comparator function for the complexity of scalar expressions. Simpler expressions are smaller. Can be used when we need to decide which of several equivalent expressions to use.

fn tidy(&mut self)

Sorts and deduplicates each class, removing literal errors.

This method does not ensure equivalence relation structure, but instead performs only minimal structural clean-up.

fn refresh(&mut self) -> bool

Restore equivalence relation structure to self.classes and refresh self.remap.

This method takes roughly linear time, and returns true iff self.remap has changed. This is the only method that refreshes self.remap, and is a perfect place to decide whether the equivalence classes it represents have experienced any changes since the last refresh.

pub fn minimize(&mut self, columns: Option<&[ColumnType]>)

Update self to maintain the same equivalences which potentially reducing along Ord::le.

Informally this means simplifying constraints, removing redundant constraints, and unifying equivalence classes.

fn expand(&self) -> Vec<Vec<MirScalarExpr>>

Proposes new equivalences that are likely to be novel.

This method invokes self.implications() to propose equivalences, and then judges them to be novel or not based on existing knowledge, reducing the equivalences down to their novel core. This method may produce non-novel equivalences, due to its inability to perform MSE::reduce. We can end up with e.g. constant expressions that cannot be found until they are so reduced. The novelty detection is best-effort, and meant to provide a clearer signal and minimize the number of times we call and amount of work we do in self.refresh().

fn implications(&self) -> Vec<Vec<MirScalarExpr>>

Derives potentially novel equivalences without regard for minimization.

This is an opportunity to explore equivalences that do not correspond to expression minimization, and therefore should not be used in minimize_once. They are still potentially important, but required additional guardrails to ensure we reach a fixed point.

The implications will be introduced into self.classes and will prompt a round of minimization, making it somewhat polite to avoid producing outputs that cannot result in novel equivalences. For example, before producing a new equivalence, one could check that the involved terms are not already present in the same class.

fn minimize_once(&mut self, columns: Option<&[ColumnType]>) -> bool

A single iteration of minimization, which we expect to repeat but benefit from factoring out.

This invocation should take roughly linear time. It starts with equivalence class invariants maintained (closed under transitivity), and then

1. Performs per-expression reduction, including the class structure to replace subexpressions.
2. Applies idiom detection to e.g. unpack expressions equivalence to literal true or false.
3. Restores the equivalence class invariants.

pub fn union(&self, other: &Self) -> Self

Produce the equivalences present in both inputs.

pub fn union_many<'a, I>(&self, others: I) -> Self

where I: IntoIterator<Item = &'a Self>,

The equivalence classes of terms equivalent in all inputs.

This method relies on the remap member of each input, and bases the intersection on these rather than classes. This means one should ensure minimize() has been called on all inputs, or risk getting a stale, but conservatively correct, result.

This method currently misses opportunities, because it only looks for exactly matches in expressions, which may not include all possible matches. For example, f(#1) == g(#1) may exist in one class, but in another class where #0 == #1 it may exist as f(#0) == g(#0).

pub fn permute(&mut self, permutation: &[usize])

Permutes each expression, looking up each column reference in permutation and replacing with what it finds.

pub fn project<I>(&mut self, output_columns: I)

where I: IntoIterator<Item = usize> + Clone,

Subject the constraints to the column projection, reworking and removing equivalences.

This method should also introduce equivalences representing any repeated columns.

pub fn unsatisfiable(&self) -> bool

True if any equivalence class contains two distinct non-error literals.

pub fn reducer(&self) -> &BTreeMap<MirScalarExpr, MirScalarExpr>

Returns a map that can be used to replace (sub-)expressions.

fn class_contains_literal<P>(class: &[MirScalarExpr], predicate: P) -> bool

where P: FnMut(&Result<Datum<'_>, &EvalError>) -> bool,

Examines the prefix of class of literals, looking for any satisfying predicate.

This test bails out as soon as it sees a non-literal, and may have false negatives if the data are not sorted with literals at the front.

Trait Implementations

impl Clone for EquivalenceClasses

fn clone(&self) -> EquivalenceClasses

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EquivalenceClasses

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

Formats the value using the given formatter.

impl Default for EquivalenceClasses

fn default() -> EquivalenceClasses

Returns the “default value” for a type.

impl Display for EquivalenceClasses

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

Formats the value using the given formatter.

impl Ord for EquivalenceClasses

fn cmp(&self, other: &EquivalenceClasses) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized + PartialOrd,

Restrict a value to a certain interval.

impl PartialEq for EquivalenceClasses

fn eq(&self, other: &EquivalenceClasses) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl PartialOrd for EquivalenceClasses

fn partial_cmp(&self, other: &EquivalenceClasses) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl Eq for EquivalenceClasses

impl StructuralPartialEq for EquivalenceClasses