Skip to content

Commit c9f1f89

Browse files
kumarUjjawalOmega359
authored andcommitted
fix: preserve uncertainty in singleton filter statistics (apache#25863)
## 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 An equality filter can narrow a column's bounds to one value without proving that any row contains that value. With input bounds [1, 100] and actual values 1 and 100, `a = 5` returns no rows, but currently reports an exact distinct count of one when its estimated row count is positive. ## What changes are included in this PR? Report `Inexact(1)` for a singleton domain when the filtered row count is an estimate or is unknown. Preserve exact zero for an exactly empty output and exact one when an exact positive row count proves that the singleton is present. Add an execution regression for the absent value and update affected unit-test and Parquet EXPLAIN expectations. ## What is the testing strategy for this PR? Passed on this independent branch: - `cargo test --profile ci -p datafusion-physical-plan --lib` (2,364 tests) - `cargo clippy --profile ci -p datafusion-physical-plan --all-targets --all-features -- -D warnings` - `cargo test --profile ci -p datafusion-sqllogictest --test sqllogictests -- parquet_statistics.slt` - `cargo fmt --all` and `git diff --check` Benchmarks were not rerun for this split. This extracts the singleton-precision implementation already present in apache#25648. ## Are there any user-facing changes? EXPLAIN reports an estimated distinct count when a matching row is not proven. No public API changes.
1 parent 86982bd commit c9f1f89

2 files changed

Lines changed: 63 additions & 30 deletions

File tree

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

Lines changed: 57 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -1254,20 +1254,20 @@ fn scale_byte_size_at_rows(
12541254

12551255
/// Returns the NDV for a column constrained to one non-null value (e.g.
12561256
/// `column = literal` or a singleton interval), derived from the filtered row
1257-
/// estimate: zero rows means zero distinct values, a known positive row count
1258-
/// means exactly one, and an unknown row count means an inexact one (the column
1259-
/// could still be empty).
1257+
/// estimate: zero rows means zero distinct values, an exact positive row count
1258+
/// means exactly one, and an estimated or unknown row count means an inexact
1259+
/// one (the column could still be empty).
12601260
///
12611261
/// The caller is responsible for proving the singleton domain.
12621262
fn distinct_count_for_singleton_domain(
12631263
filtered_num_rows: Precision<usize>,
12641264
) -> Precision<usize> {
12651265
match filtered_num_rows {
12661266
Precision::Exact(0) | Precision::Inexact(0) => filtered_num_rows,
1267-
// The row count is unknown, so the column could still be empty (zero
1268-
// distinct values); report an inexact one rather than overstating it.
1269-
Precision::Absent => Precision::Inexact(1),
1270-
_ => Precision::Exact(1),
1267+
Precision::Exact(_) => Precision::Exact(1),
1268+
// The row count is not known exactly, so the column could still be
1269+
// empty (zero distinct values); report an inexact one.
1270+
Precision::Inexact(_) | Precision::Absent => Precision::Inexact(1),
12711271
}
12721272
}
12731273

@@ -2990,7 +2990,7 @@ mod tests {
29902990
Operator::Eq,
29912991
Arc::new(Literal::new(ScalarValue::Utf8(Some("hello".to_string())))),
29922992
)),
2993-
vec![Precision::Exact(1)],
2993+
vec![Precision::Inexact(1)],
29942994
),
29952995
(
29962996
"utf8view equality",
@@ -3006,7 +3006,7 @@ mod tests {
30063006
"hello".to_string(),
30073007
)))),
30083008
)),
3009-
vec![Precision::Exact(1)],
3009+
vec![Precision::Inexact(1)],
30103010
),
30113011
(
30123012
"largeutf8 equality",
@@ -3022,7 +3022,7 @@ mod tests {
30223022
"hello".to_string(),
30233023
)))),
30243024
)),
3025-
vec![Precision::Exact(1)],
3025+
vec![Precision::Inexact(1)],
30263026
),
30273027
(
30283028
"utf8 reversed (literal = column)",
@@ -3036,7 +3036,7 @@ mod tests {
30363036
Operator::Eq,
30373037
Arc::new(Column::new("name", 0)),
30383038
)),
3039-
vec![Precision::Exact(1)],
3039+
vec![Precision::Inexact(1)],
30403040
),
30413041
(
30423042
"OR is not collapsed to NDV=1, but NDV is capped at filtered rows",
@@ -3093,7 +3093,7 @@ mod tests {
30933093
Arc::new(Literal::new(ScalarValue::Int32(Some(42)))),
30943094
)),
30953095
)),
3096-
vec![Precision::Exact(1), Precision::Exact(1)],
3096+
vec![Precision::Inexact(1), Precision::Inexact(1)],
30973097
),
30983098
(
30993099
"numeric equality with min/max bounds (interval analysis path)",
@@ -3109,7 +3109,7 @@ mod tests {
31093109
Operator::Eq,
31103110
Arc::new(Literal::new(ScalarValue::Int32(Some(42)))),
31113111
)),
3112-
vec![Precision::Exact(1)],
3112+
vec![Precision::Inexact(1)],
31133113
),
31143114
(
31153115
"timestamp equality",
@@ -3130,7 +3130,7 @@ mod tests {
31303130
None,
31313131
))),
31323132
)),
3133-
vec![Precision::Exact(1)],
3133+
vec![Precision::Inexact(1)],
31343134
),
31353135
(
31363136
"contradictory numeric equality (infeasible)",
@@ -3166,7 +3166,7 @@ mod tests {
31663166
Operator::Eq,
31673167
Arc::new(Literal::new(ScalarValue::Utf8(Some("hello".to_string())))),
31683168
)),
3169-
vec![Precision::Exact(1)],
3169+
vec![Precision::Inexact(1)],
31703170
),
31713171
(
31723172
"contradictory utf8 equality (infeasible)",
@@ -3231,7 +3231,7 @@ mod tests {
32313231
Arc::new(Literal::new(ScalarValue::Int32(Some(2)))),
32323232
)),
32333233
)),
3234-
vec![Precision::Exact(1), Precision::Exact(1)],
3234+
vec![Precision::Inexact(1), Precision::Inexact(1)],
32353235
),
32363236
];
32373237

@@ -3529,7 +3529,7 @@ mod tests {
35293529
// Equality predicates collapse NDV and reject nulls for their columns.
35303530
assert_eq!(
35313531
statistics.column_statistics[0].distinct_count,
3532-
Precision::Exact(1)
3532+
Precision::Inexact(1)
35333533
);
35343534
assert_eq!(
35353535
statistics.column_statistics[0].null_count,
@@ -3544,7 +3544,7 @@ mod tests {
35443544
);
35453545
assert_eq!(
35463546
statistics.column_statistics[2].distinct_count,
3547-
Precision::Exact(1)
3547+
Precision::Inexact(1)
35483548
);
35493549
assert_eq!(
35503550
statistics.column_statistics[2].null_count,
@@ -3582,7 +3582,7 @@ mod tests {
35823582
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
35833583
assert_eq!(
35843584
statistics.column_statistics[0].distinct_count,
3585-
Precision::Exact(1)
3585+
Precision::Inexact(1)
35863586
);
35873587
Ok(())
35883588
}
@@ -3616,7 +3616,7 @@ mod tests {
36163616
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
36173617
assert_eq!(
36183618
statistics.column_statistics[0].distinct_count,
3619-
Precision::Exact(1)
3619+
Precision::Inexact(1)
36203620
);
36213621
Ok(())
36223622
}
@@ -3650,7 +3650,7 @@ mod tests {
36503650
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
36513651
assert_eq!(
36523652
statistics.column_statistics[0].distinct_count,
3653-
Precision::Exact(1)
3653+
Precision::Inexact(1)
36543654
);
36553655
Ok(())
36563656
}
@@ -3684,7 +3684,7 @@ mod tests {
36843684
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
36853685
assert_eq!(
36863686
statistics.column_statistics[0].distinct_count,
3687-
Precision::Exact(1)
3687+
Precision::Inexact(1)
36883688
);
36893689
Ok(())
36903690
}
@@ -3719,7 +3719,7 @@ mod tests {
37193719
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
37203720
assert_eq!(
37213721
statistics.column_statistics[0].distinct_count,
3722-
Precision::Exact(1)
3722+
Precision::Inexact(1)
37233723
);
37243724
Ok(())
37253725
}
@@ -3766,7 +3766,7 @@ mod tests {
37663766
StatisticsContext::new().compute(filter.as_ref(), &StatisticsArgs::new())?;
37673767
assert_eq!(
37683768
statistics.column_statistics[0].distinct_count,
3769-
Precision::Exact(1)
3769+
Precision::Inexact(1)
37703770
);
37713771
Ok(())
37723772
}
@@ -4174,6 +4174,39 @@ mod tests {
41744174
Ok(())
41754175
}
41764176

4177+
#[tokio::test]
4178+
async fn test_filter_statistics_singleton_precision() -> Result<()> {
4179+
use Precision::{Exact, Inexact};
4180+
4181+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, true)]));
4182+
// The bounds include 5, but no row contains it.
4183+
let values = Int32Array::from_iter_values(
4184+
(0..1000).map(|i| if i % 2 == 0 { 1 } else { 100 }),
4185+
);
4186+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![Arc::new(values)])?;
4187+
let input = test::TestMemoryExec::try_new_exec(
4188+
&[vec![batch]],
4189+
Arc::clone(&schema),
4190+
None,
4191+
)?;
4192+
let mut input_stats = StatisticsContext::new()
4193+
.compute(input.as_ref(), &StatisticsArgs::new())?
4194+
.as_ref()
4195+
.clone();
4196+
// Supply the bounds a file scan could report for these rows.
4197+
input_stats.column_statistics[0].min_value = Exact(ScalarValue::Int32(Some(1)));
4198+
input_stats.column_statistics[0].max_value = Exact(ScalarValue::Int32(Some(100)));
4199+
let predicate = binary(col("a", &schema)?, Operator::Eq, lit(5i32), &schema)?;
4200+
let filter = FilterExecBuilder::new(predicate, input).build()?;
4201+
let stats = filter
4202+
.statistics_from_inputs(&[Arc::new(input_stats)], &StatisticsArgs::new())?;
4203+
let batches =
4204+
collect(filter.execute(0, Arc::new(TaskContext::default()))?).await?;
4205+
assert_eq!(batches.iter().map(RecordBatch::num_rows).sum::<usize>(), 0);
4206+
assert_eq!(stats.column_statistics[0].distinct_count, Inexact(1));
4207+
Ok(())
4208+
}
4209+
41774210
#[tokio::test]
41784211
async fn test_filter_statistics_is_not_null_rejects_nulls() -> Result<()> {
41794212
let schema = Schema::new(vec![Field::new("name", DataType::Utf8, true)]);

‎datafusion/sqllogictest/test_files/parquet_statistics.slt‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -59,7 +59,7 @@ query TT
5959
EXPLAIN SELECT * FROM test_table WHERE column1 = 1;
6060
----
6161
physical_plan
62-
01)FilterExec: column1@0 = 1, statistics=[Rows=Inexact(2), Bytes=Inexact(10), [(Col[0]: Min=Exact(Int64(1)) Max=Exact(Int64(1)) Null=Exact(0) Distinct=Exact(1) ScanBytes=Inexact(10))]]
62+
01)FilterExec: column1@0 = 1, statistics=[Rows=Inexact(2), Bytes=Inexact(10), [(Col[0]: Min=Exact(Int64(1)) Max=Exact(Int64(1)) Null=Exact(0) Distinct=Inexact(1) ScanBytes=Inexact(10))]]
6363
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=2, statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(4)) Null=Inexact(0) ScanBytes=Inexact(40))]]
6464
03)----DataSourceExec: file_groups={2 groups: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/test_table/0.parquet], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/test_table/1.parquet]]}, projection=[column1], file_type=parquet, predicate=column1@0 = 1, pruning_predicate=column1_null_count@2 != row_count@3 AND column1_min@0 <= 1 AND 1 <= column1_max@1, required_guarantees=[column1 in (1)], statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(4)) Null=Inexact(0) ScanBytes=Inexact(40))]]
6565

@@ -84,7 +84,7 @@ query TT
8484
EXPLAIN SELECT * FROM test_table WHERE column1 = 1;
8585
----
8686
physical_plan
87-
01)FilterExec: column1@0 = 1, statistics=[Rows=Inexact(2), Bytes=Inexact(10), [(Col[0]: Min=Exact(Int64(1)) Max=Exact(Int64(1)) Null=Exact(0) Distinct=Exact(1) ScanBytes=Inexact(10))]]
87+
01)FilterExec: column1@0 = 1, statistics=[Rows=Inexact(2), Bytes=Inexact(10), [(Col[0]: Min=Exact(Int64(1)) Max=Exact(Int64(1)) Null=Exact(0) Distinct=Inexact(1) ScanBytes=Inexact(10))]]
8888
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=2, statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(4)) Null=Inexact(0) ScanBytes=Inexact(40))]]
8989
03)----DataSourceExec: file_groups={2 groups: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/test_table/0.parquet], [WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/test_table/1.parquet]]}, projection=[column1], file_type=parquet, predicate=column1@0 = 1, pruning_predicate=column1_null_count@2 != row_count@3 AND column1_min@0 <= 1 AND 1 <= column1_max@1, required_guarantees=[column1 in (1)], statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(4)) Null=Inexact(0) ScanBytes=Inexact(40))]]
9090

@@ -152,7 +152,7 @@ query TT
152152
EXPLAIN SELECT i8 FROM typed_table WHERE i8 = 2;
153153
----
154154
physical_plan
155-
01)FilterExec: i8@0 = 2, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Int8(2)) Max=Exact(Int8(2)) Null=Exact(0) Distinct=Exact(1) ScanBytes=Inexact(1))]]
155+
01)FilterExec: i8@0 = 2, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Int8(2)) Max=Exact(Int8(2)) Null=Exact(0) Distinct=Inexact(1) ScanBytes=Inexact(1))]]
156156
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, statistics=[Rows=Inexact(5), Bytes=Inexact(5), [(Col[0]: Min=Inexact(Int8(1)) Max=Inexact(Int8(5)) Null=Inexact(0) ScanBytes=Inexact(5))]]
157157
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/typed_table.parquet]]}, projection=[i8], file_type=parquet, predicate=i8@0 = 2, pruning_predicate=i8_null_count@2 != row_count@3 AND i8_min@0 <= 2 AND 2 <= i8_max@1, required_guarantees=[i8 in (2)], statistics=[Rows=Inexact(5), Bytes=Inexact(5), [(Col[0]: Min=Inexact(Int8(1)) Max=Inexact(Int8(5)) Null=Inexact(0) ScanBytes=Inexact(5))]]
158158

@@ -161,7 +161,7 @@ query TT
161161
EXPLAIN SELECT i64 FROM typed_table WHERE i64 = 2;
162162
----
163163
physical_plan
164-
01)FilterExec: i64@0 = 2, statistics=[Rows=Inexact(1), Bytes=Inexact(8), [(Col[0]: Min=Exact(Int64(2)) Max=Exact(Int64(2)) Null=Exact(0) Distinct=Exact(1) ScanBytes=Inexact(8))]]
164+
01)FilterExec: i64@0 = 2, statistics=[Rows=Inexact(1), Bytes=Inexact(8), [(Col[0]: Min=Exact(Int64(2)) Max=Exact(Int64(2)) Null=Exact(0) Distinct=Inexact(1) ScanBytes=Inexact(8))]]
165165
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(5)) Null=Inexact(0) ScanBytes=Inexact(40))]]
166166
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/typed_table.parquet]]}, projection=[i64], file_type=parquet, predicate=i64@1 = 2, pruning_predicate=i64_null_count@2 != row_count@3 AND i64_min@0 <= 2 AND 2 <= i64_max@1, required_guarantees=[i64 in (2)], statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Int64(1)) Max=Inexact(Int64(5)) Null=Inexact(0) ScanBytes=Inexact(40))]]
167167

@@ -170,7 +170,7 @@ query TT
170170
EXPLAIN SELECT f32 FROM typed_table WHERE f32 = 2.5;
171171
----
172172
physical_plan
173-
01)FilterExec: CAST(f32@0 AS Float64) = 2.5, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Float32(2.5)) Max=Exact(Float32(2.5)) Null=Inexact(0) Distinct=Exact(1) ScanBytes=Inexact(1))]]
173+
01)FilterExec: CAST(f32@0 AS Float64) = 2.5, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Float32(2.5)) Max=Exact(Float32(2.5)) Null=Inexact(0) Distinct=Inexact(1) ScanBytes=Inexact(1))]]
174174
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, statistics=[Rows=Inexact(5), Bytes=Inexact(20), [(Col[0]: Min=Inexact(Float32(1.5)) Max=Inexact(Float32(5.5)) Null=Inexact(0) ScanBytes=Inexact(20))]]
175175
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/typed_table.parquet]]}, projection=[f32], file_type=parquet, predicate=CAST(f32@2 AS Float64) = 2.5, pruning_predicate=f32_null_count@2 != row_count@3 AND CAST(f32_min@0 AS Float64) <= 2.5 AND 2.5 <= CAST(f32_max@1 AS Float64), required_guarantees=[], statistics=[Rows=Inexact(5), Bytes=Inexact(20), [(Col[0]: Min=Inexact(Float32(1.5)) Max=Inexact(Float32(5.5)) Null=Inexact(0) ScanBytes=Inexact(20))]]
176176

@@ -179,7 +179,7 @@ query TT
179179
EXPLAIN SELECT f64 FROM typed_table WHERE 2.5 = f64;
180180
----
181181
physical_plan
182-
01)FilterExec: f64@0 = 2.5, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Float64(2.5)) Max=Exact(Float64(2.5)) Null=Exact(0) Distinct=Exact(1) ScanBytes=Inexact(1))]]
182+
01)FilterExec: f64@0 = 2.5, statistics=[Rows=Inexact(1), Bytes=Inexact(1), [(Col[0]: Min=Exact(Float64(2.5)) Max=Exact(Float64(2.5)) Null=Exact(0) Distinct=Inexact(1) ScanBytes=Inexact(1))]]
183183
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Float64(1.5)) Max=Inexact(Float64(5.5)) Null=Inexact(0) ScanBytes=Inexact(40))]]
184184
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/parquet_statistics/typed_table.parquet]]}, projection=[f64], file_type=parquet, predicate=f64@3 = 2.5, pruning_predicate=f64_null_count@2 != row_count@3 AND f64_min@0 <= 2.5 AND 2.5 <= f64_max@1, required_guarantees=[f64 in (2.5)], statistics=[Rows=Inexact(5), Bytes=Inexact(40), [(Col[0]: Min=Inexact(Float64(1.5)) Max=Inexact(Float64(5.5)) Null=Inexact(0) ScanBytes=Inexact(40))]]
185185

0 commit comments

Comments
 (0)