Sunninsky commented on PR #27410:
URL: https://github.com/apache/datafusion/pull/27410#issuecomment-6930034103

   Thanks @alamb. This PR does not add a segment tree. It makes the algorithm 
DataFusion already uses cheaper per row.
   
   Frame offsets in DataFusion are constants, so both ends of a frame only move 
forward. A moving frame is already evaluated with the paper's removable 
cumulative aggregation (4.3.3: add the rows that enter the frame, subtract the 
rows that leave it; MIN and MAX use an amortized O(1) queue, so they are O(n) 
and not the O(n log n) of Table 1, as noted in #4904), and `RANGE` bounds 
advance row by row (4.2). On `main` the cost per row does not depend on the 
frame size (`SUM` over `ROWS` 5..5 and 500..500: 261 and 259 ns, #27400), so 
what costs is the constant: a `Vec<ScalarValue>` copied for every step of the 
`RANGE` search, array slices, dynamic calls, a `ScalarValue` per row. The PR 
runs the same two steps, in the same order, on typed slices for a whole run of 
rows (`SUM` over `RANGE BETWEEN 5 PRECEDING AND 5 FOLLOWING`: 779 to 21 ns of 
CPU per input row). Of the two "raw evaluation speed in the core" directions in 
#23197 this is #15607 ([as scoped there](https://github.com/apache/dat
 afusion/issues/15607#issuecomment-2857839305)), not #4904.
   
   A tree helps where this cannot: frame bounds that differ per row (DataFusion 
rejects them when planning, see #15714), aggregates that cannot subtract 
(`bit_and` and `string_agg` fail in a moving frame: "`retract_batch` is not 
implemented"), and one very large partition spread over threads (#22355; not 
addressed here, the numbers are single-threaded). For constant offsets the 
paper's Fig. 10 has removable cumulative ahead of the tree, and in 5.7 the tree 
overtakes it only on very large frames with many cores. I did not build a tree 
to compare.
   
   ("Segments" in `evaluate_window_segments` are runs of whole partitions 
inside one batch, not tree nodes.)
   


-- 
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]

Reply via email to