Repository navigation
Description
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.
Reproducer
-- 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);elapsed_compute of BoundedWindowAggExec, built from 73e0b03 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
StandardWindowExprtoo, at least forfirst_value,last_valueandnth_valuewith anUNBOUNDED PRECEDINGframe start. Forlast_value(x) IGNORE NULLSfromUNBOUNDED PRECEDINGtoCURRENT ROW, one pass over the batch can find each row's result index, resetting at partition boundaries and taking peer rows into account forRANGE. Onetakefor the whole batch then replaces atakeor aScalarValueper partition.
Keeping only the columns that the window expressions read in the partition batches is the first point of #26541 and is tracked there, not here. For reference, 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.
Activity
[-]`BoundedWindowAggExec`: evaluate small partitions of window functions such as `last_value` without per-partition state, and do not slice carried columns[/-][+]`BoundedWindowAggExec`: evaluate small partitions of window functions such as `last_value` without per-partition state[/+]BoundedWindowAggExechas a high fixed cost per partition when partitions are small #26541Sunninsky commentedon Nov 16, 2026
Thanks for the reproducer. Yes, #27410 covers this shape: the frames of all rows of the complete partitions of an input batch are computed in one pass and
NthValueEvaluatorevaluates them with a singleevaluate_rangescall, so there is onetakeinstead of one per partition.I ran your four queries unchanged with
datafusion-clibuilt withrelease-nonltofrommainat adffd19 (the merge base of both PRs), #27410 at e82bd18 and #27466 at ed7a1f7.target_partitions = 1, on a dedicated r7i.8xlarge node (Xeon Platinum 8488C), the process pinned to two cores.elapsed_computeofBoundedWindowAggExec, median of 6 runs (min and max are within 4% of the median):mainlast_value(s) IGNORE NULLS, 10 carried columnslast_value(s) IGNORE NULLS, no carried columnslast_value(i) IGNORE NULLSon an int, 10 carried columnsmax(i), 10 carried columnsThe results of queries 1, 3 and 4 are identical in all three builds, compared on all 5,000,000 rows. For #27466 on query 1 I get 7.9x, in line with your 5.3 s -> 0.65 s.
The two PRs overlap: both evaluate the complete partitions of a batch directly in
SortedSearch, each through its own new provided methods (evaluate_partitionsandevaluates_frames_independentlyin #27466,evaluate_complete_partitionsandevaluate_segmentsin #27410), and a trial merge of #27466 into #27410 conflicts in five files. #27466 is the smaller change, so I am happy for it to go first, and I can rebase #27410 on it afterwards. #27410 would then shrink to what #27466 does not cover, mainly aggregates over all complete partitions in one pass (query 4), bulk frame bounds for moving andRANGEoffset frames, androw_number/rank/lag. Does that order work for you, or would you split it differently?