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]