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

[jonathanc-n]

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: #20731

Where NDV is currently used:

• estimate_inner_join_cardinality uses the same approach as spark's catalyst optimizer (code)

Describe the solution you'd like

I looked into Trino/Spark and added a list of optimizations that can be made with this statistic:

• feat: Improve partition_statistics() for AggregateExec using distinct_count #20731
• feat: Use NDV for equality filter selectivity calculation #20789
• Semi/anti join selectivity calculations
• HJ vs. SMJ
• 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
• count(distinct col) can use distinct_count
• Propagate distinct_count through UNION

Describe alternatives you've considered

No response

Additional context

No response

[jonathanc-n]

cc @gabotechs @asolimando @xudong963 @gene-bordegaray @LiaCastaneda

[jonathanc-n]

Before #19957 merges, the issues for propagating NDV statistics can be done. Actual optimization decisions made using NDVs should be worked on afterwards.

[xudong963]

I'll have a look at #19957 first.

And the todo list in the issue makes sense to me. All of them will make datafusion smarter

[buraksenn]

Hi @jonathanc-n,

I'd be happy to help with some of the optimizations in the list. I saw relevant PRs and if there's something suitable, I’d be glad to take a look and try to tackle it.

[asolimando]

I am supportive of the initiative, I am actively working towards the same goal, better statistics for improving CBO (e.g., NDV for deciding HJ vs SMJ, is mentioned here), I plan to contribute some PRs and also review contributions from others to help them get merged.

If I can help in any other way, please let me know!