cetra3 opened a new issue, #27390:
URL: https://github.com/apache/datafusion/issues/27390
> Claude (an AI agent) is raising this issue on behalf of @cetra3.
## Describe the bug
`first_value` and `last_value` over a nested value (struct, list or map)
that contains a `Utf8View` or `BinaryView` field take time quadratic in the
number of groups. The same query with a `Utf8` field runs in linear time.
The cost is in the final aggregation stage. Each `merge_batch` call runs
synchronously for the whole batch and does not yield. So a query of this shape
can hold every thread of the runtime for minutes, and it does not respond to
cancellation during that time. We found this when one such query stopped all
other queries on a service from making progress.
## To Reproduce
```sql
SET datafusion.execution.target_partitions = 8;
-- Control: a Utf8 field. 32,000 groups: 24 ms.
SELECT count(c) FROM (
SELECT first_value(struct('a string over 12 bytes')) AS c
FROM generate_series(1, 32000) GROUP BY value::text
);
-- A Utf8View field. 16,000 groups: 2.0 s.
SELECT count(c) FROM (
SELECT first_value(struct(arrow_cast('a string over 12 bytes',
'Utf8View'))) AS c
FROM generate_series(1, 16000) GROUP BY value::text
);
-- A Utf8View field. 32,000 groups: 5.9 s.
SELECT count(c) FROM (
SELECT first_value(struct(arrow_cast('a string over 12 bytes',
'Utf8View'))) AS c
FROM generate_series(1, 32000) GROUP BY value::text
);
```
I measured these with `SessionContext::new()` on `main` at
f94aaa1876581d7010b0d643aded9b691f0c30e7. Twice the groups takes about three
times as long.
Notes on the shape of the query:
- The string must be longer than 12 bytes. A shorter value is stored inline
in the view and has no data buffer.
- The group key must arrive out of order. `value::text` does this. With an
ordered key, the partial stage emits groups early, the state batches stay
small, and the cost stays linear.
- `count(c)` keeps `first_value` in the plan. `count(*)` lets the optimizer
remove it.
## Expected behavior
The `Utf8View` query runs in about the same time as the `Utf8` query, and
its time grows linearly with the number of groups.
## Additional context
The path is `GenericValueState` in
`datafusion/functions-aggregate/src/first_last/state.rs`, which #23628 added
for nested values.
1. In the partial stage, `GenericValueState::update` stores each winning row
as a `ScalarValue` and calls `compact()` on it. For a view array, `compact()`
gives the value its own data buffer.
2. `GenericValueState::take` builds the state array with
`ScalarValue::iter_to_array`. That calls arrow's `concat`, which keeps every
data buffer of every input. So the state array for N groups has N data buffers.
3. In the final stage, `merge_batch` calls `GenericValueState::update` for
each winning row of that state array. `compact()` copies the row through
`MutableArrayData`, which clones the list of all N data buffers of the source
array before `gc` drops the unused ones.
So each merged row costs O(N), and a merge of N groups costs O(N^2).
#24742 reports a constant per-row cost on the same state path. This report
is a separate problem with a different cause. It is quadratic, and it applies
only to values that contain view types. #23682 would rewrite peer `first_value`
/ `last_value` calls into one struct aggregate, so it would send more queries
onto this path.
A fix that compacts the view buffers of the array in
`GenericValueState::take`, only when the data type contains a view type, brings
the 32,000-group query down to about 30 ms. Every value in that array already
owns its bytes, so the compacted array is not larger than the values. I will
open a PR with this fix.
## Willingness to contribute
I plan to contribute a fix for this bug independently
--
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]
