You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "andygrove (via GitHub)" <gi...@apache.org> on 2023/11/10 16:31:09 UTC
[PR] WIP: Fix join order for TPCH Q17 [arrow-datafusion]
andygrove opened a new pull request, #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126
…nality
## 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 https://github.com/apache/arrow-datafusion/issues/7949
## 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.
-->
Improve benchmark results
## 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.
-->
This PR changes the behavior of `FilterExec:statistics` in the case where we are unable to determine accurate statistics. Rather then return num_rows as `Precision::Absent`, we now assume that the filter is highly selective (worst case scenario) and return the input statistics.
## 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)?
-->
I have confirmed an improved join order for TPCH Q17 and am now running the full benchmark comparision.
## Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
No
<!--
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] Fix join order for TPCH Q17 [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1389924893
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
This is an interesting idea. Since statistics will be `Inexact`, it should never result in an incorrect output, but may improve average-case complexity.
--
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 join order for TPCH Q17 [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1389869661
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
I wonder if we can make a slightly different assumption that is a better metric, e.g. each filter returning 50% or 20% of input rows?
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1808238377
I am surprised no test needed changing after this PR. How will we ensure future statistics changes don't mess up the TPCH plans 🤔
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1808244829
BTW when statistics support range estimates, we will not need to hardcode any assumption like 20% within how the operator reports the statistics. In this specific example, the filter would say it could be anything between 0 and the incoming number of rows, which is accurate. The logic that consumes these stats is now free to make any heuristic assumptions it wants to make on top of this information.
--
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 join order for TPCH Q17 [arrow-datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1389924479
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
We could add a configuration option to control the default selectivity. I'll take a look.
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1807058116
Thanks @andygrove impressive results with a small 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 join order for TPCH Q17 [arrow-datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1390040161
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
The talk [Join Order Optimization with (almost) no Statistics](https://www.youtube.com/watch?v=aNRoR0Z3SzU) is focused on full join reordering rather than just choosing the build side of a join but talks about selectivity estimates and is very relevant to this discussion. They found that selectivity of 0.2 worked well with TPC-H.
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1808275984
> > I am surprised no test needed changing after this PR. How will we ensure future statistics changes don't mess up the TPCH plans 🤔
>
> Was surprised as well and checked why, it is because the tests use CSV rather than Parquet.
Maybe we can create a test with some sort of 'statistics only' with the statistics from the parquet files, but that doesn't need the actual data and verify the plan that way.
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1808269567
> I am surprised no test needed changing after this PR. How will we ensure future statistics changes don't mess up the TPCH plans 🤔
Was surprisesd as well and checked why, it is because the tests use CSV rather than Parquet.
--
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 join order for TPCH Q17 [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1389867777
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
Review Comment:
```suggestion
// assume worst case, that the filter is highly unselective and
```
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1390274643
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,19 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume filter selects 20% of rows if we cannot do anything smarter
+ // tracking issue for making this configurable:
+ // https://github.com/apache/arrow-datafusion/issues/8133
+ let selectivity = 0.2_f32;
+ let mut stats = input_stats.clone().into_inexact();
+ if let Precision::Inexact(n) = stats.num_rows {
+ stats.num_rows = Precision::Inexact((selectivity * n as f32) as usize);
Review Comment:
I think we can/should do the same for the `total_byte_size` value
--
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 join order for TPCH Q17 & q18 [arrow-datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1390252617
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
I pushed a change to use 0.2 as the default, and now Q18 has an improved join order as well. I updated the results in the PR description.
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "Dandandan (via GitHub)" <gi...@apache.org>.
Dandandan merged PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126
--
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 join order for TPCH Q17 [arrow-datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1806270941
@berkaysynnada Could you take a look and make sure this looks sensible?
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "ozankabak (via GitHub)" <gi...@apache.org>.
ozankabak commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1807075567
Once the type `Precision` is extended to support range estimates in addition to point estimates, we will be able to do much more. This small change demonstrates the potential of a good statistics infrastructure really well. Thanks @andygrove
--
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 join order for TPCH Q17 [arrow-datafusion]
Posted by "andygrove (via GitHub)" <gi...@apache.org>.
andygrove commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1390004784
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
It looks like making this configurable will be a larger change. I filed https://github.com/apache/arrow-datafusion/issues/8133 and linked to it from the comment here.
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#discussion_r1391219185
##########
datafusion/physical-plan/src/filter.rs:
##########
@@ -194,11 +194,13 @@ impl ExecutionPlan for FilterExec {
fn statistics(&self) -> Result<Statistics> {
let predicate = self.predicate();
+ let input_stats = self.input.statistics()?;
let schema = self.schema();
if !check_support(predicate, &schema) {
- return Ok(Statistics::new_unknown(&schema));
+ // assume worst case, that the filter is highly selective and
+ // returns all the rows from its input
+ return Ok(input_stats.clone().into_inexact());
Review Comment:
Default selectivities / cost estimates work ok for TPCH queries where the data is relatively uniformly distributed.
However, in general in my experience they tend to cause problems when the data is skewed or has correlations between the columns.
Hopefully we'll be able to keep the number of hard coded constants / assumptions low in DataFusion (so there are fewer things for the optimizer to get wrong :) )
--
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 join order for TPCH Q17 & Q18 by improving FilterExec statistics [arrow-datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #8126:
URL: https://github.com/apache/arrow-datafusion/pull/8126#issuecomment-1808236841
cc @NGA-TRAN
--
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