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]

Reply via email to