Skip to content

Commit e8940ac

Browse files
test: generate NULLs in equivalence fuzz tests (#26086)
## 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. --> Part of #24243 ## Rationale for this change <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> The equivalence fuzz tests never generated NULLs. So they could not catch NULL-ordering bugs in `SortProperties` propagation such as #11596 and #24208. ## What changes are included in this PR? <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> - Generated columns contain NULLs at configurable rates (`NULL_PCTS = [0.0, 0.1, 0.5]`), crossed with every seed; the schema is nullable only when the rate is non-zero. - `create_random_schema` picks random `SortOptions` for each ordering key. - Requirements with random `SortOptions` are checked only for soundness: if `ordering_satisfy` accepts an ordering, the data must be sorted by it. The converse is not checked, since one batch can be sorted by coincidence (e.g. NULLs of independent columns landing in the same rows). For the same reason, `contains_overflowable_arithmetic` is renamed to `contains_conservative_ordering_op` and also covers comparisons and `AND`/`OR`. ## What is the testing strategy for this PR? <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code Briefly describe how this PR is tested, and point to the specific tests you added. For example: 'This new feature is covered by the `sqllogictest` cases added in `foo.slt`'. If this PR does not add tests, explain why. For example, if the change is already covered by existing tests, please mention it. You should also check the `codecov` bot reply on this PR to confirm the changed code is exercised. --> Test-only change. Verified locally that reverting the fixes from #24276 and #24206 makes `test_ordering_satisfy_with_equivalence_complex_random` fail, and that it passes on main: ```bash git revert -n ceaef16 4042812 cargo test -p datafusion --test fuzz --features extended_tests equivalence # test_ordering_satisfy_with_equivalence_complex_random fails ``` ## Are there any user-facing changes? <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. --> No
1 parent 269e49f commit e8940ac

4 files changed

Lines changed: 384 additions & 72 deletions

File tree

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

Lines changed: 237 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -3,22 +3,27 @@
33
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
44

55
use crate::fuzz_cases::equivalence::utils::{
6-
TestScalarUDF, contains_overflowable_arithmetic, create_random_schema,
7-
create_test_params, create_test_schema_2, generate_table_for_eq_properties,
8-
generate_table_for_orderings, is_table_same_after_sort,
6+
NULL_PCTS, TestScalarUDF, assert_random_ordering_satisfy_is_sound,
7+
contains_conservative_ordering_op, create_random_schema, create_test_params,
8+
create_test_schema_2, generate_table_for_eq_properties, generate_table_for_orderings,
9+
is_table_same_after_sort,
910
};
10-
use arrow::compute::SortOptions;
11-
use datafusion_common::Result;
11+
use arrow::array::{ArrayRef, Float64Array, RecordBatch, new_null_array};
12+
use arrow::compute::{SortOptions, sort};
13+
use arrow::datatypes::{DataType, Field, Schema};
1214
use datafusion_common::config::ConfigOptions;
15+
use datafusion_common::{Result, ScalarValue};
1316
use datafusion_expr::{Operator, ScalarUDF};
14-
use datafusion_physical_expr::ScalarFunctionExpr;
1517
use datafusion_physical_expr::equivalence::{
1618
convert_to_orderings, convert_to_sort_exprs,
1719
};
18-
use datafusion_physical_expr::expressions::{BinaryExpr, col};
20+
use datafusion_physical_expr::expressions::{BinaryExpr, col, lit};
21+
use datafusion_physical_expr::{EquivalenceProperties, ScalarFunctionExpr};
1922
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
2023
use datafusion_physical_expr_common::sort_expr::{LexOrdering, PhysicalSortExpr};
2124
use itertools::Itertools;
25+
use rand::rngs::StdRng;
26+
use rand::{Rng, SeedableRng};
2227
use std::sync::Arc;
2328

2429
#[test]
@@ -31,12 +36,16 @@ fn test_ordering_satisfy_with_equivalence_random() -> Result<()> {
3136
nulls_first: false,
3237
};
3338

34-
for seed in 0..N_RANDOM_SCHEMA {
39+
for (seed, &null_pct) in (0..N_RANDOM_SCHEMA).cartesian_product(NULL_PCTS) {
3540
// Create a random schema with random properties
36-
let (test_schema, eq_properties) = create_random_schema(seed as u64)?;
41+
let (test_schema, eq_properties) = create_random_schema(seed as u64, null_pct)?;
3742
// Generate a data that satisfies properties given
38-
let table_data_with_properties =
39-
generate_table_for_eq_properties(&eq_properties, N_ELEMENTS, N_DISTINCT)?;
43+
let table_data_with_properties = generate_table_for_eq_properties(
44+
&eq_properties,
45+
N_ELEMENTS,
46+
N_DISTINCT,
47+
null_pct,
48+
)?;
4049
let col_exprs = [
4150
col("a", &test_schema)?,
4251
col("b", &test_schema)?,
@@ -46,8 +55,16 @@ fn test_ordering_satisfy_with_equivalence_random() -> Result<()> {
4655
col("f", &test_schema)?,
4756
];
4857

58+
let mut options_rng = StdRng::seed_from_u64(seed as u64);
4959
for n_req in 1..=col_exprs.len() {
5060
for exprs in col_exprs.iter().combinations(n_req) {
61+
assert_random_ordering_satisfy_is_sound(
62+
&eq_properties,
63+
&exprs,
64+
&table_data_with_properties,
65+
&mut options_rng,
66+
&format!("seed: {seed}, null_pct: {null_pct}"),
67+
)?;
5168
let sort_exprs = exprs
5269
.into_iter()
5370
.map(|expr| PhysicalSortExpr::new(Arc::clone(expr), SORT_OPTIONS));
@@ -59,7 +76,7 @@ fn test_ordering_satisfy_with_equivalence_random() -> Result<()> {
5976
&table_data_with_properties,
6077
)?;
6178
let err_msg = format!(
62-
"Error in test case requirement:{ordering:?}, expected: {expected:?}, eq_properties {eq_properties}"
79+
"Error in test case seed: {seed}, null_pct: {null_pct}, requirement:{ordering:?}, expected: {expected:?}, eq_properties {eq_properties}"
6380
);
6481
// Check whether ordering_satisfy API result and
6582
// experimental result matches.
@@ -75,6 +92,19 @@ fn test_ordering_satisfy_with_equivalence_random() -> Result<()> {
7592
Ok(())
7693
}
7794

95+
const N_EXHAUSTIVE_EXPRS: usize = 8;
96+
const SAMPLED_COMBINATION_PROBABILITY: f64 = 0.03;
97+
98+
/// Selects all combinations of the first `N_EXHAUSTIVE_EXPRS` expressions and
99+
/// all combinations of at most two expressions, and samples the others.
100+
fn is_combination_selected(indices: &[usize], rng: &mut StdRng) -> bool {
101+
let only_exhaustive_exprs =
102+
indices.last().is_none_or(|&last| last < N_EXHAUSTIVE_EXPRS);
103+
only_exhaustive_exprs
104+
|| indices.len() <= 2
105+
|| rng.random_bool(SAMPLED_COMBINATION_PROBABILITY)
106+
}
107+
78108
#[test]
79109
fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
80110
const N_RANDOM_SCHEMA: usize = 100;
@@ -85,12 +115,16 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
85115
nulls_first: false,
86116
};
87117

88-
for seed in 0..N_RANDOM_SCHEMA {
118+
for (seed, &null_pct) in (0..N_RANDOM_SCHEMA).cartesian_product(NULL_PCTS) {
89119
// Create a random schema with random properties
90-
let (test_schema, eq_properties) = create_random_schema(seed as u64)?;
120+
let (test_schema, eq_properties) = create_random_schema(seed as u64, null_pct)?;
91121
// Generate a data that satisfies properties given
92-
let table_data_with_properties =
93-
generate_table_for_eq_properties(&eq_properties, N_ELEMENTS, N_DISTINCT)?;
122+
let table_data_with_properties = generate_table_for_eq_properties(
123+
&eq_properties,
124+
N_ELEMENTS,
125+
N_DISTINCT,
126+
null_pct,
127+
)?;
94128

95129
let test_fun = Arc::new(ScalarUDF::new_from_impl(TestScalarUDF::new()));
96130
let col_a = col("a", &test_schema)?;
@@ -105,6 +139,31 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
105139
Operator::Plus,
106140
col("b", &test_schema)?,
107141
)) as Arc<dyn PhysicalExpr>;
142+
let binary = |lhs: Arc<dyn PhysicalExpr>, op, rhs: Arc<dyn PhysicalExpr>| {
143+
Arc::new(BinaryExpr::new(lhs, op, rhs)) as Arc<dyn PhysicalExpr>
144+
};
145+
// Ordered when `a` and `b` lead orderings in opposite directions.
146+
let a_gt_b = binary(
147+
col("a", &test_schema)?,
148+
Operator::Gt,
149+
col("b", &test_schema)?,
150+
);
151+
// `e` is constant, so each operand has the ordering of its column.
152+
// `a` and `b` lead separate orderings whose NULLs sit in different
153+
// rows, which is where Kleene `AND`/`OR` can break an ordering.
154+
let a_gt_e = binary(
155+
col("a", &test_schema)?,
156+
Operator::Gt,
157+
col("e", &test_schema)?,
158+
);
159+
let b_gt_e = binary(
160+
col("b", &test_schema)?,
161+
Operator::Gt,
162+
col("e", &test_schema)?,
163+
);
164+
let a_gt_e_and_b_gt_e =
165+
binary(Arc::clone(&a_gt_e), Operator::And, Arc::clone(&b_gt_e));
166+
let a_gt_e_or_b_gt_e = binary(a_gt_e, Operator::Or, b_gt_e);
108167
let exprs = [
109168
col("a", &test_schema)?,
110169
col("b", &test_schema)?,
@@ -114,10 +173,26 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
114173
col("f", &test_schema)?,
115174
floor_a,
116175
a_plus_b,
176+
a_gt_b,
177+
a_gt_e_and_b_gt_e,
178+
a_gt_e_or_b_gt_e,
117179
];
118180

181+
let mut options_rng = StdRng::seed_from_u64(seed as u64);
182+
let mut selection_rng = StdRng::seed_from_u64(!(seed as u64));
119183
for n_req in 1..=exprs.len() {
120-
for exprs in exprs.iter().combinations(n_req) {
184+
for indices in (0..exprs.len()).combinations(n_req) {
185+
if !is_combination_selected(&indices, &mut selection_rng) {
186+
continue;
187+
}
188+
let exprs = indices.iter().map(|&i| &exprs[i]).collect::<Vec<_>>();
189+
assert_random_ordering_satisfy_is_sound(
190+
&eq_properties,
191+
&exprs,
192+
&table_data_with_properties,
193+
&mut options_rng,
194+
&format!("seed: {seed}, null_pct: {null_pct}"),
195+
)?;
121196
let sort_exprs = exprs
122197
.into_iter()
123198
.map(|expr| PhysicalSortExpr::new(Arc::clone(expr), SORT_OPTIONS));
@@ -129,19 +204,20 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
129204
&table_data_with_properties,
130205
)?;
131206
let err_msg = format!(
132-
"Error in test case requirement:{ordering:?}, expected: {expected:?}, eq_properties: {eq_properties}",
207+
"Error in test case seed: {seed}, null_pct: {null_pct}, requirement:{ordering:?}, expected: {expected:?}, eq_properties: {eq_properties}",
133208
);
134-
// A rejection turns inconclusive only from the first `+`/`-`
135-
// key onwards, since possible overflow makes an ordering
136-
// underivable even when the sample happens to be sorted. A
137-
// table sorted by the full ordering is sorted by every prefix
138-
// of it, so a rejected arithmetic-free prefix still proves
139-
// the rejection is genuine.
209+
// A rejection turns inconclusive only from the first key with
210+
// a conservative ordering rule onwards (see
211+
// `contains_conservative_ordering_op`), since such a rule can
212+
// make an ordering underivable even when the sample happens
213+
// to be sorted. A table sorted by the full ordering is sorted
214+
// by every prefix of it, so a rejected prefix without such
215+
// keys still proves the rejection is genuine.
140216
let conclusive_prefix = LexOrdering::new(
141217
ordering
142218
.iter()
143219
.take_while(|sort_expr| {
144-
!contains_overflowable_arithmetic(&sort_expr.expr)
220+
!contains_conservative_ordering_op(&sort_expr.expr)
145221
})
146222
.cloned(),
147223
);
@@ -159,6 +235,140 @@ fn test_ordering_satisfy_with_equivalence_complex_random() -> Result<()> {
159235
Ok(())
160236
}
161237

238+
const ALL_SORT_OPTIONS: [SortOptions; 4] = [
239+
SortOptions {
240+
descending: false,
241+
nulls_first: false,
242+
},
243+
SortOptions {
244+
descending: false,
245+
nulls_first: true,
246+
},
247+
SortOptions {
248+
descending: true,
249+
nulls_first: false,
250+
},
251+
SortOptions {
252+
descending: true,
253+
nulls_first: true,
254+
},
255+
];
256+
257+
/// Returns `0.0..=5.0` and `n_nulls` NULLs, sorted with `options`.
258+
fn sorted_f64_array(options: SortOptions, n_nulls: usize) -> Result<ArrayRef> {
259+
let values = (0..6)
260+
.map(|v| Some(v as f64))
261+
.chain(std::iter::repeat_n(None, n_nulls))
262+
.collect::<Float64Array>();
263+
Ok(sort(&values, Some(options))?)
264+
}
265+
266+
/// Returns whether `eq_properties` claims the ordering of `exprs` with
267+
/// `options`, and asserts that `batch` has every claimed ordering.
268+
fn assert_claim_is_sound(
269+
eq_properties: &EquivalenceProperties,
270+
exprs: &[&Arc<dyn PhysicalExpr>],
271+
options: SortOptions,
272+
batch: &RecordBatch,
273+
) -> Result<bool> {
274+
let sort_exprs = exprs
275+
.iter()
276+
.map(|expr| PhysicalSortExpr::new(Arc::clone(expr), options));
277+
let Some(ordering) = LexOrdering::new(sort_exprs) else {
278+
unreachable!("Test should always produce non-degenerate orderings");
279+
};
280+
let claimed = eq_properties.ordering_satisfy(ordering.clone())?;
281+
if claimed {
282+
assert!(
283+
is_table_same_after_sort(ordering.clone(), batch)?,
284+
"requirement: {ordering:?}, eq_properties: {eq_properties}"
285+
);
286+
}
287+
Ok(claimed)
288+
}
289+
290+
#[test]
291+
fn test_ordering_satisfy_all_null_ordered_column() -> Result<()> {
292+
let schema = Arc::new(Schema::new(vec![
293+
Field::new("a", DataType::Float64, true),
294+
Field::new("b", DataType::Float64, true),
295+
]));
296+
let col_a = &col("a", &schema)?;
297+
let col_b = &col("b", &schema)?;
298+
for options in ALL_SORT_OPTIONS {
299+
let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
300+
eq_properties.add_ordering([
301+
PhysicalSortExpr::new(Arc::clone(col_a), options),
302+
PhysicalSortExpr::new(Arc::clone(col_b), options),
303+
]);
304+
let batch = RecordBatch::try_new(
305+
Arc::clone(&schema),
306+
vec![
307+
new_null_array(&DataType::Float64, 6),
308+
sorted_f64_array(options, 0)?,
309+
],
310+
)?;
311+
for required in ALL_SORT_OPTIONS {
312+
for exprs in [
313+
vec![col_a],
314+
vec![col_b],
315+
vec![col_a, col_b],
316+
vec![col_b, col_a],
317+
] {
318+
assert_claim_is_sound(&eq_properties, &exprs, required, &batch)?;
319+
}
320+
}
321+
for exprs in [vec![col_a], vec![col_a, col_b]] {
322+
assert!(
323+
assert_claim_is_sound(&eq_properties, &exprs, options, &batch)?,
324+
"requirement: {exprs:?} {options:?}, eq_properties: {eq_properties}"
325+
);
326+
}
327+
}
328+
Ok(())
329+
}
330+
331+
#[test]
332+
fn test_ordering_satisfy_null_constant_operand() -> Result<()> {
333+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Float64, true)]));
334+
let col_a = col("a", &schema)?;
335+
// `x` has the ordering of `a`.
336+
let x =
337+
Arc::new(BinaryExpr::new(col_a, Operator::Gt, lit(2.0))) as Arc<dyn PhysicalExpr>;
338+
let null = lit(ScalarValue::Boolean(None));
339+
let x_and_null = Arc::new(BinaryExpr::new(
340+
Arc::clone(&x),
341+
Operator::And,
342+
Arc::clone(&null),
343+
)) as Arc<dyn PhysicalExpr>;
344+
let x_or_null = Arc::new(BinaryExpr::new(Arc::clone(&x), Operator::Or, null))
345+
as Arc<dyn PhysicalExpr>;
346+
for options in ALL_SORT_OPTIONS {
347+
let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
348+
eq_properties.add_ordering([PhysicalSortExpr::new(col("a", &schema)?, options)]);
349+
let batch = RecordBatch::try_new(
350+
Arc::clone(&schema),
351+
vec![sorted_f64_array(options, 2)?],
352+
)?;
353+
assert!(
354+
assert_claim_is_sound(&eq_properties, &[&x], options, &batch)?,
355+
"requirement: {x} {options:?}, eq_properties: {eq_properties}"
356+
);
357+
// A NULL operand moves rows to the NULL position, so `AND` and `OR`
358+
// keep the ordering only for some NULL positions.
359+
let mut n_claimed = 0;
360+
for expr in [&x_and_null, &x_or_null] {
361+
for required in ALL_SORT_OPTIONS {
362+
if assert_claim_is_sound(&eq_properties, &[expr], required, &batch)? {
363+
n_claimed += 1;
364+
}
365+
}
366+
}
367+
assert!(n_claimed > 0, "no claim with {options:?}");
368+
}
369+
Ok(())
370+
}
371+
162372
#[test]
163373
fn test_ordering_satisfy_with_equivalence() -> Result<()> {
164374
// Schema satisfies following orderings:
@@ -184,7 +394,7 @@ fn test_ordering_satisfy_with_equivalence() -> Result<()> {
184394
nulls_first: true,
185395
};
186396
let table_data_with_properties =
187-
generate_table_for_eq_properties(&eq_properties, 625, 5)?;
397+
generate_table_for_eq_properties(&eq_properties, 625, 5, 0.0)?;
188398

189399
// First element in the tuple stores vector of requirement, second element is the expected return value for ordering_satisfy function
190400
let requirements = vec![
@@ -359,7 +569,7 @@ fn test_ordering_satisfy_on_data() -> Result<()> {
359569
];
360570
let orderings = convert_to_orderings(&orderings);
361571

362-
let batch = generate_table_for_orderings(orderings, schema, 1000, 10)?;
572+
let batch = generate_table_for_orderings(orderings, schema, 1000, 10, 0.0)?;
363573

364574
// [a ASC, c ASC, d ASC] cannot be deduced
365575
let ordering = vec![

0 commit comments

Comments
 (0)