Skip to content

Commit a9c78d7

Browse files
kumarUjjawalOmega359
authored andcommitted
fix: apply pushed-down fetch to filter statistics (apache#25862)
## Which issue does this PR close? Related to apache#25620. Split from apache#25648 following [the review request](apache#25648 (comment)). This PR can be reviewed and merged independently. ## Rationale for this change A pushed-down `fetch` stops each FilterExec partition after a bounded number of rows, but filter statistics currently ignore it. A filter with 100 matching rows and `fetch=3` still estimates 100 rows in a single partition. This can distort downstream planning decisions. ## What changes are included in this PR? Apply the per-partition fetch in both the built-in filter statistics and FilterStatisticsProvider. Adjust row and byte estimates while keeping empty, all-null, and proven singleton column statistics consistent. Overall statistics remain estimates when rows may be distributed unevenly across partitions. Add independent execution tests with one and two partitions, plus tests for zero fetch, all-null columns, singleton preservation, and the provider path. ## What is the testing strategy for this PR? Passed on this independent branch: - `cargo test --profile ci -p datafusion-physical-plan --lib` (2,367 tests) - `cargo clippy --profile ci -p datafusion-physical-plan --all-targets --all-features -- -D warnings` - `cargo fmt --all` and `git diff --check` Benchmarks were not rerun for the split. This extracts the fetch implementation already present in apache#25648; its earlier combined measurements are not isolated measurements of this PR. ## Are there any user-facing changes? EXPLAIN statistics account for a fetch pushed into FilterExec. Plan choices can change as a result. No public API changes.
1 parent 9e57cbf commit a9c78d7

2 files changed

Lines changed: 246 additions & 13 deletions

File tree

‎datafusion/physical-plan/src/filter.rs‎

Lines changed: 230 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -64,7 +64,7 @@ use datafusion_execution::TaskContext;
6464
use datafusion_expr::Operator;
6565
use datafusion_physical_expr::equivalence::ProjectionMapping;
6666
use datafusion_physical_expr::expressions::{
67-
BinaryExpr, Column, InListExpr, IsNotNullExpr, Literal, lit,
67+
BinaryExpr, Column, InListExpr, IsNotNullExpr, IsNullExpr, Literal, lit,
6868
};
6969
use datafusion_physical_expr::intervals::utils::check_support;
7070
use datafusion_physical_expr::utils::collect_columns;
@@ -380,17 +380,8 @@ impl FilterExec {
380380
let match_limit = unique_match_limit(predicate, &input_stats);
381381

382382
let (selectivity, num_rows, column_statistics) = if is_infeasible {
383-
// Contradictory predicate: no rows survive. Row-bounded counts are
384-
// zero; value statistics are undefined on an empty column.
385-
let mut cs = input_stats.to_inexact().column_statistics;
386-
for col_stat in &mut cs {
387-
col_stat.distinct_count = Precision::Exact(0);
388-
col_stat.null_count = Precision::Exact(0);
389-
col_stat.min_value = Precision::Absent;
390-
col_stat.max_value = Precision::Absent;
391-
col_stat.sum_value = Precision::Absent;
392-
col_stat.byte_size = Precision::Exact(0);
393-
}
383+
// Contradictory predicate: no rows survive.
384+
let cs = vec![empty_column_statistics(); input_stats.column_statistics.len()];
394385
(0.0, Precision::Exact(0), cs)
395386
} else {
396387
let null_rejecting_columns = collect_null_rejecting_columns(predicate);
@@ -456,6 +447,87 @@ impl FilterExec {
456447
})
457448
}
458449

450+
/// Applies the filter's `fetch` to its output statistics for `partition`,
451+
/// or for all partitions when `partition` is `None`. The fetch stops each
452+
/// partition separately.
453+
#[inline]
454+
pub(crate) fn statistics_with_fetch(
455+
&self,
456+
stats: Statistics,
457+
partition: Option<usize>,
458+
) -> Result<Statistics> {
459+
match self.fetch {
460+
Some(fetch) => self.statistics_under_fetch(stats, fetch, partition),
461+
None => Ok(stats),
462+
}
463+
}
464+
465+
fn statistics_under_fetch(
466+
&self,
467+
stats: Statistics,
468+
fetch: usize,
469+
partition: Option<usize>,
470+
) -> Result<Statistics> {
471+
if stats
472+
.num_rows
473+
.get_value()
474+
.is_some_and(|rows| *rows <= fetch)
475+
{
476+
// No partition reaches the fetch, so no rows are dropped.
477+
return Ok(stats);
478+
}
479+
let partitions = self.properties().partitioning.partition_count();
480+
let single = partition.is_some() || partitions <= 1;
481+
let bound = if single {
482+
fetch
483+
} else {
484+
fetch.saturating_mul(partitions)
485+
};
486+
let input_columns = stats.column_statistics.clone();
487+
let stats = if single {
488+
stats
489+
} else {
490+
// Any partition can hold more than `fetch` rows, so the total
491+
// under the fetch is only an estimate.
492+
stats.to_inexact()
493+
};
494+
495+
let mut stats = stats.with_fetch(Some(bound), 0, 1)?;
496+
if stats.num_rows == Precision::Exact(0) {
497+
stats.total_byte_size = Precision::Exact(0);
498+
stats.column_statistics.fill(empty_column_statistics());
499+
return Ok(stats);
500+
}
501+
// A fetch only drops rows. A count that is exactly zero stays exact, and
502+
// so does a column with one value in every row while rows remain.
503+
for (column_stats, input) in stats.column_statistics.iter_mut().zip(input_columns)
504+
{
505+
if input.null_count == Precision::Exact(0) {
506+
if fetch > 0 && input.is_singleton() {
507+
column_stats.min_value = input.min_value;
508+
column_stats.max_value = input.max_value;
509+
if input.distinct_count == Precision::Exact(1) {
510+
column_stats.distinct_count = input.distinct_count;
511+
}
512+
}
513+
column_stats.null_count = input.null_count;
514+
} else {
515+
column_stats.null_count =
516+
cap_at_rows(column_stats.null_count, stats.num_rows);
517+
}
518+
if input.distinct_count == Precision::Exact(0) {
519+
column_stats.distinct_count = input.distinct_count;
520+
}
521+
}
522+
if let Some((column, true)) = null_check_column(self.predicate())
523+
&& let Some(column_stats) = stats.column_statistics.get_mut(column)
524+
{
525+
// Every surviving row is still null after the fetch.
526+
column_stats.null_count = stats.num_rows;
527+
}
528+
Ok(stats)
529+
}
530+
459531
/// This function creates the cache object that stores the plan properties such as schema, equivalence properties, ordering, partitioning, etc.
460532
fn compute_properties(
461533
input: &Arc<dyn ExecutionPlan>,
@@ -673,7 +745,7 @@ impl ExecutionPlan for FilterExec {
673745
fn statistics_from_inputs(
674746
&self,
675747
input_stats: &[Arc<Statistics>],
676-
_args: &StatisticsArgs,
748+
args: &StatisticsArgs,
677749
) -> Result<Arc<Statistics>> {
678750
let input_stats = input_stats[0].as_ref().clone();
679751
let stats = Self::statistics_helper(
@@ -682,6 +754,7 @@ impl ExecutionPlan for FilterExec {
682754
self.predicate(),
683755
self.default_selectivity,
684756
)?;
757+
let stats = self.statistics_with_fetch(stats, args.partition())?;
685758
Ok(Arc::new(stats.project(self.projection.as_ref())))
686759
}
687760

@@ -1207,6 +1280,31 @@ fn collect_null_rejecting_columns(predicate: &Arc<dyn PhysicalExpr>) -> HashSet<
12071280
columns
12081281
}
12091282

1283+
/// Returns the checked column index, and whether the check is `IS NULL`, when
1284+
/// `predicate` is a bare `IS NULL` or `IS NOT NULL` check on a column.
1285+
pub(crate) fn null_check_column(
1286+
predicate: &Arc<dyn PhysicalExpr>,
1287+
) -> Option<(usize, bool)> {
1288+
let (arg, is_null) = if let Some(expr) = predicate.downcast_ref::<IsNullExpr>() {
1289+
(expr.arg(), true)
1290+
} else {
1291+
let expr = predicate.downcast_ref::<IsNotNullExpr>()?;
1292+
(expr.arg(), false)
1293+
};
1294+
Some((arg.downcast_ref::<Column>()?.index(), is_null))
1295+
}
1296+
1297+
/// Column statistics of an exactly empty output: no nulls, distinct values or
1298+
/// bytes, and no value bounds.
1299+
fn empty_column_statistics() -> ColumnStatistics {
1300+
ColumnStatistics {
1301+
null_count: Precision::Exact(0),
1302+
distinct_count: Precision::Exact(0),
1303+
byte_size: Precision::Exact(0),
1304+
..ColumnStatistics::new_unknown()
1305+
}
1306+
}
1307+
12101308
/// Converts an interval bound to a [`Precision`] value. NULL bounds (which
12111309
/// represent "unbounded" in the interval type) map to [`Precision::Absent`].
12121310
fn interval_bound_to_precision(
@@ -4174,6 +4272,125 @@ mod tests {
41744272
Ok(())
41754273
}
41764274

4275+
#[test]
4276+
fn test_filter_statistics_fetch_preserves_singleton() -> Result<()> {
4277+
use Precision::{Absent, Exact, Inexact};
4278+
4279+
let schema = Schema::new(vec![Field::new("a", DataType::Int32, true)]);
4280+
let input = Arc::new(StatisticsExec::new(
4281+
Statistics::new_unknown(&schema),
4282+
schema,
4283+
));
4284+
let filter = FilterExecBuilder::new(lit(true), input)
4285+
.with_fetch(Some(3))
4286+
.build()?;
4287+
// A positive fetch keeps the singleton that its input reports, for
4288+
// both overall and partition stats.
4289+
for num_rows in [Exact(100), Inexact(100), Absent] {
4290+
for partition in [None, Some(0)] {
4291+
let stats = filter.statistics_with_fetch(
4292+
Statistics {
4293+
num_rows,
4294+
total_byte_size: Absent,
4295+
column_statistics: vec![ColumnStatistics {
4296+
null_count: Exact(0),
4297+
distinct_count: Exact(1),
4298+
min_value: Exact(ScalarValue::Int32(Some(5))),
4299+
max_value: Exact(ScalarValue::Int32(Some(5))),
4300+
..Default::default()
4301+
}],
4302+
},
4303+
partition,
4304+
)?;
4305+
let column = &stats.column_statistics[0];
4306+
assert_eq!(column.null_count, Exact(0));
4307+
assert!(column.is_singleton());
4308+
assert_eq!(column.distinct_count, Exact(1));
4309+
}
4310+
}
4311+
Ok(())
4312+
}
4313+
4314+
#[tokio::test]
4315+
async fn test_filter_fetch_statistics_match_execution() -> Result<()> {
4316+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
4317+
let batch = RecordBatch::try_new(
4318+
Arc::clone(&schema),
4319+
vec![Arc::new(Int32Array::from_iter_values(0..100))],
4320+
)?;
4321+
for partitions in [1, 2] {
4322+
let input: Arc<dyn ExecutionPlan> = test::TestMemoryExec::try_new_exec(
4323+
&vec![vec![batch.clone()]; partitions],
4324+
Arc::clone(&schema),
4325+
None,
4326+
)?;
4327+
for fetch in [0, 3] {
4328+
let filter: Arc<dyn ExecutionPlan> = Arc::new(
4329+
FilterExecBuilder::new(lit(true), Arc::clone(&input))
4330+
.with_fetch(Some(fetch))
4331+
.build()?,
4332+
);
4333+
let stats = StatisticsContext::new()
4334+
.compute(filter.as_ref(), &StatisticsArgs::new())?;
4335+
let partition_stats = StatisticsContext::new().compute(
4336+
filter.as_ref(),
4337+
&StatisticsArgs::new().with_partition(Some(0)),
4338+
)?;
4339+
assert_eq!(stats.num_rows.get_value(), Some(&(fetch * partitions)));
4340+
assert_eq!(partition_stats.num_rows.get_value(), Some(&fetch));
4341+
let batches = crate::execution_plan::collect(
4342+
filter,
4343+
Arc::new(TaskContext::default()),
4344+
)
4345+
.await?;
4346+
assert_eq!(
4347+
batches.iter().map(RecordBatch::num_rows).sum::<usize>(),
4348+
fetch * partitions
4349+
);
4350+
}
4351+
}
4352+
Ok(())
4353+
}
4354+
4355+
#[test]
4356+
fn test_filter_fetch_null_column_statistics() -> Result<()> {
4357+
use Precision::{Exact, Inexact};
4358+
4359+
let schema = Schema::new(vec![Field::new("a", DataType::Int32, true)]);
4360+
let stats = Statistics {
4361+
num_rows: Exact(100),
4362+
total_byte_size: Exact(400),
4363+
column_statistics: vec![ColumnStatistics {
4364+
null_count: Exact(100),
4365+
distinct_count: Exact(0),
4366+
byte_size: Exact(400),
4367+
..Default::default()
4368+
}],
4369+
};
4370+
let input: Arc<dyn ExecutionPlan> = Arc::new(
4371+
StatisticsExec::new(stats.clone(), schema.clone())
4372+
.with_partition_statistics(vec![stats.clone()]),
4373+
);
4374+
for fetch in [0, 3, 200] {
4375+
let filter =
4376+
FilterExecBuilder::new(is_null(col("a", &schema)?)?, Arc::clone(&input))
4377+
.with_fetch(Some(fetch))
4378+
.build()?;
4379+
let output = filter.statistics_with_fetch(stats.clone(), None)?;
4380+
assert_eq!(output.num_rows, Exact(fetch.min(100)));
4381+
assert_eq!(output.column_statistics[0].null_count, output.num_rows);
4382+
assert_eq!(output.column_statistics[0].distinct_count, Exact(0));
4383+
let expected_bytes = match fetch {
4384+
0 => Exact(0),
4385+
3 => Inexact(12),
4386+
_ => Exact(400),
4387+
};
4388+
assert_eq!(output.total_byte_size, expected_bytes);
4389+
assert_eq!(output.column_statistics[0].byte_size, expected_bytes);
4390+
}
4391+
Ok(())
4392+
}
4393+
41774394
#[tokio::test]
41784395
async fn test_filter_statistics_singleton_precision() -> Result<()> {
41794396
use Precision::{Exact, Inexact};

‎datafusion/physical-plan/src/operator_statistics/mod.rs‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -637,6 +637,7 @@ impl StatisticsProvider for FilterStatisticsProvider {
637637
}
638638
}
639639

640+
let stats = filter.statistics_with_fetch(stats, None)?;
640641
let stats = stats.project(filter.projection().as_ref());
641642
Ok(StatisticsResult::Computed(ExtendedStatistics::new(stats)))
642643
}
@@ -1794,6 +1795,21 @@ mod tests {
17941795
Ok(())
17951796
}
17961797

1798+
#[test]
1799+
fn test_filter_provider_applies_fetch() -> Result<()> {
1800+
use crate::filter::FilterExecBuilder;
1801+
1802+
let registry =
1803+
StatisticsRegistry::with_providers(vec![Arc::new(FilterStatisticsProvider)]);
1804+
let source = make_source(1000);
1805+
let filter = FilterExecBuilder::new(lit(true), source)
1806+
.with_fetch(Some(3))
1807+
.build()?;
1808+
let stats = compute(&registry, &filter)?;
1809+
assert_eq!(stats.base.num_rows, Precision::Inexact(3));
1810+
Ok(())
1811+
}
1812+
17971813
#[test]
17981814
fn test_filter_adjusts_ndv_by_selectivity() -> Result<()> {
17991815
use datafusion_common::ScalarValue;

0 commit comments

Comments
 (0)