You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "david-mollitor-db (via GitHub)" <gi...@apache.org> on 2026/09/11 01:29:01 UTC
[PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
david-mollitor-db opened a new pull request, #58724:
URL: https://github.com/apache/spark/pull/58724
### What changes were proposed in this pull request?
`ExpressionEquals` is the key type of `EquivalentExpressions.equivalenceMap`
(`mutable.HashMap[ExpressionEquals, ExpressionStats]`), the map that drives common-subexpression
elimination (CSE). Its `hashCode` was:
```scala
override def hashCode: Int = Objects.hash(e.semanticHash(): Integer, height: Integer)
```
`java.util.Objects.hash(...)` is varargs, so every call boxes both ints to `Integer` and allocates an
`Object[2]`. This PR computes the hash directly, with no boxing or array allocation:
```scala
override def hashCode: Int = {
val prime = 31
var result = 1
result = prime * result + e.semanticHash()
result = prime * result + height
result
}
```
While here, `equals` is reordered to test the O(1) `height` before the recursive `semanticEquals`,
and the now-unused `import java.util.Objects` is removed.
### Why are the changes needed?
`ExpressionEquals.hashCode` is invoked on every `addExpr` / `updateExprInMap` / `getExprState`
lookup during CSE, so expression-heavy queries generate a steady stream of short-lived `Object[2]` +
boxed-`Integer` allocations during optimization/codegen. Computing the hash directly removes that
per-lookup allocation.
The new form reproduces the **exact** value the old `Objects.hash(e.semanticHash(), height)`
produced: `Objects.hash` delegates to `java.util.Arrays.hashCode`, which starts `result` at 1 and
folds each element as `prime * result + element.hashCode()` (and `Integer.hashCode` is the int
value). So the hash value -- and therefore the bucket distribution -- is unchanged.
The `equals` reorder is behavior-preserving: `semanticEquals` implies equal `height`, so testing the
cheap `height` first short-circuits an unequal comparison without walking the expression tree, and
`&&` yields the identical boolean. `equals` runs only on hash-bucket collisions, which is exactly
where the cheap pre-check helps.
### Does this PR introduce _any_ user-facing change?
No. This is an internal optimization with no behavior change.
### How was this patch tested?
Added a `SubexpressionEliminationSuite` test asserting the new `hashCode` equals
`Objects.hash(e.semanticHash(): Integer, height: Integer)` across several expressions (varying
`semanticHash` and `height`), pinning the byte-for-byte equivalence. Existing
`SubexpressionEliminationSuite` and `SubExprEvaluationRuntimeSuite` pass unchanged; scalastyle is
clean.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 4.8
This pull request and its description were written by Isaac.
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-5632306458
Thank you @david-mollitor-db! Adding @stevomitric here to review 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: 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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-5743554018
Thank you @uros-b and @stevomitric for the reviews. This has two approvals and CI is green. @uros-b, whenever you have a moment, would you be able to merge it? Much appreciated.
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-5874863883
Hi @uros-b, thanks for the review and approval here! Whenever you have a moment, would you be able to merge it? Thanks so much.
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b closed pull request #58724: [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode
URL: https://github.com/apache/spark/pull/58724
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-5775009466
Thank you @david-mollitor-db! Please resolve conflicts
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on code in PR #58724:
URL: https://github.com/apache/spark/pull/58724#discussion_r4022202158
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala:
##########
@@ -263,11 +261,19 @@ case class ExpressionEquals(e: Expression) {
def height: Int = e.height
override def equals(o: Any): Boolean = o match {
- case other: ExpressionEquals => e.semanticEquals(other.e) && height == other.height
+ // Check the cheap `height` before the recursive `semanticEquals` (which implies equal height).
Review Comment:
Good catch, thanks -- you're right. I reworded the comment so it no longer claims `semanticEquals` implies equal `height`; it now notes that semantically equal expressions can still differ in `height`, so the `height` check is a genuine part of equality and testing it first just short-circuits the recursive `semanticEquals`. I corrected the same wording in the commit message as well. Updated in e32fa6eb202.
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "david-mollitor-db (via GitHub)" <gi...@apache.org>.
david-mollitor-db commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-6171523359
Thanks @uros-b and @stevomitric for the reviews! I rebased onto the latest master to resolve the conflict. It was only in `SubexpressionEliminationSuite`, where the new SPARK-59579 test landed right next to this PR's test; the change itself is unchanged. @uros-b, whenever you have a moment, would you be able to merge this once CI is green? Much appreciated.
--
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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "stevomitric (via GitHub)" <gi...@apache.org>.
stevomitric commented on code in PR #58724:
URL: https://github.com/apache/spark/pull/58724#discussion_r4007459997
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala:
##########
@@ -263,11 +261,19 @@ case class ExpressionEquals(e: Expression) {
def height: Int = e.height
override def equals(o: Any): Boolean = o match {
- case other: ExpressionEquals => e.semanticEquals(other.e) && height == other.height
+ // Check the cheap `height` before the recursive `semanticEquals` (which implies equal height).
Review Comment:
"implies equal height" isn't true (e.g. (a+b)+(c+d) and ((a+b)+c)+d are semantically equal but differ in height). Could you please reword it?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: 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
Re: [PR] [SPARK-59426][SQL] Avoid per-lookup allocation in EquivalentExpressions.ExpressionEquals.hashCode [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #58724:
URL: https://github.com/apache/spark/pull/58724#issuecomment-6279963132
**Merge Summary:**
- merged into master https://github.com/apache/spark/commit/0dd75bdb5d13e8ebaad023ce10e2c5f5c04876af
- merged into branch-4.x https://github.com/apache/spark/commit/0d864d519066a22c6618841f266fba23df1f399a
*Posted by `merge_spark_pr.py`*
--
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