Skip to content

Commit b93ef03

Browse files
authored
fix: handle nested RANGE CURRENT ROW peers (#26067)
## Which issue does this PR close? Related to #24937. This PR fixes RANGE-window comparisons. #26689 tracks the related GROUPS, `rank()`, and `dense_rank()` results for logically equal dictionary nulls. ## Rationale for this change RANGE windows can return incorrect counts for ordinary lists containing nulls. ```sql SELECT count(*) OVER (ORDER BY l NULLS FIRST) FROM (VALUES ([NULL::int]), ([1]), ([NULL::int])) t(l); ``` The result should be `2, 2, 3`, but the old peer search returns `3, 3, 3`. Lists containing lists or structs can also fail with `Uncomparable values`, including during streaming execution in Linear mode. ## What changes are included in this PR? Use Arrow's logical comparison to find nested CURRENT ROW peers. A null dictionary key and a key pointing to a null dictionary value can encode the same nested value. The window frame state owns its comparator and reuses it while the ordering arrays are identical. Pruning releases the old arrays. Cloned states construct a comparator on demand. The public `WindowFrameStateRange` keeps its unwind-safety traits. Arrow's `partition` also recognizes the dictionary-null peers. It checks adjacent rows for every ordering column and materializes the group ranges when `ranges()` is called. A bounded window can resume partway through a partition after appending a batch. Keeping the boundary scan lets it resume from the previous frame without enumerating every group in the replacement buffer. Nested-type dispatch runs once per range calculation when either bound is CURRENT ROW. Linear-mode completion uses Arrow comparison and computes its Boolean result lazily once per partition evaluation. The SQL analyzer governs type admission, and finite RANGE offsets use the scalar arithmetic path. ## What is the testing strategy for this PR? `window.slt` covers the ordinary-list wrong result and tied `List<List>` and `List<Struct>` keys with a secondary sort key and one-row batches. The bounded and unbounded-following queries exercise `BoundedWindowAggExec` (Sorted) and `WindowAggExec`, respectively. The physical integration tests cover struct keys, Linear execution, and emission before EOF. In the descending streaming case, a row in another partition completes the waiting peers under `DESC NULLS LAST`, both when its key is smaller and when it is NULL. State tests cover nested dictionary nulls, cloning, pruning, and unwind safety. Validation at `39358f523` on upstream base `364613296` included the extended workspace suite (12,745 Rust tests passed, eight ignored, 535 SQL-logic files completed), formatting, all-target and all-feature Clippy with warnings denied, and the CI Clippy configuration. All ten bounded-window benchmark cases passed in smoke mode on both the base and the patch. License, spelling, TOML formatting, local Markdown links, and unused dependency checks passed. Earlier validation at `99100274` also covered generated docs and the Rust and website documentation builds. `cargo audit` reports RUSTSEC-2026-0382, RUSTSEC-2026-0383, and RUSTSEC-2026-0385 on both the PR and its unmodified upstream base, which share a lockfile. Current `main` contains the fixed versions of all three crates. [Certificate dependency updates](#26550) · [ctutils update](#26666) ## Are there any user-facing changes? Already-admitted SQL RANGE windows over nested keys return correct peer counts. Physical window execution handles these peer boundaries in both Sorted and Linear modes.
1 parent ca23256 commit b93ef03

6 files changed

Lines changed: 646 additions & 57 deletions

File tree

‎datafusion/core/tests/execution/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,3 +19,4 @@ mod coop;
1919
mod datasource_split;
2020
mod logical_plan;
2121
mod register_arrow;
22+
mod window_nested_range;
Lines changed: 345 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,345 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! Nested RANGE peers through public physical execution APIs.
19+
//! Construct plans directly to test peer boundaries independently of SQL type admission.
20+
21+
use std::sync::Arc;
22+
use std::time::Duration;
23+
24+
use arrow::array::{ArrayRef, AsArray, Int32Array, Int64Array, ListArray, StructArray};
25+
use arrow::buffer::{NullBuffer, OffsetBuffer};
26+
use arrow::compute::concat_batches;
27+
use arrow::datatypes::{DataType, Field, Int32Type, Int64Type, SchemaRef};
28+
use arrow::record_batch::RecordBatch;
29+
use datafusion::datasource::memory::MemorySourceConfig;
30+
use datafusion::datasource::source::DataSourceExec;
31+
use datafusion::execution::TaskContext;
32+
use datafusion::physical_plan::stream::RecordBatchStreamAdapter;
33+
use datafusion::physical_plan::streaming::{PartitionStream, StreamingTableExec};
34+
use datafusion::physical_plan::windows::{
35+
BoundedWindowAggExec, WindowAggExec, create_window_expr,
36+
};
37+
use datafusion::physical_plan::{
38+
ExecutionPlan, ExecutionPlanProperties, InputOrderMode, SendableRecordBatchStream,
39+
collect,
40+
};
41+
use datafusion::prelude::SessionContext;
42+
use datafusion_common::{Result, ScalarValue};
43+
use datafusion_expr::{
44+
WindowFrame, WindowFrameBound, WindowFrameUnits, WindowFunctionDefinition,
45+
};
46+
use datafusion_functions_aggregate::sum::sum_udaf;
47+
use datafusion_physical_expr::PhysicalSortExpr;
48+
use datafusion_physical_expr::expressions::col;
49+
use datafusion_physical_expr_common::sort_expr::LexOrdering;
50+
use futures::{FutureExt, StreamExt};
51+
52+
fn nested_batches() -> Result<Vec<RecordBatch>> {
53+
// Three nested keys: a NULL container, a nested NULL, and nested 1.
54+
// Hidden values under the two NULL containers deliberately differ.
55+
let values = [Some(10), Some(99), None, None, None, Some(1)];
56+
let values: ArrayRef = Arc::new(Int32Array::from(values.to_vec()));
57+
let lists: ArrayRef = Arc::new(ListArray::new(
58+
Arc::new(Field::new("item", DataType::Int32, true)),
59+
OffsetBuffer::from_lengths([1; 6]),
60+
Arc::clone(&values),
61+
None,
62+
));
63+
let structs: ArrayRef = Arc::new(StructArray::new(
64+
vec![Arc::new(Field::new("item", DataType::Int32, true))].into(),
65+
vec![values],
66+
None,
67+
));
68+
let nulls = NullBuffer::from(vec![false, false, true, true, true, true]);
69+
let list_field = Arc::new(Field::new("item", lists.data_type().clone(), true));
70+
let keys: [ArrayRef; 3] = [
71+
Arc::new(ListArray::new(
72+
Arc::clone(&list_field),
73+
OffsetBuffer::from_lengths([1; 6]),
74+
Arc::clone(&lists),
75+
Some(nulls.clone()),
76+
)),
77+
Arc::new(ListArray::new(
78+
Arc::new(Field::new("item", structs.data_type().clone(), true)),
79+
OffsetBuffer::from_lengths([1; 6]),
80+
structs,
81+
Some(nulls.clone()),
82+
)),
83+
Arc::new(StructArray::new(
84+
vec![list_field].into(),
85+
vec![lists],
86+
Some(nulls),
87+
)),
88+
];
89+
keys.into_iter()
90+
.map(|keys| {
91+
// The tie separates the third nested NULL from the preceding peers.
92+
let tie: ArrayRef = Arc::new(Int32Array::from(vec![0, 0, 0, 0, 1, 0]));
93+
Ok(RecordBatch::try_from_iter(vec![
94+
("key", keys),
95+
("tie", tie),
96+
// In Linear mode, the final row advances another partition's peers.
97+
(
98+
"p",
99+
Arc::new(Int32Array::from(vec![0, 0, 0, 0, 0, 1])) as ArrayRef,
100+
),
101+
(
102+
"value",
103+
Arc::new(Int64Array::from(vec![1, 2, 4, 8, 16, 32])) as ArrayRef,
104+
),
105+
])?)
106+
})
107+
.collect()
108+
}
109+
110+
fn nested_ordering(schema: &SchemaRef) -> Result<LexOrdering> {
111+
Ok(LexOrdering::from([
112+
PhysicalSortExpr::new_default(col("key", schema)?),
113+
PhysicalSortExpr::new_default(col("tie", schema)?),
114+
]))
115+
}
116+
117+
fn window_plan(
118+
input: &Arc<dyn ExecutionPlan>,
119+
mode: Option<&InputOrderMode>,
120+
start: WindowFrameBound,
121+
end: WindowFrameBound,
122+
) -> Result<Arc<dyn ExecutionPlan>> {
123+
let schema = input.schema();
124+
let partition_by = if mode == Some(&InputOrderMode::Linear) {
125+
vec![col("p", &schema)?]
126+
} else {
127+
vec![]
128+
};
129+
let expr = create_window_expr(
130+
&WindowFunctionDefinition::AggregateUDF(sum_udaf()),
131+
"sum".to_string(),
132+
&[col("value", &schema)?],
133+
&partition_by,
134+
input.output_ordering().unwrap(),
135+
Arc::new(WindowFrame::new_bounds(WindowFrameUnits::Range, start, end)),
136+
schema,
137+
false,
138+
false,
139+
None,
140+
)?;
141+
let plan: Arc<dyn ExecutionPlan> = match mode {
142+
Some(mode) => Arc::new(BoundedWindowAggExec::try_new(
143+
vec![expr],
144+
Arc::clone(input),
145+
mode.clone(),
146+
false,
147+
)?),
148+
None => Arc::new(WindowAggExec::try_new(
149+
vec![expr],
150+
Arc::clone(input),
151+
false,
152+
)?),
153+
};
154+
assert!(
155+
input
156+
.equivalence_properties()
157+
.ordering_satisfy_requirement(
158+
plan.required_input_ordering()[0]
159+
.clone()
160+
.unwrap()
161+
.into_single(),
162+
)?
163+
);
164+
Ok(plan)
165+
}
166+
167+
#[tokio::test]
168+
async fn nested_range_current_row_physical_operators() -> Result<()> {
169+
use WindowFrameBound::{CurrentRow, Following, Preceding};
170+
171+
for batch in nested_batches()? {
172+
let schema = batch.schema();
173+
// Repeated peers cross input batch boundaries.
174+
let batches = (0..batch.num_rows())
175+
.map(|row| batch.slice(row, 1))
176+
.collect();
177+
let source = MemorySourceConfig::try_new(&[batches], Arc::clone(&schema), None)?
178+
.try_with_sort_information(vec![nested_ordering(&schema)?])?;
179+
let input: Arc<dyn ExecutionPlan> = DataSourceExec::from_data_source(source);
180+
// window.slt covers list keys in SQL-planned sorted windows.
181+
let modes: &[Option<InputOrderMode>] = if batch.column(0).data_type().is_list() {
182+
&[Some(InputOrderMode::Linear)]
183+
} else {
184+
&[
185+
None,
186+
Some(InputOrderMode::Sorted),
187+
Some(InputOrderMode::Linear),
188+
]
189+
};
190+
for (start, end, expected) in [
191+
(
192+
Preceding(ScalarValue::UInt64(None)),
193+
CurrentRow,
194+
[3, 3, 15, 15, 31, 63],
195+
),
196+
(CurrentRow, CurrentRow, [3, 3, 12, 12, 16, 32]),
197+
(
198+
CurrentRow,
199+
Following(ScalarValue::UInt64(None)),
200+
[63, 63, 60, 60, 48, 32],
201+
),
202+
] {
203+
for mode in modes.iter().map(Option::as_ref) {
204+
// The planner uses WindowAggExec for UNBOUNDED FOLLOWING.
205+
if mode.is_some() && end.is_unbounded() {
206+
continue;
207+
}
208+
let plan = window_plan(&input, mode, start.clone(), end.clone())?;
209+
let output_schema = plan.schema();
210+
let output = collect(plan, SessionContext::new().task_ctx()).await?;
211+
let output = concat_batches(&output_schema, &output)?;
212+
let actual = output
213+
.column(batch.num_columns())
214+
.as_primitive::<Int64Type>();
215+
let mut expected = expected;
216+
if mode == Some(&InputOrderMode::Linear) {
217+
// The final row is in its own PARTITION BY group.
218+
expected[5] = 32;
219+
}
220+
assert_eq!(
221+
actual.iter().collect::<Vec<_>>(),
222+
expected.map(Some),
223+
"{}, {start:?} to {end:?}, mode={mode:?}",
224+
batch.column(0).data_type(),
225+
);
226+
}
227+
}
228+
}
229+
Ok(())
230+
}
231+
232+
#[derive(Debug)]
233+
struct OpenEndedPartition {
234+
batch: RecordBatch,
235+
}
236+
237+
impl PartitionStream for OpenEndedPartition {
238+
fn schema(&self) -> &SchemaRef {
239+
self.batch.schema_ref()
240+
}
241+
242+
fn execute(&self, _ctx: Arc<TaskContext>) -> SendableRecordBatchStream {
243+
let batches = (0..self.batch.num_rows())
244+
.map(|row| Ok(self.batch.slice(row, 1)))
245+
.collect::<Vec<_>>();
246+
Box::pin(RecordBatchStreamAdapter::new(
247+
self.batch.schema(),
248+
futures::stream::iter(batches).chain(futures::stream::pending()),
249+
))
250+
}
251+
}
252+
253+
async fn assert_emits_before_eof(
254+
batch: &RecordBatch,
255+
order_by: LexOrdering,
256+
mode: InputOrderMode,
257+
expected: &[Option<i64>],
258+
) -> Result<()> {
259+
let source: Arc<dyn ExecutionPlan> = Arc::new(StreamingTableExec::try_new(
260+
batch.schema(),
261+
vec![Arc::new(OpenEndedPartition {
262+
batch: batch.clone(),
263+
})],
264+
None,
265+
vec![order_by],
266+
true,
267+
None,
268+
)?);
269+
let plan = window_plan(
270+
&source,
271+
Some(&mode),
272+
WindowFrameBound::Preceding(ScalarValue::UInt64(None)),
273+
WindowFrameBound::CurrentRow,
274+
)?;
275+
let mut stream = plan.execute(0, SessionContext::new().task_ctx())?;
276+
let actual = tokio::time::timeout(Duration::from_secs(5), async {
277+
let mut sums = Vec::new();
278+
while sums.len() < expected.len() {
279+
let output = stream.next().await.unwrap()?;
280+
sums.extend(
281+
output
282+
.column(batch.num_columns())
283+
.as_primitive::<Int64Type>()
284+
.iter(),
285+
);
286+
}
287+
Ok::<_, datafusion_common::DataFusionError>(sums)
288+
})
289+
.await
290+
.expect("completed peer groups should emit before EOF")?;
291+
assert_eq!(
292+
actual,
293+
expected,
294+
"{}, mode={mode:?}",
295+
batch.column(0).data_type()
296+
);
297+
// The final peer group cannot finish until another key or EOF arrives.
298+
assert!(stream.next().now_or_never().is_none());
299+
Ok(())
300+
}
301+
302+
#[tokio::test]
303+
async fn nested_range_emits_completed_peers_before_eof() -> Result<()> {
304+
for batch in nested_batches()? {
305+
for mode in [InputOrderMode::Sorted, InputOrderMode::Linear] {
306+
assert_emits_before_eof(
307+
&batch,
308+
nested_ordering(batch.schema_ref())?,
309+
mode,
310+
&[Some(3), Some(3), Some(15), Some(15), Some(31)],
311+
)
312+
.await?;
313+
}
314+
}
315+
Ok(())
316+
}
317+
318+
#[tokio::test]
319+
async fn nested_range_desc_nulls_last_emits_before_eof() -> Result<()> {
320+
// Both [1] and a top-level NULL sort after [2] under DESC NULLS LAST.
321+
// Each stream stops after that row arrives in a different partition.
322+
for last_key in [Some([Some(1)]), None] {
323+
let keys = ListArray::from_iter_primitive::<Int32Type, _, _>([
324+
Some([Some(2)]),
325+
Some([Some(2)]),
326+
last_key,
327+
]);
328+
let batch = RecordBatch::try_from_iter([
329+
("key", Arc::new(keys) as ArrayRef),
330+
("p", Arc::new(Int32Array::from(vec![0, 0, 1]))),
331+
("value", Arc::new(Int64Array::from(vec![1, 2, 4]))),
332+
])?;
333+
let order = PhysicalSortExpr::new_default(col("key", batch.schema_ref())?)
334+
.desc()
335+
.nulls_last();
336+
assert_emits_before_eof(
337+
&batch,
338+
[order].into(),
339+
InputOrderMode::Linear,
340+
&[Some(3), Some(3)],
341+
)
342+
.await?;
343+
}
344+
Ok(())
345+
}

0 commit comments

Comments
 (0)