You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/10/09 03:51:47 UTC
(datafusion) branch gh-readonly-queue/main/pr-25835-6a31aa8d1dc433c8f5bebefa138c3fca93cf8fd9 created (now 791660cd54)
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a change to branch gh-readonly-queue/main/pr-25835-6a31aa8d1dc433c8f5bebefa138c3fca93cf8fd9
in repository https://gitbox.apache.org/repos/asf/datafusion.git
at 791660cd54 fix: Estimate string equality and LIKE filter selectivity (#25835)
This branch includes the following new commits:
new 791660cd54 fix: Estimate string equality and LIKE filter selectivity (#25835)
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org
(datafusion) 01/01: fix: Estimate string equality and LIKE filter selectivity (#25835)
Posted by gi...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25835-6a31aa8d1dc433c8f5bebefa138c3fca93cf8fd9
in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 791660cd54f0196978c98e9bca165c1beb7bbc78
Author: limadog9 <ja...@gmail.com>
AuthorDate: Fri Oct 9 03:51:24 2026 +0000
fix: Estimate string equality and LIKE filter selectivity (#25835)
## Which issue does this PR close?
Closes #25614.
## Rationale for this change
String equality, LIKE, and NOT LIKE currently receive the same fallback
estimate. For a column with 1,000 rows, 200 NULLs, and 20 distinct
non-null values, equality should estimate 40 matching rows and
inequality 760, instead of estimating 200 for both.
## What changes are included in this PR?
- Estimate direct string equality/inequality using the distinct count
when available, under the existing uniform-distribution assumption.
- Classify LIKE patterns as literal, all-percent, or wildcard patterns.
Wildcard estimates use the configured fallback, halved for each anchored
end. Recognize escaped wildcards and Arrow's literal trailing-backslash
behavior.
- Complement negated estimates over non-null rows and propagate zero
null counts for LIKE operands. Literal ILIKE retains a heuristic because
case folding can merge distinct values.
- Retain existing estimates for compound or otherwise unsupported
expressions.
- Remove an unnecessary semicolon in the Windows rounding implementation
so the required Clippy check can run without that pre-existing warning.
## What is the testing strategy for this PR?
Public SQL planning tests in
`datafusion/core/tests/custom_sources_cases/statistics.rs` inject known
statistics through the existing table-provider fixture. They cover Utf8,
LargeUtf8, Utf8View, equality/inequality, pattern forms, escaped
characters, ILIKE, unknown distinct counts, and configured fallback
selectivity. Direct physical-plan tests cover patterns eliminated by SQL
simplification, NULL/empty inputs, and column-valued patterns.
Validation:
- 51 filter tests passed, including the unsupported-literal fallback.
- 3 new public SQL regression tests passed.
- `cargo fmt --all` passed.
- Targeted physical-plan Clippy passed with warnings denied.
- Ablation passed: all 3 new SQL tests fail with the original `main`
filter implementation, with the expected row-count assertion failures.
- TOML/Markdown formatting, license headers, typos, workflow checks, and
ASF YAML checks passed.
## Are there any user-facing changes?
String filter row estimates change. No public API changes. Wildcard
estimates remain heuristics in the absence of string histograms.
---
.../core/tests/custom_sources_cases/statistics.rs | 122 ++++++++
datafusion/physical-plan/src/filter.rs | 328 ++++++++++++++++++++-
2 files changed, 443 insertions(+), 7 deletions(-)
diff --git a/datafusion/core/tests/custom_sources_cases/statistics.rs b/datafusion/core/tests/custom_sources_cases/statistics.rs
index 2899acb3a1..235524d562 100644
--- a/datafusion/core/tests/custom_sources_cases/statistics.rs
+++ b/datafusion/core/tests/custom_sources_cases/statistics.rs
@@ -285,6 +285,128 @@ async fn sql_filter() -> Result<()> {
Ok(())
}
+fn string_filter_ctx(
+ data_type: DataType,
+ distinct_count: Precision<usize>,
+) -> Result<SessionContext> {
+ init_ctx(
+ Statistics {
+ num_rows: Precision::Exact(1000),
+ total_byte_size: Precision::Absent,
+ column_statistics: vec![ColumnStatistics {
+ null_count: Precision::Exact(200),
+ distinct_count,
+ ..ColumnStatistics::new_unknown()
+ }],
+ },
+ Schema::new(vec![Field::new("c1", data_type, true)]),
+ )
+}
+
+async fn string_filter_rows(
+ ctx: &SessionContext,
+ predicate: &str,
+) -> Result<Precision<usize>> {
+ let plan = ctx
+ .sql(&format!("SELECT * FROM stats_table WHERE {predicate}"))
+ .await?
+ .create_physical_plan()
+ .await?;
+ Ok(StatisticsContext::new()
+ .compute(plan.as_ref(), &StatisticsArgs::new())?
+ .num_rows)
+}
+
+#[tokio::test]
+async fn sql_string_filter_selectivity() -> Result<()> {
+ // There are 800 non-null rows and 20 distinct strings. Equality estimates
+ // 40 matches, and negated predicates exclude nulls as well as matches.
+ // LIKE estimates distinguish unanchored patterns from patterns anchored
+ // at one or both ends; escaped wildcards are literal characters.
+ let cases = [
+ ("c1 = 'foo'", 40),
+ ("'foo' = c1", 40),
+ ("c1 != 'foo'", 760),
+ ("'foo' != c1", 760),
+ ("c1 LIKE 'foo'", 40),
+ ("c1 NOT LIKE 'foo'", 760),
+ ("c1 LIKE '%foo%'", 160),
+ ("c1 NOT LIKE '%foo%'", 640),
+ ("c1 LIKE 'foo%'", 80),
+ ("c1 NOT LIKE 'foo%'", 720),
+ ("c1 LIKE '%foo'", 80),
+ ("c1 NOT LIKE '%foo'", 720),
+ ("c1 LIKE 'f_o'", 40),
+ ("c1 NOT LIKE 'f_o'", 760),
+ (r"c1 LIKE 'foo\%'", 40),
+ (r"c1 NOT LIKE 'foo\%'", 760),
+ (r"c1 LIKE 'foo\%%'", 80),
+ (r"c1 NOT LIKE 'foo\%%'", 720),
+ (r"c1 LIKE 'foo\'", 40),
+ (r"c1 NOT LIKE 'foo\'", 760),
+ (r"c1 LIKE '%foo\'", 80),
+ (r"c1 NOT LIKE '%foo\'", 720),
+ // Case-sensitive NDV cannot estimate a case-insensitive equality.
+ ("c1 ILIKE 'foo'", 160),
+ ("c1 NOT ILIKE 'foo'", 640),
+ ];
+ for data_type in [DataType::Utf8, DataType::LargeUtf8, DataType::Utf8View] {
+ let ctx = string_filter_ctx(data_type.clone(), Precision::Exact(20))?;
+ for (predicate, expected_rows) in cases {
+ assert_eq!(
+ string_filter_rows(&ctx, predicate).await?,
+ Precision::Inexact(expected_rows),
+ "{data_type:?}: {predicate}"
+ );
+ }
+ }
+ Ok(())
+}
+
+#[tokio::test]
+async fn sql_string_filter_without_distinct_count() -> Result<()> {
+ let ctx = string_filter_ctx(DataType::Utf8View, Precision::Absent)?;
+ // Without NDV, use the configured default (20%) over non-null rows.
+ for (predicate, expected_rows) in [
+ ("c1 = 'foo'", 160),
+ ("c1 != 'foo'", 640),
+ ("c1 LIKE 'foo'", 160),
+ ("c1 NOT LIKE 'foo'", 640),
+ ] {
+ assert_eq!(
+ string_filter_rows(&ctx, predicate).await?,
+ Precision::Inexact(expected_rows),
+ "{predicate}"
+ );
+ }
+ Ok(())
+}
+
+#[tokio::test]
+async fn sql_string_filter_custom_selectivity() -> Result<()> {
+ let ctx = string_filter_ctx(DataType::Utf8View, Precision::Absent)?;
+ ctx.sql("SET datafusion.optimizer.default_filter_selectivity = 40")
+ .await?
+ .collect()
+ .await?;
+
+ for (predicate, expected_rows) in [
+ ("c1 = 'foo'", 320),
+ ("c1 != 'foo'", 480),
+ ("c1 LIKE '%foo%'", 320),
+ ("c1 NOT LIKE '%foo%'", 480),
+ ("c1 LIKE 'foo%'", 160),
+ ("c1 NOT LIKE 'foo%'", 640),
+ ] {
+ assert_eq!(
+ string_filter_rows(&ctx, predicate).await?,
+ Precision::Inexact(expected_rows),
+ "{predicate}"
+ );
+ }
+ Ok(())
+}
+
#[tokio::test]
async fn sql_limit() -> Result<()> {
let (stats, schema) = fully_defined();
diff --git a/datafusion/physical-plan/src/filter.rs b/datafusion/physical-plan/src/filter.rs
index bc1c1ce5d1..cc5e0846d3 100644
--- a/datafusion/physical-plan/src/filter.rs
+++ b/datafusion/physical-plan/src/filter.rs
@@ -64,7 +64,7 @@ use datafusion_execution::TaskContext;
use datafusion_expr::Operator;
use datafusion_physical_expr::equivalence::ProjectionMapping;
use datafusion_physical_expr::expressions::{
- BinaryExpr, Column, InListExpr, IsNotNullExpr, IsNullExpr, Literal, lit,
+ BinaryExpr, Column, InListExpr, IsNotNullExpr, IsNullExpr, LikeExpr, Literal, lit,
};
use datafusion_physical_expr::intervals::utils::check_support;
use datafusion_physical_expr::utils::collect_columns;
@@ -346,8 +346,8 @@ impl FilterExec {
}
/// Calculates `Statistics` for `FilterExec` by applying the filter's
- /// selectivity (default, or estimated from interval analysis) to the input
- /// statistics.
+ /// selectivity (estimated from interval analysis or string statistics, with
+ /// a configurable fallback) to the input statistics.
///
/// The estimated output row count is used to keep the per-column statistics
/// consistent with it:
@@ -405,10 +405,17 @@ impl FilterExec {
);
(selectivity, filtered_num_rows, cs)
} else {
- // Without interval boundaries, use the default selectivity and
- // apply the row-count constraints that still follow from the
- // filter predicate.
- let selectivity = default_selectivity as f64 / 100.0;
+ // String predicates cannot use interval analysis. Estimate them
+ // from distinct counts and pattern form when possible, then
+ // apply the row-count constraints implied by the predicate.
+ let default_selectivity = default_selectivity as f64 / 100.0;
+ let selectivity = string_selectivity(
+ predicate,
+ schema,
+ &input_stats,
+ default_selectivity,
+ )
+ .unwrap_or(default_selectivity);
let filtered_num_rows =
input_num_rows.with_estimated_selectivity(selectivity);
let mut cs = input_stats.to_inexact().column_statistics;
@@ -1254,6 +1261,17 @@ fn collect_null_rejecting_columns(predicate: &Arc<dyn PhysicalExpr>) -> HashSet<
let mut columns = HashSet::new();
for expr in split_conjunction(predicate) {
+ // LIKE (including ILIKE and their negations) returns NULL if either
+ // operand is NULL.
+ if let Some(like) = expr.downcast_ref::<LikeExpr>() {
+ for operand in [like.expr(), like.pattern()] {
+ if let Some(col) = operand.downcast_ref::<Column>() {
+ columns.insert(col.index());
+ }
+ }
+ continue;
+ }
+
// `col IS NOT NULL` keeps only rows where `col` is non-null.
if let Some(is_not_null) = expr.downcast_ref::<IsNotNullExpr>() {
if let Some(col) = is_not_null.arg().downcast_ref::<Column>() {
@@ -1280,6 +1298,135 @@ fn collect_null_rejecting_columns(predicate: &Arc<dyn PhysicalExpr>) -> HashSet<
columns
}
+/// Estimates a single string comparison against a literal. Compound predicates
+/// retain the fallback: multiplying estimates for predicates on the same column
+/// would count null rejection (and possibly the same restriction) repeatedly.
+fn string_selectivity(
+ predicate: &Arc<dyn PhysicalExpr>,
+ schema: &SchemaRef,
+ input_stats: &Statistics,
+ default_selectivity: f64,
+) -> Option<f64> {
+ let (column, literal, negated, like) =
+ if let Some(binary) = predicate.downcast_ref::<BinaryExpr>() {
+ if !matches!(binary.op(), Operator::Eq | Operator::NotEq) {
+ return None;
+ }
+ let operands = [
+ (binary.left(), binary.right()),
+ (binary.right(), binary.left()),
+ ];
+ let (column, literal) = operands.into_iter().find_map(|(left, right)| {
+ Some((
+ left.downcast_ref::<Column>()?,
+ right.downcast_ref::<Literal>()?,
+ ))
+ })?;
+ (column, literal, *binary.op() == Operator::NotEq, None)
+ } else {
+ let like = predicate.downcast_ref::<LikeExpr>()?;
+ (
+ like.expr().downcast_ref::<Column>()?,
+ like.pattern().downcast_ref::<Literal>()?,
+ like.negated(),
+ Some(like),
+ )
+ };
+
+ if !matches!(
+ schema.field(column.index()).data_type(),
+ DataType::Utf8 | DataType::LargeUtf8 | DataType::Utf8View
+ ) {
+ return None;
+ }
+ let Some(value) = literal.value().try_as_str()? else {
+ // Both a comparison and its negation evaluate to NULL here.
+ return Some(0.0);
+ };
+ let column_stats = &input_stats.column_statistics[column.index()];
+ let equality_selectivity = column_stats
+ .distinct_count
+ .get_value()
+ .filter(|&&ndv| ndv > 0)
+ .map_or(default_selectivity, |&ndv| 1.0 / ndv as f64);
+ let positive_selectivity = match like {
+ Some(like) => like_selectivity(
+ value,
+ like.case_insensitive(),
+ equality_selectivity,
+ default_selectivity,
+ ),
+ None => equality_selectivity,
+ };
+ let selectivity = if negated {
+ 1.0 - positive_selectivity
+ } else {
+ positive_selectivity
+ };
+
+ // Apply the complement within the non-null rows, not across all input
+ // rows. Unknown null counts use the usual assumption of no nulls.
+ match (
+ input_stats.num_rows.get_value(),
+ column_stats.null_count.get_value(),
+ ) {
+ (Some(&rows), Some(&nulls)) if rows > 0 => {
+ Some(rows.saturating_sub(nulls) as f64 * selectivity / rows as f64)
+ }
+ (Some(0), _) => Some(0.0),
+ _ => Some(selectivity),
+ }
+}
+
+/// Classifies a LIKE pattern without treating escaped wildcards as operators.
+/// In the absence of string histograms, wildcard patterns use the configured
+/// fallback, halved for each anchored end. Thus prefix/suffix patterns are
+/// estimated to match fewer rows than an unanchored contains pattern. These are
+/// heuristics, not bounds on the number of matches.
+fn like_selectivity(
+ pattern: &str,
+ case_insensitive: bool,
+ equality_selectivity: f64,
+ default_selectivity: f64,
+) -> f64 {
+ let mut chars = pattern.chars();
+ let mut has_wildcard = false;
+ let mut all_percent = !pattern.is_empty();
+ let mut starts_with_percent = false;
+ let mut ends_with_percent = false;
+ let mut first = true;
+ while let Some(ch) = chars.next() {
+ let percent = ch == '%';
+ if ch == '\\' {
+ // Arrow treats a trailing backslash as a literal backslash too.
+ chars.next();
+ } else if matches!(ch, '%' | '_') {
+ has_wildcard = true;
+ }
+ all_percent &= percent;
+ if first {
+ starts_with_percent = percent;
+ first = false;
+ }
+ ends_with_percent = percent;
+ }
+ if all_percent {
+ 1.0
+ } else if !has_wildcard {
+ // Case folding may merge several distinct input values, so the raw
+ // NDV does not give the selectivity of a literal ILIKE pattern.
+ if case_insensitive {
+ default_selectivity
+ } else {
+ equality_selectivity
+ }
+ } else {
+ let start_factor = if starts_with_percent { 1.0 } else { 0.5 };
+ let end_factor = if ends_with_percent { 1.0 } else { 0.5 };
+ default_selectivity * start_factor * end_factor
+ }
+}
+
/// Returns the checked column index, and whether the check is `IS NULL`, when
/// `predicate` is a bare `IS NULL` or `IS NOT NULL` check on a column.
pub(crate) fn null_check_column(
@@ -4272,6 +4419,173 @@ mod tests {
Ok(())
}
+ #[test]
+ fn test_string_selectivity_non_string_literal() {
+ let schema =
+ Arc::new(Schema::new(vec![Field::new("name", DataType::Utf8, true)]));
+ let predicate: Arc<dyn PhysicalExpr> = Arc::new(BinaryExpr::new(
+ Arc::new(Column::new("name", 0)),
+ Operator::Eq,
+ lit(42_i32),
+ ));
+ let statistics = Statistics::new_unknown(&schema);
+
+ // SQL coerces comparison operands, so exercise this defensive fallback directly.
+ assert_eq!(
+ string_selectivity(&predicate, &schema, &statistics, 0.2),
+ None
+ );
+ }
+
+ fn like_filter_statistics(
+ num_rows: Precision<usize>,
+ column: ColumnStatistics,
+ pattern: Option<&str>,
+ negated: bool,
+ ) -> Arc<Statistics> {
+ let schema = Schema::new(vec![Field::new("name", DataType::Utf8, true)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows,
+ total_byte_size: Precision::Absent,
+ column_statistics: vec![column],
+ },
+ schema.clone(),
+ ));
+ let predicate = Arc::new(LikeExpr::new(
+ negated,
+ false,
+ col("name", &schema).expect("name column exists"),
+ lit(ScalarValue::Utf8(pattern.map(str::to_owned))),
+ ));
+ let filter = FilterExec::try_new(predicate, input).expect("valid LIKE filter");
+ StatisticsContext::new()
+ .compute(&filter, &StatisticsArgs::new())
+ .expect("LIKE filter statistics")
+ }
+
+ #[test]
+ fn test_filter_statistics_like_literal_patterns() {
+ // SQL simplification rewrites these patterns before FilterExec sees
+ // them. Construct LIKE directly to exercise physical-plan callers too.
+ for (pattern, positive_rows, negative_rows) in [
+ (Some("%"), 800, 0),
+ (Some("%%%"), 800, 0),
+ (Some(""), 40, 760),
+ (Some(r"\%"), 40, 760),
+ (Some(r"\_"), 40, 760),
+ (Some(r"\%%"), 80, 720),
+ (Some(r"%\%"), 80, 720),
+ (None, 0, 0),
+ ] {
+ for (negated, expected_rows) in
+ [(false, positive_rows), (true, negative_rows)]
+ {
+ let statistics = like_filter_statistics(
+ Precision::Exact(1000),
+ ColumnStatistics {
+ null_count: Precision::Exact(200),
+ distinct_count: Precision::Exact(20),
+ ..Default::default()
+ },
+ pattern,
+ negated,
+ );
+ assert_eq!(
+ statistics.num_rows,
+ Precision::Inexact(expected_rows),
+ "pattern={pattern:?}, negated={negated}"
+ );
+ assert_eq!(
+ statistics.column_statistics[0].null_count,
+ Precision::Exact(0)
+ );
+ }
+ }
+ }
+
+ #[test]
+ fn test_filter_statistics_like_missing_or_zero_counts() {
+ use Precision::{Absent, Exact, Inexact};
+
+ for (rows, nulls, distinct, positive_rows, negative_rows) in [
+ (Exact(1000), Absent, Exact(20), Inexact(50), Inexact(950)),
+ (
+ Exact(1000),
+ Exact(200),
+ Exact(0),
+ Inexact(160),
+ Inexact(640),
+ ),
+ (Exact(1000), Exact(1000), Exact(0), Inexact(0), Inexact(0)),
+ (Exact(0), Exact(0), Exact(0), Exact(0), Exact(0)),
+ (Inexact(0), Absent, Absent, Inexact(0), Inexact(0)),
+ (Absent, Absent, Exact(20), Absent, Absent),
+ ] {
+ for (negated, expected_rows) in
+ [(false, positive_rows), (true, negative_rows)]
+ {
+ let statistics = like_filter_statistics(
+ rows,
+ ColumnStatistics {
+ null_count: nulls,
+ distinct_count: distinct,
+ ..Default::default()
+ },
+ Some(""),
+ negated,
+ );
+ assert_eq!(
+ statistics.num_rows, expected_rows,
+ "rows={rows:?}, nulls={nulls:?}, distinct={distinct:?}, negated={negated}"
+ );
+ assert_eq!(statistics.column_statistics[0].null_count, Exact(0));
+ }
+ }
+ }
+
+ #[test]
+ fn test_filter_statistics_like_column_pattern_rejects_nulls() {
+ let schema = Schema::new(vec![
+ Field::new("name", DataType::Utf8, true),
+ Field::new("pattern", DataType::Utf8, true),
+ ]);
+ for negated in [false, true] {
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows: Precision::Exact(1000),
+ total_byte_size: Precision::Absent,
+ column_statistics: [200, 300]
+ .into_iter()
+ .map(|nulls| ColumnStatistics {
+ null_count: Precision::Exact(nulls),
+ distinct_count: Precision::Exact(20),
+ ..Default::default()
+ })
+ .collect(),
+ },
+ schema.clone(),
+ ));
+ let predicate = Arc::new(LikeExpr::new(
+ negated,
+ false,
+ col("name", &schema).expect("name column exists"),
+ col("pattern", &schema).expect("pattern column exists"),
+ ));
+ let filter =
+ FilterExec::try_new(predicate, input).expect("valid LIKE filter");
+ let statistics = StatisticsContext::new()
+ .compute(&filter, &StatisticsArgs::new())
+ .expect("LIKE filter statistics");
+ // A varying pattern retains the fallback estimate, but neither
+ // operand can be NULL in any surviving row.
+ assert_eq!(statistics.num_rows, Precision::Inexact(200));
+ for column in &statistics.column_statistics {
+ assert_eq!(column.null_count, Precision::Exact(0));
+ }
+ }
+ }
+
#[test]
fn test_filter_statistics_fetch_preserves_singleton() -> Result<()> {
use Precision::{Absent, Exact, Inexact};
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org