englefly opened a new pull request, #69817:
URL: https://github.com/apache/doris/pull/69817
### What problem does this PR solve?
Issue Number: N/A
Related PR: N/A
Problem Summary:
`FilterEstimation` reduces the row count of the estimated `Statistics` for
every conjunct, but the
null counts of the columns were only clamped to the new row count instead of
being scaled with it.
The column statistics then no longer matched the row count they were
combined with, and predicates
that estimate from the absolute null count produced wrong results.
Concrete plan (TPCDS store_sales, 28.8B rows): both `ss_customer_sk` and
`ss_sold_date_sk` have
about 4.5% nulls (1,296,000,270 and 1,296,010,052). For
ss_customer_sk is null and not (ss_sold_date_sk is null)
`visitIsNull` estimates the first conjunct as 1,296,000,270 rows (`visitAnd`
then clamps
`ss_sold_date_sk.numNulls` to `rowCount - ndv` = 1,295,998,441), and
`visitNot` estimates the second
conjunct as `rowCount - numNulls` = 1,296,000,270 - 1,295,998,441 = 1829,
i.e. exactly the NDV of
`ss_sold_date_sk`. The filter was estimated to output 1829 rows instead of
about 1.24B rows, which
made the join build the 648M-row side and capped the runtime filter NDV at
1829.
The same inconsistency made a following `is null` predicate use the
base-table null count after an
`in`, a `not`, a `like` or a column-to-column comparison had already reduced
the row count: for
example `a in (1..10) and b is null` was estimated 10x too large.
Fix: scale the null counts of the other columns with the selectivity of the
predicate whenever it
reduces the row count. It is applied to `visitIsNull` (including the
unknown-stats path),
`visitInPredicate` (including the unknown-stats path), `visitNot`,
`visitLike`,
`estimateColumnEqualToColumn`, `estimateColumnLessThanColumn` and the
default/unknown selectivity
paths. The two `visitOr` calls that normalized the children a second time
are removed, because the
children already return statistics consistent with their own row count. The
scaled statistics keep
`numNulls` consistent with `Statistics.rowCount`, so predicates that combine
a null count with the
row count (is-null, not, not-in, not-null selectivity) no longer cancel each
other.
The `Statistics.normalizeColumnStatistics(inputRowCount, boolean)` API is
split into
`enforceValid()` and `rescaleNumNulls(inputRowCount)`: the boolean was easy
to get wrong (the two
modes differ only in whether the null counts are rescaled, and
`inputRowCount` was unused when the
flag was false). `enforceValid` only clamps invalid `ndv`/`numNulls` and is
used after an operator
or a predicate has finished estimating (filter/join/scan/agg);
`rescaleNumNulls` scales the null
counts by `rowCount / inputRowCount` and is used where a predicate just
reduced the row count.
### Release note
None
### Check List (For Author)
- Test: Unit Test
- `FilterEstimationTest#testIsNullAndIsNotNull` reproduces the TPCDS
numbers above: without the
fix the filter is estimated to output 1829 rows, with the fix
1,237,679,772 rows.
- `FilterEstimationTest#testInPredicateScalesNumNulls`,
`#testNotPredicateScalesNumNulls`, `#testLikePredicateScalesNumNulls`
and
`#testColumnToColumnScalesNumNulls` verify that the null count is
scaled by the predicate
selectivity; without the fix the following `is null` predicate is 10x
too large.
- `StatisticsTest#testEnforceValid` and `#testRescaleNumNulls` cover the
split API.
- `FilterEstimationTest` (69), `ExpressionEstimationTest` (17),
`JoinEstimateTest` (3),
`StatsCalculatorTest` (20), `MemoStatsAndCostRecomputerTest` (12) and
`StatisticsTest` (3)
pass, 124 tests in total.
- checkstyle passes.
- `shape_check/tpcds_sf100/shape` (98 suites) produces byte-identical
plan shapes on this
branch and on origin/master (the suite itself fails against the stale
in-repo goldens, which
predate the base commit and are unrelated to this change).
- Behavior changed: No (statistics estimation only)
- Does this need documentation: No
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
