EPIC: Making use of NDVs (number of distinct values) in DataFusion
- Dominant language
- Rust
- Stars
- 9.3k
- Forks
- 2.4k
- Avg merge
- 3d 7h
- Merged PRs (30d)
- 344
Description
### Is your feature request related to a problem or challenge?
In #15265 brings up that we do not really use NDVs or `distinct_count` anywhere in the code. However, it will become more practical after #19957 is merged.
An optimization that uses `distinct_count` can be shown here: https://github.com/apache/datafusion/pull/20731
Where NDV is currently used:
- `estimate_inner_join_cardinality` uses the same approach as spark's catalyst optimizer ([code](https://github.com/apache/datafusion/blob/4dbb4498fc92539e96993692f0263e74f557e20a/datafusion/physical-plan/src/joins/utils.rs#L590))
### Describe the solution you'd like
I looked into Trino/Spark and added a list of optimizations that can be made with this statistic:
- https://github.com/apache/datafusion/pull/20731
- https://github.com/apache/datafusion/pull/20789
- https://github.com/apache/datafusion/pull/20904
- https://github.com/apache/datafusion/pull/21077
- https://github.com/apache/datafusion/pull/21081
- HJ vs. SMJ
- https://github.com/apache/datafusion/pull/20926
- Multi-join column selectivity with decay
- Choose hash key with high NDV for better spread (maybe reject low NDV columns to avoid skew) - very good for distributed datafusion
- Possibly check at runtime whether partial aggregation is useful enough for reduction -> trino uses the formula, `NDV x 2 > input_rows`.
- Top k output cardinality estimates
- https://github.com/apache/datafusion/pull/20845
- https://github.com/apache/datafusion/pull/20846
- https://github.com/apache/datafusion/issues/20966
- https://github.com/apache/datafusion/pull/21077
- https://github.com/apache/datafusion/pull/21081
- https://github.com/apache/datafusion/issues/21109
- https://github.com/apache/datafusion/issues/21111
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Research direction
Start by reading estimate_inner_join_cardinality in datafusion/physical-plan/src/joins/utils.rs and the linked NDV-related pull requests. Choose one optimization from the list and define its scope from the corresponding PR or issue; done means that focused optimization is implemented and its associated validation is complete.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- data-engineering, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100