You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "korowa (via GitHub)" <gi...@apache.org> on 2024/03/25 21:17:41 UTC
[PR] fix: semi/anti join output statistics [arrow-datafusion]
korowa opened a new pull request, #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
Closes #.
## Rationale for this change
<!--
Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed.
Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes.
-->
While #9676 found that NLJoin input reordering in benchmarks doesn't happen if one of inputs is AntiJoin -- the reason is that output statistics for all Semi/Anti join types is always set as `Absent`. This PR propagates "outer" input statistics to Anti/Semi join output.
## What changes are included in this PR?
<!--
There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR.
-->
- "outer" input statistics for Anti/Semi join cases is now propagated as output statistics (worst case assumption -- filtering not occurs at all, an alternative might be either to use `default_filter_statistics` or use similar to regular joins algorithm based on estimated distinct values, which though could be misleading as it assumes that "all values from smaller side are present in larger side" -- not sure if it's fine for filter estimation)
- the only exception is disjoint inputs case -- if inputs statistics values are non-overlapping, the output cardinality will be estimated as zero
- avoid early returns on absent statistics value while non-overlapping statistics checks
## Are these changes tested?
<!--
We typically require tests for all PRs in order to:
1. Prevent the code from being accidentally broken by subsequent changes
2. Serve as another way to document the expected behavior of the code
If tests are not included in your PR, please explain why (for example, are they covered by existing tests)?
-->
Added test coverage for SemiJoin cardinality estimation
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
Execution plans containing Semi/Anti joins might change
<!--
If there are any breaking changes to public APIs, please add the `api change` label.
-->
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2026073276
> /benchmark
I think the SF 10 in-memory bench OOM-ed the run, so we should remove it for now.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#discussion_r1543497471
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -888,10 +888,45 @@ fn estimate_join_cardinality(
})
}
- JoinType::LeftSemi
- | JoinType::RightSemi
- | JoinType::LeftAnti
- | JoinType::RightAnti => None,
+ JoinType::LeftSemi | JoinType::LeftAnti => {
+ let cardinality = estimate_semi_join_cardinality(
Review Comment:
Indeed, they were not correct. I've changed estimations a bit -- now disjoint statistics affects only semi-joins (supposing that it's rather strong assumption, and filtered outer table will be zero), for anti-joins, disjoint inputs don't seem to make much sense -- if statistics are non-overlapping -- the result will be equal to outer num_rows side, otherwilse (having no info/some statistics overlapping) -- it still will be estimated as outer side.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2025451049
/benchmark
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021230240
On the other side, as far as I understand, at this moment this benchmarking is aimed to detect larger scale performance regressions like x3+ (while default benchmark report has 5% diff threshold as "no change")
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021187728
> Checked on the fork ([1](https://github.com/korowa/arrow-datafusion/pull/171#issuecomment-2021147381) and [2](https://github.com/korowa/arrow-datafusion/pull/171#issuecomment-2021165595)) for the same base/PR commits -- the results don't seem to be reliable
Yes, it seems not too reliable at the moment unfortunately. Based on that, seems there is no significant difference.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "gruuya (via GitHub)" <gi...@apache.org>.
gruuya commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2027400317
> # Benchmark results
> Benchmarks comparing [179179c](https://github.com/apache/arrow-datafusion/commit/179179c0b719a7f9e33d138ab728fdc2b0e1e1d8) (main) and [9bd30ea](https://github.com/apache/arrow-datafusion/commit/9bd30ea74264feec521a6b740261cfaecfc19e43) (PR)
>
> ```
> Comparing 179179c and 9bd30ea
> Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_mem_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_mem_sf1.json does not exist
> Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf1.json does not exist
> Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf10.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf10.json does not exist
> ```
So what seem to have happened here is that the step benchmarking the PR changes uses it's version of the `benchmarks/bench.sh` file, and that is different from the one on main now due to this https://github.com/apache/arrow-datafusion/blob/179179c0b719a7f9e33d138ab728fdc2b0e1e1d8/benchmarks/bench.sh#L317
I needed to add a distinction between the results since previously SF1/SF10 would overwrite the same file.
So the resolution is just to rebase on/merge from main and re-run the benches again. ๐
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2027389085
# Benchmark results
<details>
<summary>Benchmarks comparing 179179c0b719a7f9e33d138ab728fdc2b0e1e1d8 (main) and 9bd30ea74264feec521a6b740261cfaecfc19e43 (PR)</summary>
```
Comparing 179179c and 9bd30ea
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_mem_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_mem_sf1.json does not exist
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf1.json does not exist
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf10.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf10.json does not exist
```
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021220084
Probably this is the case described [here](https://github.com/apache/arrow-datafusion/pull/9461#pullrequestreview-1926263842) as a concern regarding GH runners.
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2028848371
> What do you think about trying to extract the cost models (e.g. cardinality estimation) into some API?
@alamb, I don't have any strong opinion here (probably I'm lacking knowledge of usecases for this), and if I got the idea right -- on one side it might help by adding versatility to DF usage (there is already available, AFAIU, an option to customize physical optimizer, and this API should allow to reuse optimizer with custom cost model), but on the other side, if end goal is an (extensible/customizable) API, providing data required for physical plan optimization, I'm not sure that statistics estimation API will be enough, as there are more attributes affecting phyiscal plan significantly (e.g. partitioning and ordering related attributes), and as a result, to provide all required inputs random external planner needs, we may end up with +- same `ExecutionPlan`.
Maybe it'll be better to start with internal estimator API (maybe not "API", but just set of functions, like we have now across multiple various utility-files, but better organized), and, for now, provide statistics through operators (as it's working right now) using this utility functional?
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021195715
# Benchmark results
<details>
<summary>Benchmarks comparing 39f4aaf5cd1abfc9204c3eb96effdb4ebcf5b882 (main) and 29f1cca2f12236fba1b69b130df57f23e7818f8e (PR)</summary>
```
Comparing 39f4aaf and 29f1cca
--------------------
Benchmark tpch.json
--------------------
โโโโโโโโโโโโโโโโณโโโโโโโโโโโณโโโโโโโโโโโณโโโโโโโโโโโโโโโ
โ Query โ 39f4aaf โ 29f1cca โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 446.24ms โ 505.53ms โ 1.13x slower โ
โ QQuery 2 โ 58.17ms โ 77.06ms โ 1.32x slower โ
โ QQuery 3 โ 148.50ms โ 151.10ms โ no change โ
โ QQuery 4 โ 89.58ms โ 90.13ms โ no change โ
โ QQuery 5 โ 204.90ms โ 209.82ms โ no change โ
โ QQuery 6 โ 110.61ms โ 109.62ms โ no change โ
โ QQuery 7 โ 281.84ms โ 293.58ms โ no change โ
โ QQuery 8 โ 194.27ms โ 203.05ms โ no change โ
โ QQuery 9 โ 319.48ms โ 312.89ms โ no change โ
โ QQuery 10 โ 249.44ms โ 245.80ms โ no change โ
โ QQuery 11 โ 62.59ms โ 63.01ms โ no change โ
โ QQuery 12 โ 127.26ms โ 127.85ms โ no change โ
โ QQuery 13 โ 181.71ms โ 191.56ms โ 1.05x slower โ
โ QQuery 14 โ 132.04ms โ 132.48ms โ no change โ
โ QQuery 15 โ 212.20ms โ 209.90ms โ no change โ
โ QQuery 16 โ 51.83ms โ 51.61ms โ no change โ
โ QQuery 17 โ 326.16ms โ 350.28ms โ 1.07x slower โ
โ QQuery 18 โ 451.92ms โ 482.47ms โ 1.07x slower โ
โ QQuery 19 โ 236.19ms โ 237.95ms โ no change โ
โ QQuery 20 โ 191.50ms โ 199.72ms โ no change โ
โ QQuery 21 โ 326.33ms โ 329.98ms โ no change โ
โ QQuery 22 โ 54.79ms โ 53.14ms โ no change โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโดโโโโโโโโโโโดโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (39f4aaf) โ 4457.57ms โ
โ Total Time (29f1cca) โ 4628.56ms โ
โ Average Time (39f4aaf) โ 202.62ms โ
โ Average Time (29f1cca) โ 210.39ms โ
โ Queries Faster โ 0 โ
โ Queries Slower โ 5 โ
โ Queries with No Change โ 17 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโ
```
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2024090215
Just to aid the discussions on benchmark variance, let's try and run the newer version once more
/benchmark
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2019592540
# Benchmark results
<details>
<summary>Benchmarks comparing 349c586ea7c680c802f36c750e5f1e2dc7beb65b (main) and 29f1cca2f12236fba1b69b130df57f23e7818f8e (PR)</summary>
```
Comparing 349c586 and 29f1cca
--------------------
Benchmark tpch.json
--------------------
โโโโโโโโโโโโโโโโณโโโโโโโโโโโณโโโโโโโโโโโณโโโโโโโโโโโโโโโ
โ Query โ 349c586 โ 29f1cca โ Change โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ QQuery 1 โ 442.56ms โ 447.23ms โ no change โ
โ QQuery 2 โ 57.74ms โ 58.90ms โ no change โ
โ QQuery 3 โ 145.56ms โ 149.88ms โ no change โ
โ QQuery 4 โ 89.29ms โ 121.83ms โ 1.36x slower โ
โ QQuery 5 โ 201.46ms โ 247.68ms โ 1.23x slower โ
โ QQuery 6 โ 105.37ms โ 110.09ms โ no change โ
โ QQuery 7 โ 284.15ms โ 291.72ms โ no change โ
โ QQuery 8 โ 198.73ms โ 202.66ms โ no change โ
โ QQuery 9 โ 310.13ms โ 313.32ms โ no change โ
โ QQuery 10 โ 234.28ms โ 251.45ms โ 1.07x slower โ
โ QQuery 11 โ 62.78ms โ 64.24ms โ no change โ
โ QQuery 12 โ 129.96ms โ 130.64ms โ no change โ
โ QQuery 13 โ 177.83ms โ 187.69ms โ 1.06x slower โ
โ QQuery 14 โ 128.79ms โ 135.48ms โ 1.05x slower โ
โ QQuery 15 โ 192.30ms โ 197.11ms โ no change โ
โ QQuery 16 โ 52.21ms โ 51.71ms โ no change โ
โ QQuery 17 โ 313.30ms โ 328.26ms โ no change โ
โ QQuery 18 โ 455.63ms โ 469.28ms โ no change โ
โ QQuery 19 โ 236.01ms โ 237.34ms โ no change โ
โ QQuery 20 โ 194.17ms โ 202.15ms โ no change โ
โ QQuery 21 โ 335.41ms โ 334.95ms โ no change โ
โ QQuery 22 โ 54.90ms โ 55.99ms โ no change โ
โโโโโโโโโโโโโโโโดโโโโโโโโโโโดโโโโโโโโโโโดโโโโโโโโโโโโโโโ
โโโโโโโโโโโโโโโโโโโโโโโโโโณโโโโโโโโโโโโ
โ Benchmark Summary โ โ
โกโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโฉ
โ Total Time (349c586) โ 4402.55ms โ
โ Total Time (29f1cca) โ 4589.59ms โ
โ Average Time (349c586) โ 200.12ms โ
โ Average Time (29f1cca) โ 208.62ms โ
โ Queries Faster โ 0 โ
โ Queries Slower โ 5 โ
โ Queries with No Change โ 17 โ
โโโโโโโโโโโโโโโโโโโโโโโโโโดโโโโโโโโโโโโ
```
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021203848
Queries running slower seem inconsistent again :)
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021172463
Checked on the fork ([1](https://github.com/korowa/arrow-datafusion/pull/171#issuecomment-2021147381) and [2](https://github.com/korowa/arrow-datafusion/pull/171#issuecomment-2021165595)) for the same base/PR commits -- the results don't seem to be reliable
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2027429235
# Benchmark results
<details>
<summary>Benchmarks comparing 179179c0b719a7f9e33d138ab728fdc2b0e1e1d8 (main) and 9bd30ea74264feec521a6b740261cfaecfc19e43 (PR)</summary>
```
Comparing 179179c and 9bd30ea
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_mem_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_mem_sf1.json does not exist
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf1.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf1.json does not exist
Note: Skipping /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/179179c/tpch_sf10.json as /home/runner/work/arrow-datafusion/arrow-datafusion/benchmarks/results/9bd30ea/tpch_sf10.json does not exist
```
</details>
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "korowa (via GitHub)" <gi...@apache.org>.
korowa commented on code in PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#discussion_r1543497471
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -888,10 +888,45 @@ fn estimate_join_cardinality(
})
}
- JoinType::LeftSemi
- | JoinType::RightSemi
- | JoinType::LeftAnti
- | JoinType::RightAnti => None,
+ JoinType::LeftSemi | JoinType::LeftAnti => {
+ let cardinality = estimate_semi_join_cardinality(
Review Comment:
Indeed, they were not correct. I've changed estimations a bit -- now disjoint statistics affects only semi-joins (filtering outer table should produce zero rows). For anti-joins, disjoint inputs don't seem to make much sense -- if statistics are non-overlapping the result will be equal to outer num_rows side, otherwise (having no info or overlapping statistics) -- it still will be estimated as outer side, since we know nothing about actual distribution besides min/max, and assuming that all rows will be filtered out is too much (may significantly affect further planning)
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2027357566
/benchmark
Final one
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2019565943
/benchmark
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2032797206
๐ค In my mind the way a cost based optimizer (CBO) typically works is that there are:
1. A set of heuristics that take things like partitioning/ordering into account to create potential plans (with potentially different join orders)
2. A cost model that is then used to pick between the potential plans
I was thinking if we could decouple the "make some potential plans" and "what would it cost to run this query" parts, we could let people implement their own cost based optimizer (and we could pull the basic cardinality estimation code into the "build in" cost model)
I don't have time to pursue the idea much now
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2027355532
> What do you think about trying to extract the cost models (e.g. cardinality estimation) into some API? For example
TO be clear this is a suggestion for some other potential future PR, not this one
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Implement semi/anti join output statistics estimation [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#discussion_r1541124956
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -968,6 +991,78 @@ fn estimate_inner_join_cardinality(
}
}
+/// Estimates semi join cardinality based on statistics.
+///
+/// The estimation result is either zero, in cases inputs statistics are non-overlapping
+/// or equal to number of rows for outer input.
+fn estimate_semi_join_cardinality(
Review Comment:
Long term it would be really nice to pull these types of calculations into some trait (aka an extensibility API)
##########
datafusion/physical-plan/src/joins/utils.rs:
##########
@@ -888,10 +888,45 @@ fn estimate_join_cardinality(
})
}
- JoinType::LeftSemi
- | JoinType::RightSemi
- | JoinType::LeftAnti
- | JoinType::RightAnti => None,
+ JoinType::LeftSemi | JoinType::LeftAnti => {
+ let cardinality = estimate_semi_join_cardinality(
Review Comment:
it doesn't seem correct to me that the same calculation is used for both Semi and Anti joins (shouldn't they be the inverse of each other?)
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] fix: semi/anti join output statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #9800:
URL: https://github.com/apache/arrow-datafusion/pull/9800#issuecomment-2021176628
/benchmark
--
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@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org