You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2022/12/05 20:52:21 UTC
[GitHub] [arrow-datafusion] isidentical opened a new pull request, #4519: Enrich filter statistics with known column boundaries
isidentical opened a new pull request, #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519
# Which issue does this PR close?
Closes #3845 .
# Rationale for this change
Allowing the propagation of column statistics in filter estimations theoretically unlocks all the parent estimations which in turn should benefit us greatly when dealing with nested joins.
# What changes are included in this PR?
The major change here is the new analysis context API which allows it to be attached with an expression boundaries alongside the information it already holds (column boundaries). With this in our hand, we can derive the column statistics for filter's result and all other use cases where the expression analysis used.
The initial design was around sharing a single `&mut Context` around and returning `ExprBoundaries` as we do now, but thanks to @alamb's suggestion on [my fork](https://github.com/isidentical/arrow-datafusion/pull/5#discussion_r1023180238) we can achieve a similar thing (albeit a bit more verbose) while still keeping the analysis process mut-free.
# 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)?
-->
Yes
# 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. This includes a break in the expression analysis API but it was specifically marked as experimental for stuff like this (it is currently evolving).
<!--
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
[GitHub] [arrow-datafusion] jackwener commented on a diff in pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
jackwener commented on code in PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#discussion_r1043520191
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -3109,13 +3173,16 @@ mod tests {
((Operator::GtEq, 200), (0.0, 1, 100)),
];
- for ((operator, rhs), (exp_selectivity, _, _)) in cases {
+ for ((operator, rhs), (exp_selectivity, exp_min, exp_max)) in cases {
let context = AnalysisContext::from_statistics(&schema, &statistics);
let left = col("a", &schema).unwrap();
let right = ScalarValue::Int64(Some(rhs));
- let boundaries =
- analyze_expr_scalar_comparison(&operator, &context, &left, right)
- .expect("this case should not return None");
+ let analysis_ctx =
+ analyze_expr_scalar_comparison(context, &operator, &left, right);
+ let boundaries = analysis_ctx
+ .clone()
+ .boundaries
Review Comment:
look like we can
```suggestion
.boundaries
.clone()
```
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -3109,13 +3173,16 @@ mod tests {
((Operator::GtEq, 200), (0.0, 1, 100)),
];
- for ((operator, rhs), (exp_selectivity, _, _)) in cases {
+ for ((operator, rhs), (exp_selectivity, exp_min, exp_max)) in cases {
let context = AnalysisContext::from_statistics(&schema, &statistics);
let left = col("a", &schema).unwrap();
let right = ScalarValue::Int64(Some(rhs));
- let boundaries =
- analyze_expr_scalar_comparison(&operator, &context, &left, right)
- .expect("this case should not return None");
+ let analysis_ctx =
+ analyze_expr_scalar_comparison(context, &operator, &left, right);
+ let boundaries = analysis_ctx
+ .clone()
+ .boundaries
Review Comment:
have saw @alamb has commented with similar comments below, his code is correct.
--
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
[GitHub] [arrow-datafusion] jackwener commented on pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
jackwener commented on PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#issuecomment-1342933432
A question that don't relate with this PR. Why Statistics save `total_byte_size` instead of `column_avg_byte_size`, the latter is generally what I see in other systems
--
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
[GitHub] [arrow-datafusion] alamb commented on pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#issuecomment-1340016112
I plan to review this carefully tomorrow morning
--
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
[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#discussion_r1042075509
##########
datafusion/core/src/physical_plan/filter.rs:
##########
@@ -502,6 +523,52 @@ mod tests {
Ok(())
}
+ #[tokio::test]
+ async fn test_filter_statistics_column_level_nested() -> Result<()> {
+ // Table:
+ // a: min=1, max=100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows: Some(100),
+ column_statistics: Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(1))),
+ max_value: Some(ScalarValue::Int32(Some(100))),
+ ..Default::default()
+ }]),
+ ..Default::default()
+ },
+ schema.clone(),
+ ));
+
+ // WHERE a <= 25
+ let sub_filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::LtEq, lit(25i32), &schema)?,
+ input,
+ )?);
+
+ // Nested filters (two separate physical plans, instead of AND chain in the expr)
+ // WHERE a >= 10
+ // WHERE a <= 25
+ let filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::GtEq, lit(10i32), &schema)?,
+ sub_filter,
+ )?);
+
+ let statistics = filter.statistics();
+ assert_eq!(statistics.num_rows, Some(16));
Review Comment:
👍 Nice test / demonstration
##########
datafusion/core/src/physical_plan/filter.rs:
##########
@@ -502,6 +523,52 @@ mod tests {
Ok(())
}
+ #[tokio::test]
+ async fn test_filter_statistics_column_level_nested() -> Result<()> {
+ // Table:
+ // a: min=1, max=100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows: Some(100),
+ column_statistics: Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(1))),
+ max_value: Some(ScalarValue::Int32(Some(100))),
+ ..Default::default()
+ }]),
+ ..Default::default()
+ },
+ schema.clone(),
+ ));
+
+ // WHERE a <= 25
+ let sub_filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::LtEq, lit(25i32), &schema)?,
+ input,
+ )?);
+
+ // Nested filters (two separate physical plans, instead of AND chain in the expr)
+ // WHERE a >= 10
+ // WHERE a <= 25
+ let filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::GtEq, lit(10i32), &schema)?,
+ sub_filter,
+ )?);
+
+ let statistics = filter.statistics();
+ assert_eq!(statistics.num_rows, Some(16));
+ assert_eq!(
+ statistics.column_statistics,
+ Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(10))),
+ max_value: Some(ScalarValue::Int32(Some(25))),
+ ..Default::default()
+ }])
+ );
+
+ Ok(())
+ }
+
Review Comment:
What would you think about adding a test showing multiple column boundaries, like
```
Filter (a <= 25)
Filter( b > 5)
Filter(a <= 20)
```
?
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -3178,13 +3253,16 @@ mod tests {
((Operator::GtEq, 50.7), (1.0 / distance, 50.7, 50.7)),
];
- for ((operator, rhs), (exp_selectivity, _, _)) in cases {
+ for ((operator, rhs), (exp_selectivity, exp_min, exp_max)) in cases {
let context = AnalysisContext::from_statistics(&schema, &statistics);
let left = col("a", &schema).unwrap();
let right = ScalarValue::from(rhs);
- let boundaries =
- analyze_expr_scalar_comparison(&operator, &context, &left, right)
- .expect("this case should not return None");
+ let analysis_ctx =
+ analyze_expr_scalar_comparison(context, &operator, &left, right);
+ let boundaries = analysis_ctx
+ .clone()
+ .boundaries
Review Comment:
It doesn't matter for the test, but you might be able to avoid this clone with something like
```suggestion
let boundaries = analysis_ctx
.boundaries
.as_ref()
```
##########
datafusion/physical-expr/src/expressions/binary.rs:
##########
@@ -704,12 +721,12 @@ impl PartialEq<dyn Any> for BinaryExpr {
// (on the right). The new boundaries will indicate whether it is always true, always
// false, or unknown (with a probablistic selectivity value attached).
Review Comment:
I wonder if these docstrings could/should be updated based on the changed signature
--
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
[GitHub] [arrow-datafusion] jackwener commented on pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
jackwener commented on PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#issuecomment-1339166285
I prepare to review in the later day. Thanks @isidentical .❤️
--
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
[GitHub] [arrow-datafusion] alamb merged pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
alamb merged PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519
--
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
[GitHub] [arrow-datafusion] isidentical commented on pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
isidentical commented on PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#issuecomment-1344760428
Thanks a lot for the reviews people (and sorry for the delay), added a new test and handled other suggestions so hopefully it should be good to go!
--
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
[GitHub] [arrow-datafusion] isidentical commented on a diff in pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#discussion_r1044827928
##########
datafusion/core/src/physical_plan/filter.rs:
##########
@@ -502,6 +523,52 @@ mod tests {
Ok(())
}
+ #[tokio::test]
+ async fn test_filter_statistics_column_level_nested() -> Result<()> {
+ // Table:
+ // a: min=1, max=100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows: Some(100),
+ column_statistics: Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(1))),
+ max_value: Some(ScalarValue::Int32(Some(100))),
+ ..Default::default()
+ }]),
+ ..Default::default()
+ },
+ schema.clone(),
+ ));
+
+ // WHERE a <= 25
+ let sub_filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::LtEq, lit(25i32), &schema)?,
+ input,
+ )?);
+
+ // Nested filters (two separate physical plans, instead of AND chain in the expr)
+ // WHERE a >= 10
+ // WHERE a <= 25
+ let filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::GtEq, lit(10i32), &schema)?,
+ sub_filter,
+ )?);
+
+ let statistics = filter.statistics();
+ assert_eq!(statistics.num_rows, Some(16));
+ assert_eq!(
+ statistics.column_statistics,
+ Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(10))),
+ max_value: Some(ScalarValue::Int32(Some(25))),
+ ..Default::default()
+ }])
+ );
+
+ Ok(())
+ }
+
Review Comment:
Great suggestion, pushed a test for it!
--
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
[GitHub] [arrow-datafusion] alamb commented on a diff in pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#discussion_r1045068803
##########
datafusion/core/src/physical_plan/filter.rs:
##########
@@ -494,6 +513,52 @@ mod tests {
Ok(())
}
+ #[tokio::test]
+ async fn test_filter_statistics_column_level_nested() -> Result<()> {
+ // Table:
+ // a: min=1, max=100
+ let schema = Schema::new(vec![Field::new("a", DataType::Int32, false)]);
+ let input = Arc::new(StatisticsExec::new(
+ Statistics {
+ num_rows: Some(100),
+ column_statistics: Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(1))),
+ max_value: Some(ScalarValue::Int32(Some(100))),
+ ..Default::default()
+ }]),
+ ..Default::default()
+ },
+ schema.clone(),
+ ));
+
+ // WHERE a <= 25
+ let sub_filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::LtEq, lit(25i32), &schema)?,
+ input,
+ )?);
+
+ // Nested filters (two separate physical plans, instead of AND chain in the expr)
+ // WHERE a >= 10
+ // WHERE a <= 25
+ let filter: Arc<dyn ExecutionPlan> = Arc::new(FilterExec::try_new(
+ binary(col("a", &schema)?, Operator::GtEq, lit(10i32), &schema)?,
+ sub_filter,
+ )?);
+
+ let statistics = filter.statistics();
+ assert_eq!(statistics.num_rows, Some(16));
+ assert_eq!(
+ statistics.column_statistics,
+ Some(vec![ColumnStatistics {
+ min_value: Some(ScalarValue::Int32(Some(10))),
Review Comment:
nice
--
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
[GitHub] [arrow-datafusion] Dandandan commented on pull request #4519: Enrich filter statistics with known column boundaries
Posted by GitBox <gi...@apache.org>.
Dandandan commented on PR #4519:
URL: https://github.com/apache/arrow-datafusion/pull/4519#issuecomment-1342946947
> A question that don't relate with this PR. Why Statistics save `total_byte_size` instead of `column_avg_byte_size`, the latter is generally what I see in other systems. Although they have same effect.
I think I may have added this. It also makes sense to have average column size, although they can easily be derived if you have the estimated number of rows and the other way around.
--
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