Use exponential decay for multi-column join selectivity estimation
- 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?
Current join cardinality estimation for multi-column equi-joins is too conservative.
When a join has several equality keys, the estimate mostly follows only the single strongest key. That means extra join predicates do not reduce the estimated output rows enough. This can overestimate join size and lead to weaker join planning decisions.
### Describe the solution you'd like
Use NDV-based exponential decay for multi-column join selectivity.
For an equi-join, compute one NDV factor per join key pair as:
`max(NDV(left_key), NDV(right_key))`
Then sort these factors from largest to smallest and combine them with decay:
`ndv0 * ndv1^(1/2) * ndv2^(1/4) * ndv3^(1/8) * ...`
Use that decayed value as the denominator for inner join cardinality estimation instead of using only the single largest NDV.
In practice, this would mean:
- collect the per-key NDV factors for all join keys
- sort them descending
- combine them with powers `1`, `1/2`, `1/4`, ...
- estimate rows as `left_num_rows * right_num_rows / decayed_ndv`
- keep the current disjoint-range short-circuit
- keep the current fallback behavior when NDV stats are missing
This should make multi-key join estimates tighter without being as aggressive as multiplying all key NDVs directly.
It would also be good to add tests for:
- single-key joins keeping the current behavior
- multi-key joins producing smaller estimates than the current largest-NDV-only rule
- missing NDV stats falling back cleanly
- disjoint join keys still producing zero where applicable
- join-key order not changing the estimate
### Describe alternatives you've considered
Keep the current largest-NDV-only rule.
This is simple, but it ignores useful information from the other join keys.
Multiply all join-key NDVs directly.
This is likely too aggressive and can under-estimate badly when keys are correlated.
Use histograms or stronger correlation models.
This could be more accurate, but it is a larger change and not needed for a first improvement.
### Additional context
Part of #20766.
Generated with Codex
Contributor guide
Research direction
The issue names no source file or test path; begin by locating the current multi-column equi-join cardinality estimator and its existing tests. Compare the current largest-NDV-only behavior with the requested decayed estimate, then verify single-key behavior, missing-stat fallbacks, disjoint ranges, and join-key order using focused tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- databases
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100