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/11/05 23:23:50 UTC
[GitHub] [arrow-datafusion] isidentical opened a new pull request, #4115: Linearize binary expressions to reduce proto tree complexity
isidentical opened a new pull request, #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115
# 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 #4066.
# 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.
-->
This PR tries to represent chained binary expressions (like `a AND b AND C` or `a + b + c`) in a linearized manner (so instead of `((a, AND, b), AND, c)`, they are represented as `([a, b, c], AND)`) which reduces the complexity of protobuf trees and help serialize some of the complex expressions that weren't possible to serialize before.
# 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.
-->
New representation of the binary expressions in serialized logical plans.
# Are there any user-facing changes?
This PR changes the structure in the logical plan, so not sure if this qualifies as an API change. If it might be better to actually do it without removing the existing fields from the protobuf declaration of `BinaryExpr`, we also add a new field to the current form and represent all the extra operands there (but I think this one is much more straightforward).
<!--
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] yahoNanJing commented on pull request #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
yahoNanJing commented on PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#issuecomment-1314026857
Seems it brings a regression issue which causes stack overflow issue for "sum case when"
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015555037
##########
datafusion/proto/src/to_proto.rs:
##########
@@ -455,11 +455,36 @@ impl TryFrom<&Expr> for protobuf::LogicalExprNode {
}
}
Expr::BinaryExpr(BinaryExpr { left, op, right }) => {
- let binary_expr = Box::new(protobuf::BinaryExprNode {
- l: Some(Box::new(left.as_ref().try_into()?)),
- r: Some(Box::new(right.as_ref().try_into()?)),
+ // Try to linerize a nested binary expression tree of the same operator
Review Comment:
Though just to clarify, `(B and (C AND D))` part of the second expression will be linearized. It just won't include `A` (the left one has a depth of 1; the right one has depth of 2).
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015435959
##########
datafusion/proto/src/from_proto.rs:
##########
@@ -690,11 +690,34 @@ pub fn parse_expr(
.ok_or_else(|| Error::required("expr_type"))?;
match expr_type {
- ExprType::BinaryExpr(binary_expr) => Ok(Expr::BinaryExpr(BinaryExpr::new(
- Box::new(parse_required_expr(&binary_expr.l, registry, "l")?),
- from_proto_binary_op(&binary_expr.op)?,
- Box::new(parse_required_expr(&binary_expr.r, registry, "r")?),
- ))),
+ ExprType::BinaryExpr(binary_expr) => {
+ let op = from_proto_binary_op(&binary_expr.op)?;
+ let operands = binary_expr
+ .operands
+ .iter()
+ .map(|expr| parse_expr(expr, registry))
+ .collect::<Result<Vec<_>, _>>()?;
+
+ if operands.len() < 2 {
+ return Err(proto_error(
+ "A binary expression must always have at least 2 operands",
+ ));
+ }
+
+ // Reduce the linearized operands (ordered by left innermost to right
+ // outermost) into a single expression tree.
+ Ok(operands
+ .into_iter()
+ .reduce(|left, right| {
+ Expr::BinaryExpr(BinaryExpr::new(Box::new(left), op, Box::new(right)))
+ })
+ .unwrap_or_else(|| {
+ // As long as we have the bounds check above, this should never happen.
+ panic!(
Review Comment:
This should not happen in theory (we already have an error that is handling it), so it is pretty much a programmatic guard to satisfy the compiler. But I can change it to also construct an error (didn't want to duplicate the check above).
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015547987
##########
datafusion/proto/src/from_proto.rs:
##########
@@ -690,11 +690,34 @@ pub fn parse_expr(
.ok_or_else(|| Error::required("expr_type"))?;
match expr_type {
- ExprType::BinaryExpr(binary_expr) => Ok(Expr::BinaryExpr(BinaryExpr::new(
- Box::new(parse_required_expr(&binary_expr.l, registry, "l")?),
- from_proto_binary_op(&binary_expr.op)?,
- Box::new(parse_required_expr(&binary_expr.r, registry, "r")?),
- ))),
+ ExprType::BinaryExpr(binary_expr) => {
+ let op = from_proto_binary_op(&binary_expr.op)?;
+ let operands = binary_expr
+ .operands
+ .iter()
+ .map(|expr| parse_expr(expr, registry))
+ .collect::<Result<Vec<_>, _>>()?;
+
+ if operands.len() < 2 {
+ return Err(proto_error(
+ "A binary expression must always have at least 2 operands",
+ ));
+ }
+
+ // Reduce the linearized operands (ordered by left innermost to right
+ // outermost) into a single expression tree.
+ Ok(operands
+ .into_iter()
+ .reduce(|left, right| {
+ Expr::BinaryExpr(BinaryExpr::new(Box::new(left), op, Box::new(right)))
+ })
+ .unwrap_or_else(|| {
+ // As long as we have the bounds check above, this should never happen.
+ panic!(
Review Comment:
Makes sense, thanks for the suggestion folks! Changed it to `expect()`.
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#issuecomment-1315521221
Ah, no problem at all. Let me know if it resurfaces @yahoNanJing!
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
alamb merged PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015834100
##########
datafusion/proto/src/bytes/mod.rs:
##########
@@ -321,6 +321,98 @@ mod test {
Expr::from_bytes(&bytes).unwrap();
}
+ fn roundtrip_expr(expr: &Expr) -> Expr {
+ let bytes = expr.to_bytes().unwrap();
+ Expr::from_bytes(&bytes).unwrap()
+ }
+
+ #[test]
+ fn exact_roundtrip_linearized_binary_expr() {
+ // (((A AND B) AND C) AND D)
+ let expr_ordered = col("A").and(col("B")).and(col("C")).and(col("D"));
+ assert_eq!(expr_ordered, roundtrip_expr(&expr_ordered));
+
+ // Ensure that no other variation becomes equal
Review Comment:
❤️
##########
datafusion/proto/src/bytes/mod.rs:
##########
@@ -321,6 +321,98 @@ mod test {
Expr::from_bytes(&bytes).unwrap();
}
+ fn roundtrip_expr(expr: &Expr) -> Expr {
+ let bytes = expr.to_bytes().unwrap();
+ Expr::from_bytes(&bytes).unwrap()
+ }
+
+ #[test]
+ fn exact_roundtrip_linearized_binary_expr() {
+ // (((A AND B) AND C) AND D)
+ let expr_ordered = col("A").and(col("B")).and(col("C")).and(col("D"));
+ assert_eq!(expr_ordered, roundtrip_expr(&expr_ordered));
+
+ // Ensure that no other variation becomes equal
+ let other_variants = vec![
+ // (((B AND A) AND C) AND D)
+ col("B").and(col("A")).and(col("C")).and(col("D")),
+ // (((A AND C) AND B) AND D)
+ col("A").and(col("C")).and(col("B")).and(col("D")),
+ // (((A AND B) AND D) AND C)
+ col("A").and(col("B")).and(col("D")).and(col("C")),
+ // A AND (B AND (C AND D)))
+ col("A").and(col("B").and(col("C").and(col("D")))),
+ ];
+ for case in other_variants {
+ // Each variant is still equal to itself
+ assert_eq!(case, roundtrip_expr(&case));
+
+ // But non of them is equal to the original
+ assert_ne!(expr_ordered, roundtrip_expr(&case));
+ assert_ne!(roundtrip_expr(&expr_ordered), roundtrip_expr(&case));
+ }
+ }
+
+ #[test]
+ fn roundtrip_deeply_nested_binary_expr() {
+ // We need more stack space so this doesn't overflow in dev builds
+ std::thread::Builder::new()
+ .stack_size(10_000_000)
+ .spawn(|| {
+ let n = 100;
+ // a < 5
+ let basic_expr = col("a").lt(lit(5i32));
+ // (a < 5) OR (a < 5) OR (a < 5) OR ...
+ let or_chain = (0..n)
+ .fold(basic_expr.clone(), |expr, _| expr.or(basic_expr.clone()));
+ // (a < 5) OR (a < 5) AND (a < 5) OR (a < 5) AND (a < 5) AND (a < 5) OR ...
+ let expr =
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] isidentical commented on a diff in pull request #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015555749
##########
datafusion/proto/src/bytes/mod.rs:
##########
@@ -332,7 +361,8 @@ mod test {
println!("testing: {n}");
let expr_base = col("a").lt(lit(5i32));
- let expr = (0..n).fold(expr_base.clone(), |expr, _| expr.and(expr_base.clone()));
+ // Generate a tree of AND and OR expressions (no subsequent ANDs or ORs).
Review Comment:
Thanks, added one (`roundtrip_deeply_nested_binary_expr_reverse_order`).
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015548507
##########
datafusion/proto/src/to_proto.rs:
##########
@@ -455,11 +455,36 @@ impl TryFrom<&Expr> for protobuf::LogicalExprNode {
}
}
Expr::BinaryExpr(BinaryExpr { left, op, right }) => {
- let binary_expr = Box::new(protobuf::BinaryExprNode {
- l: Some(Box::new(left.as_ref().try_into()?)),
- r: Some(Box::new(right.as_ref().try_into()?)),
+ // Try to linerize a nested binary expression tree of the same operator
Review Comment:
Yep, it only goes rightwards.
--
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] ursabot commented on pull request #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
ursabot commented on PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#issuecomment-1306109396
Benchmark runs are scheduled for baseline = 3892a1fd6862e18cb2c5eafc0aa8ef302f073d8a and contender = 6b712948362b078f1226623ca46ab96d8bd2b768. 6b712948362b078f1226623ca46ab96d8bd2b768 is a master commit associated with this PR. Results will be available as each benchmark for each run completes.
Conbench compare runs links:
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ec2-t3-xlarge-us-east-2] [ec2-t3-xlarge-us-east-2](https://conbench.ursa.dev/compare/runs/857057bb61b848b7a7151e7e9325fec2...668a88827c0148ed9dd3dcf3a4c3b0cb/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on test-mac-arm] [test-mac-arm](https://conbench.ursa.dev/compare/runs/327c85e0adc44e86bb80bc9744d880e9...1455fdf881c346e7a0f4f9cb49ded0c9/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-i9-9960x] [ursa-i9-9960x](https://conbench.ursa.dev/compare/runs/f767dd54abcc48b9bbb92ccff13b4423...7369c50ca7aa4f429f265af25fabeefc/)
[Skipped :warning: Benchmarking of arrow-datafusion-commits is not supported on ursa-thinkcentre-m75q] [ursa-thinkcentre-m75q](https://conbench.ursa.dev/compare/runs/dc5939c9a183469b8dcda24d0ba5c694...acd03781f23a455c8e4b3f1f8d7f7449/)
Buildkite builds:
Supported benchmarks:
ec2-t3-xlarge-us-east-2: Supported benchmark langs: Python, R. Runs only benchmarks with cloud = True
test-mac-arm: Supported benchmark langs: C++, Python, R
ursa-i9-9960x: Supported benchmark langs: Python, R, JavaScript
ursa-thinkcentre-m75q: Supported benchmark langs: C++, Java
--
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] yahoNanJing commented on pull request #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
yahoNanJing commented on PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#issuecomment-1314964665
Hi @isidentical, the issue may not relate to this PR. I made a mistake in our testing environment. Really sorry for bringing the confusing info.
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
isidentical commented on PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#issuecomment-1314079591
Thanks @yahoNanJing for the report! Would you mind sharing the logs (or linking them) (I don't see a new issue relevant to this and the CI on main is passing so not sure when it fails 🤔)
--
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] HaoYang670 commented on a diff in pull request #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
HaoYang670 commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1014942609
##########
datafusion/proto/src/from_proto.rs:
##########
@@ -690,11 +690,34 @@ pub fn parse_expr(
.ok_or_else(|| Error::required("expr_type"))?;
match expr_type {
- ExprType::BinaryExpr(binary_expr) => Ok(Expr::BinaryExpr(BinaryExpr::new(
- Box::new(parse_required_expr(&binary_expr.l, registry, "l")?),
- from_proto_binary_op(&binary_expr.op)?,
- Box::new(parse_required_expr(&binary_expr.r, registry, "r")?),
- ))),
+ ExprType::BinaryExpr(binary_expr) => {
+ let op = from_proto_binary_op(&binary_expr.op)?;
+ let operands = binary_expr
+ .operands
+ .iter()
+ .map(|expr| parse_expr(expr, registry))
+ .collect::<Result<Vec<_>, _>>()?;
+
+ if operands.len() < 2 {
+ return Err(proto_error(
+ "A binary expression must always have at least 2 operands",
+ ));
+ }
+
+ // Reduce the linearized operands (ordered by left innermost to right
+ // outermost) into a single expression tree.
+ Ok(operands
+ .into_iter()
+ .reduce(|left, right| {
+ Expr::BinaryExpr(BinaryExpr::new(Box::new(left), op, Box::new(right)))
+ })
+ .unwrap_or_else(|| {
+ // As long as we have the bounds check above, this should never happen.
+ panic!(
Review Comment:
nit: We should avoid panic in a function returning `Result`.
--
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 #4115: Linearize binary expressions to reduce proto tree complexity
Posted by GitBox <gi...@apache.org>.
alamb commented on code in PR #4115:
URL: https://github.com/apache/arrow-datafusion/pull/4115#discussion_r1015485753
##########
datafusion/proto/src/to_proto.rs:
##########
@@ -455,11 +455,36 @@ impl TryFrom<&Expr> for protobuf::LogicalExprNode {
}
}
Expr::BinaryExpr(BinaryExpr { left, op, right }) => {
- let binary_expr = Box::new(protobuf::BinaryExprNode {
- l: Some(Box::new(left.as_ref().try_into()?)),
- r: Some(Box::new(right.as_ref().try_into()?)),
+ // Try to linerize a nested binary expression tree of the same operator
Review Comment:
Is it correct that this code will work for `(((A AND B) AND C) AND D)` but not `A AND (B AND (C AND D)))`?
##########
datafusion/proto/src/bytes/mod.rs:
##########
@@ -332,7 +361,8 @@ mod test {
println!("testing: {n}");
let expr_base = col("a").lt(lit(5i32));
- let expr = (0..n).fold(expr_base.clone(), |expr, _| expr.and(expr_base.clone()));
+ // Generate a tree of AND and OR expressions (no subsequent ANDs or ORs).
Review Comment:
I would love to see a test that made the other type of nesting `(expr_base.clone().and(expr))`
##########
datafusion/proto/src/from_proto.rs:
##########
@@ -690,11 +690,34 @@ pub fn parse_expr(
.ok_or_else(|| Error::required("expr_type"))?;
match expr_type {
- ExprType::BinaryExpr(binary_expr) => Ok(Expr::BinaryExpr(BinaryExpr::new(
- Box::new(parse_required_expr(&binary_expr.l, registry, "l")?),
- from_proto_binary_op(&binary_expr.op)?,
- Box::new(parse_required_expr(&binary_expr.r, registry, "r")?),
- ))),
+ ExprType::BinaryExpr(binary_expr) => {
+ let op = from_proto_binary_op(&binary_expr.op)?;
+ let operands = binary_expr
+ .operands
+ .iter()
+ .map(|expr| parse_expr(expr, registry))
+ .collect::<Result<Vec<_>, _>>()?;
+
+ if operands.len() < 2 {
+ return Err(proto_error(
+ "A binary expression must always have at least 2 operands",
+ ));
+ }
+
+ // Reduce the linearized operands (ordered by left innermost to right
+ // outermost) into a single expression tree.
+ Ok(operands
+ .into_iter()
+ .reduce(|left, right| {
+ Expr::BinaryExpr(BinaryExpr::new(Box::new(left), op, Box::new(right)))
+ })
+ .unwrap_or_else(|| {
+ // As long as we have the bounds check above, this should never happen.
+ panic!(
Review Comment:
I think the comment is clear that this "should not happen" and thus I believe the `panic` is fine
You could also write this same logic slightly more concisely as `expect("Binary expression could not be reduced to a single expression.")`
--
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