akupchinskiy opened a new issue, #27516:
URL: https://github.com/apache/datafusion/issues/27516
### Describe the bug
With default settings, string columns are `Utf8View`. A window over such a
column keeps every
data buffer it has seen. Two symptoms:
1. **A plain `lag` over unsorted data gets much slower than with `Utf8`.**
On 8M rows,
`BoundedWindowAggExec` takes 2.1–2.3 s, vs 0.40–0.43 s with `Utf8`
(5–6x). The whole
query takes 2.6–2.9 s, vs 0.74–0.77 s.
2. **On an unbounded input, memory grows with every row and is never
released.** The memory pool
does not see it, so a memory limit does not stop it.
### To Reproduce
#### 1. `lag` after a sort
```sql
COPY (SELECT (value * 7919) % 8000000 AS ts,
concat('key-', lpad(CAST(value AS VARCHAR), 56, '0')) AS s
FROM generate_series(1, 8000000) AS t(value))
TO 'events.parquet';
CREATE EXTERNAL TABLE events STORED AS PARQUET LOCATION 'events.parquet';
EXPLAIN ANALYZE
SELECT count(*), max(prev) FROM (SELECT lag(s, 1) OVER (ORDER BY ts) AS prev
FROM events);
```
`main` d9752d6, three runs each:
| | total | `BoundedWindowAggExec` `elapsed_compute` |
|---|---|---|
| `Utf8View` (default) | 2.76 / 2.85 / 2.57 s | 2.13 / 2.30 / 2.19 s |
| `Utf8` (`SET datafusion.execution.parquet.schema_force_view_types = false`
before `CREATE`) | 0.77 / 0.74 / 0.75 s | 0.42 / 0.40 / 0.43 s |
The plan is scan → sort → merge → window. In this reproduction, the batches
reaching the window
after sort and merge reference buffers spanning nearly the entire string
column:
`SortPreservingMergeExec` reports 466 GB of cumulative `output_bytes` over
977 batches. The window
appends every batch to its partition buffer and keeps all those buffer
entries. We observed the
cost growing faster than linearly: in one run on 16M rows, the window took
about 25 s. Peak memory
is the same with both types here (the sort holds the whole input anyway);
this case is about time.
#### 2. Unbounded input
```sql
-- stream.sql; run as: datafusion-cli -q --format csv -m 256m -f stream.sql
> /dev/null
CREATE UNBOUNDED EXTERNAL TABLE events (ts BIGINT NOT NULL, s VARCHAR NOT
NULL)
STORED AS CSV LOCATION 'rows.csv' WITH ORDER (ts ASC) OPTIONS
('format.has_header' 'false');
SELECT ts, lag(s, 1) OVER (ORDER BY ts) AS prev FROM events;
```
The input is fed from a FIFO with `mkfifo rows.csv && python3 writer.py >
rows.csv`, where
`writer.py` is:
```python
import os, sys
for i in range(10**12):
sys.stdout.write(f"{i},{os.urandom(30).hex()}\n")
```
Memory of the `datafusion-cli` process, with `-m 256m`:
| rows received | 4M | 8M | 13M | 17M |
|---|---|---|---|---|
| `main` | 279 MB | 551 MB | 825 MB | 1,101 MB |
This is macOS `footprint`, which also counts compressed pages. RSS shows the
same growth when the
strings don't compress: in another run, RSS passed 3 GB after 49M rows, 12x
the configured limit,
when our harness stopped it. Left running, a third run reached a 12 GB
footprint after 198M rows.
In this workload the process keeps ~60–65 bytes per row, i.e. the strings of
every row it has seen.
The query never fails with `ResourcesExhausted`, because the window reserves
no memory (#26707).
Nothing stops the growth. `BoundedWindowAggExec` exists to evaluate windows
on unbounded inputs in
bounded memory; with a `VARCHAR` column it doesn't.
The same happens without a stream, as memory proportional to the input. For
example, a sorted
Parquet file declared `WITH ORDER` and read through `lag(s)` / `lead(s)` /
`row_number()` keeps
~600 MB on 8M rows, vs ~140 MB with `Utf8`.
It is worse when one window combines a lookahead function with a string
result, e.g. previous and
next values:
```sql
SELECT lead(k) OVER (ORDER BY k), lag(s) OVER (ORDER BY k) FROM t; -- t
sorted by k, 8M rows
```
`lag(s)` results are computed before `lead(k)` can emit their rows, so they
wait in the window
across batches and keep growing the same buffer list. Peak RSS is 0.8–1.1 GB
(~130 MB with the
fix), and the window reports 461 GB of cumulative `output_bytes`.
### Expected behavior
A window that keeps a bounded number of rows across batches should not
accumulate the buffer-list
entries of all batches it has seen. Its per-batch work and memory should not
grow with the number
of batches that came before. A kept row still pins the buffer it points
into, as any slice does.
### Additional context
#### Mechanism
In short: the operator prunes the rows it keeps with `slice`, a sliced
`Utf8View` column keeps its
whole data buffer list, and the next `concat_batches` copies that list.
`Utf8` is not affected,
because its `concat` copies only the selected bytes.
<details><summary>Details</summary>
The operator keeps the rows it still needs in a `RecordBatch` per partition
and in an input buffer:
- it extends them with `concat_batches` on every input batch
(`PartitionBatchState::extend`,
`PartitionSearcher::update_partition_batch`);
- it prunes them with `slice` (`prune_partition_batches`,
`prune_input_batch`).
A slice of a `Utf8View` column keeps its whole data buffer list, and
`concat` copies the lists of
both inputs (`GenericByteViewBuilder::append_array`), referenced or not. So
after `k` batches a
one-row buffer lists the data buffers of all `k` batches:
- the `k`-th `concat` clones a list of about `k · b` entries (`b` buffers
per batch), which is
O(k² · b) in total;
- every buffer stays allocated.
The results a window expression keeps across batches
(`WindowAggState::out_col`) are pruned the
same way, so they grow the same way when expressions in one window emit at
different rates.
</details>
#### Who is affected
Windows that keep a partition alive across many batches:
- no `PARTITION BY`, or a few large partitions (per tenant, per symbol);
- any window on an unbounded input;
- a column of strings longer than 12 bytes, used by the function (`lag`,
`lead`, `first_value`,
`last_value`, `nth_value`) or passed through the window.
Windows whose partitions end after a few batches (e.g. per user on sorted
data) avoid the
accumulation: their state is dropped when the partition ends. In our
short-partition controls the
fix made no measurable difference.
#### Workaround
Read strings as `Utf8`:
- `SET datafusion.execution.parquet.schema_force_view_types = false` for
Parquet;
- `SET datafusion.sql_parser.map_string_types_to_utf8view = false` for
`VARCHAR` columns declared
in DDL (CSV, JSON, streams).
Both must be set before the table is created. They turn off view types for
every query, not just
windows.
#### Possible fix
When pruning, rewrite the kept view columns, and the kept results, to list
only the buffers they
reference. Buffer indices are remapped and no string bytes are copied. The
rewrite is amortized: it
is attempted again only when a column's list has doubled. A list that stops
growing may keep unused
entries until it grows again or empties. A PR follows.
#### Related
- #26707: window operators reserve no memory.
- #25712, #26606: the same buffer-list growth on the hash join build side.
- #27400 / #27410: bulk window evaluation. It drops unused columns from the
partition buffers,
which fixes a string that only passes through e.g. `row_number()`. It does
not cover columns read
by the function (`lag(s)` / `lead(s)`), which both examples above use, or
the input buffer.
- arrow-rs#10692: `append_array` keeps duplicate buffers; it was closed in
favour of cheaper cloning.
#### Environment
- DataFusion `main` d9752d6 (arrow 60.1.0), `datafusion-cli` built with the
`release-nonlto` profile.
- macOS arm64, 10 cores, 16 GB.
- Default configuration (`target_partitions = 10`, `batch_size = 8192`).
### 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]