Skip to content

Commit de80dd7

Browse files
Dandandanclaude
andcommitted
fix: estimate a filter one conjunct at a time, and estimate IN lists
Interval analysis rejects a predicate outright if any part of it is out of reach, and `OR` is out of reach -- which an `IN` list becomes once the planner expands it. So a predicate that is mostly analyzable fell back to the flat default selectivity for all of it. TPC-DS q68 filters `date_dim` by `d_dom between 1 and 2 AND d_year IN (1999, 2000, 2001)`, which was estimated at 20% of the table, 14,610 rows, against 72 that survive. Split the predicate into top-level conjuncts, analyze the ones interval arithmetic supports, and estimate an `IN` list -- or the chain of `OR`ed equalities a short list expands into -- as the fraction of the column's values it selects, the same reasoning `col = literal` gets from `1 / NDV`. An unrecognized conjunct still contributes the default, once, as the whole predicate used to. The predicate is passed through untouched when nothing was split off it, because rebuilding the conjunction re-associates it and interval propagation is sensitive to the shape of the tree it walks. That `date_dim` filter is now estimated at 71 rows. Better estimates also mean better plans: TPC-DS q17 goes from 1.05x slower to 0.74x with join enumeration on, q6 to 0.99x and q68 to 1.02x, while every TPC-H win holds and q7 improves to 0.65x. The baseline gains too, independently of enumeration: q22 drops from 147ms to 116ms. One expectation moves: a cross join whose filtered side is now correctly estimated smaller swaps its inputs, which reorders the rows of a query that does not ask for an order. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent aa652b5 commit de80dd7

2 files changed

Lines changed: 162 additions & 18 deletions

File tree

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

Lines changed: 155 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@ use crate::filter_pushdown::{
3535
ChildFilterDescription, ChildPushdownResult, FilterDescription, FilterPushdownPhase,
3636
FilterPushdownPropagation, PushedDown,
3737
};
38+
use crate::joins::utils::max_distinct_count;
3839
use crate::limit::LocalLimitExec;
3940
use crate::metrics::{MetricBuilder, MetricType};
4041
use crate::projection::{
@@ -63,13 +64,13 @@ use datafusion_execution::TaskContext;
6364
use datafusion_expr::Operator;
6465
use datafusion_physical_expr::equivalence::ProjectionMapping;
6566
use datafusion_physical_expr::expressions::{
66-
BinaryExpr, Column, IsNotNullExpr, Literal, lit,
67+
BinaryExpr, Column, InListExpr, IsNotNullExpr, Literal, lit,
6768
};
6869
use datafusion_physical_expr::intervals::utils::check_support;
6970
use datafusion_physical_expr::utils::{collect_columns, reassign_expr_columns};
7071
use datafusion_physical_expr::{
7172
AcrossPartitions, AnalysisContext, ConstExpr, ExprBoundaries, PhysicalExpr, analyze,
72-
conjunction, split_conjunction,
73+
conjunction, conjunction_opt, split_conjunction,
7374
};
7475

7576
use datafusion_physical_expr_common::physical_expr::fmt_sql;
@@ -359,29 +360,84 @@ impl FilterExec {
359360
} else {
360361
let null_rejecting_columns = collect_null_rejecting_columns(predicate);
361362

362-
if check_support(predicate, schema) {
363+
// Estimate the predicate one top-level conjunct at a time. Interval
364+
// analysis rejects a whole predicate if any part of it is out of
365+
// reach, and an `IN` list is out of reach because the planner expands
366+
// it into a chain of `OR`s. Splitting first means a query like
367+
// `d_dom between 1 and 2 AND d_year IN (1999, 2000, 2001)` no longer
368+
// falls back to the default selectivity for all of it: TPC-DS
369+
// estimates that at 20% of `date_dim`, or 14,610 rows, where 72
370+
// survive.
371+
let (supported, rest): (Vec<_>, Vec<_>) = split_conjunction(predicate)
372+
.into_iter()
373+
.partition(|conjunct| check_support(conjunct, schema));
374+
let split_anything = !rest.is_empty();
375+
376+
// Selectivity of the conjuncts interval analysis cannot see. An
377+
// unrecognized one still contributes the default, once, as the whole
378+
// predicate used to.
379+
let mut unanalyzed_selectivity = 1.0;
380+
let mut has_unknown_conjunct = false;
381+
for conjunct in rest {
382+
match in_list_selectivity(
383+
conjunct,
384+
&input_stats.column_statistics,
385+
&input_num_rows,
386+
) {
387+
Some(selectivity) => unanalyzed_selectivity *= selectivity,
388+
None => has_unknown_conjunct = true,
389+
}
390+
}
391+
if has_unknown_conjunct {
392+
unanalyzed_selectivity *= default_selectivity as f64 / 100.0;
393+
}
394+
395+
// Rebuilding the conjunction re-associates it, and interval
396+
// propagation is sensitive to the shape of the tree it walks, so the
397+
// predicate is passed through untouched unless something was actually
398+
// split off it. It must never be passed through when something was:
399+
// interval analysis rejects the parts that were split off, and asking
400+
// it to walk them anyway is an error rather than a fallback.
401+
let analyzable = if split_anything {
402+
conjunction_opt(supported.into_iter().cloned())
403+
} else {
404+
Some(Arc::clone(predicate))
405+
};
406+
if let Some(analyzable) = analyzable {
363407
let input_analysis_ctx = AnalysisContext::try_from_statistics(
364408
schema,
365409
&input_stats.column_statistics,
366410
)?;
367-
let analysis_ctx = analyze(predicate, input_analysis_ctx, schema)?;
368-
let selectivity = analysis_ctx.selectivity.unwrap_or(1.0);
411+
let analysis_ctx = analyze(&analyzable, input_analysis_ctx, schema)?;
412+
let selectivity =
413+
analysis_ctx.selectivity.unwrap_or(1.0) * unanalyzed_selectivity;
369414
let filtered_num_rows =
370415
input_num_rows.with_estimated_selectivity(selectivity);
371-
let cs = collect_new_statistics(
416+
let mut cs = collect_new_statistics(
372417
schema,
373418
&input_stats.column_statistics,
374419
analysis_ctx.boundaries,
375420
selectivity,
376421
&null_rejecting_columns,
377422
filtered_num_rows,
378423
);
424+
// A column pinned by an equality that was split off has one
425+
// distinct value left, which interval analysis of the remaining
426+
// conjuncts cannot know.
427+
for idx in &eq_columns {
428+
if let Some(col_stat) = cs.get_mut(*idx)
429+
&& col_stat.distinct_count != Precision::Exact(1)
430+
{
431+
col_stat.distinct_count =
432+
distinct_count_for_singleton_domain(filtered_num_rows);
433+
}
434+
}
379435
(selectivity, filtered_num_rows, cs)
380436
} else {
381-
// Without interval boundaries, use the default selectivity and
382-
// apply the row-count constraints that still follow from the
383-
// filter predicate.
384-
let selectivity = default_selectivity as f64 / 100.0;
437+
// Nothing to derive boundaries from, so keep the input's value
438+
// statistics and apply only the row-count constraints that still
439+
// follow from the filter predicate.
440+
let selectivity = unanalyzed_selectivity;
385441
let filtered_num_rows =
386442
input_num_rows.with_estimated_selectivity(selectivity);
387443
let mut cs = input_stats.to_inexact().column_statistics;
@@ -959,6 +1015,91 @@ impl EmbeddedProjection for FilterExec {
9591015
///
9601016
/// Only AND conjunctions are traversed; OR is intentionally skipped
9611017
/// since `a = 1 OR a = 2` does not pin NDV to 1.
1018+
/// Estimates the selectivity of `col IN (a, b, c)`, including the chain of
1019+
/// `OR`ed equalities the planner expands a short list into.
1020+
///
1021+
/// Interval arithmetic cannot narrow a column from a disjunction, so without this
1022+
/// such a conjunct would contribute nothing but the default selectivity. Here the
1023+
/// fraction of values the list selects is `distinct literals / distinct values`,
1024+
/// the same reasoning `col = literal` gets from `1 / NDV`.
1025+
///
1026+
/// Returns `None` when the conjunct is not a list of literals over one column.
1027+
fn in_list_selectivity(
1028+
conjunct: &Arc<dyn PhysicalExpr>,
1029+
column_statistics: &[ColumnStatistics],
1030+
num_rows: &Precision<usize>,
1031+
) -> Option<f64> {
1032+
let mut column = None;
1033+
let mut values = HashSet::new();
1034+
if let Some(in_list) = conjunct.downcast_ref::<InListExpr>() {
1035+
if in_list.negated() {
1036+
// `NOT IN` selects the complement, which is usually most of the
1037+
// column, and is left to the default rather than guessed at.
1038+
return None;
1039+
}
1040+
column = Some(in_list.expr().downcast_ref::<Column>()?);
1041+
for value in in_list.list() {
1042+
values.insert(value.downcast_ref::<Literal>()?.value().clone());
1043+
}
1044+
} else {
1045+
// Only a disjunction, so that a plain `col = literal` keeps whatever
1046+
// estimate it gets today rather than being re-derived here.
1047+
let binary = conjunct.downcast_ref::<BinaryExpr>()?;
1048+
if *binary.op() != Operator::Or {
1049+
return None;
1050+
}
1051+
collect_or_equalities(conjunct, &mut column, &mut values)?;
1052+
}
1053+
1054+
let column = column?;
1055+
if values.len() < 2 {
1056+
return None;
1057+
}
1058+
let stats = column_statistics.get(column.index())?;
1059+
let distinct = *max_distinct_count(num_rows, stats).get_value()?;
1060+
if distinct == 0 {
1061+
return None;
1062+
}
1063+
Some((values.len() as f64 / distinct as f64).min(1.0))
1064+
}
1065+
1066+
/// Collects the literals of an `OR` chain of equalities over a single column.
1067+
///
1068+
/// Returns `None` as soon as the expression is anything else, so a mixed
1069+
/// disjunction such as `a = 1 OR b = 2` is not mistaken for a list.
1070+
fn collect_or_equalities<'a>(
1071+
expr: &'a Arc<dyn PhysicalExpr>,
1072+
column: &mut Option<&'a Column>,
1073+
values: &mut HashSet<ScalarValue>,
1074+
) -> Option<()> {
1075+
let binary = expr.downcast_ref::<BinaryExpr>()?;
1076+
match binary.op() {
1077+
Operator::Or => {
1078+
collect_or_equalities(binary.left(), column, values)?;
1079+
collect_or_equalities(binary.right(), column, values)
1080+
}
1081+
Operator::Eq => {
1082+
let (found, literal) = match (
1083+
binary.left().downcast_ref::<Column>(),
1084+
binary.right().downcast_ref::<Column>(),
1085+
) {
1086+
(Some(col), None) => (col, binary.right()),
1087+
(None, Some(col)) => (col, binary.left()),
1088+
_ => return None,
1089+
};
1090+
// Every equality has to constrain the same column, or the fraction
1091+
// below would not describe the conjunct.
1092+
if column.is_some_and(|current| current != found) {
1093+
return None;
1094+
}
1095+
*column = Some(found);
1096+
values.insert(literal.downcast_ref::<Literal>()?.value().clone());
1097+
Some(())
1098+
}
1099+
_ => None,
1100+
}
1101+
}
1102+
9621103
fn collect_equality_columns(predicate: &Arc<dyn PhysicalExpr>) -> (HashSet<usize>, bool) {
9631104
let mut eq_values: HashMap<usize, ScalarValue> = HashMap::new();
9641105
let mut infeasible = false;
@@ -2747,9 +2888,10 @@ mod tests {
27472888
Arc::new(Literal::new(ScalarValue::Utf8(Some("b".to_string())))),
27482889
)),
27492890
)),
2750-
// Input NDV is 50, but the 20% default selectivity on 100 rows
2751-
// estimates 20 output rows, so NDV is capped at 20.
2752-
vec![Precision::Inexact(20)],
2891+
// The two listed values are 2 of the column's 50, so 4 of the
2892+
// 100 input rows are expected and NDV is capped at 4. Still not
2893+
// collapsed to 1, which is what this case guards.
2894+
vec![Precision::Inexact(4)],
27532895
),
27542896
(
27552897
"AND with mixed types (Utf8 + Int32)",

‎datafusion/sqllogictest/test_files/join.slt.part‎

Lines changed: 7 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -934,10 +934,12 @@ logical_plan
934934
05)--SubqueryAlias: d
935935
06)----TableScan: department projection=[dept_name]
936936
physical_plan
937-
01)CrossJoinExec
938-
02)--FilterExec: name@1 = Alice OR name@1 = Bob
937+
01)ProjectionExec: expr=[emp_id@1 as emp_id, name@2 as name, dept_name@0 as dept_name]
938+
02)--CrossJoinExec
939939
03)----DataSourceExec: partitions=1, partition_sizes=[1]
940-
04)--DataSourceExec: partitions=1, partition_sizes=[1]
940+
04)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
941+
05)------FilterExec: name@1 = Alice OR name@1 = Bob
942+
06)--------DataSourceExec: partitions=1, partition_sizes=[1]
941943

942944
# expect no row for Carol
943945
query ITT
@@ -947,10 +949,10 @@ JOIN department AS d
947949
ON (e.name = 'Alice' OR e.name = 'Bob');
948950
----
949951
1 Alice HR
950-
1 Alice Engineering
951-
1 Alice Sales
952952
2 Bob HR
953+
1 Alice Engineering
953954
2 Bob Engineering
955+
1 Alice Sales
954956
2 Bob Sales
955957

956958
# OR conditions on Filter (not join filter)

0 commit comments

Comments
 (0)