Repository navigation
Commit 02b7149
authored
fix: use NDV for unresolved scalar subquery selectivity instead of 20% fallback (apache#25719)
## Which issue does this PR close?
Closes apache#25623.
Part of apache#25610.
## Rationale for this change
When estimating output statistics for a `FilterExec`, DataFusion
attempts interval analysis via `check_support`. If interval analysis is
unsupported for a predicate—most notably equality against an unresolved
scalar subquery (`WHERE col = (SELECT ...)`), or unsupported column
types such as `Utf8`—interval estimation cannot proceed and selectivity
falls back to an unconditional `default_selectivity` (20%).
In real-world workloads such as TPC-DS Q6, this blanket 20% fallback
causes severe cardinality misestimates:
- Filtering against a scalar subquery on a high-cardinality column (e.g.
`d_month_seq` with NDV ~2,400 out of 73,049 rows) estimates ~14,610 rows
instead of ~30 rows.
- For low-cardinality columns (e.g. NDV = 2), estimated selectivity is
0.20 instead of 0.50.
These inflated or deflated row counts propagate up the physical
execution plan, leading to suboptimal join ordering and incorrect
build/probe side selection.
## What changes are included in this PR?
- **`compute_fallback_selectivity` in `filter.rs`**: When
`check_support` evaluates to false, conjunctions are split to inspect
equality predicates:
- Extracts column NDV for `col = expr` and `expr = col` symmetrically.
- For column-to-column equalities (`col_a = col_b`), computes `1.0 /
max(NDV(a), NDV(b))` when distinct counts are known for both columns,
avoiding operand-order bias.
- Any remaining unhandled conjuncts (such as inequalities or columns
lacking statistics) apply `default_selectivity` at most once across the
combined unhandled set, preventing exponential underestimation.
- Retains existing behavior when no distinct counts are available or
when all conjuncts remain unhandled.
## What is the testing strategy for this PR?
Unit and execution plan statistics tests in
`datafusion/physical-plan/src/filter.rs`:
1. **`FilterExec` Plan Statistics**:
- `test_filter_statistics_fallback_scalar_subquery_uses_ndv`: Asserts
that an unresolved `ScalarSubqueryExpr` equality (`a =
<ScalarSubqueryExpr>`) uses `1 / NDV` rather than the 20% default.
- `test_filter_statistics_fallback_cast_scalar_subquery_uses_default`:
Verifies `CAST(a AS Int64) = <ScalarSubqueryExpr>` falls back to default
selectivity since casts are not unwrapped for NDV.
- `test_filter_statistics_fallback_uses_ndv_for_unsupported_predicate`:
Confirms `Utf8` equality (`name = 'alice'`), which fails
`check_support`, correctly estimates via `1 / NDV`.
2. **`compute_fallback_selectivity` Unit Tests**:
- `test_fallback_selectivity_single_handled_equality`: Checks single
equality against a column with NDV.
- `test_fallback_selectivity_col_eq_col_uses_max_ndv`: Exercises `col_a
= col_b` verifying both left-dominates and right-dominates ordering.
- `test_fallback_selectivity_right_col_uses_ndv`: Validates `<expr> =
col` operand symmetry.
- `test_fallback_selectivity_multiple_unhandled_conjuncts`: Confirms
multiple unhandled conjuncts apply default selectivity only once.
- `test_fallback_selectivity_mixed_handled_and_unhandled`: Confirms
handled equality multiplies cleanly with single unhandled default.
- `test_fallback_selectivity_ndv_zero_falls_back_to_default`,
`test_fallback_selectivity_col_eq_col_no_ndv_falls_back_to_default`, and
`test_fallback_selectivity_missing_column_statistics`: Verifies graceful
fallback when statistics are missing or zero.
## Are there any user-facing changes?
No public API changes. Queries with equality filters on unsupported
types or unresolved scalar subqueries will produce more accurate plan
row-count estimates when NDV statistics are present.1 parent acbad14 commit 02b7149
1 file changed
Lines changed: 479 additions & 3 deletions
0 commit comments