Repository navigation
A sort by a rolling max, min, count or unsigned sum is dropped when DataFusion misreads the window's order #354
Description
Problem
A sort by the output of a rolling(...) aggregate can be dropped, so its rows come back in the window's order instead of sorted. It happens when the window has no partition_by, for rolling().max() of any type but float, rolling().count() and unsigned rolling().sum(). min gets the same kind of claim (see Cause):
from ltseq import LTSeq
t = (
LTSeq.from_dict({"x": [3, 2, 1, 0]})
.sort("x", desc=True)
.derive(m=lambda r: r.x.rolling(2).max())
)
[r["m"] for r in t.sort("m").to_dicts()] # [3, 3, 2, 1]
[r["m"] for r in t.collect().sort("m").to_dicts()] # [1, 2, 3, 3]Probed on the #353 branch (7e6b042):
Window, no partition_by |
Table order | sort("m") lazily |
after collect() |
|---|---|---|---|
rolling(2).max(), int64 |
x descending |
[3, 3, 2, 1] |
[1, 2, 3, 3] |
rolling(2).max(), string |
x descending |
['c', 'c', 'b'] |
['b', 'c', 'c'] |
rolling(2).sum(), uint64 |
x descending |
[3, 5, 3, 1] |
[1, 3, 3, 5] |
rolling(2).count(), int64 [1, 2, None, None] |
x ascending (NULLs last) |
[1, 2, 1, 0] |
[0, 1, 1, 2] |
These go through DataFusion's own aggregates on that branch as on main. #353 changes only float min/max, and sum and count not at all. I have not rerun them on a main build. With partition_by, the same max window sorted correctly, and so did signed sum, which DataFusion does not mark as monotonic.
Cause
DataFusion 55's window_equivalence_properties (datafusion-physical-plan, src/windows/mod.rs, the branch for a causal sliding frame) adds an output ordering for a set-monotonic aggregate whose argument is already ordered. With no partitioning, it claims ascending output for an increasing aggregate (max, count, unsigned sum) whatever direction the argument is ordered in, because of increasing && (asc || no_partitioning). It claims descending output for min the same way. A rolling max over a descending argument falls. A non-NULL count falls once NULLs enter the frame. EnforceSorting then removes a sort that the output does not satisfy. I found no upstream report by searching apache/datafusion.
Not checked: the min claim is DESC NULLS LAST, while sort(desc=True) asks for NULLs first, so no dropped sort was seen for it. Whether a window order_by or another consumer of the ordering can reach it is unknown.
Impact
sort returns rows out of order, and so does everything that reads the sorted order after it: slice, head, tail, positional operations and writers. No error is raised.
Why it is not fixed in #353
#353 is about float min/max (#253). Its review found the float form of this problem, a running float extreme that is monotonic only in the contract's order, and #353 fixes that by having float min/max claim no monotonicity. The rest predates #353, involves aggregates it does not touch, and needs the decision below.
Open question
set_monotonicity sees only the data type, not the frame, so an aggregate cannot drop the claim for sliding frames alone. The two options seen so far are to report the bug upstream and wait for a fix, or to have ltseq's max, min, count and sum claim nothing. The second also gives up the correct sort elision after cum_max, cum_min and unsigned cum_sum, whose frames only grow.
Acceptance criteria
- For
rolling(...).max(),.min(),.count()and.sum()over every argument type, with the argument sorted ascending or descending, with and without NULLs and with and withoutpartition_by,t.sort("m")andt.sort("m", desc=True)return the rows thatt.collect().sort(...)does, whole and throughslice. cum_*windows keep correct results.
Found while addressing #353 (comment).
Activity
iceboundrock commentedon Nov 10, 2026
Follow-up plan (2026-11-09): upstream linkage, two-phase fix, and expanded acceptance
Related Apache DataFusion issue
ORDER BY ... NULLS LASTon a runningMAXwindow function puts the NULL row first apache/datafusion#27267 — Wrong results:ORDER BY ... NULLS LASTon a runningMAXwindow function puts the NULL row first (open as checked on 2026-11-09).MAXwith NULL placement; this issue additionally covers slidingmax/min/count/unsigned sumwith nopartition_by, input direction, and elements entering/leaving a frame. Fixing #27267 alone may not fix A sort by a rolling max, min, count or unsigned sum is dropped when DataFusion misreads the window's order #354.branch-56, andmainfound the problematicwindow_equivalence_propertiescausal sliding-frame condition (increasing && (asc || no_partitioning), and the corresponding decreasing case) still present. This is not a runtime regression result for those branches.Recommended implementation: two phases
Phase 1 — correctness first (P0 candidate; confirm against the current launch policy).
mainand pinned DataFusion; record exact HEAD/dependency versions, observed results, and physicalEXPLAINevidence identifying an incorrectly eliminated sort. Check whether other changes have already fixed or altered any paths.SetMonotonicity::NotMonotonicfor impactedmin/max/count/sumvariants so that unsupported ordering claims cannot remove required sorts. Confirm which aggregate wrappers and call sites actually supply those properties; avoid unnecessary semantic/accumulator rewrites.Phase 2 — recover safe optimizations (only if justified by evidence).
cum_min/cum_max/cum_sumand rolling aggregates, including elapsed time, peak memory, and addedSortExec/TopK operators; vary data size, batches, partitions, and in-memory/Parquet inputs.Expanded acceptance criteria (proposed additions to the issue's existing criteria)
Correctness matrix:
rolling(...).min/max/count/sumand applicablecum_*variants. Verify all supported argument types; explicitly include signed/unsigned integer, float (including the fix: order float min and max by the contract on every path (#253) #353 semantics), string for extrema, and decimals where supported. Record unsupported combinations instead of silently omitting them.sort("m")andsort("m", desc=True); correct NULLS FIRST/LAST semantics according to the current LTSeq contract; ties and deterministic row identity checks where applicable.countchanging non-monotonically as NULLs enter/leave.partition_by, with one partition key, and with multiple partitions.slice/head/tail; relevant positional operations and writers; test pipelines where an optimizer could drop a requiredSortExec.t.collect().sort(...)(which remains a useful differential cross-check). Compare stable row IDs when aggregate values tie; honor documented tie-order guarantees.EXPLAINplans and prove a required sort is preserved (or ordering is otherwise correctly guaranteed). Retain legitimate optimizations when possible.cum_*results remain correct; fix: order float min and max by the contract on every path (#253) #353 floatmin/maxsemantics, grouped/ungrouped aggregates, and unaffected signedsumbehavior remain intact.Decision proposal: prioritize correctness and an LTSeq-local fix, track DataFusion #27267 without making upstream actions or upgrades a prerequisite. This comment proposes implementation and acceptance scope; it does not claim the fix has been implemented or verified.
Make window aggregates claim no output order (#354) (#391)