Skip to content

Commit 02b7149

Browse files
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

File tree

0 commit comments

Comments
 (0)