Skip to content

BoundedWindowAggExec: evaluate small partitions of window functions such as last_value without per-partition state #27463

Open

Description

@comphead

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 StandardWindowExpr too, at least for first_value, last_value and nth_value with an UNBOUNDED PRECEDING frame start. For last_value(x) IGNORE NULLS from UNBOUNDED PRECEDING to CURRENT ROW, one pass over the batch can find each row's result index, resetting at partition boundaries and taking peer rows into account for RANGE. One take for the whole batch then replaces a take or a ScalarValue per 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.

Additional context

Related: #26541, #27400, #27410, #23197, #26533.

Activity

  1. self-assigned this
    on Nov 15, 2026
  2. changed the title [-]`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[/+] on Nov 15, 2026
  3. Sunninsky commented on Nov 16, 2026

    @Sunninsky

    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 NthValueEvaluator evaluates them with a single evaluate_ranges call, so there is one take instead of one per partition.

    I ran your four queries unchanged with datafusion-cli built with release-nonlto from main at 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_compute of BoundedWindowAggExec, median of 6 runs (min and max are within 4% of the median):

    Query main #27410 #27466
    1. last_value(s) IGNORE NULLS, 10 carried columns 14.7 s 1.18 s 1.87 s
    2. last_value(s) IGNORE NULLS, no carried columns 12.1 s 1.10 s 1.77 s
    3. last_value(i) IGNORE NULLS on an int, 10 carried columns 8.07 s 0.915 s 1.58 s
    4. max(i), 10 carried columns 9.37 s 0.913 s 5.86 s

    The 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_partitions and evaluates_frames_independently in #27466, evaluate_complete_partitions and evaluate_segments in #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 and RANGE offset frames, and row_number / rank / lag. Does that order work for you, or would you split it differently?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

enhancementNew feature or requestperformanceMake DataFusion faster

Type

No type

Projects

No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions