Repository navigation
DataFusion not using NDV stat #18628
Description
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
Reacted by xudong.w
Activity
asolimando commentedon Nov 13, 2025
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), wherecis 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 commentedon Nov 14, 2025
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 commentedon Nov 14, 2025
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>> 1could be a sensible criterion),round-robinis better thanhash-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).
feat: Extract NDV (distinct_count) statistics from Parquet metadata (#…
feat: Extract NDV (distinct_count) statistics from Parquet metadata (a…
feat: Extract NDV (distinct_count) statistics from Parquet metadata (a…