You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "peter-toth (via GitHub)" <gi...@apache.org> on 2024/07/04 12:22:14 UTC
[PR] Improve volatile expression handling in `CommonSubexprEliminate` rule [datafusion]
peter-toth opened a new pull request, #11265:
URL: https://github.com/apache/datafusion/pull/11265
## Which issue does this PR close?
Part of https://github.com/apache/datafusion/issues/11194.
## Rationale for this change
Curently `CommonSubexprEliminate` always skips expressions doesn't allow volatile expressions to be extracted, but this can be improved by allowing non-volatile subexpressions of volatile expressions to be extracted:
I.e. from the plan:
```
Projection (a + b) + rand() AS c1, (a + b) + rand() AS c2
```
the expression `a + b` can be extracted as common expression despite the fact that `(a + b) + rand()` is volatile.
## What changes are included in this PR?
Changes the rule to handle volatile expressions better by adding a new boolean flag to `VisitRecord::ExprItem` and propagating up volatility (validity for CSE).
## Are these changes tested?
Yes, added new UT.
## Are there any user-facing changes?
No.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667004909
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
This question is similar to https://github.com/apache/datafusion/pull/11197#discussion_r1662618797. We can extract the surely evaluated expressions (1st legs) from those short circuiting `Or`, `And` and `CaseWhen` expressions, but we are not there yet with this PR.
My 3rd PR in the https://github.com/apache/datafusion/issues/11194 epic will implement that logic, but I want to add the improvements gradually as it will require to recurse into only certain children of a parent and that's not straightforward with the current treenode APIs (i.e. we need to stop recursion at the parent with a `Jump` and start a new recursion only on the interresting children).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#issuecomment-2208941562
cc @alamb, this the 2nd PR of https://github.com/apache/datafusion/issues/11194.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667004909
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
This question is similar to https://github.com/apache/datafusion/pull/11197#discussion_r1662618797. We can extract the surely evaluated expressions (1st legs) from those short circuiting `Or`, `And` and `CaseWhen` expressions, but we are not there yet with this PR.
My 3rd PR in the https://github.com/apache/datafusion/issues/11194 epic will implement that logic, but I want to add the improvements gradually as it will require to recurse into only certain children of a parent and that's not straightforward with the current treenode APIs (i.e. we need to stop recursion at the parent with a `Jump` and start a new recursion only on the interresting children).
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
This question is similar to https://github.com/apache/datafusion/pull/11197#discussion_r1662618797. We can extract the surely evaluated expressions (1st legs) from those short circuiting `Or`, `And` and `CaseWhen` expressions, but we are not there yet with this PR.
My 3rd PR in the https://github.com/apache/datafusion/issues/11194 epic will implement that logic, but I want to add the improvements gradually as it will require to recurse into only certain children of a parent and that's not straightforward with the current treenode APIs (i.e. we need to stop recursion at the parent with a `Jump` and start a new recursion only on the interresting children).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667022866
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -917,27 +912,36 @@ struct ExprIdentifierVisitor<'a, 'n> {
/// Record item that used when traversing an expression tree.
enum VisitRecord<'n> {
- /// Contains the post-order index assigned in during the first, visiting traversal and
- /// a boolean flag to indicate if the record marks an expression subtree (not just a
- /// single node).
+ /// Marks the beginning of expression. It contains:
+ /// - The post-order index assigned during the first, visiting traversal.
+ /// - A boolean flag if the record marks an expression subtree (not just a single
+ /// node).
EnterMark(usize, bool),
- /// Accumulated identifier of sub expression.
- ExprItem(Identifier<'n>),
+
+ /// Marks an accumulated subexpression tree. It contains:
+ /// - The accumulated identifier of a subexpression.
+ /// - A boolean flag if the expression is valid for subexpression elimination.
+ /// The flag is propagated up from children to parent. (E.g. volatile expressions
+ /// are not valid and can't be extracted, but non-volatile children of volatile
+ /// expressions can be extracted.)
+ ExprItem(Identifier<'n>, bool),
}
impl<'n> ExprIdentifierVisitor<'_, 'n> {
/// Find the first `EnterMark` in the stack, and accumulates every `ExprItem`
/// before it.
Review Comment:
Sure, good idea, I've added the comment in https://github.com/apache/datafusion/pull/11265/commits/79b2e022678177358d8325996354ea10a34582fb
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1666987160
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -917,27 +912,36 @@ struct ExprIdentifierVisitor<'a, 'n> {
/// Record item that used when traversing an expression tree.
enum VisitRecord<'n> {
- /// Contains the post-order index assigned in during the first, visiting traversal and
- /// a boolean flag to indicate if the record marks an expression subtree (not just a
- /// single node).
+ /// Marks the beginning of expression. It contains:
+ /// - The post-order index assigned during the first, visiting traversal.
+ /// - A boolean flag if the record marks an expression subtree (not just a single
+ /// node).
EnterMark(usize, bool),
- /// Accumulated identifier of sub expression.
- ExprItem(Identifier<'n>),
+
+ /// Marks an accumulated subexpression tree. It contains:
+ /// - The accumulated identifier of a subexpression.
+ /// - A boolean flag if the expression is valid for subexpression elimination.
+ /// The flag is propagated up from children to parent. (E.g. volatile expressions
+ /// are not valid and can't be extracted, but non-volatile children of volatile
+ /// expressions can be extracted.)
+ ExprItem(Identifier<'n>, bool),
}
impl<'n> ExprIdentifierVisitor<'_, 'n> {
/// Find the first `EnterMark` in the stack, and accumulates every `ExprItem`
/// before it.
Review Comment:
Could you possibly update this doc string to explain the 4-tuple that is now returned? Specifically document the two different `bool` values?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667004909
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
This question is similar to https://github.com/apache/datafusion/pull/11197#discussion_r1662618797. We can extract the surely evalueted expressions (1st legs) from those short circuiting `Or`, `And` and `CaseWhen` expressions, but we are not there yet with this PR. My 3rd PR in the https://github.com/apache/datafusion/issues/11194 epic will implement that logic, but I want to add the improvements gradually.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb merged PR #11265:
URL: https://github.com/apache/datafusion/pull/11265
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#issuecomment-2214669069
Thanks again @peter-toth and @haohuaijin
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#issuecomment-2214924076
Thanks @alamb and @haohuaijin for the review!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667004909
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
This question is similar to https://github.com/apache/datafusion/pull/11197#discussion_r1662618797. We can extract the surely evaluated expressions (1st legs) from those short circuiting `Or`, `And` and `CaseWhen` expressions, but we are not there yet with this PR. My 3rd PR in the https://github.com/apache/datafusion/issues/11194 epic will implement that logic, but I want to add the improvements gradually.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667023665
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -917,27 +912,36 @@ struct ExprIdentifierVisitor<'a, 'n> {
/// Record item that used when traversing an expression tree.
enum VisitRecord<'n> {
- /// Contains the post-order index assigned in during the first, visiting traversal and
- /// a boolean flag to indicate if the record marks an expression subtree (not just a
- /// single node).
+ /// Marks the beginning of expression. It contains:
+ /// - The post-order index assigned during the first, visiting traversal.
+ /// - A boolean flag if the record marks an expression subtree (not just a single
+ /// node).
EnterMark(usize, bool),
- /// Accumulated identifier of sub expression.
- ExprItem(Identifier<'n>),
+
+ /// Marks an accumulated subexpression tree. It contains:
+ /// - The accumulated identifier of a subexpression.
+ /// - A boolean flag if the expression is valid for subexpression elimination.
+ /// The flag is propagated up from children to parent. (E.g. volatile expressions
+ /// are not valid and can't be extracted, but non-volatile children of volatile
+ /// expressions can be extracted.)
+ ExprItem(Identifier<'n>, bool),
}
impl<'n> ExprIdentifierVisitor<'_, 'n> {
/// Find the first `EnterMark` in the stack, and accumulates every `ExprItem`
/// before it.
- fn pop_enter_mark(&mut self) -> (usize, bool, Option<Identifier<'n>>) {
+ fn pop_enter_mark(&mut self) -> (usize, bool, Option<Identifier<'n>>, bool) {
let mut expr_id = None;
+ let mut is_valid = true;
Review Comment:
I added a comment to the method in https://github.com/apache/datafusion/commit/79b2e022678177358d8325996354ea10a34582fb, I think it explains what "valid" means in this case, but let me know if we should document the variable as well.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1666985733
##########
datafusion/expr/src/expr.rs:
##########
@@ -1413,12 +1413,16 @@ impl Expr {
.unwrap()
}
+ /// Returns true if the expression node is volatile, i.e. whether it can return
+ /// different results when evaluated multiple times with the same input.
+ pub fn is_volatile_node(&self) -> bool {
Review Comment:
I think it would help to clarify in the docs the difference between `is_volatile` and `is_volatile_node`
Perhaps something like
```suggestion
///
/// Note: unlike [`Self::is_volatile`], this function does not consider inputs:
/// - `rand()` returns `true`,
/// - `a + rand()` returns `false`
pub fn is_volatile_node(&self) -> bool {
```
(and something similar for `is_volatile`)
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -917,27 +912,36 @@ struct ExprIdentifierVisitor<'a, 'n> {
/// Record item that used when traversing an expression tree.
enum VisitRecord<'n> {
- /// Contains the post-order index assigned in during the first, visiting traversal and
- /// a boolean flag to indicate if the record marks an expression subtree (not just a
- /// single node).
+ /// Marks the beginning of expression. It contains:
+ /// - The post-order index assigned during the first, visiting traversal.
+ /// - A boolean flag if the record marks an expression subtree (not just a single
+ /// node).
EnterMark(usize, bool),
- /// Accumulated identifier of sub expression.
- ExprItem(Identifier<'n>),
+
+ /// Marks an accumulated subexpression tree. It contains:
+ /// - The accumulated identifier of a subexpression.
+ /// - A boolean flag if the expression is valid for subexpression elimination.
+ /// The flag is propagated up from children to parent. (E.g. volatile expressions
+ /// are not valid and can't be extracted, but non-volatile children of volatile
+ /// expressions can be extracted.)
+ ExprItem(Identifier<'n>, bool),
}
impl<'n> ExprIdentifierVisitor<'_, 'n> {
/// Find the first `EnterMark` in the stack, and accumulates every `ExprItem`
/// before it.
- fn pop_enter_mark(&mut self) -> (usize, bool, Option<Identifier<'n>>) {
+ fn pop_enter_mark(&mut self) -> (usize, bool, Option<Identifier<'n>>, bool) {
let mut expr_id = None;
+ let mut is_valid = true;
Review Comment:
Could you please document what "valid" means in this context? I think it means "is valid for CSE" as in "this sub expression could potentially be removed via CSE" but I am not quite sure
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#issuecomment-2211216696
> It may also be worth writing a few .slt tests showing this in action and how it interacts with multiple subexpressions
Sure, I will add some tests tomorrow.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1667023792
##########
datafusion/expr/src/expr.rs:
##########
@@ -1413,12 +1413,16 @@ impl Expr {
.unwrap()
}
+ /// Returns true if the expression node is volatile, i.e. whether it can return
+ /// different results when evaluated multiple times with the same input.
+ pub fn is_volatile_node(&self) -> bool {
Review Comment:
Added in https://github.com/apache/datafusion/commit/79b2e022678177358d8325996354ea10a34582fb.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#discussion_r1666988190
##########
datafusion/optimizer/src/common_subexpr_eliminate.rs:
##########
@@ -1838,4 +1851,53 @@ mod test {
Ok(())
}
+
+ #[test]
+ fn test_volatile() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let extracted_child = col("a") + col("b");
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile = extracted_child + rand;
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile.clone().alias("c1"),
+ not_extracted_volatile.alias("c2"),
+ ])?
+ .build()?;
+
+ let expected = "Projection: __common_expr_1 + random() AS c1, __common_expr_1 + random() AS c2\
+ \n Projection: test.a + test.b AS __common_expr_1, test.a, test.b, test.c\
+ \n TableScan: test";
+
+ assert_optimized_plan_eq(expected, plan, None);
+
+ Ok(())
+ }
+
+ #[test]
+ fn test_volatile_short_circuits() -> Result<()> {
+ let table_scan = test_table_scan()?;
+
+ let rand = Expr::ScalarFunction(ScalarFunction::new_udf(math::random(), vec![]));
+ let not_extracted_volatile_short_circuit_2 =
+ rand.clone().eq(lit(0)).or(col("b").eq(lit(0)));
+ let not_extracted_volatile_short_circuit_1 =
+ col("a").eq(lit(0)).or(rand.eq(lit(0)));
+ let plan = LogicalPlanBuilder::from(table_scan.clone())
+ .project(vec![
+ not_extracted_volatile_short_circuit_1.clone().alias("c1"),
+ not_extracted_volatile_short_circuit_1.alias("c2"),
Review Comment:
🤔 I was thinking -- why can't we extract the `a = 0` part of `a = 0 OR random() = 0` out?
It seems like it would be ok to rewrite
```sql
SELECT
a = 0 OR random() = 0 as c1,
a = 0 OR random() = 0 as c2,
..
```
to something like this:
```sql
SELECT
__subexpr_1 OR random() as c1,
__subexpr_1 OR random() as c2,
...
FROM (
SELECT
a=0 as __subexpr_1
FROM
...
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Improve volatile expression handling in `CommonSubexprEliminate` [datafusion]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #11265:
URL: https://github.com/apache/datafusion/pull/11265#issuecomment-2211715751
I've added CSE tests in https://github.com/apache/datafusion/pull/11265/commits/1aa88486775266570c7219d490201eb96a8dfc4d.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org