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]
