jayzhan211 opened a new pull request, #27191: URL: https://github.com/apache/datafusion/pull/27191
## Which issue does this PR close? - Closes #26762. ## Rationale for this change A window over an input whose ordering starts with a per-partition constant fails to plan with `SanityCheckPlan`. The query in #26762 worked through 54.1.0 and has failed since 55.0.0. Across 2,016 generated query runs, `main` has 4 of these failures and this PR has none, with the same rows wherever both plan. #23528 made normalized orderings keep per-partition constants, so that a merge of partitions still orders on them, but `add_constants` still drops them. `get_window_mode` calls `add_constants`, so it sees `[total]` and adds no sort, while `SanityCheckPlan` sees `[k, total]` and rejects the plan. This PR replaces #27140 and keeps its commit, which makes ordering checks skip a leading constant. That change is right but can't ship alone: sort pushdown then removes a sort below a projection because its input has the ordering, and a projection that drops `k` can no longer prove it. That adds 110 new failures in the same runs, including the #26762 query with `k` removed from the SELECT lists, which plans on `main` today. ## What changes are included in this PR? Start reading at `handle_projection_pushdown`. The decision I most want reviewed is the second row: how to handle a projection that loses the proof. | Where | Change | Why | |---|---|---| | `SortKeyWalk::new` | An ordering's head skips leading fixed expressions before the first key is pinned | Fixes #26762, and matches how the walk already defines a head | | `handle_projection_pushdown` | If the input has the ordering but the projection can't prove it, keep the sort above the projection | Prevents the 110 new failures | | `SortKeyWalk::is_fixed` | Return early for a column that isn't pinned or constant | The first row made single-key checks about 30% slower; with this, about 10% (roughly 35 ns) | **Why keep the sort, rather than have the projection drop the constant from the ordering?** That also gives 0 failures and avoids a sort, but it only handles constants. Keeping the sort covers any proof that needs a dropped column, so it also fixes a separate `branch-56` failure from #26747: `a = CAST(c AS DATE)` proves `[k, c]` from `[k, a, c]`, and then `a` is dropped. **Who is affected.** Plans with an ordering that starts with a per-partition constant, or whose proof needs a column that a projection drops. It can't stop halfway. **Worst case.** One redundant sort that `main` doesn't have, at one partition, when the proof needs a dropped column (a `PartialSortExec` on an unbounded input). At more partitions, `main` fails on that shape. ## What is the testing strategy for this PR? - `window.slt` covers the #26762 query and plan, a constant from an aggregate without `GROUP BY`, a projection that drops the constant, and the #26747 failure. Removing the projection check fails the last two; removing the walk change fails the first two and the unit test `leading_per_partition_constant_is_not_a_head`. - All SLT files pass with no existing plan changing, as do the `physical_optimizer` integration tests and the equivalence fuzz tests. <details> <summary>Rejected alternatives, generated query runs, benchmarks, and queries that still fail</summary> **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, and that case fails at `target_partitions = 4` too. **Generated runs.** Every combination of 6 inputs (function of a filtered column, aggregate without `GROUP BY`, whole-table window, `UNION ALL` of different constants, TopK, and a non-constant control), 3 orderings (`SUM` over `PARTITION BY k`, `ROW_NUMBER` over `PARTITION BY k`, TopK), 5 projections (keep, drop or rename `k`, and so on) and up to 12 consumers (ordered windows, aggregate, sort, TopK, sort-merge, hash and left joins), at `target_partitions` 1 and 4. | Build | Plan errors | New compared with `main` | Rows differ from `main` | |---|---|---|---| | `main` | 4 | n/a | n/a | | #27140 | 110 | 110 | 0 | | This PR | 0 | 0 | 0 | **`equivalence_properties` benchmark.** Best of 10 alternating runs per build, on a busy laptop, so treat these as approximate. `sql_planner` was not run. | Benchmark | `main` | This PR | |---|---|---| | `ordering_satisfy/1_key/8` | 371 ns | 396 ns | | `ordering_satisfy_requirement/1_key/8` | 300 ns | 338 ns | | `find_longest_permutation/1_expr/32` | 302 ns | 344 ns | | `window/4` | 1,537 ns | 1,192 ns | | `window/32` | 7,241 ns | 4,848 ns | **Still failing, not made worse by this PR.** Both use a table `t3(g, a, c)`, with `a` a `DATE` and `c` a `TIMESTAMP`. This fails on every build I tried, including before #23528: ```sql SELECT a, c, ROW_NUMBER() OVER (ORDER BY c) AS r FROM (SELECT a, c FROM t3 WHERE a = CAST(c AS DATE) ORDER BY a, c LIMIT 10) ORDER BY r; ``` This one passes at #23528 and fails on `main` at `target_partitions = 1`. I haven't bisected it: ```sql SELECT k, a, c, ROW_NUMBER() OVER (ORDER BY c) AS r FROM (SELECT lower(g) AS k, a, c FROM t3 WHERE g = 'a' AND a = CAST(c AS DATE) ORDER BY k, a, c LIMIT 10) ORDER BY r; ``` </details> ## Are there any user-facing changes? Affected queries plan again. No API changes. This is a candidate for `branch-56`: the patch applies cleanly there and all SLT files pass. -- 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]
