Anupam Yadav created SPARK-57424:
------------------------------------
Summary: 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
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: [email protected]
For additional commands, e-mail: [email protected]
