Struct EquivalenceProperties

pub struct EquivalenceProperties { /* private fields */ }

EquivalenceProperties stores information about the output of a plan node that can be used to optimize the plan. Currently, it keeps track of:

• Sort expressions (orderings),
• Equivalent expressions; i.e. expressions known to have the same value.
• Constants expressions; i.e. expressions known to contain a single constant value.

Please see the Using Ordering for Better Plans blog for more details.

Example equivalent sort expressions

Consider table below:

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

In this case, both a ASC and b DESC can describe the table ordering. EquivalenceProperties tracks these different valid sort expressions and treat a ASC and b DESC on an equal footing. For example, if the query specifies the output sorted by EITHER a ASC or b DESC, the sort can be avoided.

Example equivalent expressions

Similarly, consider the table below:

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

In this case, columns a and b always have the same value. With this information, Datafusion can optimize various operations. For example, if the partition requirement is Hash(a) and output partitioning is Hash(b), then DataFusion avoids repartitioning the data as the existing partitioning satisfies the requirement.

Code Example

use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
// This object represents data that is sorted by a ASC, c DESC
// with a single constant value of b
let mut eq_properties = EquivalenceProperties::new(schema);
eq_properties.add_constants(vec![ConstExpr::from(col_b)]);
eq_properties.add_ordering([
  PhysicalSortExpr::new_default(col_a).asc(),
  PhysicalSortExpr::new_default(col_c).desc(),
]);

assert_eq!(eq_properties.to_string(), "order: [[a@0 ASC, c@2 DESC]], eq: [{members: [b@1], constant: (heterogeneous)}]");

Implementations

impl EquivalenceProperties

pub fn new(schema: Arc<Schema>) -> EquivalenceProperties

Creates an empty EquivalenceProperties object.

pub fn with_constraints(self, constraints: Constraints) -> EquivalenceProperties

Adds constraints to the properties.

pub fn new_with_orderings( schema: Arc<Schema>, orderings: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>, ) -> EquivalenceProperties

Creates a new EquivalenceProperties object with the given orderings.

pub fn schema(&self) -> &Arc<Schema>

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 constraints(&self) -> &Constraints

Returns a reference to the constraints within.

pub fn constants(&self) -> Vec<ConstExpr>

Returns all the known constants expressions.

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

Returns the output ordering of the properties.

pub fn extend( self, other: EquivalenceProperties, ) -> Result<EquivalenceProperties, DataFusionError>

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 clear_per_partition_constants(&mut self)

Removes constant expressions that may change across partitions. This method should be used when merging data from different partitions.

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

Adds new orderings into the existing ordering equivalence class.

pub fn add_ordering( &mut self, ordering: impl IntoIterator<Item = PhysicalSortExpr>, )

Adds a single ordering to the existing ordering equivalence class.

pub fn add_equivalence_group( &mut self, other_eq_group: EquivalenceGroup, ) -> Result<(), DataFusionError>

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

pub fn normalized_oeq_class(&self) -> OrderingEquivalenceClass

Returns the ordering equivalence class within in normal form. Normalization standardizes expressions according to the equivalence group within, and removes constants/duplicates.

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

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( &mut self, constants: impl IntoIterator<Item = ConstExpr>, ) -> Result<(), DataFusionError>

Track/register physical expressions with constant values.

pub fn reorder( &mut self, ordering: impl IntoIterator<Item = PhysicalSortExpr>, ) -> Result<bool, DataFusionError>

Updates the ordering equivalence class within assuming that the table is re-sorted according to the argument ordering, and returns whether this operation resulted in any change. Note that equivalence classes (and constants) do not change as they are unaffected by a re-sort. If the given ordering is already satisfied, the function does nothing.

pub fn normalize_sort_exprs( &self, sort_exprs: impl IntoIterator<Item = PhysicalSortExpr>, ) -> Option<LexOrdering>

Normalizes the given sort expressions (i.e. sort_exprs) using the equivalence group within. Returns a LexOrdering instance if the expressions define a proper lexicographical ordering. For more details, see EquivalenceGroup::normalize_sort_exprs.

pub fn normalize_sort_requirements( &self, sort_reqs: impl IntoIterator<Item = PhysicalSortRequirement>, ) -> Option<LexRequirement>

Normalizes the given sort requirements (i.e. sort_reqs) using the equivalence group within. Returns a LexRequirement instance if the expressions define a proper lexicographical requirement. For more details, see EquivalenceGroup::normalize_sort_exprs.

pub fn ordering_satisfy( &self, given: impl IntoIterator<Item = PhysicalSortExpr>, ) -> Result<bool, DataFusionError>

Iteratively checks whether the given ordering is satisfied by any of the existing orderings. See Self::ordering_satisfy_requirement for more details and examples.

pub fn ordering_satisfy_requirement( &self, given: impl IntoIterator<Item = PhysicalSortRequirement>, ) -> Result<bool, DataFusionError>

Iteratively checks whether the given sort requirement is satisfied by any of the existing orderings.

Example Scenarios

In these scenarios, assume that all expressions share the same sort properties.

Case 1: Sort Requirement [a, c]

Existing orderings: [[a, b, c], [a, d]], constants: []

1. The function first checks the leading requirement a, which is satisfied by [a, b, c].first().
2. a is added as a constant for the next iteration.
3. Normal orderings become [[b, c], [d]].
4. The function fails for c in the second iteration, as neither [b, c] nor [d] satisfies c.

Case 2: Sort Requirement [a, d]

Existing orderings: [[a, b, c], [a, d]], constants: []

1. The function first checks the leading requirement a, which is satisfied by [a, b, c].first().
2. a is added as a constant for the next iteration.
3. Normal orderings become [[b, c], [d]].
4. The function returns true as [d] satisfies d.

pub fn extract_common_sort_prefix( &self, ordering: LexOrdering, ) -> Result<(Vec<PhysicalSortExpr>, bool), DataFusionError>

Determines the longest normal prefix of ordering satisfied by the existing ordering. Returns that prefix as a new LexOrdering, and a boolean indicating whether all the sort expressions are satisfied.

pub fn requirements_compatible( &self, given: LexRequirement, reference: LexRequirement, ) -> bool

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

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

Projects argument expr according to the projection described by mapping, taking equivalences into account.

For example, assume that columns a and c are always equal, and that the projection described by mapping encodes the following:

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 is not projectable.

pub fn project_expressions<'a>( &'a self, expressions: impl IntoIterator<Item = &'a Arc<dyn PhysicalExpr>> + 'a, mapping: &'a ProjectionMapping, ) -> impl Iterator<Item = Option<Arc<dyn PhysicalExpr>>> + 'a

Projects the given expressions according to the projection described by mapping, taking equivalences into account. This function is similar to Self::project_expr, but projects multiple expressions at once more efficiently than calling project_expr for each expression.

pub fn project( &self, mapping: &ProjectionMapping, output_schema: Arc<Schema>, ) -> EquivalenceProperties

Projects the equivalences within according to mapping and output_schema.

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

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>, ) -> Option<AcrossPartitions>

This function determines whether the provided expression is constant based on the known constants. For example, if columns a and b are constant, then expressions a, b and a + b will all return true whereas expression c will return false.

Parameters

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

Returns

Returns a Some value if the expression is constant according to equivalence group, and None otherwise. The Some variant contains an AcrossPartitions value indicating whether the expression is constant across partitions, and its actual value (if available).

pub fn get_expr_properties(&self, expr: Arc<dyn PhysicalExpr>) -> ExprProperties

Retrieves the properties for a given physical expression.

This function constructs an ExprProperties object for the given expression, which encapsulates information about the expression’s properties, including its SortProperties and Interval.

Parameters

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

Returns

Returns an ExprProperties object containing the ordering and range information for the given expression.

pub fn with_new_schema( self, schema: Arc<Schema>, ) -> Result<EquivalenceProperties, DataFusionError>

Transforms this EquivalenceProperties by mapping columns in the original schema to columns in the new schema by index.

Trait Implementations

impl Clone for EquivalenceProperties

fn clone(&self) -> EquivalenceProperties

Returns a duplicate 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<(), Error>

Formats the value using the given formatter.

impl Display for EquivalenceProperties

More readable display version of the EquivalenceProperties.

Format:

order: [[b@1 ASC NULLS LAST]], eq: [{members: [a@0], constant: (heterogeneous)}]

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

Formats the value using the given formatter.

impl From<EquivalenceProperties> for OrderingEquivalenceClass

fn from(eq_properties: EquivalenceProperties) -> OrderingEquivalenceClass

Converts to this type from the input type.