@@ -19,32 +19,130 @@ use datafusion_physical_expr_common::utils::ExprPropertiesNode;
1919
2020use 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
37125pub ( 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