Skip to content

Commit 0142e91

Browse files
authored
test: refactor key-range bitmap union fuzz test to FuzzTest trait (apache#27258)
## Which issue does this PR close? Part of apache#27082. ## Rationale for this change The `union_fuzz` test in `key_range_bitmap.rs` previously ran as a standalone `#[test]` using environment variables (`DATAFUSION_KEY_RANGE_UNION_FUZZ_ITERATIONS` and `DATAFUSION_KEY_RANGE_UNION_FUZZ_SEED`) without standardized budget controls or centralized failure reporting. Migrating this suite to the `FuzzTest` framework introduced in apache#27048 makes failures reproducible via seed reporting, connects it to the unified runner in `datafusion-fuzz`, and aligns it with project-wide fuzz testing conventions. ## What changes are included in this PR? - **`datafusion-physical-plan`**: - Expose `KeyRangePart` and `KeyRangeBitmap::union` so `datafusion-fuzz` can construct partitions and test union behavior. - Expose `offset(&self)`, `span(&self)`, `shift(&self)`, and `bits(&self)` getter accessors on `KeyRangeBitmap` for internal invariant checking. - Remove legacy `union_fuzz` and `run_union_scenario` test functions from `key_range_bitmap.rs`. - **`datafusion-fuzz`**: - Implement `KeyRangeBitmapFuzzer` in `tests/suites/key_range_bitmap.rs` implementing the `FuzzTest` trait. - Register `KeyRangeBitmapFuzzer` in `tests/fuzz.rs` and `tests/suites/mod.rs`. - **`xtask`**: - Remove `union_fuzz` from `LEGACY_FUZZ_TESTS` in `ci_steps.rs` and clean up legacy runner configuration and snapshots. ## What is the testing strategy for this PR? - Validated `datafusion-physical-plan` unit tests: - `cargo test -p datafusion-physical-plan --lib -- joins::key_range_bitmap` (all 4 unit tests pass) - Validated unified fuzz runner: - `cargo test -p datafusion-fuzz --test fuzz --features extended_tests` (256 cases pass) - Validated `xtask` legacy fuzz test verification: - `cargo test -p datafusion-xtask -- legacy_fuzz_tests_exist` ## Are there any user-facing changes? No user-facing changes.
1 parent 74f841f commit 0142e91

5 files changed

Lines changed: 259 additions & 204 deletions

File tree

‎datafusion/fuzz/tests/fuzz.rs‎

Lines changed: 21 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -20,15 +20,27 @@ mod suites;
2020
#[tokio::test(flavor = "multi_thread")]
2121
async fn fuzz_tests() -> Result<()> {
2222
let spill_pool = suites::spill_pool::SpillPoolFuzzer;
23-
let suites = [Suite::new(
24-
&spill_pool,
25-
RunConfig {
26-
run_seed: Some(0),
27-
max_cases: Some(1000),
28-
time_limit: None,
29-
cases_per_dataset: 1000,
30-
},
31-
)];
23+
let key_range_bitmap = suites::key_range_bitmap::KeyRangeBitmapFuzzer;
24+
let suites = [
25+
Suite::new(
26+
&spill_pool,
27+
RunConfig {
28+
run_seed: Some(0),
29+
max_cases: Some(1000),
30+
time_limit: None,
31+
cases_per_dataset: 1000,
32+
},
33+
),
34+
Suite::new(
35+
&key_range_bitmap,
36+
RunConfig {
37+
run_seed: Some(0),
38+
max_cases: Some(10000),
39+
time_limit: None,
40+
cases_per_dataset: 10000,
41+
},
42+
),
43+
];
3244
run_suites(suites).await
3345
}
3446

Lines changed: 195 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,195 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3+
// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4+
5+
//! Randomized partitions against [`KeyRangeBitmap::union`]'s contract: it
6+
//! never excludes a key any part may hold, equals the bitmap built from all
7+
//! parts' keys when no part brings its own bitmap, and only widens that
8+
//! bitmap's buckets when one does.
9+
10+
use std::future::Future;
11+
use std::sync::Arc;
12+
13+
use arrow::array::{ArrayRef, Int64Array};
14+
use arrow::buffer::BooleanBuffer;
15+
use datafusion_common::{Result, ScalarValue};
16+
use datafusion_physical_plan::joins::key_range_bitmap::{KeyRangeBitmap, KeyRangePart};
17+
use rand::rngs::StdRng;
18+
use rand::{Rng, SeedableRng};
19+
use test_utils::fuzz::FuzzTest;
20+
21+
pub(crate) struct KeyRangeBitmapFuzzer;
22+
23+
fn parts_of(b: &KeyRangeBitmap) -> (u64, u64, u32, &BooleanBuffer) {
24+
(b.offset(), b.span(), b.shift(), b.bits())
25+
}
26+
27+
enum Part {
28+
Keys(ArrayRef),
29+
Range(ScalarValue, ScalarValue),
30+
Bitmap(KeyRangeBitmap),
31+
}
32+
33+
impl FuzzTest for KeyRangeBitmapFuzzer {
34+
type Dataset = ();
35+
36+
fn name(&self) -> &str {
37+
"key_range_bitmap_union"
38+
}
39+
40+
fn prepare_dataset(&self, _seed: u64) -> impl Future<Output = Result<()>> {
41+
std::future::ready(Ok(()))
42+
}
43+
44+
fn run_case(&self, _dataset: &(), seed: u64) -> impl Future<Output = Result<()>> {
45+
let mut rng = StdRng::seed_from_u64(seed);
46+
// Domain widths from one key per bucket to many keys per bucket, so
47+
// the union's buckets are sometimes exact and sometimes coarse.
48+
let width = [64i64, 1 << 12, 1 << 24, 1 << 40][rng.random_range(0..4)];
49+
let start = rng.random_range(-(1i64 << 50)..(1i64 << 50));
50+
let key = |rng: &mut StdRng| start + rng.random_range(0..width);
51+
let keys_array =
52+
|keys: &[i64]| -> ArrayRef { Arc::new(Int64Array::from(keys.to_vec())) };
53+
let scalar = |key: i64| ScalarValue::Int64(Some(key));
54+
55+
// Each part, and every key any part may hold.
56+
let mut parts = vec![];
57+
let mut all_keys = vec![];
58+
let mut has_bitmap = false;
59+
for _ in 0..rng.random_range(1..5) {
60+
if rng.random_bool(1.0 / 3.0) {
61+
// Narrow, so every key it may hold can be listed.
62+
let lo = key(&mut rng);
63+
let hi = lo + rng.random_range(0..64);
64+
parts.push(Part::Range(scalar(lo), scalar(hi)));
65+
all_keys.extend(lo..=hi);
66+
continue;
67+
}
68+
let keys: Vec<i64> = (0..rng.random_range(1..50))
69+
.map(|_| key(&mut rng))
70+
.collect();
71+
let (lo, hi) = (*keys.iter().min().unwrap(), *keys.iter().max().unwrap());
72+
let bitmap = rng
73+
.random_bool(0.5)
74+
.then(|| {
75+
KeyRangeBitmap::try_new(
76+
&keys_array(&keys),
77+
&scalar(lo),
78+
&scalar(hi),
79+
0,
80+
)
81+
})
82+
.flatten();
83+
parts.push(match bitmap {
84+
Some(bitmap) => {
85+
has_bitmap = true;
86+
Part::Bitmap(bitmap)
87+
}
88+
None => Part::Keys(keys_array(&keys)),
89+
});
90+
all_keys.extend(keys);
91+
}
92+
let min = ScalarValue::Int64(all_keys.iter().min().copied());
93+
let max = ScalarValue::Int64(all_keys.iter().max().copied());
94+
let context = format!(
95+
"seed {seed}: width {width}, {} parts, {} keys",
96+
parts.len(),
97+
all_keys.len()
98+
);
99+
100+
let union = KeyRangeBitmap::union(
101+
&min,
102+
&max,
103+
&parts
104+
.iter()
105+
.map(|part| match part {
106+
Part::Keys(keys) => KeyRangePart::Keys(keys.as_ref()),
107+
Part::Range(min, max) => KeyRangePart::Range { min, max },
108+
Part::Bitmap(bitmap) => KeyRangePart::Bitmap(bitmap),
109+
})
110+
.collect::<Vec<_>>(),
111+
);
112+
// Reference: one bitmap built straight from every key any part may hold.
113+
let exact = KeyRangeBitmap::try_new(&keys_array(&all_keys), &min, &max, 0);
114+
115+
// Never excludes a key any part may hold.
116+
if let Some(union) = &union {
117+
for key in &all_keys {
118+
assert!(
119+
union.may_contain_range(*key as u64, *key as u64),
120+
"{context}: dropped key {key}"
121+
);
122+
}
123+
}
124+
if has_bitmap {
125+
// A part's bitmap can only widen buckets: every bucket the exact
126+
// bitmap sets, the union sets too.
127+
match (&union, &exact) {
128+
(_, None) => assert!(union.is_none(), "{context}"),
129+
(None, Some(_)) => {}
130+
(Some(union), Some(exact)) => {
131+
assert_eq!(
132+
(union.offset(), union.span(), union.shift()),
133+
(exact.offset(), exact.span(), exact.shift()),
134+
"{context}"
135+
);
136+
for bucket in exact.bits().set_indices() {
137+
assert!(union.bits().value(bucket), "{context}: bucket {bucket}");
138+
}
139+
}
140+
}
141+
// Each set bucket of a part's bitmap stands for its whole key range,
142+
// so the union equals the one over those ranges given as `Range`s.
143+
let ranges: Vec<(ScalarValue, ScalarValue)> = parts
144+
.iter()
145+
.flat_map(|part| match part {
146+
Part::Bitmap(bitmap) => bitmap
147+
.bits()
148+
.set_indices()
149+
.map(|bucket| {
150+
let lo = (bucket as u64) << bitmap.shift();
151+
let hi = lo
152+
.saturating_add((1u64 << bitmap.shift()) - 1)
153+
.min(bitmap.span());
154+
let key =
155+
|at: u64| scalar(bitmap.offset().wrapping_add(at) as i64);
156+
(key(lo), key(hi))
157+
})
158+
.collect(),
159+
_ => vec![],
160+
})
161+
.collect();
162+
let expanded = KeyRangeBitmap::union(
163+
&min,
164+
&max,
165+
&parts
166+
.iter()
167+
.filter_map(|part| match part {
168+
Part::Keys(keys) => Some(KeyRangePart::Keys(keys.as_ref())),
169+
Part::Range(min, max) => Some(KeyRangePart::Range { min, max }),
170+
Part::Bitmap(_) => None,
171+
})
172+
.chain(
173+
ranges
174+
.iter()
175+
.map(|(min, max)| KeyRangePart::Range { min, max }),
176+
)
177+
.collect::<Vec<_>>(),
178+
);
179+
assert_eq!(
180+
union.as_ref().map(parts_of),
181+
expanded.as_ref().map(parts_of),
182+
"{context}: bitmap parts differ from their bucket ranges"
183+
);
184+
} else {
185+
// Keys and ranges mark exactly the buckets their keys fall in.
186+
assert_eq!(
187+
union.as_ref().map(parts_of),
188+
exact.as_ref().map(parts_of),
189+
"{context}"
190+
);
191+
}
192+
193+
std::future::ready(Ok(()))
194+
}
195+
}

‎datafusion/fuzz/tests/suites/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,4 +4,5 @@
44

55
//! Implementation for fuzz test cases.
66
7+
pub(crate) mod key_range_bitmap;
78
pub(crate) mod spill_pool;

0 commit comments

Comments
 (0)