Skip to content

Commit 2bdd6f4

Browse files
alambclaudejayzhan211
authored
docs: Explain SortKeyWalk with worked examples (apache#27266)
## Which issue does this PR close? - related to apache#27121 - Closes apache#27234 ## Rationale for this change While reviewing apache#27191 I was very confused about how `SortKeyWalk` (added in apache#26853) decides whether known orderings satisfy a sort requirement, and wanted to write down what I learned so others do not have to repeat it. Specifically the existing docs stated the rules but did not define the terms clearly, and had no example a reader could trace step by step. ## What changes are included in this PR? Rustdoc only, in `datafusion/physical-expr/src/equivalence/properties/walk.rs`: ## What is the testing strategy for this PR? CI ## Are there any user-facing changes? No. --------- Co-authored-by: Claude Fable 5.1 <[email protected]> Co-authored-by: Jay Zhan <[email protected]>
1 parent 0302193 commit 2bdd6f4

1 file changed

Lines changed: 161 additions & 39 deletions

File tree

  • datafusion/physical-expr/src/equivalence/properties

‎datafusion/physical-expr/src/equivalence/properties/walk.rs‎

Lines changed: 161 additions & 39 deletions
Original file line numberDiff line numberDiff line change
@@ -19,32 +19,130 @@ use datafusion_physical_expr_common::utils::ExprPropertiesNode;
1919

2020
use itertools::Itertools;
2121

22-
/// The state of one walk along a sequence of sort keys, such as the keys of a
23-
/// required ordering.
22+
/// The state of a walk along a required ordering (a sequence of sort keys).
2423
///
25-
/// A sort key only matters among the rows that tie on the keys before it. So
26-
/// once a key is satisfied, the walk *pins* it: for the rest of the walk, the
27-
/// key has one value, like a constant. An expression is *fixed* if it has one
28-
/// value among those rows: it is a literal, a constant, pinned, a leaf that
29-
/// reports itself as a singleton (such as an uncorrelated scalar subquery), or
30-
/// not volatile and computed only from fixed expressions. The *head* of an
31-
/// ordering is its first expression that is not fixed; an ordering whose
32-
/// expressions are all fixed has no head. With orderings `[a, b]` and
33-
/// `[a, c]`, the requirement `[a, c]` is satisfied, because pinning `a` makes
34-
/// `c` the head of the second ordering.
24+
/// [`EquivalenceProperties`] uses a `SortKeyWalk` to decide if a set of
25+
/// orderings satisfies a requirement. See [Checking whether a requirement is
26+
/// satisfied] for more details.
3527
///
36-
/// Pins live in the walk; the equivalence properties it reads do not change.
28+
/// # Intuition and Definitions
29+
///
30+
/// An ordering `[x, y, z]` can be thought of as a chain of claims about the
31+
/// rows: they are sorted by `x`; among rows with equal `x`, sorted by `y`;
32+
/// among rows with equal `x` and `y`, sorted by `z`.
33+
///
34+
/// ## Pinning and Fixed Expressions
35+
///
36+
/// During a walk, the code scans the ordering requirement left to right. When
37+
/// it finds key `k` satisfied, it *pins* `k`, meaning that `k` is effectively a
38+
/// constant across the remaining ordering requirement.
39+
///
40+
/// An expression is *fixed* if it has one value for all rows that tie on the
41+
/// currently pinned expressions: it is a literal, a constant, pinned, a leaf
42+
/// that reports itself as a singleton (e.g. an uncorrelated scalar subquery),
43+
/// or not volatile and computed only from fixed expressions (e.g. `a + 1`
44+
/// once `a` is pinned).
45+
///
46+
/// ## Heads
47+
///
48+
/// The *head* of an ordering is its first expression that is not fixed: the
49+
/// claim that still holds among the rows that tie on the pinned expressions.
50+
/// Each pin moves every head past the expressions that are now fixed. An
51+
/// ordering whose expressions are all fixed has no head and is used up.
52+
///
53+
/// For example, if we have data ordered by `[a, b]` as well as `[c]`, and we
54+
/// walk the requirement `[a, c]`, pinning `a` after the first step results in:
55+
///
56+
/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[c]` | Outcome |
57+
/// |------|-----------------|--------|---------------|------------|-----------|
58+
/// | 1 | a | {} | a | c | pin a |
59+
/// | 2 | c | {a} | b | c | satisfied |
60+
///
61+
/// It may be confusing that the head of `[c]` does not advance. The intuition
62+
/// is that `[c]` still promises the data is sorted by `c` for all equal values
63+
/// of `a`. This is true because the data was entirely sorted by `[c]` to begin
64+
/// with, and pinning `a` does not change the order of the rows that tie on `a`,
65+
/// as illustrated in this example:
66+
///
67+
/// ```text
68+
/// ┌───┬───┬───┐
69+
/// │ a │ b │ c │
70+
/// ├───┼───┼───┤
71+
/// │ 1 │ 1 │ 2 │
72+
/// │ 1 │ 3 │ 5 │
73+
/// │ 2 │ 1 │ 7 │
74+
/// │ 2 │ 2 │ 9 │
75+
/// └───┴───┴───┘
76+
/// ```
77+
///
78+
/// # Example: Walking a Requirement
79+
///
80+
/// * Orderings: `[a ASC, b ASC, c ASC]` and `[d ASC]`
81+
/// * Requirement: `[a ASC, b ASC]`
82+
///
83+
/// | Step | Requirement Key | Pinned | Head `[a, b, c]` | Head `[d]` | Outcome |
84+
/// |------|-----------------|--------|------------------|------------|-----------|
85+
/// | 1 | a | {} | a | d | pin a |
86+
/// | 2 | b | {a} | b | d | satisfied |
87+
///
88+
/// This requirement is satisfied (intuitively, because it is a prefix of the
89+
/// first ordering). The second ordering plays no part.
90+
///
91+
/// * Orderings: `[a ASC, b ASC]` and `[b ASC, c ASC]`
92+
/// * Requirement: `[a ASC, b ASC, c ASC]`
93+
///
94+
/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[b, c]` | Outcome |
95+
/// |------|-----------------|--------|---------------|---------------|-----------|
96+
/// | 1 | a | {} | a | b | pin a |
97+
/// | 2 | b | {a} | b | b | pin b |
98+
/// | 3 | c | {a, b} | - | c | satisfied |
99+
///
100+
/// Note that after step 2, `[a, b]` is used up, as both of its expressions are
101+
/// pinned. Among the rows that tie on `a` and `b`, the second ordering says the
102+
/// rows are sorted by `c`, which satisfies the third key.
103+
///
104+
/// * Orderings: `[a ASC, c ASC]` and `[c ASC, b ASC]`
105+
/// * Requirement: `[a ASC, b ASC, c ASC]`
106+
///
107+
/// | Step | Requirement Key | Pinned | Head `[a, c]` | Head `[c, b]` | Outcome |
108+
/// |------|-----------------|--------|---------------|---------------|-------------|
109+
/// | 1 | a | {} | a | c | pin a |
110+
/// | 2 | b | {a} | c | c | unsatisfied |
111+
///
112+
/// After pinning `a`, both orderings are headed by `c`. Since nothing says the
113+
/// rows that tie on `a` are sorted by `b`, the walk stops and reports that the
114+
/// requirement is not satisfied.
115+
///
116+
/// * Orderings: `[a ASC, b ASC]` and `[a ASC, c ASC]`
117+
/// * Requirement: `[a ASC, c ASC]`
118+
///
119+
/// | Step | Requirement Key | Pinned | Head `[a, b]` | Head `[a, c]` | Outcome |
120+
/// |------|-----------------|--------|---------------|---------------|-----------|
121+
/// | 1 | a | {} | a | a | pin a |
122+
/// | 2 | c | {a} | b | c | satisfied |
123+
///
124+
/// [Checking whether a requirement is satisfied]: EquivalenceProperties#checking-whether-a-requirement-is-satisfied
37125
pub(super) struct SortKeyWalk<'a> {
38126
props: &'a EquivalenceProperties,
39-
/// Pinned expressions. Pinning a member of an equivalence class pins all
40-
/// of its members.
127+
/// Pinned expressions.
41128
pinned: HashSet<Arc<dyn PhysicalExpr>>,
42129
/// Orderings that hold among the rows that tie on the pinned expressions,
43130
/// found by [`EquivalenceProperties::implied_ordering`] as the walk goes.
44131
implied: Vec<LexOrdering>,
45-
/// For each ordering (the normal orderings of `props`, then `implied`),
46-
/// the index of its head. Empty until a head moves, so that a walk that
47-
/// moves no head allocates nothing; until then every head is at index 0.
132+
/// The position of the head of each ordering. Empty until a head moves, so
133+
/// that a walk that moves no head allocates nothing; until then every head
134+
/// is at index 0.
135+
///
136+
/// `head_idxs[i]` tracks the position in the `LexOrdering` at index `i`,
137+
/// as returned by [`Self::ordering`].
138+
///
139+
/// The ordering at index `i` is:
140+
/// * `self.props.oeq_cache.normal_cls[i]` if `i` is less than
141+
/// `self.props.oeq_cache.normal_cls.len()`,
142+
/// * `self.implied[i - self.props.oeq_cache.normal_cls.len()]` otherwise.
143+
///
144+
/// The value is either an index into that ordering's sort expressions, or
145+
/// its length when the ordering is used up.
48146
head_idxs: Vec<usize>,
49147
}
50148

@@ -73,9 +171,11 @@ impl<'a> SortKeyWalk<'a> {
73171
walk
74172
}
75173

76-
/// Returns how many leading keys (in normal form) the existing orderings
174+
/// Returns how many leading keys (in [normal form]) the existing orderings
77175
/// satisfy, pinning each satisfied key for the keys after it. A key
78176
/// without sort options only needs to be ordered in some direction.
177+
///
178+
/// [normal form]: EquivalenceProperties#normal-form
79179
pub(super) fn sorted_prefix_len<'k>(
80180
mut self,
81181
keys: impl ExactSizeIterator<Item = (&'k Arc<dyn PhysicalExpr>, Option<SortOptions>)>,
@@ -147,10 +247,17 @@ impl<'a> SortKeyWalk<'a> {
147247
Ok(())
148248
}
149249

150-
/// Pins `expr` and the rest of its equivalence class (but, unlike
151-
/// [`Self::pin_key`], not its children), then moves the head of each
152-
/// ordering past the expressions that are now fixed, and adds the
153-
/// orderings that the heads imply, until no new ordering is found.
250+
/// Pins `expr`, an expression in [normal form].
251+
///
252+
/// See [`SortKeyWalk`] for an explanation of pinning.
253+
///
254+
/// This method pins `expr` (and thus, by extension, all members of its
255+
/// equivalence class), but not its children. See [`Self::pin_key`] for
256+
/// more details. It then moves the head of each ordering past the
257+
/// expressions that are now fixed, and adds the orderings that the heads
258+
/// imply, until no new ordering is found.
259+
///
260+
/// [normal form]: EquivalenceProperties#normal-form
154261
pub(super) fn pin(&mut self, expr: Arc<dyn PhysicalExpr>) -> Result<()> {
155262
match self.props.eq_group.get_equivalence_class(&expr) {
156263
Some(class) => self.pinned.extend(class.iter().cloned()),
@@ -261,11 +368,12 @@ impl<'a> SortKeyWalk<'a> {
261368
// strict:
262369
node.data.strictly_order_preserving = true;
263370
}
264-
// Now, check what we know about orderings. A whole-partition window
265-
// such as `SUM(x) OVER (PARTITION BY k)` adds `[k, w]` in all four
266-
// directions of `w` (see `OrderingEquivalenceClass::is_expr_partial_const`).
267-
// Once `k` is pinned, `w` heads orderings in opposite directions, so it
268-
// has one value among the rows that tie on `k`:
371+
// Now, check what we know about orderings. A window aggregate over a
372+
// whole window partition, such as `SUM(x) OVER (PARTITION BY k)`, adds
373+
// `[k, w]` in all four directions of `w` (see `EquivalenceProperties`
374+
// documentation for more details). Once `k` is pinned, `w` heads
375+
// orderings in opposite directions, so it has one value among the rows
376+
// that tie on `k`:
269377
let normal_expr = self.props.eq_group.normalize_expr(Arc::clone(&node.expr));
270378
if self.is_fixed(&normal_expr) || is_partial_const(self.heads(), &normal_expr) {
271379
node.data.sort_properties = SortProperties::Singleton;
@@ -285,10 +393,13 @@ impl<'a> SortKeyWalk<'a> {
285393
idx
286394
}
287395

288-
/// Whether `expr` is fixed (see [`SortKeyWalk`]). Callers pass `expr` in
289-
/// normal form. Pins are stored as given, so a pinned expression that is
290-
/// not in normal form is found only through its equivalence class, whose
291-
/// members are all pinned.
396+
/// Whether `expr` is fixed.
397+
///
398+
/// Note that `expr` must be in [normal form].
399+
///
400+
/// See [`SortKeyWalk`] for more details.
401+
///
402+
/// [normal form]: EquivalenceProperties#normal-form
292403
fn is_fixed(&self, expr: &Arc<dyn PhysicalExpr>) -> bool {
293404
if expr.is::<Literal>() || self.pinned.contains(expr) {
294405
return true;
@@ -319,8 +430,10 @@ impl<'a> SortKeyWalk<'a> {
319430
children.into_iter().all(|child| self.is_fixed(child))
320431
}
321432

322-
/// The ordering at `idx`: the normal orderings of `props`, then
433+
/// The ordering at `idx`: the orderings of `props` in [normal form], then
323434
/// `implied`.
435+
///
436+
/// [normal form]: EquivalenceProperties#normal-form
324437
fn ordering(&self, idx: usize) -> &LexOrdering {
325438
let normal = &self.props.oeq_cache.normal_cls;
326439
normal
@@ -737,8 +850,10 @@ mod tests {
737850
Ok(())
738851
}
739852

740-
/// A window over a whole partition, such as `SUM(..) OVER (PARTITION BY
741-
/// k)`, adds `[k, x]` in all four directions of `x`. Pinning `k` leaves `x`
853+
/// A window over a whole window partition, such as `SUM(..) OVER
854+
/// (PARTITION BY k)`, adds `[k, x]` in all four directions of `x`.
855+
///
856+
/// Pinning `k` leaves `x`
742857
/// heading orderings in opposite directions, so `x` has one value, and so
743858
/// does `CAST(x AS BIGINT)`: `[k, CAST(x AS BIGINT)]` holds in every
744859
/// direction. Without the partial constant check, `x` would only be
@@ -779,10 +894,17 @@ mod tests {
779894
Ok(())
780895
}
781896

782-
/// `find_longest_permutation` pins what it finds in normal form. With
783-
/// `b = c` and ordering `[a + b, d]`, finding either `a + b` or `a + c`
784-
/// pins the head of the ordering, whichever of `b` and `c` the class
785-
/// normalizes to, so `d` is found next.
897+
/// `find_longest_permutation` pins what it finds in [normal form].
898+
///
899+
/// For example, with `b = c` and ordering `[a + b, d]`, finding either
900+
///
901+
/// * `a + b`
902+
/// * `a + c`
903+
///
904+
/// pins the head of the ordering (whichever of `b` or `c` the equivalence
905+
/// class normalizes to), so `d` is found next.
906+
///
907+
/// [normal form]: EquivalenceProperties#normal-form
786908
#[test]
787909
fn find_longest_permutation_pins_normal_form() -> Result<()> {
788910
let schema = Arc::new(Schema::new(

0 commit comments

Comments
 (0)