alamb commented on code in PR #27266:
URL: https://github.com/apache/datafusion/pull/27266#discussion_r4539349263
##########
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
+///
+/// During a walk, the code scans the ordering requirement left to right. When
+/// it finds key `k` satisfied, it *pins* `k`, meaning that `k` is effectively
a
+/// constant across the remaining ordering requirement.
+///
+/// An expression is *fixed* if it has one value for all rows that tie on the
+/// currently pinned expressions. Fixed expressions include the pinned
+/// expressions themselves, as well as literals, constants, and singleton leaf
+/// expressions (e.g. an uncorrelated scalar subquery).
+///
+/// ## Heads
+///
+/// For each equivalent ordering, the walk tracks its current *head*
expression,
+/// which is the current claim that is valid given the currently pinned
+/// expressions. When an expression is pinned, it advances the head of any
+/// existing claim about that key. An ordering with nothing left to promise is
+/// used up.
+///
+/// For example, if we have data ordered by `[a, b]` as well as `[c]`, and we
+/// walk the requirement `[a, c]`, pinning `a` after the first step results in:
+///
+/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[c]` | Outcome
|
+///
|------|-----------------|--------|---------------|------------|-----------|
+/// | 1 | a | {} | a | c | pin a
|
+/// | 2 | c | {a} | b | c | satisfied
|
+///
+/// It may be confusing that the head of `[c]` does not advance. The intuition
+/// is that `[c]` still promises the data is sorted by `c` for all equal values
+/// of `a`. This is true because the data was entirely sorted by `[c]` to begin
+/// with, and pinning `a` does not change the order of the rows that tie on
`a`,
+/// as illustrated in this example:
+///
+/// ```text
+/// ┌───┬───┬───┐
+/// │ a │ b │ c │
+/// ├───┼───┼───┤
+/// │ 1 │ 1 │ 2 │
+/// │ 1 │ 3 │ 5 │
+/// │ 2 │ 1 │ 7 │
+/// │ 2 │ 2 │ 9 │
+/// └───┴───┴───┘
+/// ```
+///
+/// # Example: Walking a Requirement
+///
+/// * Orderings: `[a ASC, b ASC, c ASC]` and `[d ASC]`
+/// * Requirement: `[a ASC, b ASC]`
+///
+/// | Step | Requirement Key | Pinned | Head `[a, b, c]` | Head `[d]` |
Outcome |
+///
|------|-----------------|--------|------------------|------------|-----------|
+/// | 1 | a | {} | a | d | pin a
|
+/// | 2 | b | {a} | b | d |
satisfied |
+///
+/// This requirement is satisfied (intuitively, because it is a prefix of the
+/// first ordering). The second ordering plays no part.
+///
+/// * Orderings: `[a ASC, b ASC]` and `[b ASC, c ASC]`
+/// * Requirement: `[a ASC, b ASC, c ASC]`
+///
+/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[b, c]` |
Outcome |
+///
|------|-----------------|--------|---------------|---------------|-----------|
+/// | 1 | a | {} | a | b | pin a
|
+/// | 2 | b | {a} | b | b | pin b
|
+/// | 3 | c | {a, b} | - | c |
satisfied |
+///
+/// Note that after step 2, `[a, b]` is used up, as both of its expressions are
+/// pinned. Among the rows that tie on `a` and `b`, the second ordering says
the
+/// rows are sorted by `c`, which satisfies the third key.
+///
+/// * Orderings: `[a ASC, c ASC]` and `[c ASC, b ASC]`
+/// * Requirement: `[a ASC, b ASC, c ASC]`
+///
+/// | Step | Requirement Key | Pinned | Head `[a, c]` | Head `[c, b]` |
Outcome |
+///
|------|-----------------|--------|---------------|---------------|-------------|
+/// | 1 | a | {} | a | c | pin a
|
+/// | 2 | b | {a} | c | c |
unsatisfied |
+///
+/// After pinning `a`, both orderings are headed by `c`. Since nothing says the
+/// rows that tie on `a` are sorted by `b`, the walk stops and reports that the
+/// requirement is not satisfied.
+///
+/// * Orderings: `[a ASC, b ASC]` and `[a ASC, c ASC]`
+/// * Requirement: `[a ASC, c ASC]`
+///
+/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[a, c]` |
Outcome |
+///
|------|-----------------|--------|---------------|---------------|-----------|
+/// | 1 | a | {} | a | a | pin a
|
+/// | 2 | c | {a} | b | c |
satisfied |
+///
+/// [Checking whether a requirement is satisfied]:
EquivalenceProperties#checking-whether-a-requirement-is-satisfied
pub(super) struct SortKeyWalk<'a> {
props: &'a EquivalenceProperties,
- /// Pinned expressions. Pinning a member of an equivalence class pins all
- /// of its members.
+ /// Pinned expressions.
pinned: HashSet<Arc<dyn PhysicalExpr>>,
/// Orderings that hold among the rows that tie on the pinned expressions,
/// found by [`EquivalenceProperties::implied_ordering`] as the walk goes.
implied: Vec<LexOrdering>,
- /// For each ordering (the normal orderings of `props`, then `implied`),
- /// the index of its head. Empty until the first pin, so that a walk with
- /// nothing pinned allocates nothing; until then every head is at index 0.
+ /// The position of the head of each ordering. Empty until the first pin.
Review Comment:
I found the "heads" notion quite confusing at first, but I think this
captures it
--
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]
