You are viewing a plain text version of this content. The canonical link for it is here.

Posted to reviews@spark.apache.org by GitBox <gi...@apache.org> on 2021/12/13 14:45:23 UTC

[GitHub] [spark] cloud-fan opened a new pull request #34883: [SPARK-37629][SQL] Speed up Expression.canonicalized

cloud-fan opened a new pull request #34883:
URL: https://github.com/apache/spark/pull/34883

### What changes were proposed in this pull request?

`Expression.canonicalized` is very slow with a large expression tree, because its time complexity is O(n^2). To understand this performance issue, let's take a closer look at the related source code. First of all, `Expression.canonicalized` is recursive, as its default implementation is
```
lazy val canonicalized: Expression = {
val canonicalizedChildren = children.map(_.canonicalized)
Canonicalize.execute(withNewChildren(canonicalizedChildren))
}
```

However, `Canonicalize.execute` is also recursive when dealing with commutative operators, as it needs to collect all the commutative operators in the expression tree, and reorder them.

Let's say that we have a deep expression tree with 1000 `And`: `And(c1, And(c2, And(c3, ...)))`. If we call its `canonicalized` method, we first reorder 2 `And`s in a small subtree, then reorder 3 `And`s in a larger subtree, ... and finally reorder 1000 `And`s in the complete tree. This is O(n^2).

To make it O(n), this PR makes the following changes:
1. Introduce `Expression.roughlyCanonicalized`, which recursively canonicalize each expression node in the tree, without changing the tree structure (thus no commutative operators reordering).
2. `Expression.canonicalized` just reorders the commutative operators in `roughlyCanonicalized`.
3. `Canonicalize` only reorders commutative operators now. Other logics are moved to the corresponding expressions' `roughlyCanonicalized` override.

After this PR, when we canonicalize a deep expression tree with 1000 `And`, we first traverse the expression tree once, to make it roughly canonicailized (name, nullability, etc. are normalized). Then we call `Canonicalize` once to reorder `And`s, which also traverse the tree only once.

### Why are the changes needed?

Fix a performance issue when `Expression.canonicalized` can be very slow.

### Does this PR introduce _any_ user-facing change?

no

### How was this patch tested?

pass the existing tests and run a benchmark manually
```
test("benchmark") {
val col = Literal(true)
var and = And(col, col)
var i = 0
while (i < 2000) {
and = And(and, col)
i += 1
}
and.canonicalized
}
```
Before this PR, it takes 10 seconds, now it takes 200 ms.

--
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: reviews-unsubscribe@spark.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org