Skip to content

Commit fc503ee

Browse files
kumarUjjawaldiscord9
authored andcommitted
Optimize NULL-containing string IN list pruning (apache#24954)
## Which issue does this PR close? - Closes apache#24711. ## Rationale for this change apache#24781 added compact pruning for non-NULL `NOT IN` lists. Issue apache#24711 still needs support for NULL-containing lists. Large string lists can create expensive per-value pruning expressions. The compact path reduces this cost when `max_in_list_size` permits the rewrite. NULL values require special handling. Filter pruning treats FALSE and UNKNOWN equally, but full-match detection must keep these results separate. ## What changes are included in this PR? This PR makes these changes: - Supports compact pruning for large string `IN` lists that contain NULL. - Treats `NOT IN` with NULL as unable to match rows. - Treats all-NULL `IN` lists as unable to match rows. - Records whether a pruning predicate is safe for full-match inversion. - Uses the same configured list-size cap when it builds the inverse predicate. - Adds unit tests, Parquet integration tests, documentation, and benchmarks. ## What is the testing strategy for this PR? The tests cover positive and negative lists, all-NULL lists, nested `OR` expressions, configured caps, and Parquet full-match detection. These commands passed: ```shell cargo test -p datafusion-pruning cargo test -p datafusion-datasource-parquet cargo test -p datafusion --test parquet_integration string_in_list_pruning cargo fmt --all -- --check cargo clippy --all-targets --all-features -- -D warnings ``` Focused benchmarks also cover compact `IN` and constant-false `NOT IN` expressions with NULL. ## Are there any user-facing changes? Large string `IN` and `NOT IN` lists that contain NULL can now use compact pruning when the cap permits it. Query results and configuration defaults do not change. This PR adds two non-breaking `PruningPredicate` accessors: `max_in_list_size` and `can_be_inverted_for_full_match`. Backport provenance: - Upstream PR: apache#24954 - Upstream commit: 33028d5 - Upstream self-tests and all additions/removals retained; only unavoidable fork patch context resolved. - Any fork-specific adaptation is kept in a separate following commit. Signed-off-by: discord9 <[email protected]>
1 parent 57f27e9 commit fc503ee

7 files changed

Lines changed: 302 additions & 113 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1287,10 +1287,12 @@ config_namespace! {
12871287
/// rewrite; other predicates and Bloom-filter pruning remain available.
12881288
///
12891289
/// Within the cap, nonempty lists of at most 20 values use the existing
1290-
/// per-value rewrite. Larger non-null literal string lists on a string
1291-
/// column use a compact sorted domain, for both `IN` and `NOT IN`.
1292-
/// Other lists retain the existing per-value rewrite, so raising the cap
1293-
/// can make those predicates expensive to build and evaluate.
1290+
/// per-value rewrite. Larger literal string lists on a string column use
1291+
/// a compact representation, for both `IN` and `NOT IN`, including lists
1292+
/// with NULL members. `NOT IN` with NULL and all-NULL `IN` lists cannot
1293+
/// match any rows. Other lists retain the existing per-value rewrite, so
1294+
/// raising the cap can make those predicates expensive to build and
1295+
/// evaluate.
12941296
///
12951297
/// Defaults to 20.
12961298
pub max_in_list_size: usize, default = 20

‎datafusion/core/tests/parquet/string_in_list_pruning.rs‎

Lines changed: 81 additions & 51 deletions
Original file line numberDiff line numberDiff line change
@@ -440,23 +440,24 @@ async fn string_not_in_list_with_truncated_bounds() {
440440
}
441441

442442
#[tokio::test]
443-
async fn string_not_in_list_with_null_does_not_bypass_row_filter() {
443+
async fn string_in_list_with_null_preserves_filter_semantics() {
444444
let mut file = tempfile::Builder::new()
445-
.prefix("string_not_in_list_pruning")
445+
.prefix("string_in_list_null_pruning")
446446
.suffix(".parquet")
447447
.tempfile()
448448
.unwrap();
449449
let schema = Arc::new(Schema::new(vec![Field::new("value", DataType::Utf8, true)]));
450450
// The first row group has a known zero null count, and every value lies
451-
// in a gap in the IN list. Dropping the NULL list member while inverting
452-
// NOT IN would incorrectly prove that this entire row group matches.
451+
// in a gap in the IN list. The matching value in the second row group is
452+
// deliberately not first, so incorrectly bypassing the row filter changes
453+
// the result when the scan has a limit.
453454
let values = vec![
454455
Some("v000001"),
455456
Some("v000001"),
456457
Some("v000001"),
457458
Some("v000001"),
458-
Some("v000000"),
459459
Some("v000001"),
460+
Some("v000000"),
460461
None,
461462
Some("v999999"),
462463
];
@@ -475,13 +476,11 @@ async fn string_not_in_list_with_null_does_not_bypass_row_filter() {
475476
assert_eq!(writer.close().unwrap().num_row_groups(), 2);
476477

477478
// Build the physical source directly so a logical optimizer cannot fold
478-
// the SQL NOT IN (..., NULL) filter to an empty relation before the scan.
479+
// NOT IN (..., NULL) to an empty relation before the scan.
479480
let mut list = (0..21)
480481
.map(|index| lit(format!("v{:06}", index * 10)))
481482
.collect::<Vec<_>>();
482483
list.push(lit(ScalarValue::Utf8(None)));
483-
let predicate =
484-
in_list(col("value", &schema).unwrap(), list, &true, &schema).unwrap();
485484
let location = Path::from_filesystem_path(file.path()).unwrap();
486485
let partitioned_file = PartitionedFile::new(
487486
location.to_string(),
@@ -490,48 +489,79 @@ async fn string_not_in_list_with_null_does_not_bypass_row_filter() {
490489
let ctx =
491490
SessionContext::new_with_config(SessionConfig::new().with_target_partitions(1));
492491

493-
for max_in_list_size in [0, 32] {
494-
let mut options = TableParquetOptions::default();
495-
options.global.max_in_list_size = max_in_list_size;
496-
let source = Arc::new(
497-
ParquetSource::new(Arc::clone(&schema))
498-
.with_table_parquet_options(options)
499-
.with_predicate(Arc::clone(&predicate))
500-
.with_pushdown_filters(true)
501-
.with_enable_page_index(false)
502-
.with_bloom_filter_on_read(false),
503-
);
504-
let config =
505-
FileScanConfigBuilder::new(ObjectStoreUrl::local_filesystem(), source)
506-
.with_file(partitioned_file.clone())
507-
.with_limit(Some(1))
508-
.build();
509-
let plan: Arc<dyn ExecutionPlan> =
510-
Arc::new(DataSourceExec::new(Arc::new(config)));
511-
let plan_text = displayable(plan.as_ref()).indent(true).to_string();
512-
assert!(plan_text.contains("NOT IN"), "{plan_text}");
513-
let batches = collect(Arc::clone(&plan), ctx.task_ctx()).await.unwrap();
514-
let output = ScanOutput {
515-
batches,
516-
plan: plan_text,
517-
metrics: MetricsFinder::find_metrics(plan.as_ref()).unwrap(),
518-
};
519-
520-
assert_eq!(
521-
output
522-
.batches
523-
.iter()
524-
.map(RecordBatch::num_rows)
525-
.sum::<usize>(),
526-
0,
527-
"cap={max_in_list_size}, plan={}, metrics={}",
528-
output.plan,
529-
output.metrics
530-
);
531-
assert_eq!(output.fully_matched("row_groups_pruned_statistics"), 0);
532-
assert_eq!(output.pruned("row_groups_pruned_statistics"), 0);
533-
assert_eq!(output.pruned("limit_pruned_row_groups"), 0);
534-
assert_eq!(output.counter("pushdown_rows_pruned"), 8);
535-
assert_eq!(output.counter("predicate_evaluation_errors"), 0);
492+
for negated in [false, true] {
493+
let predicate = in_list(
494+
col("value", &schema).unwrap(),
495+
list.clone(),
496+
&negated,
497+
&schema,
498+
)
499+
.unwrap();
500+
for max_in_list_size in [0, 32] {
501+
let mut options = TableParquetOptions::default();
502+
options.global.max_in_list_size = max_in_list_size;
503+
let source = Arc::new(
504+
ParquetSource::new(Arc::clone(&schema))
505+
.with_table_parquet_options(options)
506+
.with_predicate(Arc::clone(&predicate))
507+
.with_pushdown_filters(true)
508+
.with_enable_page_index(false)
509+
.with_bloom_filter_on_read(false),
510+
);
511+
let config =
512+
FileScanConfigBuilder::new(ObjectStoreUrl::local_filesystem(), source)
513+
.with_file(partitioned_file.clone())
514+
.with_limit(Some(1))
515+
.build();
516+
let plan: Arc<dyn ExecutionPlan> =
517+
Arc::new(DataSourceExec::new(Arc::new(config)));
518+
let plan_text = displayable(plan.as_ref()).indent(true).to_string();
519+
assert!(plan_text.contains("IN"), "{plan_text}");
520+
let batches = collect(Arc::clone(&plan), ctx.task_ctx()).await.unwrap();
521+
let output = ScanOutput {
522+
batches,
523+
plan: plan_text,
524+
metrics: MetricsFinder::find_metrics(plan.as_ref()).unwrap(),
525+
};
526+
527+
if negated {
528+
assert!(output.batches.iter().all(|batch| batch.num_rows() == 0));
529+
} else {
530+
assert_batches_eq!(
531+
[
532+
"+---------+",
533+
"| value |",
534+
"+---------+",
535+
"| v000000 |",
536+
"+---------+",
537+
],
538+
&output.batches
539+
);
540+
}
541+
assert_eq!(
542+
output.counter("pushdown_rows_pruned"),
543+
match (negated, max_in_list_size) {
544+
(false, 0) => 7,
545+
(false, _) => 3,
546+
(true, 0) => 8,
547+
(true, _) => 0,
548+
}
549+
);
550+
assert_eq!(output.fully_matched("row_groups_pruned_statistics"), 0);
551+
assert_eq!(
552+
output.pruned("row_groups_pruned_statistics"),
553+
if max_in_list_size == 0 {
554+
0
555+
} else if negated {
556+
2
557+
} else {
558+
1
559+
},
560+
"negated={negated}, cap={max_in_list_size}, metrics={}",
561+
output.metrics
562+
);
563+
assert_eq!(output.pruned("limit_pruned_row_groups"), 0);
564+
assert_eq!(output.counter("predicate_evaluation_errors"), 0);
565+
}
536566
}
537567
}

‎datafusion/datasource-parquet/src/row_group_filter.rs‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -388,6 +388,11 @@ impl RowGroupAccessPlanFilter {
388388
if candidate_row_group_indices.is_empty() {
389389
return;
390390
}
391+
// Some pruning rewrites preserve only whether rows can be TRUE, while
392+
// full-match inference must distinguish FALSE from UNKNOWN.
393+
if !predicate.can_be_inverted_for_full_match() {
394+
return;
395+
}
391396
let arrow_schema = pruning_stats.arrow_schema;
392397

393398
let mut inverted_expr: Arc<dyn PhysicalExpr> =
@@ -425,6 +430,7 @@ impl RowGroupAccessPlanFilter {
425430

426431
let Ok(inverted_predicate) = PruningPredicateBuilder::new()
427432
.with_file_schema(Arc::clone(predicate.schema()))
433+
.with_max_in_list_size(predicate.max_in_list_size())
428434
.try_build(inverted_expr)
429435
else {
430436
return;

‎datafusion/pruning/benches/string_in_list_pruning.rs‎

Lines changed: 68 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -24,9 +24,10 @@
2424
//! without making the baseline depend on a deeply nested expression.
2525
//!
2626
//! The main cases alternate intervals pinned to a domain member with intervals
27-
//! that span a sparse gap. Supplemental `NOT IN` cases measure uniform singleton
28-
//! containers, long bounds, and long literals that share bounds' prefixes. Bloom
29-
//! filters are not involved.
27+
//! that span a sparse gap. NULL-containing variants cover the optimized
28+
//! filter-semantics paths, including the constant-false `NOT IN` rewrite.
29+
//! Supplemental `NOT IN` cases measure uniform singleton containers, long bounds,
30+
//! and long literals that share bounds' prefixes. Bloom filters are not involved.
3031
//!
3132
//! Run with `cargo bench -p datafusion-pruning --bench string_in_list_pruning`.
3233
//! The construction benchmarks reuse their input physical expressions; the
@@ -188,12 +189,16 @@ struct BenchmarkCase {
188189
size: usize,
189190
schema: SchemaRef,
190191
in_list: PhysicalExprRef,
192+
in_list_with_null: PhysicalExprRef,
191193
expanded_or: PhysicalExprRef,
192194
not_in_list: PhysicalExprRef,
195+
not_in_list_with_null: PhysicalExprRef,
193196
expanded_and: PhysicalExprRef,
194197
in_list_predicate: PruningPredicate,
198+
in_list_with_null_predicate: PruningPredicate,
195199
expanded_or_predicate: PruningPredicate,
196200
not_in_list_predicate: PruningPredicate,
201+
not_in_list_with_null_predicate: PruningPredicate,
197202
expanded_and_predicate: PruningPredicate,
198203
statistics: IntervalStatistics,
199204
}
@@ -209,15 +214,30 @@ impl BenchmarkCase {
209214
let values = (0..size)
210215
.map(|index| lit(ScalarValue::new_utf8view(value(index * 10))))
211216
.collect::<Vec<_>>();
217+
let mut values_with_null = values.clone();
218+
values_with_null.push(lit(ScalarValue::Utf8View(None)));
212219
let not_in_list =
213220
in_list(Arc::clone(&column), values.clone(), &true, &schema).unwrap();
221+
let not_in_list_with_null = in_list(
222+
Arc::clone(&column),
223+
values_with_null.clone(),
224+
&true,
225+
&schema,
226+
)
227+
.unwrap();
228+
let in_list_with_null =
229+
in_list(Arc::clone(&column), values_with_null, &false, &schema).unwrap();
214230
let in_list =
215231
in_list(Arc::clone(&column), values.clone(), &false, &schema).unwrap();
216232
let expanded_or = expanded(&column, &values, Operator::Eq, Operator::Or);
217233
let expanded_and = expanded(&column, &values, Operator::NotEq, Operator::And);
218234
let in_list_predicate = build_predicate(&in_list, &schema, size);
235+
let in_list_with_null_predicate =
236+
build_predicate(&in_list_with_null, &schema, size + 1);
219237
let expanded_or_predicate = build_predicate(&expanded_or, &schema, size);
220238
let not_in_list_predicate = build_predicate(&not_in_list, &schema, size);
239+
let not_in_list_with_null_predicate =
240+
build_predicate(&not_in_list_with_null, &schema, size + 1);
221241
let expanded_and_predicate = build_predicate(&expanded_and, &schema, size);
222242
eprintln!(
223243
"string_in_list_pruning: {size} values, compact in={}, compact not in={}",
@@ -239,6 +259,10 @@ impl BenchmarkCase {
239259
.collect::<Vec<_>>();
240260
let negated_kept = kept.iter().map(|keep| !keep).collect::<Vec<_>>();
241261
assert_eq!(in_list_predicate.prune(&statistics).unwrap(), kept);
262+
assert_eq!(
263+
in_list_with_null_predicate.prune(&statistics).unwrap(),
264+
kept
265+
);
242266
assert_eq!(expanded_or_predicate.prune(&statistics).unwrap(), kept);
243267
assert_eq!(
244268
not_in_list_predicate.prune(&statistics).unwrap(),
@@ -248,17 +272,28 @@ impl BenchmarkCase {
248272
expanded_and_predicate.prune(&statistics).unwrap(),
249273
negated_kept
250274
);
275+
assert!(
276+
not_in_list_with_null_predicate
277+
.prune(&statistics)
278+
.unwrap()
279+
.iter()
280+
.all(|keep| !keep)
281+
);
251282

252283
Self {
253284
size,
254285
schema,
255286
in_list,
287+
in_list_with_null,
256288
expanded_or,
257289
not_in_list,
290+
not_in_list_with_null,
258291
expanded_and,
259292
in_list_predicate,
293+
in_list_with_null_predicate,
260294
expanded_or_predicate,
261295
not_in_list_predicate,
296+
not_in_list_with_null_predicate,
262297
expanded_and_predicate,
263298
statistics,
264299
}
@@ -269,22 +304,28 @@ fn criterion_benchmark(criterion: &mut Criterion) {
269304
let cases = DOMAIN_SIZES.map(BenchmarkCase::new);
270305
let mut construction = criterion.benchmark_group("string_in_list_pruning/construct");
271306
for case in &cases {
272-
construction.throughput(Throughput::Elements(case.size as u64));
273-
for (name, expression) in [
274-
("in_list", &case.in_list),
275-
("expanded_or", &case.expanded_or),
276-
("not_in_list", &case.not_in_list),
277-
("expanded_and", &case.expanded_and),
307+
for (name, expression, max_in_list_size) in [
308+
("in_list", &case.in_list, case.size),
309+
("in_list_with_null", &case.in_list_with_null, case.size + 1),
310+
("expanded_or", &case.expanded_or, case.size),
311+
("not_in_list", &case.not_in_list, case.size),
312+
(
313+
"not_in_list_with_null_constant_false",
314+
&case.not_in_list_with_null,
315+
case.size + 1,
316+
),
317+
("expanded_and", &case.expanded_and, case.size),
278318
] {
319+
construction.throughput(Throughput::Elements(max_in_list_size as u64));
279320
construction.bench_with_input(
280-
BenchmarkId::new(name, case.size),
321+
BenchmarkId::new(name, max_in_list_size),
281322
expression,
282323
|bencher, expression| {
283324
bencher.iter(|| {
284325
black_box(build_predicate(
285326
black_box(expression),
286327
&case.schema,
287-
case.size,
328+
max_in_list_size,
288329
))
289330
});
290331
},
@@ -296,14 +337,24 @@ fn criterion_benchmark(criterion: &mut Criterion) {
296337
let mut evaluation = criterion.benchmark_group("string_in_list_pruning/evaluate");
297338
evaluation.throughput(Throughput::Elements(CONTAINERS as u64));
298339
for case in &cases {
299-
for (name, predicate) in [
300-
("in_list", &case.in_list_predicate),
301-
("expanded_or", &case.expanded_or_predicate),
302-
("not_in_list", &case.not_in_list_predicate),
303-
("expanded_and", &case.expanded_and_predicate),
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),
304355
] {
305356
evaluation.bench_with_input(
306-
BenchmarkId::new(name, case.size),
357+
BenchmarkId::new(name, list_size),
307358
predicate,
308359
|bencher, predicate| {
309360
bencher.iter(|| {

0 commit comments

Comments
 (0)