[jira] [Updated] (SPARK-57424) Add First/Last to segment-tree window aggregate allowlist

["ASF GitHub Bot (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-57424?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

ASF GitHub Bot updated SPARK-57424:
-----------------------------------
    Labels: pull-request-available  (was: )

> Add First/Last to segment-tree window aggregate allowlist
> ---------------------------------------------------------
>
>                 Key: SPARK-57424
>                 URL: https://issues.apache.org/jira/browse/SPARK-57424
>             Project: Spark
>          Issue Type: Improvement
>          Components: SQL
>    Affects Versions: 4.3.0
>            Reporter: Anupam Yadav
>            Priority: Major
>              Labels: pull-request-available
>
> SPARK-56546 introduced segment-tree-based window-frame aggregation for sliding ROWS/RANGE frames, and SPARK-57220 extended it to shrinking frames ({{... BETWEEN <lower> AND UNBOUNDED FOLLOWING}}). Both rely on {{WindowSegmentTree.EligibleAggregates}} -- a static allowlist of {{DeclarativeAggregate}} subclasses safe for segment-tree execution.
> {{First}} and {{Last}} were previously excluded from this allowlist, marked "order-dependent", and continued to use the legacy {{SlidingWindowFunctionFrame.write}} (O(N x W)) and {{UnboundedFollowingWindowFunctionFrame.write}} (O(N^2)) paths.
> 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}} = {{if(valueSet.left, left, right)}} and {{Last.mergeExpressions}} = {{if(valueSet.right, right, left)}} 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.
> h2. Proposal
> Add {{classOf[First]}} and {{classOf[Last]}} to {{WindowSegmentTree.EligibleAggregates}}. No new frame class, no new SQLConf, no dispatcher changes -- the existing dispatcher branches in {{WindowEvaluatorFactoryBase}} (shrinking and moving) already gate on {{eligibleForSegTree}}, which calls {{WindowSegmentTree.isEligible}}. Update the docstring to enumerate First/Last and document the audit explicitly.
> h2. Behaviour
> * Same opt-in conf: {{spark.sql.window.segmentTree.enabled=false}} (default off).
> * Same eligibility gate (DeclarativeAggregate, no FILTER, no DISTINCT, supported frame type).
> * Same fallback for partitions below {{spark.sql.window.segmentTree.minPartitionRows}}.
> * Both respect-nulls (the default for {{first()}} / {{last()}}) and IGNORE NULLS are routed.
> * No analyzer / SQL grammar / plan-shape changes.
> h2. 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 (best) || segtree (best) || 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 (best) || segtree (best) || 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.
> h2. Test surface
> * {{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.
> h2. Out of scope
> * New frame class for First/Last (a future O(1)-amortized monotonic-deque path is a separate optimization).
> * {{NthValue}} over moving frames (separate JIRA).
> * {{CollectList}}, {{CollectSet}}, {{Percentile}}, {{ApproxPercentile}}, {{HyperLogLogPlusPlus}} -- still excluded.
> * {{ImperativeAggregate}} and UDAFs -- still excluded.
> Follows up SPARK-56546 and SPARK-57220.



--
This message was sent by Atlassian Jira
(v8.20.10#820010)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org