Skip to content

Commit b07f96f

Browse files
buraksennclaude
andcommitted
fix: do not derive ordering for arithmetic that can overflow
Adding or subtracting two ordered columns was assumed to preserve ordering, but the default wrapping arithmetic breaks monotonicity on overflow (e.g. the sum of two ascending UInt8 columns wraps back to small values), so eliding a SortExec based on the derived ordering returns wrongly ordered results. Keep the derived ordering for + / - only when overflow cannot corrupt it: the expression errors on overflow instead of wrapping, the result is a constant, or the result range proves overflow is impossible. Closes apache#23902. Co-Authored-By: Claude Fable 5 <[email protected]>
1 parent 5de7f1d commit b07f96f

7 files changed

Lines changed: 104 additions & 93 deletions

File tree

‎datafusion/physical-expr/src/equivalence/ordering.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -486,8 +486,8 @@ mod tests {
486486
vec![col_e],
487487
// requirement [a ASC, c ASC, a+b ASC],
488488
vec![(col_a, options), (col_c, options), (&a_plus_b, options)],
489-
// expected: requirement is satisfied.
490-
true,
489+
// expected: requirement is not satisfied because addition can wrap.
490+
false,
491491
),
492492
// ------------ TEST CASE 4 ------------
493493
(
@@ -633,8 +633,8 @@ mod tests {
633633
vec![col_e],
634634
// requirement [c ASC, d ASC, a + b ASC],
635635
vec![(col_c, options), (col_d, options), (&a_plus_b, options)],
636-
// expected: requirement is satisfied.
637-
true,
636+
// expected: requirement is not satisfied because addition can wrap.
637+
false,
638638
),
639639
];
640640

‎datafusion/physical-expr/src/equivalence/properties/dependency.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -632,10 +632,10 @@ mod tests {
632632
]);
633633

634634
let test_cases = vec![
635-
// d + b
635+
// d + b can wrap
636636
(
637637
Arc::new(BinaryExpr::new(col_d, Operator::Plus, Arc::clone(&col_b))) as _,
638-
SortProperties::Ordered(option_asc),
638+
SortProperties::Unordered,
639639
),
640640
// b
641641
(col_b, SortProperties::Ordered(option_asc)),
@@ -717,8 +717,8 @@ mod tests {
717717
(vec![col_b], vec![]),
718718
// TEST CASE 5
719719
(vec![col_d], vec![(col_d, option_asc)]),
720-
// TEST CASE 5
721-
(vec![&a_plus_d], vec![(&a_plus_d, option_asc)]),
720+
// TEST CASE 5: a + d is not ordered because addition can wrap.
721+
(vec![&a_plus_d], vec![]),
722722
// TEST CASE 6
723723
(
724724
vec![col_b, col_d],

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

Lines changed: 41 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use datafusion_common::{Result, ScalarValue, internal_err, not_impl_err};
3333

3434
use datafusion_expr::binary::BinaryTypeCoercer;
3535
use datafusion_expr::interval_arithmetic::{Interval, apply_operator};
36-
use datafusion_expr::sort_properties::ExprProperties;
36+
use datafusion_expr::sort_properties::{ExprProperties, SortProperties};
3737
#[expect(deprecated)]
3838
use datafusion_expr::statistics::Distribution::{Bernoulli, Gaussian};
3939
#[expect(deprecated)]
@@ -118,6 +118,28 @@ impl BinaryExpr {
118118
pub fn op(&self) -> &Operator {
119119
&self.op
120120
}
121+
122+
/// The default arithmetic kernels wrap on overflow (e.g. the sum of two
123+
/// ascending `UInt8` columns wraps around to small values), which breaks
124+
/// the monotonicity that `sort_properties` derives from the operands.
125+
/// Keep the derived ordering only when overflow cannot corrupt it: the
126+
/// expression errors on overflow instead of wrapping, the result is a
127+
/// constant, or the result range proves overflow is impossible.
128+
/// See <https://github.com/apache/datafusion/issues/23902>.
129+
fn arithmetic_sort_properties(
130+
&self,
131+
sort_properties: SortProperties,
132+
range: &Interval,
133+
) -> SortProperties {
134+
if self.fail_on_overflow
135+
|| sort_properties == SortProperties::Singleton
136+
|| !range.is_unbounded()
137+
{
138+
sort_properties
139+
} else {
140+
SortProperties::Unordered
141+
}
142+
}
121143
}
122144

123145
impl std::fmt::Display for BinaryExpr {
@@ -751,16 +773,24 @@ impl PhysicalExpr for BinaryExpr {
751773
let (l_order, l_range) = (children[0].sort_properties, &children[0].range);
752774
let (r_order, r_range) = (children[1].sort_properties, &children[1].range);
753775
match self.op() {
754-
Operator::Plus => Ok(ExprProperties {
755-
sort_properties: l_order.add(&r_order),
756-
range: l_range.add(r_range)?,
757-
preserves_lex_ordering: false,
758-
}),
759-
Operator::Minus => Ok(ExprProperties {
760-
sort_properties: l_order.sub(&r_order),
761-
range: l_range.sub(r_range)?,
762-
preserves_lex_ordering: false,
763-
}),
776+
Operator::Plus => {
777+
let range = l_range.add(r_range)?;
778+
Ok(ExprProperties {
779+
sort_properties: self
780+
.arithmetic_sort_properties(l_order.add(&r_order), &range),
781+
range,
782+
preserves_lex_ordering: false,
783+
})
784+
}
785+
Operator::Minus => {
786+
let range = l_range.sub(r_range)?;
787+
Ok(ExprProperties {
788+
sort_properties: self
789+
.arithmetic_sort_properties(l_order.sub(&r_order), &range),
790+
range,
791+
preserves_lex_ordering: false,
792+
})
793+
}
764794
Operator::Gt => Ok(ExprProperties {
765795
sort_properties: l_order.gt_or_gteq(&r_order),
766796
range: l_range.gt(r_range)?,

‎datafusion/physical-expr/src/projection.rs‎

Lines changed: 16 additions & 67 deletions
Original file line numberDiff line numberDiff line change
@@ -1577,8 +1577,6 @@ pub(crate) mod tests {
15771577
vec![("a_new", option_asc), ("b_new", option_asc)],
15781578
// [a_new ASC, d_new ASC]
15791579
vec![("a_new", option_asc), ("d_new", option_asc)],
1580-
// [a_new ASC, b+d ASC]
1581-
vec![("a_new", option_asc), ("b+d", option_asc)],
15821580
],
15831581
),
15841582
// ------- TEST CASE 8 ----------
@@ -1660,12 +1658,6 @@ pub(crate) mod tests {
16601658
("b_new", option_asc),
16611659
("c_new", option_asc),
16621660
],
1663-
// [a_new ASC, b_new ASC, c+d ASC]
1664-
vec![
1665-
("a_new", option_asc),
1666-
("b_new", option_asc),
1667-
("c+d", option_asc),
1668-
],
16691661
],
16701662
),
16711663
// ------- TEST CASE 11 ----------
@@ -1687,8 +1679,6 @@ pub(crate) mod tests {
16871679
vec![
16881680
// [a_new ASC, b_new ASC]
16891681
vec![("a_new", option_asc), ("b_new", option_asc)],
1690-
// [a_new ASC, b + d ASC]
1691-
vec![("a_new", option_asc), ("b+d", option_asc)],
16921682
],
16931683
),
16941684
// ------- TEST CASE 12 ----------
@@ -1770,30 +1760,12 @@ pub(crate) mod tests {
17701760
],
17711761
// expected
17721762
vec![
1773-
// [a_new ASC, d_new ASC, b+e ASC]
1774-
vec![
1775-
("a_new", option_asc),
1776-
("d_new", option_asc),
1777-
("b+e", option_asc),
1778-
],
1779-
// [d_new ASC, a_new ASC, b+e ASC]
1780-
vec![
1781-
("d_new", option_asc),
1782-
("a_new", option_asc),
1783-
("b+e", option_asc),
1784-
],
1785-
// [c_new ASC, d_new ASC, b+e ASC]
1786-
vec![
1787-
("c_new", option_asc),
1788-
("d_new", option_asc),
1789-
("b+e", option_asc),
1790-
],
1791-
// [d_new ASC, c_new ASC, b+e ASC]
1792-
vec![
1793-
("d_new", option_asc),
1794-
("c_new", option_asc),
1795-
("b+e", option_asc),
1796-
],
1763+
// [a_new ASC]
1764+
vec![("a_new", option_asc)],
1765+
// [c_new ASC]
1766+
vec![("c_new", option_asc)],
1767+
// [d_new ASC]
1768+
vec![("d_new", option_asc)],
17971769
],
17981770
),
17991771
// ------- TEST CASE 15 ----------
@@ -1815,12 +1787,8 @@ pub(crate) mod tests {
18151787
],
18161788
// expected
18171789
vec![
1818-
// [a_new ASC, d_new ASC, b+e ASC]
1819-
vec![
1820-
("a_new", option_asc),
1821-
("c_new", option_asc),
1822-
("a+b", option_asc),
1823-
],
1790+
// [a_new ASC, c_new ASC]
1791+
vec![("a_new", option_asc), ("c_new", option_asc)],
18241792
],
18251793
),
18261794
// ------- TEST CASE 16 ----------
@@ -1845,8 +1813,6 @@ pub(crate) mod tests {
18451813
vec![
18461814
// [a_new ASC, b_new ASC]
18471815
vec![("a_new", option_asc), ("b_new", option_asc)],
1848-
// [a_new ASC, b_new ASC]
1849-
vec![("a_new", option_asc), ("b+e", option_asc)],
18501816
// [c_new ASC, b_new DESC]
18511817
vec![("c_new", option_asc), ("b_new", option_desc)],
18521818
],
@@ -2119,7 +2085,6 @@ pub(crate) mod tests {
21192085
let projection_mapping = ProjectionMapping::try_new(proj_exprs, &schema)?;
21202086
let output_schema = output_schema(&projection_mapping, &schema)?;
21212087

2122-
let col_a_plus_b_new = &col("a+b", &output_schema)?;
21232088
let col_c_new = &col("c_new", &output_schema)?;
21242089
let col_d_new = &col("d_new", &output_schema)?;
21252090

@@ -2137,18 +2102,10 @@ pub(crate) mod tests {
21372102
vec![],
21382103
// expected
21392104
vec![
2140-
// [d_new ASC, c_new ASC, a+b ASC]
2141-
vec![
2142-
(col_d_new, option_asc),
2143-
(col_c_new, option_asc),
2144-
(col_a_plus_b_new, option_asc),
2145-
],
2146-
// [c_new ASC, d_new ASC, a+b ASC]
2147-
vec![
2148-
(col_c_new, option_asc),
2149-
(col_d_new, option_asc),
2150-
(col_a_plus_b_new, option_asc),
2151-
],
2105+
// [c_new ASC]
2106+
vec![(col_c_new, option_asc)],
2107+
// [d_new ASC]
2108+
vec![(col_d_new, option_asc)],
21522109
],
21532110
),
21542111
// ---------- TEST CASE 2 ------------
@@ -2164,18 +2121,10 @@ pub(crate) mod tests {
21642121
vec![(col_e, col_a)],
21652122
// expected
21662123
vec![
2167-
// [d_new ASC, c_new ASC, a+b ASC]
2168-
vec![
2169-
(col_d_new, option_asc),
2170-
(col_c_new, option_asc),
2171-
(col_a_plus_b_new, option_asc),
2172-
],
2173-
// [c_new ASC, d_new ASC, a+b ASC]
2174-
vec![
2175-
(col_c_new, option_asc),
2176-
(col_d_new, option_asc),
2177-
(col_a_plus_b_new, option_asc),
2178-
],
2124+
// [c_new ASC]
2125+
vec![(col_c_new, option_asc)],
2126+
// [d_new ASC]
2127+
vec![(col_d_new, option_asc)],
21792128
],
21802129
),
21812130
// ---------- TEST CASE 3 ------------
Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
a,b
2+
1,1
3+
2,3
4+
200,10
5+
255,10

‎datafusion/sqllogictest/test_files/order.slt‎

Lines changed: 31 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -674,8 +674,8 @@ SELECT DISTINCT time as "first_seen" FROM t ORDER BY 1;
674674
statement ok
675675
drop table t;
676676

677-
# Create a table having 3 columns which are ordering equivalent by the source. In the next step,
678-
# we will expect to observe the removed SortExec by propagating the orders across projection.
677+
# Create a table with three independently ordered columns. Their sum is not
678+
# necessarily ordered because integer addition can wrap.
679679
statement ok
680680
CREATE EXTERNAL TABLE multiple_ordered_table (
681681
a0 INTEGER,
@@ -702,9 +702,10 @@ logical_plan
702702
03)----TableScan: multiple_ordered_table projection=[a, b, c]
703703
physical_plan
704704
01)SortPreservingMergeExec: [result@0 ASC NULLS LAST]
705-
02)--ProjectionExec: expr=[b@1 + a@0 + c@2 as result]
706-
03)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true
707-
04)------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[a, b, c], output_orderings=[[a@0 ASC NULLS LAST], [b@1 ASC NULLS LAST], [c@2 ASC NULLS LAST]], file_type=csv, has_header=true
705+
02)--SortExec: expr=[result@0 ASC NULLS LAST], preserve_partitioning=[true]
706+
03)----ProjectionExec: expr=[b@1 + a@0 + c@2 as result]
707+
04)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true
708+
05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[a, b, c], output_orderings=[[a@0 ASC NULLS LAST], [b@1 ASC NULLS LAST], [c@2 ASC NULLS LAST]], file_type=csv, has_header=true
708709

709710
statement ok
710711
drop table multiple_ordered_table;
@@ -1747,6 +1748,31 @@ EXPLAIN SELECT a, named_struct('a', a, 'b', b) AS s FROM ordered_by_a ORDER BY s
17471748
----
17481749
physical_plan DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/data/composite_order.csv]]}, projection=[a, named_struct(a, a@0, b, b@1) as s], output_ordering=[a@0 ASC NULLS LAST], file_type=csv, has_header=true
17491750

1751+
# Regression test for https://github.com/apache/datafusion/issues/23902
1752+
# Both input columns are ascending, but UInt8 addition wraps and is therefore
1753+
# not necessarily ascending.
1754+
statement ok
1755+
CREATE EXTERNAL TABLE ordered_u8 (
1756+
a TINYINT UNSIGNED NOT NULL,
1757+
b TINYINT UNSIGNED NOT NULL
1758+
)
1759+
STORED AS CSV
1760+
LOCATION 'data/uint8_overflow_order.csv'
1761+
OPTIONS ('format.has_header' 'true')
1762+
WITH ORDER (a ASC)
1763+
WITH ORDER (b ASC);
1764+
1765+
query I
1766+
SELECT (a + b) AS result FROM ordered_u8 ORDER BY result ASC;
1767+
----
1768+
2
1769+
5
1770+
9
1771+
210
1772+
1773+
statement ok
1774+
DROP TABLE ordered_u8;
1775+
17501776
# Config reset
17511777
statement ok
17521778
reset datafusion.catalog.information_schema;

‎datafusion/sqllogictest/test_files/topk.slt‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -374,14 +374,15 @@ physical_plan
374374
02)--SortExec: TopK(fetch=3), expr=[number@0 DESC, letter@1 ASC NULLS LAST, age@2 DESC], preserve_partitioning=[false], sort_prefix=[number@0 DESC, letter@1 ASC NULLS LAST]
375375
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/topk/partial_sorted/1.parquet]]}, projection=[number, letter, age], output_ordering=[number@0 DESC, letter@1 ASC NULLS LAST], file_type=parquet, predicate=DynamicFilter [ empty ], dynamic_rg_pruning=eligible
376376

377-
# Verify that the sort prefix is correctly computed over normalized, order-maintaining projections (number + 1, number, number + 1, age)
377+
# `number + 1` is not order-maintaining (addition can overflow and wrap), so
378+
# no sort prefix can be computed over the projected expression.
378379
query TT
379380
explain select number + 1 as number_plus, number, number + 1 as other_number_plus, age from partial_sorted order by number_plus desc, number desc, other_number_plus desc, age asc limit 3;
380381
----
381382
physical_plan
382383
01)SortPreservingMergeExec: [number_plus@0 DESC, number@1 DESC, other_number_plus@2 DESC, age@3 ASC NULLS LAST], fetch=3
383384
02)--ProjectionExec: expr=[__common_expr_1@0 as number_plus, number@1 as number, __common_expr_1@0 as other_number_plus, age@2 as age]
384-
03)----SortExec: TopK(fetch=3), expr=[__common_expr_1@0 DESC, number@1 DESC, age@2 ASC NULLS LAST], preserve_partitioning=[true], sort_prefix=[__common_expr_1@0 DESC, number@1 DESC]
385+
03)----SortExec: TopK(fetch=3), expr=[__common_expr_1@0 DESC, number@1 DESC, age@2 ASC NULLS LAST], preserve_partitioning=[true]
385386
04)------ProjectionExec: expr=[CAST(number@0 AS Int64) + 1 as __common_expr_1, number@0 as number, age@1 as age]
386387
05)--------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true
387388
06)----------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/topk/partial_sorted/1.parquet]]}, projection=[number, age], output_ordering=[number@0 DESC], file_type=parquet, predicate=DynamicFilter [ empty ], dynamic_rg_pruning=eligible

0 commit comments

Comments
 (0)