Struct datafusion_physical_expr::equivalence::EquivalenceProperties

pub struct EquivalenceProperties {
    pub eq_group: EquivalenceGroup,
    pub oeq_class: OrderingEquivalenceClass,
    pub constants: Vec<Arc<dyn PhysicalExpr>>,
    /* private fields */
}

A EquivalenceProperties object stores useful information related to a schema. Currently, it keeps track of:

• Equivalent expressions, e.g expressions that have same value.
• Valid sort expressions (orderings) for the schema.
• Constants expressions (e.g expressions that are known to have constant values).

Consider table below:

┌-------┐
| a | b |
|---|---|
| 1 | 9 |
| 2 | 8 |
| 3 | 7 |
| 5 | 5 |
└---┴---┘

where both a ASC and b DESC can describe the table ordering. With EquivalenceProperties, we can keep track of these different valid sort expressions and treat a ASC and b DESC on an equal footing.

Similarly, consider the table below:

┌-------┐
| a | b |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 5 | 5 |
└---┴---┘

where columns a and b always have the same value. We keep track of such equivalences inside this object. With this information, we can optimize things like partitioning. For example, if the partition requirement is Hash(a) and output partitioning is Hash(b), then we can deduce that the existing partitioning satisfies the requirement.

Fields

eq_group: EquivalenceGroup

Collection of equivalence classes that store expressions with the same value.

oeq_class: OrderingEquivalenceClass

Equivalent sort expressions for this table.

constants: Vec<Arc<dyn PhysicalExpr>>

Expressions whose values are constant throughout the table. TODO: We do not need to track constants separately, they can be tracked inside eq_groups as Literal expressions.

Implementations

impl EquivalenceProperties

pub fn new(schema: SchemaRef) -> Self

Creates an empty EquivalenceProperties object.

pub fn new_with_orderings(schema: SchemaRef, orderings: &[LexOrdering]) -> Self

Creates a new EquivalenceProperties object with the given orderings.

pub fn schema(&self) -> &SchemaRef

Returns the associated schema.

pub fn oeq_class(&self) -> &OrderingEquivalenceClass

Returns a reference to the ordering equivalence class within.

pub fn eq_group(&self) -> &EquivalenceGroup

Returns a reference to the equivalence group within.

pub fn constants(&self) -> &[Arc<dyn PhysicalExpr>]

Returns a reference to the constant expressions

pub fn output_ordering(&self) -> Option<LexOrdering>

Returns the output ordering of the properties.

pub fn normalized_oeq_class(&self) -> OrderingEquivalenceClass

Returns the normalized version of the ordering equivalence class within. Normalization removes constants and duplicates as well as standardizing expressions according to the equivalence group within.

pub fn extend(self, other: Self) -> Self

Extends this EquivalenceProperties with the other object.

pub fn clear_orderings(&mut self)

Clears (empties) the ordering equivalence class within this object. Call this method when existing orderings are invalidated.

pub fn add_ordering_equivalence_class( &mut self, other: OrderingEquivalenceClass )

Extends this EquivalenceProperties by adding the orderings inside the ordering equivalence class other.

pub fn add_new_orderings( &mut self, orderings: impl IntoIterator<Item = LexOrdering> )

Adds new orderings into the existing ordering equivalence class.

pub fn add_equivalence_group(&mut self, other_eq_group: EquivalenceGroup)

Incorporates the given equivalence group to into the existing equivalence group within.

pub fn add_equal_conditions( &mut self, left: &Arc<dyn PhysicalExpr>, right: &Arc<dyn PhysicalExpr> )

Adds a new equality condition into the existing equivalence group. If the given equality defines a new equivalence class, adds this new equivalence class to the equivalence group.

pub fn add_constants( self, constants: impl IntoIterator<Item = Arc<dyn PhysicalExpr>> ) -> Self

Track/register physical expressions with constant values.

pub fn with_reorder(self, sort_exprs: Vec<PhysicalSortExpr>) -> Self

Updates the ordering equivalence group within assuming that the table is re-sorted according to the argument sort_exprs. Note that constants and equivalence classes are unchanged as they are unaffected by a re-sort.

pub fn ordering_satisfy(&self, given: LexOrderingRef<'_>) -> bool

Checks whether the given ordering is satisfied by any of the existing orderings.

pub fn ordering_satisfy_requirement(&self, reqs: LexRequirementRef<'_>) -> bool

Checks whether the given sort requirements are satisfied by any of the existing orderings.

pub fn requirements_compatible( &self, given: LexRequirementRef<'_>, reference: LexRequirementRef<'_> ) -> bool

Checks whether the given`` sort requirements are equal or more specific than the reference` sort requirements.

pub fn get_finer_ordering( &self, lhs: LexOrderingRef<'_>, rhs: LexOrderingRef<'_> ) -> Option<LexOrdering>

Returns the finer ordering among the orderings lhs and rhs, breaking any ties by choosing lhs.

The finer ordering is the ordering that satisfies both of the orderings. If the orderings are incomparable, returns None.

For example, the finer ordering among [a ASC] and [a ASC, b ASC] is the latter.

pub fn get_finer_requirement( &self, req1: LexRequirementRef<'_>, req2: LexRequirementRef<'_> ) -> Option<LexRequirement>

Returns the finer ordering among the requirements lhs and rhs, breaking any ties by choosing lhs.

The finer requirements are the ones that satisfy both of the given requirements. If the requirements are incomparable, returns None.

For example, the finer requirements among [a ASC] and [a ASC, b ASC] is the latter.

pub fn get_meet_ordering( &self, lhs: LexOrderingRef<'_>, rhs: LexOrderingRef<'_> ) -> Option<LexOrdering>

Calculates the “meet” of the given orderings (lhs and rhs). The meet of a set of orderings is the finest ordering that is satisfied by all the orderings in that set. For details, see:

https://en.wikipedia.org/wiki/Join_and_meet

If there is no ordering that satisfies both lhs and rhs, returns None. As an example, the meet of orderings [a ASC] and [a ASC, b ASC] is [a ASC].

pub fn substitute_ordering_component( &self, mapping: &ProjectionMapping, sort_expr: &[PhysicalSortExpr] ) -> Result<Vec<Vec<PhysicalSortExpr>>>

we substitute the ordering according to input expression type, this is a simplified version In this case, we just substitute when the expression satisfy the following condition: I. just have one column and is a CAST expression TODO: Add one-to-ones analysis for monotonic ScalarFunctions. TODO: we could precompute all the scenario that is computable, for example: atan(x + 1000) should also be substituted if x is DESC or ASC After substitution, we may generate more than 1 LexOrdering. As an example, [a ASC, b ASC] will turn into [a ASC, b ASC], [CAST(a) ASC, b ASC] when projection expressions a, b, CAST(a) is applied.

pub fn substitute_oeq_class( &mut self, mapping: &ProjectionMapping ) -> Result<()>

In projection, supposed we have a input function ‘A DESC B DESC’ and the output shares the same expression with A and B, we could surely use the ordering of the original ordering, However, if the A has been changed, for example, A-> Cast(A, Int64) or any other form, it is invalid if we continue using the original ordering Since it would cause bug in dependency constructions, we should substitute the input order in order to get correct dependency map, happen in issue 8838: https://github.com/apache/datafusion/issues/8838

pub fn project_expr( &self, expr: &Arc<dyn PhysicalExpr>, projection_mapping: &ProjectionMapping ) -> Option<Arc<dyn PhysicalExpr>>

Projects argument expr according to projection_mapping, taking equivalences into account.

For example, assume that columns a and c are always equal, and that projection_mapping encodes following mapping:

a -> a1
b -> b1

Then, this function projects a + b to Some(a1 + b1), c + b to Some(a1 + b1) and d to None, meaning that it cannot be projected.

pub fn project( &self, projection_mapping: &ProjectionMapping, output_schema: SchemaRef ) -> Self

Projects the equivalences within according to projection_mapping and output_schema.

pub fn find_longest_permutation( &self, exprs: &[Arc<dyn PhysicalExpr>] ) -> (LexOrdering, Vec<usize>)

Returns the longest (potentially partial) permutation satisfying the existing ordering. For example, if we have the equivalent orderings [a ASC, b ASC] and [c DESC], with exprs containing [c, b, a, d], then this function returns ([a ASC, b ASC, c DESC], [2, 1, 0]). This means that the specification [a ASC, b ASC, c DESC] is satisfied by the existing ordering, and [a, b, c] resides at indices: 2, 1, 0 inside the argument exprs (respectively). For the mathematical definition of “partial permutation”, see:

https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n

pub fn is_expr_constant(&self, expr: &Arc<dyn PhysicalExpr>) -> bool

This function determines whether the provided expression is constant based on the known constants.

Arguments

• expr: A reference to a Arc<dyn PhysicalExpr> representing the expression to be checked.

Returns

Returns true if the expression is constant according to equivalence group, false otherwise.

pub fn get_expr_ordering(&self, expr: Arc<dyn PhysicalExpr>) -> ExprOrdering

Retrieves the ordering information for a given physical expression.

This function constructs an ExprOrdering object for the provided expression, which encapsulates information about the expression’s ordering, including its SortProperties.

Arguments

• expr: An Arc<dyn PhysicalExpr> representing the physical expression for which ordering information is sought.

Returns

Returns an ExprOrdering object containing the ordering information for the given expression.

Trait Implementations

impl Clone for EquivalenceProperties

fn clone(&self) -> EquivalenceProperties

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for EquivalenceProperties

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

Formats the value using the given formatter.