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/10/17 14:17:03 UTC
[GitHub] [arrow-datafusion] Ted-Jiang opened a new pull request, #3859: Factorize common AND factors out of OR predicates to support filterPu…
Ted-Jiang opened a new pull request, #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859
…shDown as possible
Signed-off-by: yangjiang <ya...@ebay.com>
# 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 #3858. Part #3834
# 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.
-->
# 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.
-->
# Are there any user-facing changes?
<!--
If there are user-facing changes then we may require documentation to be updated before approving the PR.
-->
<!--
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] alamb commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997541658
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -119,6 +119,121 @@ fn split_conjunction_owned_impl(expr: Expr, mut exprs: Vec<Expr>) -> Vec<Expr> {
}
}
+/// Converts an expression to conjunctive normal form (CNF).
Review Comment:
💯 for this comment
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
+ Filter: test.c = Int64(1) OR b > Int64(3) AND b > Int64(2) OR test.c = Int64(1) AND b > Int64(2) OR b > Int64(3)\
+ \n Aggregate: groupBy=[[test.a]], aggr=[[SUM(test.b) AS b]]\
+ \n Filter: test.c = Int64(1) OR test.c = Int64(1)\
Review Comment:
I think this should be a rule in https://github.com/apache/arrow-datafusion/blob/37fe938261636bb7710b26cf26e2bbd010e1dbf0/datafusion/optimizer/src/simplify_expressions.rs#L264
That pass gets run several times
I recommend we file a follow on ticket for that particular rewrite (the same thing applies to `a AND a` in addition to `a OR a`
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -529,7 +529,8 @@ fn optimize(plan: &LogicalPlan, mut state: State) -> Result<LogicalPlan> {
}
LogicalPlan::Analyze { .. } => push_down(&state, plan),
LogicalPlan::Filter(filter) => {
- let predicates = utils::split_conjunction(filter.predicate());
+ let filter_cnf = utils::CnfHelper::new().rewrite_to_cnf_impl(filter.predicate());
+ let predicates = utils::split_conjunction(&filter_cnf);
Review Comment:
I recommend putting it in SimplifyExpressions -- specifically call it from https://github.com/apache/arrow-datafusion/blob/37fe938261636bb7710b26cf26e2bbd010e1dbf0/datafusion/optimizer/src/simplify_expressions.rs#L264 somehow
You could also reuse the testing framework in that file as well
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -119,6 +119,121 @@ fn split_conjunction_owned_impl(expr: Expr, mut exprs: Vec<Expr>) -> Vec<Expr> {
}
}
+/// Converts an expression to conjunctive normal form (CNF).
+///
+/// The following expression is in CNF:
+/// `(a OR b) AND (c OR d)`
+/// The following is not in CNF:
+/// `(a AND b) OR c`.
+/// But could be rewrite to a CNF expression:
+/// `(a OR c) AND (b OR c)`.
+///
+/// # Example
+/// ```
+/// # use datafusion_expr::{col, lit};
+/// # use datafusion_optimizer::utils::CnfHelper;
+/// // （a=1 AND b=2）OR c = 3
+/// let expr1 = col("a").eq(lit(1)).and(col("b").eq(lit(2)));
+/// let expr2 = col("c").eq(lit(3));
+/// let expr = expr1.or(expr2);
+///
+/// //（a=1 or c=3）AND（b=2 or c=3）
+/// let expr1 = col("a").eq(lit(1)).or(col("c").eq(lit(3)));
+/// let expr2 = col("b").eq(lit(2)).or(col("c").eq(lit(3)));
+/// let expect = expr1.and(expr2);
+/// // use split_conjunction_owned to split them
+/// assert_eq!(CnfHelper::new().rewrite_to_cnf_impl(&expr), expect);
+/// ```
+///
+pub struct CnfHelper {
+ max_count: usize,
+ current_count: usize,
+ exprs: Vec<Expr>,
+ original_expr: Option<Expr>,
+}
+
+impl CnfHelper {
+ pub fn new() -> Self {
+ CnfHelper {
+ max_count: 100,
+ current_count: 0,
+ exprs: vec![],
+ original_expr: None,
+ }
+ }
+
+ pub fn new_with_max_count(max_count: usize) -> Self {
+ CnfHelper {
+ max_count,
+ current_count: 0,
+ exprs: vec![],
+ original_expr: None,
+ }
+ }
+
+ fn increment_and_check_overload(&mut self) -> bool {
+ self.current_count += 1;
+ self.current_count >= self.max_count
+ }
+
+ pub fn rewrite_to_cnf_impl(&mut self, expr: &Expr) -> Expr {
Review Comment:
I think if you used the `ExprRewriter` framework here you would avoid many of the `clone`s
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
Review Comment:
I think it is a good improvement for sure -- thank you
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r998237800
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -529,7 +529,8 @@ fn optimize(plan: &LogicalPlan, mut state: State) -> Result<LogicalPlan> {
}
LogicalPlan::Analyze { .. } => push_down(&state, plan),
LogicalPlan::Filter(filter) => {
- let predicates = utils::split_conjunction(filter.predicate());
+ let filter_cnf = utils::CnfHelper::new().rewrite_to_cnf_impl(filter.predicate());
+ let predicates = utils::split_conjunction(&filter_cnf);
Review Comment:
@alamb @Dandandan I prefer keep this just in `filter_push_down`, as you seen in `test_rewrite_cnf_overflow`, this is a heavy operation. It makes the exprs size expansion. IMO, we only need to spilt the filter expr to `CNF` to push filter down as many as possible, we should use normal expr to pass throuh plan.🤔
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1284522560
Actually, I think the regression is pretty bad (there are many filters) -- I am going to revert this PR to get the tests green again. I am really sorry @Ted-Jiang
--
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 a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Dandandan commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997164383
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -529,7 +529,8 @@ fn optimize(plan: &LogicalPlan, mut state: State) -> Result<LogicalPlan> {
}
LogicalPlan::Analyze { .. } => push_down(&state, plan),
LogicalPlan::Filter(filter) => {
- let predicates = utils::split_conjunction(filter.predicate());
+ let filter_cnf = utils::CnfHelper::new().rewrite_to_cnf_impl(filter.predicate());
+ let predicates = utils::split_conjunction(&filter_cnf);
Review Comment:
I wonder whether we should do this in filter pushdown or in the expression simplifier optimization?
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997122946
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
Review Comment:
It used to get
```
Filter: test.c = Int64(1) AND b > Int64(2) OR test.c = Int64(1) AND b > Int64(3)
Aggregate: groupBy=[[test.a]], aggr=[[SUM(test.b) AS b]]
TableScan: test
```
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb merged PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1284520960
🤔 this seems to have caused a logical merge conflict: https://github.com/apache/arrow-datafusion/actions/runs/3284319035/jobs/5410351533
I am working on a fix
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r998268672
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -663,4 +796,84 @@ mod tests {
"mismatch rewriting expr_from: {expr_from} to {rewrite_to}"
)
}
+
+ #[test]
+ fn test_rewrite_cnf() {
+ let a_1 = col("a").eq(lit(1i64));
+ let a_2 = col("a").eq(lit(2i64));
+
+ let b_1 = col("b").eq(lit(1i64));
+ let b_2 = col("b").eq(lit(2i64));
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> not change
+ let mut helper = CnfHelper::new();
+ let expr1 = and(a_1.clone(), b_2.clone());
+ let expect = expr1.clone();
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> (((a1 and b2) and a2) and b1)
+ let mut helper = CnfHelper::new();
+ let expr1 = and(and(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
+ let expect = and(a_1.clone(), b_2.clone())
Review Comment:
We need improve the `Expr` fmt: like
```
let expr1 = and(a_1.clone(), b_2.clone())
.and(a_2.clone())
.and(b_1.clone());
let expr2 = and(and(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
assert_eq!(expr1, expr2);
```
This is not equal but they have the same string format:
```
a = Int64(1) AND b = Int64(2) AND a = Int64(2) AND b = Int64(1)
```
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997125207
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
Review Comment:
@alamb @andygrove Do you think this is a reasonable improvement 🤔?
If this ok, i will modify the another test😂
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997681735
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -119,6 +119,121 @@ fn split_conjunction_owned_impl(expr: Expr, mut exprs: Vec<Expr>) -> Vec<Expr> {
}
}
+/// Converts an expression to conjunctive normal form (CNF).
+///
+/// The following expression is in CNF:
+/// `(a OR b) AND (c OR d)`
+/// The following is not in CNF:
+/// `(a AND b) OR c`.
+/// But could be rewrite to a CNF expression:
+/// `(a OR c) AND (b OR c)`.
+///
+/// # Example
+/// ```
+/// # use datafusion_expr::{col, lit};
+/// # use datafusion_optimizer::utils::CnfHelper;
+/// // （a=1 AND b=2）OR c = 3
+/// let expr1 = col("a").eq(lit(1)).and(col("b").eq(lit(2)));
+/// let expr2 = col("c").eq(lit(3));
+/// let expr = expr1.or(expr2);
+///
+/// //（a=1 or c=3）AND（b=2 or c=3）
+/// let expr1 = col("a").eq(lit(1)).or(col("c").eq(lit(3)));
+/// let expr2 = col("b").eq(lit(2)).or(col("c").eq(lit(3)));
+/// let expect = expr1.and(expr2);
+/// // use split_conjunction_owned to split them
+/// assert_eq!(CnfHelper::new().rewrite_to_cnf_impl(&expr), expect);
+/// ```
+///
+pub struct CnfHelper {
+ max_count: usize,
+ current_count: usize,
+ exprs: Vec<Expr>,
+ original_expr: Option<Expr>,
+}
+
+impl CnfHelper {
+ pub fn new() -> Self {
+ CnfHelper {
+ max_count: 100,
+ current_count: 0,
+ exprs: vec![],
+ original_expr: None,
+ }
+ }
+
+ pub fn new_with_max_count(max_count: usize) -> Self {
+ CnfHelper {
+ max_count,
+ current_count: 0,
+ exprs: vec![],
+ original_expr: None,
+ }
+ }
+
+ fn increment_and_check_overload(&mut self) -> bool {
+ self.current_count += 1;
+ self.current_count >= self.max_count
+ }
+
+ pub fn rewrite_to_cnf_impl(&mut self, expr: &Expr) -> Expr {
Review Comment:
I will try this.
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1284527986
@Ted-Jiang can you please re-create this PR (or I can do so to) and we can iterate on it some more. I am really sorry about that
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997125207
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
Review Comment:
@alamb @andygrove @Dandandan Do you think this is a reasonable improvement 🤔?
If this ok, i will modify the another test😂
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Dandandan commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1280987860
Seems useful and correct to me - makes sense for predicate pushdown indeed.
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Dandandan commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1280988807
Note that one of the tests now fails because of the optimization :+1:
--
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] Ted-Jiang commented on pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1284821175
> @Ted-Jiang can you please re-create this PR (or I can do so to) and we can iterate on it some more. I am really sorry about that
@alamb of course！This is not your fault 😂
--
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] Ted-Jiang commented on pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#issuecomment-1284825350
> Actually, I think the regression is pretty bad (there are many filters) -- I am going to revert this PR to get the tests green again. I am really sorry @Ted-Jiang
seems strange it pass in my local.
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r999023940
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -96,30 +96,173 @@ fn split_conjunction_impl<'a>(expr: &'a Expr, mut exprs: Vec<&'a Expr>) -> Vec<&
/// ];
///
/// // use split_conjunction_owned to split them
-/// assert_eq!(split_conjunction_owned(expr), split);
+/// assert_eq!(split_conjunction_owned(expr, Operator::And), split);
/// ```
-pub fn split_conjunction_owned(expr: Expr) -> Vec<Expr> {
- split_conjunction_owned_impl(expr, vec![])
+pub fn split_conjunction_owned(expr: Expr, op: Operator) -> Vec<Expr> {
Review Comment:
@alamb I think we could support on split on other types.
--
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 #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r999839048
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -663,4 +815,84 @@ mod tests {
"mismatch rewriting expr_from: {expr_from} to {rewrite_to}"
)
}
+
+ #[test]
+ fn test_rewrite_cnf() {
+ let a_1 = col("a").eq(lit(1i64));
+ let a_2 = col("a").eq(lit(2i64));
+
+ let b_1 = col("b").eq(lit(1i64));
+ let b_2 = col("b").eq(lit(2i64));
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> not change
+ let mut helper = CnfHelper::new();
+ let expr1 = and(a_1.clone(), b_2.clone());
+ let expect = expr1.clone();
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> (((a1 and b2) and a2) and b1)
+ let mut helper = CnfHelper::new();
+ let expr1 = and(and(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
+ let expect = and(a_1.clone(), b_2.clone())
+ .and(a_2.clone())
+ .and(b_1.clone());
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_or_b2 -> not change
+ let mut helper = CnfHelper::new();
+ let expr1 = or(a_1.clone(), b_2.clone());
+ let expect = expr1.clone();
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_and_b2 or a2_and_b1 -> a1_or_a2 and a1_or_b1 and b2_or_a2 and b2_or_b1
+ let mut helper = CnfHelper::new();
+ let expr1 = or(and(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
+ let a1_or_a2 = or(a_1.clone(), a_2.clone());
+ let a1_or_b1 = or(a_1.clone(), b_1.clone());
+ let b2_or_a2 = or(b_2.clone(), a_2.clone());
+ let b2_or_b1 = or(b_2.clone(), b_1.clone());
+ let expect = and(a1_or_a2, a1_or_b1).and(b2_or_a2).and(b2_or_b1);
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_or_b2 or a2_and_b1 -> ( a1_or_a2 or a2 ) and (a1_or_a2 or b1)
+ let mut helper = CnfHelper::new();
+ let a1_or_b2 = or(a_1.clone(), b_2.clone());
+ let expr1 = or(or(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
+ let expect = or(a1_or_b2.clone(), a_2.clone()).and(or(a1_or_b2, b_1.clone()));
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_or_b2 or a2_or_b1 -> not change
+ let mut helper = CnfHelper::new();
+ let expr1 = or(or(a_1, b_2), or(a_2, b_1));
+ let expect = expr1.clone();
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+ }
+
+ #[test]
+ fn test_rewrite_cnf_overflow() {
Review Comment:
❤️
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -663,4 +796,84 @@ mod tests {
"mismatch rewriting expr_from: {expr_from} to {rewrite_to}"
)
}
+
+ #[test]
+ fn test_rewrite_cnf() {
+ let a_1 = col("a").eq(lit(1i64));
+ let a_2 = col("a").eq(lit(2i64));
+
+ let b_1 = col("b").eq(lit(1i64));
+ let b_2 = col("b").eq(lit(2i64));
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> not change
+ let mut helper = CnfHelper::new();
+ let expr1 = and(a_1.clone(), b_2.clone());
+ let expect = expr1.clone();
+ let res = expr1.rewrite(&mut helper).unwrap();
+ assert_eq!(expect, res);
+
+ // Test rewrite on a1_and_b2 and a2_and_b1 -> (((a1 and b2) and a2) and b1)
+ let mut helper = CnfHelper::new();
+ let expr1 = and(and(a_1.clone(), b_2.clone()), and(a_2.clone(), b_1.clone()));
+ let expect = and(a_1.clone(), b_2.clone())
Review Comment:
> This is not equal but they have the same string format:
I agree this is not ideal
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
+ Filter: test.c = Int64(1) OR b > Int64(3) AND b > Int64(2) OR test.c = Int64(1) AND b > Int64(2) OR b > Int64(3)\
+ \n Aggregate: groupBy=[[test.a]], aggr=[[SUM(test.b) AS b]]\
+ \n Filter: test.c = Int64(1) OR test.c = Int64(1)\
Review Comment:
Filed https://github.com/apache/arrow-datafusion/issues/3895
##########
datafusion/optimizer/src/utils.rs:
##########
@@ -96,30 +96,173 @@ fn split_conjunction_impl<'a>(expr: &'a Expr, mut exprs: Vec<&'a Expr>) -> Vec<&
/// ];
///
/// // use split_conjunction_owned to split them
-/// assert_eq!(split_conjunction_owned(expr), split);
+/// assert_eq!(split_conjunction_owned(expr, Operator::And), split);
/// ```
-pub fn split_conjunction_owned(expr: Expr) -> Vec<Expr> {
- split_conjunction_owned_impl(expr, vec![])
+pub fn split_conjunction_owned(expr: Expr, op: Operator) -> Vec<Expr> {
Review Comment:
I agree this is useful -- though I would prefer this function to remain named `split_conjunction` (as the `conjunction` implies `AND` and instead have a new function called `split_operator` or something. Maybe I can make a quick PR
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997126635
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
+ Filter: test.c = Int64(1) OR b > Int64(3) AND b > Int64(2) OR test.c = Int64(1) AND b > Int64(2) OR b > Int64(3)\
+ \n Aggregate: groupBy=[[test.a]], aggr=[[SUM(test.b) AS b]]\
+ \n Filter: test.c = Int64(1) OR test.c = Int64(1)\
Review Comment:
Somewhere need simplify this
--
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] Ted-Jiang commented on a diff in pull request #3859: Factorize common AND factors out of OR predicates to support filterPu…
Posted by GitBox <gi...@apache.org>.
Ted-Jiang commented on code in PR #3859:
URL: https://github.com/apache/arrow-datafusion/pull/3859#discussion_r997122946
##########
datafusion/optimizer/src/filter_push_down.rs:
##########
@@ -952,6 +953,30 @@ mod tests {
Ok(())
}
+ #[test]
+ fn filter_keep_partial_agg() -> Result<()> {
+ let table_scan = test_table_scan()?;
+ let f1 = col("c").eq(lit(1i64)).and(col("b").gt(lit(2i64)));
+ let f2 = col("c").eq(lit(1i64)).and(col("b").gt(lit(3i64)));
+ let filter = f1.or(f2);
+ let plan = LogicalPlanBuilder::from(table_scan)
+ .aggregate(vec![col("a")], vec![sum(col("b")).alias("b")])?
+ .filter(filter)?
+ .build()?;
+ // filter of aggregate is after aggregation since they are non-commutative
+ // (c =1 AND b > 2) OR (c = 1 AND b > 3)
+ // rewrite to CNF
+ // (c = 1 OR c = 1) [can pushDown] AND (c = 1 OR b > 3) AND (b > 2 OR C = 1) AND (b > 2 OR b > 3)
+
+ let expected = "\
Review Comment:
It used to get not pushed:
```
Filter: test.c = Int64(1) AND b > Int64(2) OR test.c = Int64(1) AND b > Int64(3)
Aggregate: groupBy=[[test.a]], aggr=[[SUM(test.b) AS b]]
TableScan: test
```
--
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