Re: [I] Use exponential decay for multi-column join selectivity estimation [datafusion]

["gabotechs (via GitHub)" <gi...@apache.org>]

gabotechs commented on issue #21583:
URL: https://github.com/apache/datafusion/issues/21583#issuecomment-5778926953

   A reduced TPC-H SF1 reproducer for this issue, tracked in #25610.
   
   ## Describe the bug
   
   A partsupp–lineitem composite-key join overestimates output fourfold despite
   exact input row counts. The estimator uses only the strongest equality key’s
   selectivity.
   
   ## To Reproduce
   
   From the repository root, with the CLI fix from
   [PR #25570](https://github.com/apache/datafusion/pull/25570) applied:
   
   ```sh
   cargo build --profile ci --locked -p datafusion-benchmarks --bin dfbench
   cargo install tpchgen-cli --version 1.1.1 --locked # if not already installed
   repro_dir=$(mktemp -d)
   tpchgen-cli --scale-factor 1 --format parquet \
     --parquet-compression 'ZSTD(1)' --parts 1 --output-dir "$repro_dir/data"
   cat > "$repro_dir/repro.sql" <<'SQL'
   SET datafusion.execution.target_partitions = 1;
   SET datafusion.optimizer.enable_dynamic_filter_pushdown = false;
   SELECT l_orderkey FROM partsupp JOIN lineitem ON ps_partkey = l_partkey AND ps_suppkey = l_suppkey;
   SQL
   target/ci/dfbench statistics \
     --path "$repro_dir/data" --query_path "$repro_dir/repro.sql"
   ```
   
   Observed with `tpchgen-cli` 1.1.1 at
   [6c320561b5](https://github.com/apache/datafusion/commit/6c320561b5b1aef7a235a12435c3c96b62956c67).
   Inspect the SELECT reports; ignore the empty `SET` reports.
   
   | Operator     | Node | Estimated rows | Actual rows |
   | ------------ | ---- | -------------: | ----------: |
   | HashJoinExec | `0`  |     24,004,860 |   6,001,215 |
   
   ## Expected behavior
   
   Account for additional keys using a correlation-aware rule, multi-column NDVs or
   composite constraints. Blindly multiplying selectivities can underestimate
   correlated keys.
   
   ## Additional context
   
   Input row counts are 800,000 partsupp rows and 6,001,215 lineitems.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org