yadavay-amzn opened a new pull request, #56485: URL: https://github.com/apache/spark/pull/56485
### What changes were proposed in this pull request? Add `classOf[First]` and `classOf[Last]` to `WindowSegmentTree.EligibleAggregates`, routing First/Last window aggregates through the segment-tree path established by SPARK-56546 (sliding) and SPARK-57220 (shrinking) instead of the legacy O(N x W) sliding / O(N^2) shrinking frame implementations. No new frame class, no new SQLConf, no dispatcher changes -- the existing dispatcher branches in `WindowEvaluatorFactoryBase` already gate on `eligibleForSegTree`, which calls `WindowSegmentTree.isEligible`. ### Why are the changes needed? `First` and `Last` were previously denylisted as "order-dependent". This was over-conservative: order-dependence in row-traversal order is exactly what `WindowSegmentTree.query` provides. The query walks left-to-right (left partial -> full blocks ascending -> right partial; within a block, `queryDescend` walks children in ascending index order). `First.mergeExpressions` and `Last.mergeExpressions` are correct under that traversal -- they pick the row-order extreme across any contiguous range. For IGNORE NULLS the same merge is mode-agnostic: per-row `updateExpressions` only set `valueSet=true` on non-null values, so a per-block partial of `(null, false)` for an all-NULL block is correctly skipped when merged with a later non-null block. JIRA: https://issues.apache.org/jira/browse/SPARK-57424 **Note: this PR depends on #56291 (SPARK-57220).** It is currently in draft mode because it is based on the SPARK-57220 branch. Once #56291 merges into master, this branch will be rebased onto master and marked ready for review. ### Does this PR introduce _any_ user-facing change? Yes -- when `spark.sql.window.segmentTree.enabled=true`, FIRST/LAST window aggregates over sliding or shrinking ROWS/RANGE frames execute through the segment-tree path instead of the legacy frame implementations. Same opt-in conf (default off), same eligibility allowlist mechanism, same fallback below `minPartitionRows`, same SQLMetrics. No public API changes. ### How was this patch tested? * `WindowSegmentTreeAllowlistSuite`: 4 routing tests added for `first / last / first_ignore_nulls / last_ignore_nulls`; previous "falls through" negative tests flipped; mixed-allowlist test updated to use `collect_list` (still on the denylist). * `SegmentTreeWindowFunctionSuite`: 6 oracle equivalence tests covering sliding First/Last respect-nulls and ignore-nulls, all-NULL columns in both modes, and a dedicated stretches-of-consecutive-NULLs test for the IGNORE NULLS merge path. * `UnboundedFollowingSegmentTreeSuite`: 5 oracle equivalence tests covering shrinking First/Last respect-nulls and ignore-nulls plus all-NULL boundary case. * All 97 tests in the three suites pass; 33 adjacent segtree tests pass unchanged; scalastyle clean. ### Benchmark `FirstLastSegmentTreeWindowBenchmark` on Linux x86_64 (Intel Xeon Platinum 8259CL @ 2.50GHz, OpenJDK 25.0.3+9-LTS): Sliding frame `[-1000, +1000]` at N=10K: | Aggregate | Naive | Segtree | Speedup | |---|---|---|---| | FIRST respect-nulls | 414 ms | 94 ms | 4.4x | | LAST respect-nulls | 728 ms | 101 ms | 7.2x | | FIRST ignore-nulls | 528 ms | 86 ms | 6.1x | | LAST ignore-nulls | 913 ms | 91 ms | 10.0x | Shrinking frame `[CURRENT ROW, UNBOUNDED FOLLOWING]` at N=10K: | Aggregate | Naive | Segtree | Speedup | |---|---|---|---| | FIRST respect-nulls | 2,158 ms | 79 ms | 27.5x | | LAST respect-nulls | 2,412 ms | 79 ms | 30.6x | | FIRST ignore-nulls | 2,363 ms | 76 ms | 30.9x | | LAST ignore-nulls | 3,399 ms | 79 ms | 43.0x | N-sweep on FIRST shrinking: | N | Naive | Segtree | Speedup | |---|---|---|---| | 5K | 580 ms | 64 ms | 9.1x | | 25K | 13,407 ms | 107 ms | 125.5x | | 50K | 53,784 ms | 172 ms | 312.0x | | 100K | -- | 287 ms | -- | Naive at N=100K is omitted (extrapolated cost ~3-4 min/iter); segtree path stays sub-second. ### Was this patch authored or co-authored using generative AI tooling? Yes. -- 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]
