Skip to content

Commit e7304ee

Browse files
authored
fix: do not derive ordering for arithmetic that can overflow (#23910)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> - Closes #23902. ## Rationale for this change Please check the issue for details but the main idea is that `a + b` over two sorted columns is not guaranteed to be sorted. ## What changes are included in this PR? Ordering is discarded when it overflows or wraps ## Are these changes tested? Yes, adjusted existing tests and added a regression test in `order.slt`. ## Are there any user-facing changes? no api changes
1 parent 31ffab1 commit e7304ee

9 files changed

Lines changed: 390 additions & 115 deletions

File tree

‎datafusion/core/tests/fuzz_cases/equivalence/ordering.rs‎

Lines changed: 23 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -16,9 +16,9 @@
1616
// under the License.
1717

1818
use crate::fuzz_cases::equivalence::utils::{
19-
TestScalarUDF, create_random_schema, create_test_params, create_test_schema_2,
20-
generate_table_for_eq_properties, generate_table_for_orderings,
21-
is_table_same_after_sort,
19+
TestScalarUDF, contains_overflowable_arithmetic, create_random_schema,
20+
create_test_params, create_test_schema_2, generate_table_for_eq_properties,
21+
generate_table_for_orderings, is_table_same_after_sort,
2222
};
2323
use arrow::compute::SortOptions;
2424
use datafusion_common::Result;
@@ -144,14 +144,27 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
144144
let err_msg = format!(
145145
"Error in test case requirement:{ordering:?}, expected: {expected:?}, eq_properties: {eq_properties}",
146146
);
147-
// Check whether ordering_satisfy API result and
148-
// experimental result matches.
149-
150-
assert_eq!(
151-
eq_properties.ordering_satisfy(ordering)?,
152-
(expected | false),
153-
"{err_msg}"
147+
// A rejection turns inconclusive only from the first `+`/`-`
148+
// key onwards, since possible overflow makes an ordering
149+
// underivable even when the sample happens to be sorted. A
150+
// table sorted by the full ordering is sorted by every prefix
151+
// of it, so a rejected arithmetic-free prefix still proves
152+
// the rejection is genuine.
153+
let conclusive_prefix = LexOrdering::new(
154+
ordering
155+
.iter()
156+
.take_while(|sort_expr| {
157+
!contains_overflowable_arithmetic(&sort_expr.expr)
158+
})
159+
.cloned(),
154160
);
161+
if eq_properties.ordering_satisfy(ordering)? {
162+
assert!(expected, "{err_msg}");
163+
} else if let Some(prefix) = conclusive_prefix
164+
&& !eq_properties.ordering_satisfy(prefix)?
165+
{
166+
assert!(!expected, "{err_msg}");
167+
}
155168
}
156169
}
157170
}

‎datafusion/core/tests/fuzz_cases/equivalence/projection.rs‎

Lines changed: 24 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -16,8 +16,8 @@
1616
// under the License.
1717

1818
use crate::fuzz_cases::equivalence::utils::{
19-
TestScalarUDF, apply_projection, create_random_schema,
20-
generate_table_for_eq_properties, is_table_same_after_sort,
19+
TestScalarUDF, apply_projection, contains_overflowable_arithmetic,
20+
create_random_schema, generate_table_for_eq_properties, is_table_same_after_sort,
2121
};
2222
use arrow::compute::SortOptions;
2323
use datafusion_common::Result;
@@ -179,13 +179,29 @@ fn ordering_satisfy_after_projection_random() -> Result<()> {
179179
let err_msg = format!(
180180
"Error in test case requirement:{ordering:?}, expected: {expected:?}, eq_properties: {eq_properties}, projected_eq: {projected_eq}, projection_mapping: {projection_mapping:?}"
181181
);
182-
// Check whether ordering_satisfy API result and
183-
// experimental result matches.
184-
assert_eq!(
185-
projected_eq.ordering_satisfy(ordering)?,
186-
expected,
187-
"{err_msg}"
182+
// Same reasoning as in `ordering.rs`: only keys from
183+
// the first `+`/`-` source onwards are inconclusive,
184+
// so assert on the longest prefix without one.
185+
let conclusive_prefix = LexOrdering::new(
186+
ordering
187+
.iter()
188+
.take_while(|sort_expr| {
189+
!projection_mapping.iter().any(|(source, targets)| {
190+
targets
191+
.iter()
192+
.any(|(target, _)| target.eq(&sort_expr.expr))
193+
&& contains_overflowable_arithmetic(source)
194+
})
195+
})
196+
.cloned(),
188197
);
198+
if projected_eq.ordering_satisfy(ordering)? {
199+
assert!(expected, "{err_msg}");
200+
} else if let Some(prefix) = conclusive_prefix
201+
&& !projected_eq.ordering_satisfy(prefix)?
202+
{
203+
assert!(!expected, "{err_msg}");
204+
}
189205
}
190206
}
191207
}

‎datafusion/core/tests/fuzz_cases/equivalence/utils.rs‎

Lines changed: 17 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,19 +21,20 @@ use std::sync::Arc;
2121
use arrow::array::{ArrayRef, Float32Array, Float64Array, RecordBatch, UInt32Array};
2222
use arrow::compute::{SortColumn, SortOptions, lexsort_to_indices, take_record_batch};
2323
use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
24+
use datafusion_common::tree_node::TreeNode;
2425
use datafusion_common::utils::{compare_rows, get_row_at_idx};
2526
use datafusion_common::{Result, exec_err, internal_datafusion_err, plan_err};
2627
use datafusion_expr::sort_properties::{ExprProperties, SortProperties};
2728
use datafusion_expr::{
28-
ColumnarValue, ScalarFunctionArgs, ScalarUDFImpl, Signature, Volatility,
29+
ColumnarValue, Operator, ScalarFunctionArgs, ScalarUDFImpl, Signature, Volatility,
2930
};
3031
use datafusion_physical_expr::equivalence::{
3132
EquivalenceClass, ProjectionMapping, convert_to_orderings,
3233
};
3334
use datafusion_physical_expr::{ConstExpr, EquivalenceProperties};
3435
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
3536
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
36-
use datafusion_physical_plan::expressions::{Column, col};
37+
use datafusion_physical_plan::expressions::{BinaryExpr, Column, col};
3738

3839
use itertools::izip;
3940
use rand::prelude::*;
@@ -209,6 +210,20 @@ fn add_equal_conditions_test() -> Result<()> {
209210
Ok(())
210211
}
211212

213+
/// Returns `true` if `expr` contains a `+` or `-` anywhere in its tree.
214+
///
215+
/// The equivalence framework conservatively discards orderings derived from
216+
/// `+`/`-` expressions, because wrapping overflow can break them over the
217+
/// type's full domain even when a finite batch happens to remain sorted.
218+
pub fn contains_overflowable_arithmetic(expr: &Arc<dyn PhysicalExpr>) -> bool {
219+
expr.exists(|e| {
220+
Ok(e.downcast_ref::<BinaryExpr>().is_some_and(|binary| {
221+
matches!(binary.op(), Operator::Plus | Operator::Minus)
222+
}))
223+
})
224+
.unwrap()
225+
}
226+
212227
/// Checks if the table (RecordBatch) remains unchanged when sorted according to the provided `required_ordering`.
213228
///
214229
/// The function works by adding a unique column of ascending integers to the original table. This column ensures

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -525,8 +525,8 @@ mod tests {
525525
vec![col_e],
526526
// requirement [a ASC, c ASC, a+b ASC],
527527
vec![(col_a, options), (col_c, options), (&a_plus_b, options)],
528-
// expected: requirement is satisfied.
529-
true,
528+
// expected: requirement is not satisfied because addition can wrap.
529+
false,
530530
),
531531
// ------------ TEST CASE 4 ------------
532532
(
@@ -672,8 +672,8 @@ mod tests {
672672
vec![col_e],
673673
// requirement [c ASC, d ASC, a + b ASC],
674674
vec![(col_c, options), (col_d, options), (&a_plus_b, options)],
675-
// expected: requirement is satisfied.
676-
true,
675+
// expected: requirement is not satisfied because addition can wrap.
676+
false,
677677
),
678678
];
679679

‎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],

0 commit comments

Comments
 (0)