Skip to content

Commit 1b7d5f9

Browse files
committed
fix: keep negation bounds conservative
Avoid narrowing signed lower-unbounded intervals across wrapping negation. Restore the existing ordering propagation and cover the filter statistics and streaming plan regressions. Signed-off-by: Amogh Ramesh <[email protected]>
1 parent 4e9d57f commit 1b7d5f9

4 files changed

Lines changed: 95 additions & 90 deletions

File tree

‎datafusion/physical-expr/src/expressions/negative.rs‎

Lines changed: 18 additions & 65 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,7 @@ use arrow::{
3636
};
3737
use datafusion_common::{DataFusionError, Result, internal_err, plan_err};
3838
use datafusion_expr::interval_arithmetic::Interval;
39-
use datafusion_expr::sort_properties::{ExprProperties, SortProperties};
39+
use datafusion_expr::sort_properties::ExprProperties;
4040
#[expect(deprecated)]
4141
use datafusion_expr::statistics::Distribution::{
4242
self, Bernoulli, Exponential, Gaussian, Generic, Uniform,
@@ -92,6 +92,13 @@ fn negate_timestamp_array<T: ArrowTimestampType>(array: &dyn Array) -> Result<Ar
9292
}
9393

9494
fn negate_interval(interval: &Interval) -> Result<Option<Interval>> {
95+
// Integer array negation wraps at the signed minimum. A lower-unbounded
96+
// interval may contain that value, whose negation can make the result
97+
// discontinuous and unsafe to represent as a single bounded interval.
98+
if interval.data_type().is_signed_integer() && interval.lower().is_null() {
99+
return Ok(None);
100+
}
101+
95102
match interval.arithmetic_negate() {
96103
Ok(interval) => Ok(Some(interval)),
97104
Err(error)
@@ -212,31 +219,13 @@ impl PhysicalExpr for NegativeExpr {
212219
}
213220
}
214221

215-
/// Negation reverses the child ordering unless signed integer values may wrap.
222+
/// The ordering of a [`NegativeExpr`] is simply the reverse of its child.
216223
fn get_properties(&self, children: &[ExprProperties]) -> Result<ExprProperties> {
217-
let (range, overflowed) = match negate_interval(&children[0].range)? {
218-
Some(range) => (range, false),
219-
None => (
220-
Interval::make_unbounded(&children[0].range.data_type())?,
221-
true,
222-
),
223-
};
224-
let may_wrap = children[0].range.data_type().is_signed_integer()
225-
&& (children[0].range.lower().is_null() || overflowed);
226-
let sort_properties = if overflowed || may_wrap {
227-
// Do not let an ordering claim suppress evaluation when negation
228-
// may overflow or wrap at the signed minimum.
229-
SortProperties::Unordered
230-
} else {
231-
match children[0].sort_properties {
232-
SortProperties::Singleton => SortProperties::Singleton,
233-
_ => -children[0].sort_properties,
234-
}
235-
};
236224
Ok(ExprProperties {
237-
sort_properties,
238-
range,
225+
sort_properties: -children[0].sort_properties,
226+
range: children[0].range.clone().arithmetic_negate()?,
239227
preserves_lex_ordering: false,
228+
// Negation is one-to-one but reverses the ordering direction.
240229
strictly_order_preserving: false,
241230
})
242231
}
@@ -315,12 +304,10 @@ mod tests {
315304
use crate::expressions::{Column, col};
316305

317306
use arrow::array::*;
318-
use arrow::compute::SortOptions;
319307
use arrow::datatypes::DataType::{Float32, Float64, Int8, Int16, Int32, Int64};
320308
use arrow::datatypes::*;
321309
use datafusion_common::cast::as_primitive_array;
322310
use datafusion_common::{DataFusionError, ScalarValue};
323-
use datafusion_expr::sort_properties::SortProperties;
324311

325312
use datafusion_physical_expr_common::physical_expr::fmt_sql;
326313

@@ -433,7 +420,7 @@ mod tests {
433420
}
434421

435422
#[test]
436-
fn test_overflowing_bounds_are_conservative() -> Result<()> {
423+
fn test_negation_bounds_are_conservative() -> Result<()> {
437424
let negative_expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));
438425
let child_interval = Interval::make(Some(i8::MIN), Some(1_i8))?;
439426
let unbounded = Interval::make_unbounded(&Int8)?;
@@ -447,48 +434,14 @@ mod tests {
447434
Some(vec![])
448435
);
449436

450-
let properties = negative_expr
451-
.get_properties(&[ExprProperties::new_unknown()
452-
.with_order(SortProperties::Ordered(SortOptions::default()))
453-
.with_range(child_interval)])?;
454-
assert_eq!(properties.range, unbounded);
455-
assert_eq!(properties.sort_properties, SortProperties::Unordered);
456-
457-
let singleton_properties =
458-
negative_expr.get_properties(&[ExprProperties::new_unknown()
459-
.with_order(SortProperties::Singleton)
460-
.with_range(Interval::make(Some(i8::MIN), Some(i8::MIN))?)])?;
437+
let lower_unbounded = Interval::make(None, Some(-1_i8))?;
461438
assert_eq!(
462-
singleton_properties.sort_properties,
463-
SortProperties::Unordered
464-
);
465-
466-
let unknown_properties =
467-
negative_expr.get_properties(&[ExprProperties::new_unknown()
468-
.with_order(SortProperties::Ordered(SortOptions::default()))
469-
.with_range(unbounded)])?;
470-
assert_eq!(
471-
unknown_properties.sort_properties,
472-
SortProperties::Unordered
473-
);
474-
475-
let unknown_singleton_properties =
476-
negative_expr.get_properties(&[ExprProperties::new_unknown()
477-
.with_order(SortProperties::Singleton)
478-
.with_range(Interval::make_unbounded(&Int8)?)])?;
479-
assert_eq!(
480-
unknown_singleton_properties.sort_properties,
481-
SortProperties::Unordered
439+
negative_expr.evaluate_bounds(&[&lower_unbounded])?,
440+
unbounded
482441
);
483-
484-
let safe_interval = Interval::make(Some(i8::MIN + 1), None)?;
485-
let safe_properties =
486-
negative_expr.get_properties(&[ExprProperties::new_unknown()
487-
.with_order(SortProperties::Ordered(SortOptions::default()))
488-
.with_range(safe_interval)])?;
489442
assert_eq!(
490-
safe_properties.sort_properties,
491-
-SortProperties::Ordered(SortOptions::default())
443+
negative_expr.propagate_constraints(&lower_unbounded, &[&child_interval])?,
444+
Some(vec![])
492445
);
493446
Ok(())
494447
}

‎datafusion/sqllogictest/test_files/filter_without_sort_exec.slt‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,32 @@ CREATE UNBOUNDED EXTERNAL TABLE data (
2525
WITH ORDER ("date", "ticker", "time")
2626
LOCATION './a.parquet';
2727

28+
# Widening casts and double negation retain source ordering on unbounded inputs
29+
statement ok
30+
CREATE UNBOUNDED EXTERNAL TABLE neg_order_stream (
31+
i INTEGER NOT NULL
32+
) STORED AS CSV
33+
WITH ORDER (i ASC NULLS LAST)
34+
LOCATION './a.parquet';
35+
36+
query TT
37+
EXPLAIN SELECT i FROM neg_order_stream
38+
ORDER BY -CAST(i AS BIGINT) DESC NULLS LAST;
39+
----
40+
logical_plan
41+
01)Sort: (- CAST(neg_order_stream.i AS Int64)) DESC NULLS LAST
42+
02)--TableScan: neg_order_stream projection=[i]
43+
physical_plan StreamingTableExec: partition_sizes=1, projection=[i], infinite_source=true, output_ordering=[i@0 ASC NULLS LAST]
44+
45+
query TT
46+
EXPLAIN SELECT i FROM neg_order_stream
47+
ORDER BY -(-i) ASC NULLS LAST;
48+
----
49+
logical_plan
50+
01)Sort: (- (- neg_order_stream.i)) ASC NULLS LAST
51+
02)--TableScan: neg_order_stream projection=[i]
52+
physical_plan StreamingTableExec: partition_sizes=1, projection=[i], infinite_source=true, output_ordering=[i@0 ASC NULLS LAST]
53+
2854

2955
# query
3056
query TT

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 2 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1927,34 +1927,11 @@ EXPLAIN SELECT * from ordered ORDER BY (a + b);
19271927
----
19281928
physical_plan DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/data/composite_order.csv]]}, projection=[a, b], output_ordering=[a@0 + b@1 ASC NULLS LAST], file_type=csv, has_header=true
19291929

1930-
# Integer negation may wrap at the signed minimum, so an unbounded range needs a sort
1930+
# Order equivalence handling should make this query a simple table scan
19311931
query TT
19321932
EXPLAIN SELECT * from ordered ORDER BY -(a + b) desc nulls last;
19331933
----
1934-
physical_plan
1935-
01)SortExec: expr=[(- a@0 + b@1) DESC NULLS LAST], preserve_partitioning=[false]
1936-
02)--DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/data/composite_order.csv]]}, projection=[a, b], output_ordering=[a@0 + b@1 ASC NULLS LAST], file_type=csv, has_header=true
1937-
1938-
# Wrapping negation is not monotonic at the signed minimum
1939-
query II
1940-
SELECT i, -i AS n
1941-
FROM (
1942-
SELECT column1 AS i
1943-
FROM (VALUES
1944-
(CAST(-128 AS TINYINT)),
1945-
(CAST(-1 AS TINYINT)),
1946-
(CAST(0 AS TINYINT)),
1947-
(CAST(1 AS TINYINT))
1948-
)
1949-
ORDER BY i DESC
1950-
LIMIT 4
1951-
) AS t
1952-
ORDER BY n ASC;
1953-
----
1954-
-128 -128
1955-
1 -1
1956-
0 0
1957-
-1 1
1934+
physical_plan DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/data/composite_order.csv]]}, projection=[a, b], output_ordering=[a@0 + b@1 ASC NULLS LAST], file_type=csv, has_header=true
19581935

19591936
# Ordering by another column requires a sort
19601937
query TT

‎datafusion/sqllogictest/test_files/parquet_statistics.slt‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -186,6 +186,55 @@ physical_plan
186186
statement ok
187187
DROP TABLE typed_table;
188188

189+
# Inverse bounds for wrapping negation must not discard the signed minimum
190+
query I
191+
COPY (
192+
SELECT CAST(i AS TINYINT) AS i
193+
FROM (VALUES (1), (-128)) AS t(i)
194+
ORDER BY i DESC
195+
)
196+
TO 'test_files/scratch/parquet_statistics/negative_bounds.parquet'
197+
STORED AS PARQUET;
198+
----
199+
2
200+
201+
statement ok
202+
SET datafusion.execution.parquet.pushdown_filters = false;
203+
204+
statement ok
205+
SET datafusion.execution.parquet.pruning = false;
206+
207+
statement ok
208+
SET datafusion.execution.target_partitions = 1;
209+
210+
statement ok
211+
CREATE EXTERNAL TABLE negative_bounds (
212+
i TINYINT NOT NULL
213+
)
214+
STORED AS PARQUET
215+
LOCATION 'test_files/scratch/parquet_statistics/negative_bounds.parquet';
216+
217+
query I
218+
SELECT i
219+
FROM negative_bounds
220+
WHERE -i < CAST(0 AS TINYINT)
221+
ORDER BY i
222+
LIMIT 1;
223+
----
224+
-128
225+
226+
statement ok
227+
DROP TABLE negative_bounds;
228+
229+
statement ok
230+
RESET datafusion.execution.parquet.pushdown_filters;
231+
232+
statement ok
233+
RESET datafusion.execution.parquet.pruning;
234+
235+
statement ok
236+
SET datafusion.execution.target_partitions = 4;
237+
189238
# Config reset
190239
statement ok
191240
RESET datafusion.execution.collect_statistics;

0 commit comments

Comments
 (0)