apache / apache/datafusion

EPIC: Making use of NDVs (number of distinct values) in DataFusion

Open
#20,766 7 comments 0 reactions 0 assignees View on GitHub
enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.