viirya commented on code in PR #16217:
URL: https://github.com/apache/datafusion/pull/16217#discussion_r2122154995
##########
datafusion/physical-expr/src/equivalence/properties/mod.rs:
##########
@@ -125,40 +120,85 @@ use itertools::Itertools;
/// # let col_c = col("c", &schema).unwrap();
/// // 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)
-/// .with_constants(vec![ConstExpr::from(col_b)]);
-/// eq_properties.add_new_ordering(LexOrdering::new(vec![
+/// 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]],
const: [b@1(heterogeneous)]")
+/// assert_eq!(eq_properties.to_string(), "order: [[a@0 ASC, c@2 DESC]], eq:
[{members: [b@1], constant: (heterogeneous)}]");
/// ```
-#[derive(Debug, Clone)]
+#[derive(Clone, Debug)]
pub struct EquivalenceProperties {
- /// Distinct equivalence classes (exprs known to have the same expressions)
+ /// Distinct equivalence classes (i.e. expressions with the same value).
eq_group: EquivalenceGroup,
- /// Equivalent sort expressions
+ /// Equivalent sort expressions (i.e. those define the same ordering).
oeq_class: OrderingEquivalenceClass,
- /// Expressions whose values are constant
- ///
- /// TODO: We do not need to track constants separately, they can be tracked
- /// inside `eq_group` as `Literal` expressions.
- constants: Vec<ConstExpr>,
- /// Table constraints
+ /// Cache storing equivalent sort expressions in normal form (i.e. without
+ /// constants/duplicates and in standard form) and a map associating
leading
+ /// terms with full sort expressions.
+ oeq_cache: OrderingEquivalenceCache,
+ /// Table constraints that factor in equivalence calculations.
constraints: Constraints,
/// Schema associated with this object.
schema: SchemaRef,
}
+/// This object serves as a cache for storing equivalent sort expressions
+/// in normal form, and a map associating leading sort expressions with
+/// full lexicographical orderings. With this information, DataFusion can
+/// efficiently determine whether a given ordering is satisfied by the
+/// existing orderings, and discover new orderings based on the existing
+/// equivalence properties.
+#[derive(Clone, Debug, Default)]
+struct OrderingEquivalenceCache {
+ /// Equivalent sort expressions in normal form.
+ normal_cls: OrderingEquivalenceClass,
Review Comment:
If this is an efficient way to leverage the info provided by
`OrderingEquivalenceClass`, I wonder why you don't just incorporate cache into
`OrderingEquivalenceClass` so we don't need to expose an additional cache?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscr...@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscr...@datafusion.apache.org
For additional commands, e-mail: github-h...@datafusion.apache.org
