Skip to content

Commit bf4d0f0

Browse files
haohuaijinOmega359
authored andcommitted
fix: preserve sorts for wrapping integer negation (apache#25568)
## Which issue does this PR close? Closes apache#24683. Related to apache#25407. ## Rationale for this change An ordered signed integer column does not necessarily remain ordered after negation: the minimum value wraps to itself. Treating negation as always reversing order can remove a required sort and return incorrectly ordered rows. Negating inferred interval endpoints can also raise an overflow error even though array evaluation uses wrapping negation. ## What changes are included in this PR? - Stop deriving reversed ordering when the input range may contain the signed minimum, while preserving existing Singleton properties and reversal for known safe ranges. - Use unbounded intervals for potentially wrapping signed integer negation in forward and reverse constraint propagation, including singleton MIN ranges. - Add regression cases to the existing `order.slt` and update the expected plan for negation of an ordered BIGINT expression. Runtime scalar and array negation semantics are unchanged. This conservative fix can retain additional sorts when safe bounds are unavailable, including after widening casts; improving cast range propagation is left to separate work. ## What is the testing strategy for this PR? - A table-driven unit test covers all four signed integer widths, unbounded and MIN ranges, Singleton properties, safe reversal, and unknown input properties. - Four cases in `order.slt` cover the original incorrect ordering, MIN filter propagation, double negation on an unbounded stream, and ordering MIN values mixed with NULL. - The original ordering query and MIN filter reproduced failures before the fix. - Passed the 9 negation unit tests and `order.slt`, plus formatting, full Clippy, and `uv run ./dev/rust_lint.sh` checks. ## Are there any user-facing changes? Queries involving signed minimum negation retain necessary sorts and no longer fail solely because an inferred negation endpoint overflows. Some range refinement and sort elimination become more conservative. No public API changes.
1 parent df7f85a commit bf4d0f0

2 files changed

Lines changed: 227 additions & 11 deletions

File tree

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

Lines changed: 163 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,9 @@ use arrow::{
2828
datatypes::{DataType, Schema},
2929
record_batch::RecordBatch,
3030
};
31-
use datafusion_common::{Result, internal_err, plan_err};
31+
use datafusion_common::{Result, ScalarValue, internal_err, plan_err};
3232
use datafusion_expr::interval_arithmetic::Interval;
33-
use datafusion_expr::sort_properties::ExprProperties;
33+
use datafusion_expr::sort_properties::{ExprProperties, SortProperties};
3434
#[expect(deprecated)]
3535
use datafusion_expr::statistics::Distribution::{
3636
self, Bernoulli, Exponential, Gaussian, Generic, Uniform,
@@ -115,10 +115,9 @@ impl PhysicalExpr for NegativeExpr {
115115
}
116116

117117
/// Given the child interval of a NegativeExpr, it calculates the NegativeExpr's interval.
118-
/// It replaces the upper and lower bounds after multiplying them with -1.
119-
/// Ex: `(a, b]` => `[-b, -a)`
118+
/// Reflects the bounds unless signed integer negation can wrap.
120119
fn evaluate_bounds(&self, children: &[&Interval]) -> Result<Interval> {
121-
children[0].arithmetic_negate()
120+
negate_bounds(children[0])
122121
}
123122

124123
/// Returns a new [`Interval`] of a NegativeExpr that has the existing `interval` given that
@@ -128,7 +127,7 @@ impl PhysicalExpr for NegativeExpr {
128127
interval: &Interval,
129128
children: &[&Interval],
130129
) -> Result<Option<Vec<Interval>>> {
131-
let negated_interval = interval.arithmetic_negate()?;
130+
let negated_interval = negate_bounds(interval)?;
132131

133132
Ok(children[0]
134133
.intersect(negated_interval)?
@@ -160,11 +159,17 @@ impl PhysicalExpr for NegativeExpr {
160159
}
161160
}
162161

163-
/// The ordering of a [`NegativeExpr`] is simply the reverse of its child.
162+
/// Negation reverses ordering only when the input cannot cross a wrap.
164163
fn get_properties(&self, children: &[ExprProperties]) -> Result<ExprProperties> {
165164
Ok(ExprProperties {
166-
sort_properties: -children[0].sort_properties,
167-
range: children[0].range.clone().arithmetic_negate()?,
165+
sort_properties: if children[0].sort_properties != SortProperties::Singleton
166+
&& negation_may_wrap(&children[0].range)
167+
{
168+
SortProperties::Unordered
169+
} else {
170+
-children[0].sort_properties
171+
},
172+
range: negate_bounds(&children[0].range)?,
168173
preserves_lex_ordering: false,
169174
// Negation is one-to-one but reverses the ordering direction.
170175
strictly_order_preserving: false,
@@ -196,6 +201,26 @@ impl PhysicalExpr for NegativeExpr {
196201
}
197202
}
198203

204+
fn negate_bounds(range: &Interval) -> Result<Interval> {
205+
if range.data_type() == DataType::Null {
206+
return Ok(range.clone());
207+
}
208+
if range.data_type().is_signed_integer() && negation_may_wrap(range) {
209+
// Do not derive bounds across a possible integer wrap.
210+
return Interval::make_unbounded(&range.data_type());
211+
}
212+
range.arithmetic_negate()
213+
}
214+
215+
// Signed integer array negation wraps at the minimum value.
216+
fn negation_may_wrap(range: &Interval) -> bool {
217+
let data_type = range.data_type();
218+
data_type == DataType::Null
219+
|| (data_type.is_signed_integer()
220+
&& (range.lower().is_null()
221+
|| ScalarValue::min(&data_type).as_ref() == Some(range.lower())))
222+
}
223+
199224
#[cfg(feature = "proto")]
200225
impl NegativeExpr {
201226
/// Reconstruct a [`NegativeExpr`] from its protobuf representation.
@@ -290,6 +315,135 @@ mod tests {
290315
Ok(())
291316
}
292317

318+
#[test]
319+
fn test_wrapping_negation_properties() {
320+
let expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));
321+
let ordered = SortProperties::Ordered(Default::default());
322+
for data_type in [Int8, Int16, Int32, Int64] {
323+
let minimum = ScalarValue::min(&data_type).unwrap();
324+
let full = Interval::make_unbounded(&data_type).unwrap();
325+
let singleton = Interval::try_new(minimum.clone(), minimum.clone()).unwrap();
326+
for range in [
327+
full.clone(),
328+
singleton.clone(),
329+
Interval::try_new(ScalarValue::try_from(&data_type).unwrap(), minimum)
330+
.unwrap(),
331+
] {
332+
let child = ExprProperties::new_unknown()
333+
.with_range(range.clone())
334+
.with_order(ordered);
335+
let result = expr.get_properties(&[child]).unwrap();
336+
assert_eq!(result.sort_properties, SortProperties::Unordered);
337+
assert_eq!(result.range, full);
338+
assert_eq!(expr.evaluate_bounds(&[&range]).unwrap(), full);
339+
assert_eq!(
340+
expr.propagate_constraints(&range, &[&full]).unwrap(),
341+
Some(vec![full.clone()])
342+
);
343+
}
344+
let child = ExprProperties::new_unknown()
345+
.with_range(singleton)
346+
.with_order(SortProperties::Singleton);
347+
assert_eq!(
348+
expr.get_properties(&[child]).unwrap().sort_properties,
349+
SortProperties::Singleton
350+
);
351+
}
352+
}
353+
354+
#[test]
355+
fn test_non_wrapping_negation_properties() {
356+
let expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));
357+
let ranges = [
358+
Interval::make(Some(i8::MIN + 1), Some(1_i8)).unwrap(),
359+
Interval::make(Some(i16::MIN + 1), Some(1_i16)).unwrap(),
360+
Interval::make(Some(i32::MIN + 1), Some(1_i32)).unwrap(),
361+
Interval::make(Some(i64::MIN + 1), Some(1_i64)).unwrap(),
362+
// An unbounded upper bound cannot introduce MIN when the lower bound excludes it.
363+
Interval::make(Some(i8::MIN + 1), None).unwrap(),
364+
Interval::make(Some(i16::MIN + 1), None).unwrap(),
365+
Interval::make(Some(i32::MIN + 1), None).unwrap(),
366+
Interval::make(Some(i64::MIN + 1), None).unwrap(),
367+
Interval::make(Some(-2_f32), Some(1_f32)).unwrap(),
368+
Interval::make(Some(-2_f64), Some(1_f64)).unwrap(),
369+
Interval::make_unbounded(&Float32).unwrap(),
370+
Interval::make_unbounded(&Float64).unwrap(),
371+
];
372+
for range in ranges {
373+
let expected_range = range.arithmetic_negate().unwrap();
374+
for descending in [false, true] {
375+
for nulls_first in [false, true] {
376+
let ordered = SortProperties::Ordered(arrow::compute::SortOptions {
377+
descending,
378+
nulls_first,
379+
});
380+
let child = ExprProperties::new_unknown()
381+
.with_range(range.clone())
382+
.with_order(ordered);
383+
let result = expr.get_properties(&[child]).unwrap();
384+
assert_eq!(result.sort_properties, -ordered);
385+
assert_eq!(result.range, expected_range);
386+
}
387+
}
388+
assert_eq!(expr.evaluate_bounds(&[&range]).unwrap(), expected_range);
389+
assert_eq!(
390+
expr.propagate_constraints(&expected_range, &[&range])
391+
.unwrap(),
392+
Some(vec![range])
393+
);
394+
}
395+
}
396+
397+
#[test]
398+
fn test_unknown_negation_properties() {
399+
let expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));
400+
for order in [
401+
SortProperties::Ordered(Default::default()),
402+
SortProperties::Unordered,
403+
SortProperties::Singleton,
404+
] {
405+
let child = ExprProperties::new_unknown().with_order(order);
406+
let range = child.range.clone();
407+
let result = expr.get_properties(&[child]).unwrap();
408+
assert_eq!(
409+
result.sort_properties,
410+
if order == SortProperties::Singleton {
411+
SortProperties::Singleton
412+
} else {
413+
SortProperties::Unordered
414+
}
415+
);
416+
assert_eq!(result.range, range);
417+
assert_eq!(expr.evaluate_bounds(&[&range]).unwrap(), range);
418+
}
419+
}
420+
421+
#[test]
422+
fn test_negation_bounds_errors() {
423+
let expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));
424+
// Boolean intervals cannot be negated. All callers must propagate the error.
425+
let range = Interval::make(Some(false), Some(true)).unwrap();
426+
let child = ExprProperties::new_unknown().with_range(range.clone());
427+
// Compare the error messages without call-site-dependent backtraces.
428+
let expected = range.arithmetic_negate().unwrap_err().strip_backtrace();
429+
assert_eq!(
430+
expr.evaluate_bounds(&[&range])
431+
.unwrap_err()
432+
.strip_backtrace(),
433+
expected
434+
);
435+
assert_eq!(
436+
expr.get_properties(&[child]).unwrap_err().strip_backtrace(),
437+
expected
438+
);
439+
assert_eq!(
440+
expr.propagate_constraints(&range, &[&range])
441+
.unwrap_err()
442+
.strip_backtrace(),
443+
expected
444+
);
445+
}
446+
293447
#[test]
294448
fn test_evaluate_bounds() -> Result<()> {
295449
let negative_expr = NegativeExpr::new(Arc::new(Column::new("a", 0)));

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 64 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1966,11 +1966,13 @@ EXPLAIN SELECT * from ordered ORDER BY (a + b);
19661966
----
19671967
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
19681968

1969-
# Order equivalence handling should make this query a simple table scan
1969+
# Negation may wrap at BIGINT's minimum, so the declared ordering is insufficient.
19701970
query TT
19711971
EXPLAIN SELECT * from ordered ORDER BY -(a + b) desc nulls last;
19721972
----
1973-
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
1973+
physical_plan
1974+
01)SortExec: expr=[(- a@0 + b@1) DESC NULLS LAST], preserve_partitioning=[false]
1975+
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
19741976

19751977
# Ordering by another column requires a sort
19761978
query TT
@@ -2159,3 +2161,63 @@ DROP TABLE sort_key_sink;
21592161

21602162
statement ok
21612163
DROP TABLE t2;
2164+
2165+
# Regression for #24683: signed minimum negation wraps.
2166+
query II
2167+
SELECT i, -i AS n
2168+
FROM (
2169+
SELECT i FROM (VALUES
2170+
(CAST(-128 AS TINYINT)), (CAST(-1 AS TINYINT)),
2171+
(CAST(0 AS TINYINT)), (CAST(1 AS TINYINT))
2172+
) AS v(i)
2173+
ORDER BY i DESC LIMIT 4
2174+
) AS t
2175+
ORDER BY n ASC;
2176+
----
2177+
-128 -128
2178+
1 -1
2179+
0 0
2180+
-1 1
2181+
2182+
# Interval propagation must not overflow when the filter negates MIN.
2183+
statement ok
2184+
CREATE TABLE negative_values (i TINYINT) AS VALUES (-128), (-1), (0), (1);
2185+
2186+
query I
2187+
SELECT i FROM negative_values WHERE -i = CAST(-128 AS TINYINT);
2188+
----
2189+
-128
2190+
2191+
statement ok
2192+
DROP TABLE negative_values;
2193+
2194+
statement ok
2195+
CREATE UNBOUNDED EXTERNAL TABLE negative_stream (i INT)
2196+
STORED AS CSV WITH ORDER (i ASC)
2197+
LOCATION '../core/tests/data/empty.csv'
2198+
OPTIONS ('format.has_header' 'true');
2199+
2200+
# Double negation must not require sorting an unbounded stream.
2201+
query TT
2202+
EXPLAIN SELECT i FROM negative_stream ORDER BY -(-i) ASC;
2203+
----
2204+
logical_plan
2205+
01)Sort: negative_stream.i AS (- (- negative_stream.i)) ASC NULLS LAST
2206+
02)--TableScan: negative_stream projection=[i]
2207+
physical_plan StreamingTableExec: partition_sizes=1, projection=[i], infinite_source=true, output_ordering=[i@0 ASC NULLS LAST]
2208+
2209+
statement ok
2210+
DROP TABLE negative_stream;
2211+
2212+
# Equal non-null values do not remove the need to order NULLs.
2213+
query II
2214+
SELECT i, -i AS n FROM (
2215+
SELECT i FROM (VALUES
2216+
(CAST(-128 AS TINYINT)), (CAST(NULL AS TINYINT)), (CAST(-128 AS TINYINT))
2217+
) AS v(i)
2218+
ORDER BY i DESC NULLS FIRST LIMIT 3
2219+
) AS t ORDER BY n ASC NULLS LAST;
2220+
----
2221+
-128 -128
2222+
-128 -128
2223+
NULL NULL

0 commit comments

Comments
 (0)