Skip to content

Commit fd101e9

Browse files
authored
perf: prune ListingTable files before grouping (apache#26441)
## Which issue does this PR close? Closes apache#26130. ## Rationale for this change When files contain disjoint ranges of a filtered column, ListingTable groups all files before file-statistics pruning. The matching files can therefore land in a single scan partition, and scan statistics still include files that cannot match. In the eight-file example from the issue, `d >= 20 AND d < 40` currently places both matching files in the second of four groups and estimates 80 rows. Pruning before grouping retains only `f2` and `f3`, puts them in separate groups, and aggregates 20 survivor rows. ## What changes are included in this PR? - Pass non-partition filters through a private listing path and reuse `PruningPredicateBuilder` with already collected file statistics before splitting regular scan file groups. - Keep files with missing/inexact statistics or evaluation errors, retain normal row filtering, and avoid evaluating volatile filters during planning. - Bypass the optimization for custom expression adapters and declared output partitioning, preserving partition identities and empty trailing groups. - Recompute aggregate statistics from survivors without additional object-store requests. - Add regression coverage and update physical-plan/runtime-metric expectations for files eliminated during planning. No public API change. ## What is the testing strategy for this PR? On the investigated baseline (`a4b8198cf`), local validation passed 12,579 distinct Rust tests and 533 SQL logic files. This includes 23 listing unit tests, 10 focused pruning integration tests, all 246 Parquet integration tests, and 126 extended fuzz tests. The no-extra-I/O test compares object-store requests during planning. Coverage includes the eight-file grouping example, partially matching files, missing and inexact bounds, NULL semantics, Hash/Range partition layouts, Hive/data predicates, LIMIT/OFFSET, custom adapters, volatile UDF invocation counts, survivor statistics, and conservative filtered-statistics precision. Nine SQL snapshot files change physical-plan expectations only. On current upstream main (`5f2158269`), all 1,459 core integration tests (including all 10 pruning regressions and the no-extra-I/O test), all 247 Parquet tests, and all 535 SQL logic files pass. The full extended workspace run completed successfully: 12,742 Rust tests passed, including all 126 fuzz tests, with eight tests ignored and no failures. All 535 SQL logic files also passed. Formatting, diff whitespace, TOML formatting, and license headers on all 2,331 tracked project source files pass. The earlier full workspace Clippy run passed with explicit allowances for pre-existing upstream/toolchain diagnostics. The mandatory strict Clippy invocation also fails on the updated main branch with Rust 1.99, on three pre-existing `clippy::mutable_key_type` diagnostics in untouched `datafusion/optimizer/src/push_down_filter.rs`. The CI-style Clippy invocation (`--workspace --all-targets --features avro,integration-tests,extended_tests -- -D warnings`) passes. The full lint wrapper stops at its license walk because locally exported third-party SQLite fixture snapshots lack project headers; the separate tracked-project-source license check passes. Subsequent wrapper steps have not been run. No lint suppression or unrelated optimizer change is included in this PR. No performance speedup is claimed: the prior Hive-only planning benchmark is not representative of data-column pruning and ran under differing concurrent load. ## Are there any user-facing changes? With statistics collection enabled, regular listing scans can contain fewer files and report tighter statistics in EXPLAIN. Query results and row filtering are unchanged. Unsupported or inconclusive statistics keep files, and declared partition layouts are preserved. This contribution was developed with AI assistance. The design and safeguards are described above; performance under distributed execution remains unmeasured.
1 parent 6e0e0da commit fd101e9

19 files changed

Lines changed: 970 additions & 57 deletions

‎Cargo.lock‎

Lines changed: 1 addition & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/catalog-listing/Cargo.toml‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ datafusion-physical-expr = { workspace = true }
2929
datafusion-physical-expr-adapter = { workspace = true }
3030
datafusion-physical-expr-common = { workspace = true }
3131
datafusion-physical-plan = { workspace = true }
32+
datafusion-pruning = { workspace = true }
3233
futures = { workspace = true }
3334
itertools = { workspace = true }
3435
log = { workspace = true }

‎datafusion/catalog-listing/src/table.rs‎

Lines changed: 249 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@ use crate::{ListingOptions, ListingTableConfig};
1010
use arrow::datatypes::{Field, Metadata, Schema, SchemaBuilder, SchemaRef};
1111
use async_trait::async_trait;
1212
use datafusion_catalog::{ScanArgs, ScanResult, Session, TableProvider};
13+
use datafusion_common::pruning::PrunableStatistics;
1314
use datafusion_common::stats::{Precision, is_known_empty};
1415
use datafusion_common::{
1516
Constraints, DFSchema, SchemaExt, SplitPoint, Statistics, internal_datafusion_err,
@@ -41,6 +42,7 @@ use datafusion_physical_expr_common::sort_expr::LexOrdering;
4142
use datafusion_physical_plan::ExecutionPlan;
4243
use datafusion_physical_plan::empty::EmptyExec;
4344
use datafusion_physical_plan::limit::GlobalLimitExec;
45+
use datafusion_pruning::PruningPredicateBuilder;
4446
use futures::future::BoxFuture;
4547
use futures::{Stream, StreamExt, TryStreamExt, future, stream};
4648
use object_store::ObjectStore;
@@ -662,7 +664,12 @@ impl ListingTable {
662664
grouped_by_partition: partitioned_by_file_group,
663665
partition_split_points,
664666
} = self
665-
.list_files_for_scan(state, &partition_filters, statistic_file_limit)
667+
.list_files_for_scan_inner(
668+
state,
669+
&partition_filters,
670+
&filters,
671+
statistic_file_limit,
672+
)
666673
.await?;
667674

668675
// if no files need to be read, return an `EmptyExec`
@@ -915,15 +922,28 @@ impl ListingTable {
915922
filters: &'a [Expr],
916923
limit: Option<usize>,
917924
) -> datafusion_common::Result<ListFilesResult> {
925+
self.list_files_for_scan_inner(ctx, filters, &[], limit)
926+
.await
927+
}
928+
929+
async fn list_files_for_scan_inner<'a>(
930+
&'a self,
931+
ctx: &'a dyn Session,
932+
partition_filters: &'a [Expr],
933+
data_filters: &'a [Expr],
934+
limit: Option<usize>,
935+
) -> datafusion_common::Result<ListFilesResult> {
936+
// Declared layouts must retain their partition identities, including empty groups.
918937
if let Some(output_partitioning) = self.options.output_partitioning.as_ref() {
919938
self.list_files_for_declared_output_partitioning(
920939
ctx,
921940
output_partitioning,
922-
filters,
941+
partition_filters,
923942
)
924943
.await
925944
} else {
926-
self.list_files_for_regular_scan(ctx, filters, limit).await
945+
self.list_files_for_regular_scan(ctx, partition_filters, data_filters, limit)
946+
.await
927947
}
928948
}
929949

@@ -979,10 +999,51 @@ impl ListingTable {
979999
get_files_with_limit(files, file_limit, ctx.config().collect_statistics()).await
9801000
}
9811001

1002+
/// Build a predicate that can remove files whose collected statistics prove
1003+
/// the filter cannot match. This performs no I/O and leaves the normal row
1004+
/// filters in place.
1005+
fn file_statistics_pruning_predicate(
1006+
&self,
1007+
ctx: &dyn Session,
1008+
filters: &[Expr],
1009+
) -> Option<Arc<datafusion_pruning::PruningPredicate>> {
1010+
if !ctx.config().collect_statistics() || self.expr_adapter_factory.is_some() {
1011+
return None;
1012+
}
1013+
// Custom adapters can change values relative to file statistics, and volatile
1014+
// expressions must not be evaluated while planning.
1015+
let filter = filters
1016+
.iter()
1017+
.filter(|f| !f.is_volatile())
1018+
.cloned()
1019+
.reduce(Expr::and)?;
1020+
let Ok(schema) = DFSchema::try_from(self.table_schema.as_ref().clone()) else {
1021+
return None;
1022+
};
1023+
let Ok(predicate) = ctx.create_physical_expr(filter, &schema) else {
1024+
return None;
1025+
};
1026+
PruningPredicateBuilder::new()
1027+
.with_file_schema(Arc::clone(&self.table_schema))
1028+
.build(predicate)
1029+
}
1030+
1031+
fn prune_files_by_statistics(
1032+
&self,
1033+
predicate: Option<&datafusion_pruning::PruningPredicate>,
1034+
files: FileGroup,
1035+
) -> FileGroup {
1036+
let Some(predicate) = predicate else {
1037+
return files;
1038+
};
1039+
prune_collected_files(predicate, &self.file_schema, files)
1040+
}
1041+
9821042
async fn list_files_for_regular_scan<'a>(
9831043
&'a self,
9841044
ctx: &'a dyn Session,
9851045
filters: &'a [Expr],
1046+
data_filters: &'a [Expr],
9861047
limit: Option<usize>,
9871048
) -> datafusion_common::Result<ListFilesResult> {
9881049
let file_group_count = ctx.config().target_partitions();
@@ -1005,6 +1066,7 @@ impl ListingTable {
10051066
let (file_group, inexact_stats) = self
10061067
.collect_files_for_scan(ctx, &store, filters, limit)
10071068
.await?;
1069+
let pruning_predicate = self.file_statistics_pruning_predicate(ctx, data_filters);
10081070

10091071
// Threshold: 0 = disabled, N > 0 = enabled when distinct_keys >= N
10101072
//
@@ -1018,17 +1080,30 @@ impl ListingTable {
10181080
let (grouped, split_points) = file_group
10191081
.group_by_partition_values_with_split_points(file_group_count);
10201082
if grouped.len() >= threshold {
1083+
// Preserve the groups and split points derived from all files so
1084+
// pruning cannot change the declared range partitioning.
1085+
let grouped = grouped
1086+
.into_iter()
1087+
.map(|group| {
1088+
self.prune_files_by_statistics(
1089+
pruning_predicate.as_deref(),
1090+
group,
1091+
)
1092+
})
1093+
.collect();
10211094
(grouped, true, split_points)
10221095
} else {
10231096
let all_files: Vec<_> =
10241097
grouped.into_iter().flat_map(|g| g.into_inner()).collect();
1025-
(
1026-
FileGroup::new(all_files).split_files(file_group_count),
1027-
false,
1028-
vec![],
1029-
)
1098+
let file_group = self.prune_files_by_statistics(
1099+
pruning_predicate.as_deref(),
1100+
FileGroup::new(all_files),
1101+
);
1102+
(file_group.split_files(file_group_count), false, vec![])
10301103
}
10311104
} else {
1105+
let file_group = self
1106+
.prune_files_by_statistics(pruning_predicate.as_deref(), file_group);
10321107
(file_group.split_files(file_group_count), false, vec![])
10331108
};
10341109

@@ -1260,6 +1335,39 @@ async fn get_files_with_limit(
12601335
Ok((file_group, inexact_stats))
12611336
}
12621337

1338+
/// Keep a file unless the pruning predicate proves it cannot contain a match.
1339+
fn prune_collected_files(
1340+
predicate: &datafusion_pruning::PruningPredicate,
1341+
file_schema: &SchemaRef,
1342+
files: FileGroup,
1343+
) -> FileGroup {
1344+
FileGroup::new(
1345+
files
1346+
.into_inner()
1347+
.into_iter()
1348+
.filter(|file| {
1349+
// Same check as `FilePruner::try_new`: all-`Absent` statistics
1350+
// cannot prune, so skip building `PrunableStatistics` for them.
1351+
if !file.has_statistics() {
1352+
return true;
1353+
}
1354+
let Some(statistics) = &file.statistics else {
1355+
return true;
1356+
};
1357+
// One unknown file must not hide the exact bounds of another file.
1358+
let statistics = PrunableStatistics::new(
1359+
vec![Arc::clone(statistics)],
1360+
Arc::clone(file_schema),
1361+
);
1362+
predicate
1363+
.prune(&statistics)
1364+
.map(|keep| keep != [false])
1365+
.unwrap_or(true)
1366+
})
1367+
.collect(),
1368+
)
1369+
}
1370+
12631371
#[cfg(test)]
12641372
mod tests {
12651373
use super::*;
@@ -1421,4 +1529,137 @@ mod tests {
14211529
let result = derive_common_ordering_from_files(&file_groups);
14221530
assert_eq!(result, Some(ordering));
14231531
}
1532+
1533+
fn prune_test_files(expr: Expr, statistics: Vec<Option<Statistics>>) -> Vec<String> {
1534+
use arrow::datatypes::DataType;
1535+
let schema = Arc::new(Schema::new(vec![Field::new("d", DataType::Int64, true)]));
1536+
let physical = datafusion_physical_expr::create_physical_expr(
1537+
&expr,
1538+
&DFSchema::try_from(schema.as_ref().clone()).unwrap(),
1539+
&ExecutionProps::new(),
1540+
&PhysicalPlanningContext::default(),
1541+
)
1542+
.unwrap();
1543+
let predicate = PruningPredicateBuilder::new()
1544+
.with_file_schema(Arc::clone(&schema))
1545+
.try_build(physical)
1546+
.unwrap();
1547+
let files = FileGroup::new(
1548+
statistics
1549+
.into_iter()
1550+
.enumerate()
1551+
.map(|(i, stats)| {
1552+
let mut file = PartitionedFile::new(format!("f{i}"), 10);
1553+
file.statistics = stats.map(Arc::new);
1554+
file
1555+
})
1556+
.collect(),
1557+
);
1558+
prune_collected_files(&predicate, &schema, files)
1559+
.iter()
1560+
.map(|f| f.object_meta.location.to_string())
1561+
.collect()
1562+
}
1563+
1564+
fn bounds(
1565+
min: Precision<datafusion_common::ScalarValue>,
1566+
max: Precision<datafusion_common::ScalarValue>,
1567+
) -> Statistics {
1568+
Statistics {
1569+
num_rows: Precision::Exact(10),
1570+
column_statistics: vec![datafusion_common::ColumnStatistics {
1571+
min_value: min,
1572+
max_value: max,
1573+
..Default::default()
1574+
}],
1575+
..Default::default()
1576+
}
1577+
}
1578+
1579+
#[test]
1580+
fn statistics_pruning_keeps_missing_and_inexact_bounds() {
1581+
use datafusion_expr::{col, lit};
1582+
let exact = |v: i64| Precision::Exact(v.into());
1583+
let inexact = |v: i64| Precision::Inexact(v.into());
1584+
assert_eq!(
1585+
prune_test_files(
1586+
col("d").gt_eq(lit(20_i64)),
1587+
vec![
1588+
None,
1589+
Some(bounds(Precision::Absent, Precision::Absent)),
1590+
Some(bounds(inexact(0), inexact(9))),
1591+
Some(bounds(exact(0), exact(9))),
1592+
Some(bounds(exact(20), exact(29)))
1593+
]
1594+
),
1595+
["f0", "f1", "f2", "f4"]
1596+
);
1597+
}
1598+
1599+
#[test]
1600+
fn statistics_pruning_uses_independent_bounds() {
1601+
use datafusion_expr::{col, lit};
1602+
assert_eq!(
1603+
prune_test_files(
1604+
col("d").lt(lit(20_i64)),
1605+
vec![
1606+
Some(bounds(Precision::Exact(30_i64.into()), Precision::Absent)),
1607+
Some(bounds(Precision::Absent, Precision::Exact(10_i64.into())))
1608+
]
1609+
),
1610+
["f1"]
1611+
);
1612+
}
1613+
1614+
#[test]
1615+
fn statistics_pruning_preserves_null_semantics() {
1616+
use datafusion_expr::{col, lit};
1617+
let mut all_null = bounds(Precision::Absent, Precision::Absent);
1618+
all_null.column_statistics[0].null_count = Precision::Exact(10);
1619+
let mut no_null = bounds(
1620+
Precision::Exact(0_i64.into()),
1621+
Precision::Exact(9_i64.into()),
1622+
);
1623+
no_null.column_statistics[0].null_count = Precision::Exact(0);
1624+
assert_eq!(
1625+
prune_test_files(
1626+
col("d").is_null(),
1627+
vec![Some(all_null.clone()), Some(no_null.clone())]
1628+
),
1629+
["f0"]
1630+
);
1631+
assert_eq!(
1632+
prune_test_files(
1633+
col("d").is_not_null(),
1634+
vec![Some(all_null.clone()), Some(no_null.clone())]
1635+
),
1636+
["f1"]
1637+
);
1638+
assert!(
1639+
prune_test_files(col("d").eq(lit(5_i64)), vec![Some(all_null)]).is_empty()
1640+
);
1641+
assert_eq!(
1642+
prune_test_files(
1643+
col("d").eq(lit(5_i64)).or(col("d").is_null()),
1644+
vec![Some(no_null)]
1645+
),
1646+
["f0"]
1647+
);
1648+
}
1649+
1650+
#[test]
1651+
fn statistics_pruning_keeps_file_on_evaluation_error() {
1652+
use datafusion_common::ScalarValue;
1653+
use datafusion_expr::{col, lit};
1654+
// Binary bounds cannot be cast to Int64, so `prune` returns an error.
1655+
// A Utf8 bound does not error, so it would not reach that branch.
1656+
let binary = || Precision::Exact(ScalarValue::Binary(Some(vec![1])));
1657+
assert_eq!(
1658+
prune_test_files(
1659+
col("d").gt(lit(10_i64)),
1660+
vec![Some(bounds(binary(), binary()))]
1661+
),
1662+
["f0"]
1663+
);
1664+
}
14241665
}

0 commit comments

Comments
 (0)