apache / apache/datafusion

Never fallback to cartesian product for join estimation when we know the min/max values for columns

Open
#3,813 1 comment 0 reactions 0 assignees View on GitHub
enhancement
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? Please describe what you are trying to do.**
`distinct_count` is usually expensive to compute, so some platforms which save parquet files abstain from injecting it at the metadata section. We should be able to estimate the join cardinality without it before falling back to cartesian product.

**Describe the solution you'd like**
Since we already require min/max values to be present, we should be able to just do `min(num_left_rows - num_nulls or 0, scalar_range(left_stats.min, left_stats.max))` to determine an alternative distinct count.

**Describe alternatives you've considered**
None.

**Additional context**
Original discussion was here https://github.com/apache/arrow-datafusion/pull/3787#discussion_r992751749

Contributor guide

Open the contributing guide

Research direction

Start by reading the join cardinality estimation logic and the linked discussion from pull request 3787. Trace how min/max column metadata and null counts are used when distinct_count is absent; done means estimates use the available range information instead of falling back to a cartesian product.

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
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.