Skip to content

Commit ca5d10b

Browse files
authored
perf: extend string IN-list pruning benchmark coverage (apache#24836)
## Which issue does this PR close? - Closes apache#24707. ## Rationale for this change The string IN-list pruning benchmark only covered domain sizes 20, 21, 256, and 1,024 with a fixed 4,096 pruning containers. This did not provide the small-list or container-scaling measurements needed by the follow-up work in apache#24709 and apache#24710. This PR extends the benchmark before making any production threshold change, following the contributor guide's recommendation to isolate benchmark additions from the optimization they are intended to evaluate. ## What changes are included in this PR? - Add domain sizes 1, 2, 4, 8, and 16 while retaining the existing boundary and large-domain cases. - Evaluate each domain at 16, 256, and 4,096 pruning containers. - Keep construction benchmarks independent of container count. - Preserve the existing 4,096-container Criterion benchmark IDs so historical baselines remain comparable. - Validate both representations produce the same pruning results for every evaluation matrix cell outside the timed loop. The production pruning implementation and its current threshold are unchanged. ## What is the testing strategy for this PR? - `./dev/rust_lint.sh` - `cargo test --locked -p datafusion-pruning` (95 tests passed) - Extended workspace test suite: ```shell RUST_BACKTRACE=1 cargo test --locked --profile ci --exclude datafusion-examples --exclude datafusion-benchmarks --exclude datafusion-cli --workspace --lib --tests --bins --features avro,json,backtrace,extended_tests,recursive_protection,parquet_encryption ``` - Full 72-case Criterion matrix: ```shell cargo bench --locked --profile release-nonlto -p datafusion-pruning --bench string_in_list_pruning -- --sample-size 10 --warm-up-time 0.1 --measurement-time 0.2 --noplot ``` ## Are there any user-facing changes? No. This PR only extends benchmark coverage.
1 parent 93eaa0d commit ca5d10b

1 file changed

Lines changed: 151 additions & 86 deletions

File tree

‎datafusion/pruning/benches/string_in_list_pruning.rs‎

Lines changed: 151 additions & 86 deletions
Original file line numberDiff line numberDiff line change
@@ -15,23 +15,26 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
//! Compare compact string IN-list pruning with per-value min/max expansion.
18+
//! Compare string IN-list pruning with per-value min/max expansion.
1919
//!
2020
//! Every case raises `max_in_list_size` to the domain size. On a baseline
2121
//! without compact pruning, `in_list` and `not_in_list` measure the ordinary
2222
//! raised-cap path. The explicit `expanded_or` and `expanded_and` are balanced
2323
//! trees of (in)equalities, which produce the same per-value statistics checks
2424
//! without making the baseline depend on a deeply nested expression.
2525
//!
26-
//! The main cases alternate intervals pinned to a domain member with intervals
27-
//! that span a sparse gap. NULL-containing variants cover the optimized
26+
//! Small domain sizes make representation threshold changes measurable, and the
27+
//! evaluation matrix varies the number of statistics containers. The main cases
28+
//! alternate intervals pinned to a domain member with intervals that span a
29+
//! sparse gap. NULL-containing variants cover the optimized
2830
//! filter-semantics paths, including the constant-false `NOT IN` rewrite.
2931
//! Supplemental `NOT IN` cases measure uniform singleton containers, long bounds,
3032
//! and long literals that share bounds' prefixes. Bloom filters are not involved.
3133
//!
3234
//! Run with `cargo bench -p datafusion-pruning --bench string_in_list_pruning`.
33-
//! The construction benchmarks reuse their input physical expressions; the
34-
//! evaluation benchmarks reuse their already-built pruning predicates.
35+
//! Construction is independent of the statistics batch size, so it varies only
36+
//! the IN-list domain size. Evaluation varies both the domain size and number
37+
//! of containers, reusing already-built pruning predicates and statistics.
3538
3639
use std::collections::HashSet;
3740
use std::hint::black_box;
@@ -44,15 +47,47 @@ use datafusion_common::{Column, ScalarValue};
4447
use datafusion_expr_common::operator::Operator;
4548
use datafusion_physical_expr::PhysicalExprRef;
4649
use datafusion_physical_expr::expressions::{BinaryExpr, col, in_list, lit};
47-
use datafusion_pruning::{PruningPredicate, PruningPredicateBuilder, PruningStatistics};
50+
use datafusion_pruning::{
51+
MAX_IN_LIST_SIZE, PruningPredicate, PruningPredicateBuilder, PruningStatistics,
52+
};
4853

49-
const DOMAIN_SIZES: [usize; 4] = [20, 21, 256, 1024];
50-
const CONTAINERS: usize = 4096;
54+
const DOMAIN_SIZES: [usize; 9] = [1, 2, 4, 8, 16, 20, 21, 256, 1024];
55+
const CONTAINER_COUNTS: [usize; 3] = [16, 256, 4096];
56+
const BASELINE_CONTAINER_COUNT: usize = 4096;
5157

5258
fn value(index: usize) -> String {
5359
format!("key{index:08}")
5460
}
5561

62+
/// Maps an interval pair to an evenly distributed position in the full domain.
63+
///
64+
/// When there are more pairs than domain values, the full distribution repeats.
65+
fn sampled_domain_index(
66+
pair_index: usize,
67+
pair_count: usize,
68+
domain_size: usize,
69+
) -> usize {
70+
let sampled_positions = pair_count.min(domain_size);
71+
let position = pair_index % sampled_positions;
72+
if sampled_positions == 1 {
73+
0
74+
} else {
75+
position * (domain_size - 1) / (sampled_positions - 1)
76+
}
77+
}
78+
79+
fn validate_sampling_distribution() {
80+
assert_eq!(
81+
(0..8)
82+
.map(|pair| sampled_domain_index(pair, 8, 1024))
83+
.collect::<Vec<_>>(),
84+
vec![0, 146, 292, 438, 584, 730, 876, 1023]
85+
);
86+
assert_eq!(sampled_domain_index(0, 8, 1), 0);
87+
assert_eq!(sampled_domain_index(1024, 2048, 1024), 0);
88+
assert_eq!(sampled_domain_index(2047, 2048, 1024), 1023);
89+
}
90+
5691
fn balanced(expressions: &[PhysicalExprRef], op: Operator) -> PhysicalExprRef {
5792
if expressions.len() == 1 {
5893
return Arc::clone(&expressions[0]);
@@ -102,20 +137,21 @@ struct IntervalStatistics {
102137
}
103138

104139
impl IntervalStatistics {
105-
fn new(domain_size: usize) -> Self {
106-
let min = StringViewArray::from_iter_values((0..CONTAINERS).map(|index| {
107-
let start = (index / 2 % domain_size) * 10;
140+
fn new(domain_size: usize, container_count: usize) -> Self {
141+
let pair_count = container_count.div_ceil(2);
142+
let min = StringViewArray::from_iter_values((0..container_count).map(|index| {
143+
let start = sampled_domain_index(index / 2, pair_count, domain_size) * 10;
108144
value(start + if index % 2 == 0 { 0 } else { 3 })
109145
}));
110-
let max = StringViewArray::from_iter_values((0..CONTAINERS).map(|index| {
111-
let start = (index / 2 % domain_size) * 10;
146+
let max = StringViewArray::from_iter_values((0..container_count).map(|index| {
147+
let start = sampled_domain_index(index / 2, pair_count, domain_size) * 10;
112148
value(start + if index % 2 == 0 { 0 } else { 7 })
113149
}));
114150
Self {
115151
min: Arc::new(min),
116152
max: Arc::new(max),
117-
null_counts: Arc::new(UInt64Array::from(vec![0; CONTAINERS])),
118-
row_counts: Arc::new(UInt64Array::from(vec![128; CONTAINERS])),
153+
null_counts: Arc::new(UInt64Array::from(vec![0; container_count])),
154+
row_counts: Arc::new(UInt64Array::from(vec![128; container_count])),
119155
}
120156
}
121157

@@ -125,14 +161,16 @@ impl IntervalStatistics {
125161
}
126162

127163
fn singleton(value: &str) -> Self {
128-
let min =
129-
StringViewArray::from_iter_values(std::iter::repeat_n(value, CONTAINERS));
164+
let min = StringViewArray::from_iter_values(std::iter::repeat_n(
165+
value,
166+
BASELINE_CONTAINER_COUNT,
167+
));
130168
let max = min.clone();
131169
Self {
132170
min: Arc::new(min),
133171
max: Arc::new(max),
134-
null_counts: Arc::new(UInt64Array::from(vec![0; CONTAINERS])),
135-
row_counts: Arc::new(UInt64Array::from(vec![128; CONTAINERS])),
172+
null_counts: Arc::new(UInt64Array::from(vec![0; BASELINE_CONTAINER_COUNT])),
173+
row_counts: Arc::new(UInt64Array::from(vec![128; BASELINE_CONTAINER_COUNT])),
136174
}
137175
}
138176

@@ -143,14 +181,14 @@ impl IntervalStatistics {
143181
Self {
144182
min: Arc::new(StringViewArray::from_iter_values(std::iter::repeat_n(
145183
min.as_str(),
146-
CONTAINERS,
184+
BASELINE_CONTAINER_COUNT,
147185
))),
148186
max: Arc::new(StringViewArray::from_iter_values(std::iter::repeat_n(
149187
max.as_str(),
150-
CONTAINERS,
188+
BASELINE_CONTAINER_COUNT,
151189
))),
152-
null_counts: Arc::new(UInt64Array::from(vec![0; CONTAINERS])),
153-
row_counts: Arc::new(UInt64Array::from(vec![128; CONTAINERS])),
190+
null_counts: Arc::new(UInt64Array::from(vec![0; BASELINE_CONTAINER_COUNT])),
191+
row_counts: Arc::new(UInt64Array::from(vec![128; BASELINE_CONTAINER_COUNT])),
154192
}
155193
}
156194
}
@@ -165,7 +203,7 @@ impl PruningStatistics for IntervalStatistics {
165203
}
166204

167205
fn num_containers(&self) -> usize {
168-
CONTAINERS
206+
self.min.len()
169207
}
170208

171209
fn null_counts(&self, column: &Column) -> Option<ArrayRef> {
@@ -200,7 +238,6 @@ struct BenchmarkCase {
200238
not_in_list_predicate: PruningPredicate,
201239
not_in_list_with_null_predicate: PruningPredicate,
202240
expanded_and_predicate: PruningPredicate,
203-
statistics: IntervalStatistics,
204241
}
205242

206243
impl BenchmarkCase {
@@ -250,36 +287,6 @@ impl BenchmarkCase {
250287
.to_string()
251288
.contains("NOT_IN_SET_MAY_MATCH")
252289
);
253-
let statistics = IntervalStatistics::new(size);
254-
255-
// Check that every benchmark path does the same useful work, rather
256-
// than comparing compact pruning with an always-true fallback.
257-
let kept = (0..CONTAINERS)
258-
.map(|index| index % 2 == 0)
259-
.collect::<Vec<_>>();
260-
let negated_kept = kept.iter().map(|keep| !keep).collect::<Vec<_>>();
261-
assert_eq!(in_list_predicate.prune(&statistics).unwrap(), kept);
262-
assert_eq!(
263-
in_list_with_null_predicate.prune(&statistics).unwrap(),
264-
kept
265-
);
266-
assert_eq!(expanded_or_predicate.prune(&statistics).unwrap(), kept);
267-
assert_eq!(
268-
not_in_list_predicate.prune(&statistics).unwrap(),
269-
negated_kept
270-
);
271-
assert_eq!(
272-
expanded_and_predicate.prune(&statistics).unwrap(),
273-
negated_kept
274-
);
275-
assert!(
276-
not_in_list_with_null_predicate
277-
.prune(&statistics)
278-
.unwrap()
279-
.iter()
280-
.all(|keep| !keep)
281-
);
282-
283290
Self {
284291
size,
285292
schema,
@@ -295,12 +302,61 @@ impl BenchmarkCase {
295302
not_in_list_predicate,
296303
not_in_list_with_null_predicate,
297304
expanded_and_predicate,
298-
statistics,
299305
}
300306
}
301307
}
302308

309+
fn expected_results(container_count: usize) -> Vec<bool> {
310+
(0..container_count).map(|index| index % 2 == 0).collect()
311+
}
312+
313+
fn assert_equivalent_results(case: &BenchmarkCase, statistics: &IntervalStatistics) {
314+
let expected = expected_results(statistics.num_containers());
315+
assert_eq!(case.in_list_predicate.prune(statistics).unwrap(), expected);
316+
assert_eq!(
317+
case.expanded_or_predicate.prune(statistics).unwrap(),
318+
expected
319+
);
320+
let negated_expected = expected.iter().map(|keep| !keep).collect::<Vec<_>>();
321+
assert_eq!(
322+
case.not_in_list_predicate.prune(statistics).unwrap(),
323+
negated_expected
324+
);
325+
assert_eq!(
326+
case.expanded_and_predicate.prune(statistics).unwrap(),
327+
negated_expected
328+
);
329+
330+
let in_with_null = case.in_list_with_null_predicate.prune(statistics).unwrap();
331+
let not_in_with_null = case
332+
.not_in_list_with_null_predicate
333+
.prune(statistics)
334+
.unwrap();
335+
if case.size + 1 > MAX_IN_LIST_SIZE {
336+
// Compact pruning applies filter semantics: NULL does not change which
337+
// rows can satisfy IN, while NOT IN (..., NULL) can never be true.
338+
assert_eq!(in_with_null, expected);
339+
assert!(not_in_with_null.iter().all(|keep| !keep));
340+
} else {
341+
// The legacy per-value rewrite keeps UNKNOWN IN results and drops the
342+
// NULL term from NOT IN statistics pruning.
343+
assert!(in_with_null.iter().all(|keep| *keep));
344+
assert_eq!(not_in_with_null, negated_expected);
345+
}
346+
}
347+
348+
fn evaluation_group_name(container_count: usize) -> String {
349+
// Keep the original benchmark IDs for the pre-existing 4,096-container
350+
// cases so Criterion baselines remain directly comparable.
351+
if container_count == BASELINE_CONTAINER_COUNT {
352+
"string_in_list_pruning/evaluate".to_string()
353+
} else {
354+
format!("string_in_list_pruning/evaluate/{container_count}_containers")
355+
}
356+
}
357+
303358
fn criterion_benchmark(criterion: &mut Criterion) {
359+
validate_sampling_distribution();
304360
let cases = DOMAIN_SIZES.map(BenchmarkCase::new);
305361
let mut construction = criterion.benchmark_group("string_in_list_pruning/construct");
306362
for case in &cases {
@@ -334,41 +390,50 @@ fn criterion_benchmark(criterion: &mut Criterion) {
334390
}
335391
construction.finish();
336392

337-
let mut evaluation = criterion.benchmark_group("string_in_list_pruning/evaluate");
338-
evaluation.throughput(Throughput::Elements(CONTAINERS as u64));
339-
for case in &cases {
340-
for (name, predicate, list_size) in [
341-
("in_list", &case.in_list_predicate, case.size),
342-
(
343-
"in_list_with_null",
344-
&case.in_list_with_null_predicate,
345-
case.size + 1,
346-
),
347-
("expanded_or", &case.expanded_or_predicate, case.size),
348-
("not_in_list", &case.not_in_list_predicate, case.size),
349-
(
350-
"not_in_list_with_null_constant_false",
351-
&case.not_in_list_with_null_predicate,
352-
case.size + 1,
353-
),
354-
("expanded_and", &case.expanded_and_predicate, case.size),
355-
] {
356-
evaluation.bench_with_input(
357-
BenchmarkId::new(name, list_size),
358-
predicate,
359-
|bencher, predicate| {
360-
bencher.iter(|| {
361-
black_box(predicate.prune(black_box(&case.statistics)).unwrap())
362-
});
363-
},
364-
);
393+
for container_count in CONTAINER_COUNTS {
394+
let mut evaluation =
395+
criterion.benchmark_group(evaluation_group_name(container_count));
396+
evaluation.throughput(Throughput::Elements(container_count as u64));
397+
for case in &cases {
398+
let statistics = IntervalStatistics::new(case.size, container_count);
399+
400+
// Check every matrix cell outside the timed loop so all paths do
401+
// the same useful work rather than measuring an always-true fallback.
402+
assert_equivalent_results(case, &statistics);
403+
404+
for (name, predicate, list_size) in [
405+
("in_list", &case.in_list_predicate, case.size),
406+
(
407+
"in_list_with_null",
408+
&case.in_list_with_null_predicate,
409+
case.size + 1,
410+
),
411+
("expanded_or", &case.expanded_or_predicate, case.size),
412+
("not_in_list", &case.not_in_list_predicate, case.size),
413+
(
414+
"not_in_list_with_null_constant_false",
415+
&case.not_in_list_with_null_predicate,
416+
case.size + 1,
417+
),
418+
("expanded_and", &case.expanded_and_predicate, case.size),
419+
] {
420+
evaluation.bench_with_input(
421+
BenchmarkId::new(name, list_size),
422+
predicate,
423+
|bencher, predicate| {
424+
bencher.iter(|| {
425+
black_box(predicate.prune(black_box(&statistics)).unwrap())
426+
});
427+
},
428+
);
429+
}
365430
}
431+
evaluation.finish();
366432
}
367-
evaluation.finish();
368433

369434
let mut distributions =
370435
criterion.benchmark_group("string_in_list_pruning/not_in_distributions");
371-
distributions.throughput(Throughput::Elements(CONTAINERS as u64));
436+
distributions.throughput(Throughput::Elements(BASELINE_CONTAINER_COUNT as u64));
372437
let singleton = IntervalStatistics::uniform_singleton();
373438
for case in cases.iter().filter(|case| case.size > 20) {
374439
let compact = case.not_in_list_predicate.prune(&singleton).unwrap();

0 commit comments

Comments
 (0)