apache / apache/datafusion

Use exponential decay for multi-column join selectivity estimation

Open
#21,583 0 comments 0 reactions 0 assignees View on GitHub
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.