DataFusion not using NDV stat

[LiaCastaneda]

Describe the bug

This was brought up before here #15265
From the top of my head my I think we could use these in:

• Join swapping strategy
• Optimal number of partitions in Hash Join partitioning where we use Hash Partitioning.
• Filter pushdown decision: if we have an very low NDV it might not be worth pushing down // computing predicates?

This would likely require further investigation into how other query engines use NDV for optimization decisions 🤔

To Reproduce

No response

Expected behavior

ndv being used

Additional context

No response

[asolimando]

NDV is also generally used for aggregation pushdown, as it helps understanding how the the number of groups relates with the number of tuples, ranging from the case where you group over a primary key (#tuple = #groups) to grouping over a single valued column (#groups = 1).

Roughly #groups(c) = NDV(c), where c is a column (some form of interpolation is needed for multi-columns group-by, starting from individual NDVs for the given columns).

#11627 introduced a runtime optimization to this effect, skipping the partial aggregation when it doesn't see enough reduction, as you would end up doing the same work twice.

It would indeed be nice to have the planner make use of NDV to improve the plan.

(this seems more an enhancement than a bug, as it's a missed opportunity but it doesn't affect correctness)

[asolimando]

Another place where NDV would help is dynamic filtering, as the NDV of the join columns the size of the filter (hashmap/in list) is proportional to that, and same goes for the estimated selectivity on the probe side. This could help decide if it interesting or not to activate dynamic filtering for a given join, which is not available at the moment IIRC (we are in a "all-or-nothing" setting).

[asolimando]

Thinking of aggregation and repartitioning, NDV could also help estimating data skewness: the average load per key is #tuples / NDV(c). If this value is higher than a threshold (usually >> 1 could be a sensible criterion), round-robin is better than hash-repartitioning(c) as one key would get too much data. Salting could be used as a refinement, but that's a simple case to add on top of the others.

You mentioned join ordering, but also the join selection algorithm could benefit from NDV: if the build side of a hash join has a high NDV, it might be better to go with a nested-loop join or a sort-merge join (depending on the sorting properties of the input operators).