akupchinskiy opened a new pull request, #27520:
URL: https://github.com/apache/datafusion/pull/27520

   ## Which issue does this PR close?
   
   - Closes #27516.
   
   ## Rationale for this change
   
   Window functions over string columns (`Utf8View`, the default) get slow 
after a sort, and on an
   unbounded input their memory grows with every row. A memory limit does not 
stop the growth. The
   issue has repros and numbers.
   
   The cause: `BoundedWindowAggExec` prunes the rows it keeps across batches 
with `slice`. A sliced
   `Utf8View` column keeps its whole data buffer list, and the next 
`concat_batches` copies that
   list. After `k` input batches, the kept rows list the buffers of all `k` 
batches.
   
   ## What changes are included in this PR?
   
   A new module, `windows/view_buffers.rs`, replaces the `slice` calls that 
prune what the operator
   keeps across batches:
   - the partition batches (`prune_partition_batches`);
   - the input buffer (`prune_input_batch`);
   - the results each window expression keeps per partition 
(`WindowAggState::out_col`, in
     `prune_out_columns`).
   
   Each pruned batch is handled as follows:
   - **No view columns, or none due:** the same slice as before.
   - **A view column that is due:** rewritten so that its buffer list holds 
only the buffers its
     kept views reference, each once (identified by pointer and length). View 
buffer indices are
     remapped.
     - No string bytes are copied; the kept entries are the original `Buffer`s.
     - Columns that are the same array are rewritten once and stay shared.
   - **Nothing kept:** a view column becomes an empty array with no buffers.
   
   A rewrite scans the kept rows, so it is amortized per column by a watermark. 
A column is due again
   only after both:
   - its buffer list has at least doubled since the previous attempt;
   - the list has grown by at least one entry per 4096 kept rows.
   
   This way a frame that spans many batches is not rescanned on every batch. 
The watermarks live in
   the operator's stream; there are no public API changes.
   
   Known limitation: a list that stops growing is not re-examined until it 
grows again or is emptied.
   
   Not included:
   - memory reservation: the operator still reserves nothing (#26707);
   - bulk evaluation, which is #27410 (see below).
   
   ### Benchmarks
   
   Setup: `release-nonlto` `datafusion-cli` on macOS arm64, default settings, 
interleaved runs.
   
   | | `main` | this PR | `Utf8` on `main` |
   |---|---|---|---|
   | `lag(s)` after a sort, 8M rows: window `elapsed_compute` | 2.13–2.30 s | 
0.64–0.66 s | 0.40–0.43 s |
   | `lead(k)` + `lag(s)`, default frames, sorted 8M rows: peak RSS | 807–893 
MB | 122–132 MB | — |
   | sorted Parquet `WITH ORDER`, 8M rows, `lag(s)`: peak RSS | 603–608 MB | 
113–126 MB | 139–145 MB |
   | unbounded CSV `lag(s)`: memory (macOS footprint) after 198M rows | 12.3 
GB, growing | 16 MB, flat | — |
   
   Regression checks:
   
   | | `main` | this PR |
   |---|---|---|
   | 256 `Int64` columns, `batch_size = 37`: `row_number` / `lead` window | 
163–166 / 250–260 ms | 161–165 / 251–260 ms |
   | 512 `Utf8View` columns, 30k rows, `batch_size = 37`: `row_number` window | 
2.30–2.79 s | 205–218 ms |
   | 3M-row frame of 1M `PRECEDING`, with a view column: window | 545–597 ms | 
541–581 ms |
   
   ### Relation to #27410
   
   The two PRs are complementary and touch mostly different code:
   - #27410 drops unused columns from the partition buffers. That fixes a 
string that only passes
     through, e.g. `row_number()`.
   - This PR fixes columns the function reads (`lag(s)`, `lead(s)`), the input 
buffer and the kept
     results.
   
   In the sort example, the window takes 3.3–3.9 s with #27410 alone and about 
0.02 s with both. The
   "both" number was measured with an earlier revision of this patch.
   
   On top of #27410, this patch needs three small rebase adjustments:
   - a `mod.rs` context line;
   - the private stream constructor and the `get_search_algo` calls in the 
operator test helper;
   - one unused import.
   
   ## What is the testing strategy for this PR?
   
   - **Unit tests in `windows::view_buffers` (4):**
     - remap correctness: nulls, inline views, sliced input, `BinaryView`, 
aliased columns, nothing
       kept, and kept rows that reference no buffer;
     - duplicate entries merged by pointer and length;
     - the plain-slice fast path, which shares the input's buffers;
     - trigger boundaries and amortization.
   - **Operator tests in `windows::bounded_window_agg_exec` (4).** They drive 
`BoundedWindowAggStream`
     and, after every batch, check how many buffers are listed by the input 
buffer, the partition
     batches and the emitted columns. The cases are `lead(ts)`, `lag(s)`, 
`InputOrderMode::Linear`, and
     `lead(ts)` next to `last_value(s)` / `lag(s)`. The values are checked as 
well.
   - **`window_view_small_batches.slt`,** run at `batch_size` 1, 3 and 8192: 
pass-through,
     default frame, `lead` / `lag` with nulls, `first_value` / `last_value` 
over `ROWS`, sorted
     partitions.
   
   With plain `slice` restored, 7 of the 8 new unit tests fail. The remaining 
one tests the fast path.
   
   ## Are there any user-facing changes?
   
   No. Results are unchanged; window queries over `Utf8View` / `BinaryView` 
columns use less time and
   memory.
   
   AI assistance: I prepared the investigation, patch and tests with Claude 
(Anthropic). I have read
   and understand the whole change. The design choice I would most like 
feedback on is the
   amortization trigger (the doubling watermark and the one-entry-per-4096-rows 
term).
   


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