comphead opened a new issue, #27463:
URL: https://github.com/apache/datafusion/issues/27463

   ### Is your feature request related to a problem or challenge?
   
   #26541 describes the fixed cost per partition in `BoundedWindowAggExec` when 
partitions are small. Its second point, evaluating the partitions that start 
and end inside one input batch directly, fits aggregate window expressions 
(`PlainAggregateWindowExpr`, `SlidingAggregateWindowExpr`). Window functions 
such as `first_value`, `last_value` and `nth_value` run as 
`StandardWindowExpr`, so they would still take the per-partition path.
   
   This shows up in Comet, which runs Spark's `last(x, ignoreNulls)` window as 
DataFusion's `last_value` window function. In a Spark job with about 2 rows per 
window partition, a 5-field struct argument and 23 carried columns, that window 
is the largest cost of its stage: 36 s per task of about 5M rows.
   
   The reproducer below runs in `datafusion-cli` on one partition. It builds 5M 
rows with about 2 rows per `(k1, k2, k3)` partition, a nullable 5-field struct 
`s` and 10 carried columns.
   
   <details><summary>Reproducer</summary>
   
   ```sql
   -- 5M rows. k1 has 32 rows each; k2 (3 values) and k3 (6 values) are chosen 
per row, so a
   -- (k1, k2, k3) partition holds about 2 rows. s is a nullable struct of 5 
fields, c0..c9 are carried.
   SET datafusion.execution.target_partitions = 1;
   CREATE TABLE t AS SELECT
     md5(CAST(value / 32 AS VARCHAR)) AS k1,
     CAST((value * 3812015801 + 1) % 2147483647 % 3 AS VARCHAR) AS k2,
     CAST((value * 2246822507 + 7) % 2147483647 % 6 AS VARCHAR) AS k3,
     value AS ts,
     CAST((value * 1664525091 + 3) % 2147483647 % 2 AS INT) AS i,
     CASE WHEN (value * 1013904223 + 5) % 2147483647 % 3 <> 0 THEN named_struct(
       'a', concat('a-', CAST(value % 40 AS VARCHAR)), 'b', value % 2 = 0, 'c', 
CAST(value % 30 AS INT),
       'd', concat('d-', CAST(value % 7 AS VARCHAR)), 'e', concat('e-', 
CAST(value % 5000 AS VARCHAR))) END AS s,
     concat('carried-0-', value) AS c0, concat('carried-1-', value) AS c1, 
concat('carried-2-', value) AS c2,
     concat('carried-3-', value) AS c3, concat('carried-4-', value) AS c4, 
concat('carried-5-', value) AS c5,
     concat('carried-6-', value) AS c6, concat('carried-7-', value) AS c7, 
concat('carried-8-', value) AS c8,
     concat('carried-9-', value) AS c9
   FROM generate_series(0, 4999999);
   SELECT round(5000000.0 / count(*), 2) AS rows_per_partition FROM (SELECT 
DISTINCT k1, k2, k3 FROM t);
   -- 1. last_value(struct) IGNORE NULLS with 10 carried columns
   EXPLAIN ANALYZE SELECT count(w), max(c0), max(c1), max(c2), max(c3), 
max(c4), max(c5), max(c6), max(c7), max(c8), max(c9)
   FROM (SELECT *, last_value(s) IGNORE NULLS OVER (PARTITION BY k1, k2, k3 
ORDER BY ts) AS w FROM t);
   -- 2. the same without carried columns
   EXPLAIN ANALYZE SELECT count(w) FROM (SELECT last_value(s) IGNORE NULLS OVER 
(PARTITION BY k1, k2, k3 ORDER BY ts) AS w FROM t);
   -- 3. last_value of an int with 10 carried columns
   EXPLAIN ANALYZE SELECT count(w), max(c0), max(c1), max(c2), max(c3), 
max(c4), max(c5), max(c6), max(c7), max(c8), max(c9)
   FROM (SELECT *, last_value(i) IGNORE NULLS OVER (PARTITION BY k1, k2, k3 
ORDER BY ts) AS w FROM t);
   -- 4. max(int), an aggregate window expression, with 10 carried columns
   EXPLAIN ANALYZE SELECT count(w), max(c0), max(c1), max(c2), max(c3), 
max(c4), max(c5), max(c6), max(c7), max(c8), max(c9)
   FROM (SELECT *, max(i) OVER (PARTITION BY k1, k2, k3 ORDER BY ts) AS w FROM 
t);
   ```
   
   </details>
   
   `elapsed_compute` of `BoundedWindowAggExec`, built from 73e0b0339 with the 
`release-nonlto` profile on an Apple M5 Max:
   
   | Query | `main` | Prototype of #26541's second point for aggregate window 
expressions |
   |---|---:|---:|
   | 1. `last_value(s) IGNORE NULLS`, 10 carried columns | 5.2 s | 5.3 s |
   | 2. `last_value(s) IGNORE NULLS`, no carried columns | 4.4 s | 4.5 s |
   | 3. `last_value(i) IGNORE NULLS` on an int, 10 carried columns | 2.9 s | 
2.9 s |
   | 4. `max(i)`, 10 carried columns | 3.4 s | 1.9 s |
   
   A profile of query 1 (macOS `sample`), as shares of the window's own time:
   
   | Part | Share |
   |---|---:|
   | `evaluate_partition_batches`: a `Vec<ScalarValue>` key and a slice of 
every column for each partition | ~20% |
   | `NthValueEvaluator::evaluate_ranges`, called once per partition, mostly a 
`take` of the struct | ~21% |
   | `NthValueEvaluator::memoize`: a `ScalarValue::try_from_array` of the 
struct for each partition | ~5% |
   | `WindowFrameContext::calculate_range` | ~5% |
   | `calculate_out_columns`: concatenating the per-partition outputs | ~10-16% 
|
   | `prune_partition_batches` | ~6-10% |
   
   ### Describe the solution you'd like
   
   - Evaluate complete partitions directly for `StandardWindowExpr` too, at 
least for `first_value`, `last_value` and `nth_value` with an `UNBOUNDED 
PRECEDING` frame start. For `last_value(x) IGNORE NULLS` from `UNBOUNDED 
PRECEDING` to `CURRENT ROW`, one pass over the batch can find each row's result 
index, resetting at partition boundaries and taking peer rows into account for 
`RANGE`. One `take` for the whole batch then replaces a `take` or a 
`ScalarValue` per partition.
   - Keep only the columns that the window expressions read in the partition 
batches, the first point of #26541. Without the 10 carried columns, query 1 
takes 4.4 s instead of 5.2 s.
   
   ### Describe alternatives you've considered
   
   #27410 (design in #27400) evaluates runs of small partitions in bulk and 
lists `first_value` among its shapes. If it covers `last_value IGNORE NULLS` 
over a `RANGE` frame with a struct argument, this issue overlaps with it.
   
   ### Additional context
   
   Related: #26541, #27400, #27410, #23197, #26533.
   


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