alamb commented on code in PR #27266: URL: https://github.com/apache/datafusion/pull/27266#discussion_r4515015368
########## datafusion/physical-expr/src/equivalence/properties/walk.rs: ########## @@ -19,32 +19,128 @@ use datafusion_physical_expr_common::utils::ExprPropertiesNode; use itertools::Itertools; -/// The state of one walk along a sequence of sort keys, such as the keys of a -/// required ordering. +/// The state of a walk along a required ordering (a sequence of sort keys). /// -/// A sort key only matters among the rows that tie on the keys before it. So -/// once a key is satisfied, the walk *pins* it: for the rest of the walk, the -/// key has one value, like a constant. An expression is *fixed* if it has one -/// value among those rows: it is a literal, a constant, pinned, a leaf that -/// reports itself as a singleton (such as an uncorrelated scalar subquery), or -/// not volatile and computed only from fixed expressions. The *head* of an -/// ordering is its first expression that is not fixed; an ordering whose -/// expressions are all fixed has no head. With orderings `[a, b]` and -/// `[a, c]`, the requirement `[a, c]` is satisfied, because pinning `a` makes -/// `c` the head of the second ordering. +/// [`EquivalenceProperties`] uses a `SortKeyWalk` to decide if a set of +/// orderings satisfies a requirement. See [Checking whether a requirement is +/// satisfied] for more details. /// -/// Pins live in the walk; the equivalence properties it reads do not change. +/// # Intuition and Definitions +/// +/// An ordering `[x, y, z]` can be thought of as a chain of claims about the +/// rows: they are sorted by `x`; among rows with equal `x`, sorted by `y`; +/// among rows with equal `x` and `y`, sorted by `z`. +/// +/// ## Pinning and Fixed Expressions Review Comment: Once I went through this logic, I found the algorithm quite clever and the refactoring well done. Thank you for working on this @jayzhan211 -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
