Skip to content

Commit ac1a63d

Browse files
jayzhan211alambclaude
authored
fix: SanityCheckPlan error when a per-partition constant leads an ordering (#27191)
## Which issue does this PR close? - Closes #26762. ## Rationale for this change Queries that planned in earlier releases fail with `SanityCheckPlan` when a window's input ordering starts with a per-partition constant or is proven through an equality such as `a = CAST(c AS DATE)`. Across 7,440 generated query runs, `main` has 62 failures on queries that plan on 55.2.0, and this PR has none, with the same rows wherever both plan. There are three causes. In each one, window planning and `SanityCheckPlan` reach different answers about whether the input is sorted: | Introduced by | Example | Why they disagree | |---|---|---| | #23528 (in 55.0.0) | The #26762 query | Normalized orderings keep per-partition constants, but `add_constants` drops them, so window planning sees `[total]` and `SanityCheckPlan` sees `[k, total]` | | #25922 (on `branch-56`) | A window on `c` over a TopK on `(k, a, c)`, with `k` a per-partition constant and `a = CAST(c AS DATE)` | `add_constants` discovers that `[a, c]` implies `[c]`, but an ordering added after the equality doesn't | | #26747 (on `branch-56`) | A window on `(k, c)` over a TopK on `(k, a, c)`, where `a` isn't selected | The sort is removed below a projection because its input has the ordering, and the projection can't prove it | This PR replaces #27140 and keeps its commit. ## What changes are included in this PR? Start reading at `add_orderings`. It is the decision I most want reviewed, because it makes the optimizer claim more orderings, and a wrong claim means wrong results. | Where | Change | Fixes | |---|---|---| | `SortKeyWalk::new` | An ordering's head skips leading fixed expressions before the first key is pinned | #23528 | | `add_orderings` | Discover the orderings a new ordering implies through known equalities, as `add_constants` and `add_equal_conditions` already do, for any key and past the constants an ordering keeps: `[k, a, c]` with `a = CAST(c AS DATE)` implies `[k, c]` | #25922, #26747 | | `handle_projection_pushdown` | If the input has the ordering but the projection can't prove it, keep the sort above the projection | The failures the first row would otherwise add, when a projection drops a leading per-partition constant | | `RepartitionExec` | Clear per-partition constants before adding the merge ordering, as `SortPreservingMergeExec` does | Otherwise the second row keeps `[c]` from `[k, a, c]` after a merge, where it holds only within each partition | | `SortKeyWalk::is_fixed` | Return early for a column that isn't pinned or constant | The first row made single-key checks about 30% slower | **Who is affected.** Plans with an ordering that starts with a per-partition constant, or that is proven through an equality or a column a projection drops. It can't stop halfway. **No API change.** Discovery in `add_orderings` can fail only on an expression that doesn't match the schema. That implied ordering is then left out, which can cost a sort but not change results. **Worst case.** 4 of the 7,440 generated runs plan a sort that `main` doesn't: a `GROUP BY k, c` over a TopK on `(a, c)` with `a = CAST(c AS DATE)`, at 4 partitions. Knowing `[c]`, the aggregate streams on `c` and sorts on `c` after its hash repartition. `main` picks the same aggregate when the ordering is known before the equality. 392 runs have fewer sorts. ## What is the testing strategy for this PR? - `window.slt` covers each cause, including a merge of partitions above the sort, and checks the plans. Removing any one of the first three changes, limiting discovery to the first key, or not skipping constants makes tests fail, in `window.slt` or in the unit tests for the walk and for implied orderings. A `RepartitionExec` unit test covers the merge. - All SLT files pass with no existing plan changing, as do the `physical_optimizer` integration tests and the equivalence fuzz tests. - A sweep of functions that look order-preserving but aren't found no wrong ordering. Details below. <details> <summary>Generated query runs, benchmarks, rejected alternatives, and queries that still fail</summary> **Generated runs.** Each sweep runs at `target_partitions` 1 and 4. A regression plans on the reference build and fails on the other build. | Sweep | Runs | `main`, vs 55.2.0 | `main`, vs before #23528 | This PR, vs both | |---|---|---|---|---| | Per-partition constants: 6 inputs, 3 orderings, 5 projections, up to 12 consumers | 2,016 | 0 | 4 | 0 | | Orderings proven through `a = CAST(c AS DATE)` | 3,120 | 56 | 56 | 0 | | An operator between the ordering and the consumer: joins of each type on either side, filter, aggregate, union | 1,584 | 6 | 36 | 0 | | `head = f(arg)` for `CAST(x AS VARCHAR)`, `ABS`, negation, modulo, `upper` and order-preserving functions, in all 4 sort directions | 720 | 0 | 0 | 0, and no wrong ordering | The results are the same with this patch on `branch-56`, where all SLT files pass as well. Compared with `main` on the runs that plan on both, the rows are the same, 4 runs have more sorts (see the worst case above) and 392 have fewer. **Benchmarks.** `equivalence_properties`, best of 10 alternating runs on a busy laptop, so approximate: single-key checks are 6-12% slower (about 20-40 ns), and window-heavy orderings are 24-33% faster. | Benchmark | `main` | This PR | |---|---|---| | `ordering_satisfy/1_key/8` | 359 ns | 380 ns | | `ordering_satisfy_requirement/1_key/8` | 307 ns | 329 ns | | `find_longest_permutation/1_expr/32` | 306 ns | 344 ns | | `window/4` | 1,543 ns | 1,181 ns | | `window/32` | 7,319 ns | 4,889 ns | **Rejected.** - Having `add_constants` keep per-partition constants fails `test_eliminate_redundant_monotonic_sorts`. - Labelling `lower(g)` as a uniform constant isn't enough, because a constant from an aggregate without `GROUP BY` really is per-partition. - Having the projection leave a per-partition constant it drops out of its orderings, instead of the check in `handle_projection_pushdown`, makes 2 generated queries fail `SanityCheckPlan`: a window over a `GROUP BY` whose input ordering leads with such a constant. - Applying the projection check to every node in `pushdown_sorts_helper` only fixes one more query, and that query already fails on every release, so I kept the narrower check. **Still failing, not regressions.** A window over a `UNION ALL` of two TopKs that have `v AS w` fails on every build I tried, including before #23528: ```sql SELECT *, ROW_NUMBER() OVER (ORDER BY w) AS r FROM ( SELECT k, v, w FROM (SELECT k, v, v AS w FROM (SELECT lower(g) AS k, v FROM t5 WHERE g = 'a') ORDER BY k, v LIMIT 30) UNION ALL SELECT k, v, w FROM (SELECT k, v, v AS w FROM (SELECT lower(g) AS k, v FROM t5 WHERE g = 'a') ORDER BY k, v LIMIT 30) ) ORDER BY r; ``` </details> ## Are there any user-facing changes? Affected queries plan again. This is a candidate for `branch-56`, where it applies without conflicts. --------- Co-authored-by: Andrew Lamb <[email protected]> Co-authored-by: Claude Fable 5.1 <[email protected]>
1 parent 3d7e191 commit ac1a63d

5 files changed

Lines changed: 891 additions & 28 deletions

File tree

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

Lines changed: 93 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -630,7 +630,8 @@ impl EquivalenceProperties {
630630
}
631631
}
632632

633-
/// Adds new orderings into the existing ordering equivalence class.
633+
/// Adds new orderings into the existing ordering equivalence class, along
634+
/// with the orderings they imply through known equalities.
634635
pub fn add_orderings(
635636
&mut self,
636637
orderings: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
@@ -642,14 +643,32 @@ impl EquivalenceProperties {
642643
.cloned()
643644
.filter_map(|o| self.normalize_sort_exprs(o))
644645
.collect();
645-
if !normal_orderings.is_empty() {
646-
self.oeq_class.extend(orderings);
647-
// Normalize given orderings to update the cache:
648-
self.oeq_cache.normal_cls.extend(normal_orderings);
649-
// TODO: If no ordering is found to be redundant during extension, we
650-
// can use a shortcut algorithm to update the leading map.
651-
self.oeq_cache.update_map();
646+
if normal_orderings.is_empty() {
647+
return;
652648
}
649+
// `add_constants` and `add_equal_conditions` discover implied orderings
650+
// too, and whether an ordering is satisfied must not depend on which of
651+
// them ran last. Deriving one fails only on an expression that does not
652+
// match the schema; that ordering is then not implied, which can cost a
653+
// sort but not a wrong result.
654+
let mut implied: Vec<LexOrdering> = vec![];
655+
for ordering in &normal_orderings {
656+
// Two orderings can imply the same one; expand it only once:
657+
for ordering in self.implied_by(ordering).unwrap_or_default() {
658+
if !implied.contains(&ordering) {
659+
implied.push(ordering);
660+
}
661+
}
662+
}
663+
self.oeq_class.extend(orderings);
664+
// Normalize given orderings to update the cache:
665+
self.oeq_cache.normal_cls.extend(normal_orderings);
666+
// TODO: If no ordering is found to be redundant during extension, we
667+
// can use a shortcut algorithm to update the leading map.
668+
self.oeq_cache.update_map();
669+
// Each implied ordering is shorter than the one implying it, so this
670+
// terminates:
671+
self.add_orderings(implied);
653672
}
654673

655674
/// Adds a single ordering to the existing ordering equivalence class.
@@ -819,15 +838,76 @@ impl EquivalenceProperties {
819838
let mut new_orderings = vec![];
820839
for idx in ordering_idxs {
821840
let ordering = &self.oeq_cache.normal_cls[*idx];
822-
new_orderings
823-
.extend(self.implied_ordering(&ordering[0], ordering[1..].iter())?);
824-
}
825-
if !new_orderings.is_empty() {
826-
self.add_orderings(new_orderings);
841+
// As in `add_orderings`, an ordering that cannot be derived is
842+
// not implied, so the result does not depend on the call order:
843+
new_orderings.extend(self.implied_by(ordering).unwrap_or_default());
827844
}
845+
self.add_orderings(new_orderings);
828846
Ok(())
829847
}
830848

849+
/// Returns the orderings that the normal ordering `ordering` implies
850+
/// through known equalities: for each key that is a function of the keys
851+
/// after it (see [`Self::implied_ordering`]), `ordering` without that key.
852+
///
853+
/// # Example: a key that is a function of the keys after it
854+
///
855+
/// * Ordering: `[k ASC, a ASC, c ASC]`
856+
/// * Equality: `a = CAST(c AS DATE)`
857+
/// * Returns: `[k ASC, c ASC]`
858+
///
859+
/// Among the rows that tie on `k`, the rows are sorted by `a`, and the
860+
/// rows that also tie on `a` are sorted by `c`. `a` is the date of `c`, so
861+
/// a row with an earlier `a` also has an earlier `c`, and the rows that
862+
/// tie on `k` are sorted by `c` alone:
863+
///
864+
/// ```text
865+
/// ┌───┬────────────┬──────────────────┐
866+
/// │ k │ a │ c │
867+
/// ├───┼────────────┼──────────────────┤
868+
/// │ x │ 2026-01-01 │ 2026-01-01 09:00 │
869+
/// │ x │ 2026-01-02 │ 2026-01-02 01:00 │
870+
/// │ x │ 2026-01-02 │ 2026-01-02 05:00 │
871+
/// │ y │ 2026-01-01 │ 2026-01-01 03:00 │
872+
/// └───┴────────────┴──────────────────┘
873+
/// ```
874+
///
875+
/// # Example: a constant that differs between partitions
876+
///
877+
/// * Ordering: `[k ASC, a ASC, c ASC]`, where `k` is a constant whose value
878+
/// differs between partitions
879+
/// * Equality: `a = CAST(c AS DATE)`
880+
/// * Returns: `[c ASC]`
881+
///
882+
/// A normal ordering can keep such a constant (see
883+
/// `EquivalenceGroup::normalize_sort_exprs`). Within a partition `k` has
884+
/// one value, so it is left out of the keys and of the result.
885+
///
886+
/// # Example: directions that differ
887+
///
888+
/// * Ordering: `[a ASC, c DESC]`
889+
/// * Equality: `a = CAST(c AS DATE)`
890+
/// * Returns: nothing
891+
///
892+
/// `c` descends within a date but ascends across dates, so the rows are
893+
/// not sorted by `c` in either direction.
894+
fn implied_by(&self, ordering: &LexOrdering) -> Result<Vec<LexOrdering>> {
895+
let keys: Vec<_> = ordering
896+
.iter()
897+
.filter(|sort_expr| self.eq_group.is_expr_constant(&sort_expr.expr).is_none())
898+
.collect();
899+
let mut implied = vec![];
900+
for (idx, key) in keys.iter().enumerate() {
901+
if let Some(rest) =
902+
self.implied_ordering(key, keys[idx + 1..].iter().copied())?
903+
{
904+
let prefix = keys[..idx].iter().copied().cloned();
905+
implied.extend(LexOrdering::new(prefix.chain(rest)));
906+
}
907+
}
908+
Ok(implied)
909+
}
910+
831911
/// Returns the ordering that the normal ordering `[leading, rest..]`
832912
/// implies through an equality on its leading expression, if any.
833913
///

0 commit comments

Comments
 (0)