You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "arnavgupta03 (via GitHub)" <gi...@apache.org> on 2025/08/15 18:35:11 UTC
[PR] [SPARK-53293] modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
arnavgupta03 opened a new pull request, #52046:
URL: https://github.com/apache/spark/pull/52046
<!--
Thanks for sending a pull request! Here are some tips for you:
1. If this is your first time, please read our contributor guidelines: https://spark.apache.org/contributing.html
2. Ensure you have added or run the appropriate tests for your PR: https://spark.apache.org/developer-tools.html
3. If the PR is unfinished, add '[WIP]' in your PR title, e.g., '[WIP][SPARK-XXXX] Your PR title ...'.
4. Be sure to keep the PR description updated to reflect all changes.
5. Please write your PR title to summarize what this PR proposes.
6. If possible, provide a concise example to reproduce the issue for a faster review.
7. If you want to add a new configuration, please read the guideline first for naming configurations in
'core/src/main/scala/org/apache/spark/internal/config/ConfigEntry.scala'.
8. If you want to add or modify an error type or message, please read the guideline first in
'common/utils/src/main/resources/error/README.md'.
-->
### What changes were proposed in this pull request?
<!--
Please clarify what changes you are proposing. The purpose of this section is to outline the changes and how this PR fixes the issue.
If possible, please consider writing useful notes for better and faster reviews in your PR. See the examples below.
1. If you refactor some codes with changing classes, showing the class hierarchy will help reviewers.
2. If you fix some SQL features, you can provide some references of other DBMSes.
3. If there is design documentation, please add the link.
4. If there is a discussion in the mailing list, please add the link.
-->
`exprIdToOrdinal` in `AttributeSeq` has been changed from a HashMap to an array contains the ordinals corresponding to the `ExprId` when evaluated with an offset. This has been done to speedup the lazy evaluation of `exprIdToOrdinal` for queries on wide tables (many attributes).
The change avoids the overhead of hashing `ExprId` and putting these elements into a `HashMap`. Since `ExprId`s are dense, this change does not cause a significant increase in memory usage.
### Why are the changes needed?
<!--
Please clarify why the changes are needed. For instance,
1. If you propose a new API, clarify the use case for a new API.
2. If you fix a bug, you can clarify why it is a bug.
-->
For queries that involve tables with a very large number of columns, when canonicalizing the query, evaluating the `exprIdToOrdinal` map becomes a dominating step as can be seen in the following flamegraph:
<img width="1615" height="671" alt="image" src="https://github.com/user-attachments/assets/1ca0375d-defd-4587-bc0c-1604d9a26bed" />
This slows down whichever step is the first to run canonicalization, which is often RemoveNoopUnion, but can vary. A speedup is needed here to improve the performance of the first rule to run canonicalization.
### Does this PR introduce _any_ user-facing change?
<!--
Note that it means *any* user-facing change including all aspects such as new features, bug fixes, or other behavior changes. Documentation-only updates are not considered user-facing changes.
If yes, please clarify the previous behavior and the change this PR proposes - provide the console output, description and/or an example to show the behavior difference if possible.
If possible, please also clarify if this is a user-facing change compared to the released Spark versions or within the unreleased branches such as master.
If no, write 'No'.
-->
No
### How was this patch tested?
<!--
If tests were added, say they were added here. Please make sure to add some test cases that check the changes thoroughly including negative and positive cases if possible.
If it was tested in a way different from regular unit tests, please clarify how you tested step by step, ideally copy and paste-able, so that other reviewers can test and check, and descendants can verify in the future.
If tests were not added, please describe why they were not added and/or why it was difficult to add.
If benchmark tests were added, please run the benchmarks in GitHub Actions for the consistent environment, and the instructions could accord to: https://spark.apache.org/developer-tools.html#github-workflow-benchmarks.
-->
Flamegraphs were generated to find if a decrease could be seen in the time spent evaluating `exprIdToOrdinal` and to check that time-consuming steps were removed or minimized, which was found:
<img width="1656" height="653" alt="image" src="https://github.com/user-attachments/assets/002c5215-e353-44de-a0b3-b395d86e9230" />
### Was this patch authored or co-authored using generative AI tooling?
<!--
If generative AI tooling has been used in the process of authoring this patch, please include the
phrase: 'Generated-by: ' followed by the name of the tool and its version.
If no, write 'No'.
Please refer to the [ASF Generative Tooling Guidance](https://www.apache.org/legal/generative-tooling.html) for details.
-->
Generated-by: claude-4.1-opus
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294033717
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
Review Comment:
```suggestion
maxExprId - minExprId >= Int.MaxValue || // prevent overflow
```
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2283751354
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -122,7 +191,8 @@ package object expressions {
* Returns the index of first attribute with a matching expression id, or -1 if no match exists.
*/
def indexOf(exprId: ExprId): Int = {
- Option(exprIdToOrdinal.get(exprId)).getOrElse(-1)
+ val id = exprId.id
+ exprIdToOrdinal(id)
Review Comment:
do we have boxing issue with invoking this lambda function? One idea is to have both the array and hashmap defined, but only one of them can be non-empty:
```
if (attrsArray.nonEmpty) ... else exprIdToOrdinal.get(exprId)).getOrElse(-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: 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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #52046:
URL: https://github.com/apache/spark/pull/52046#issuecomment-3619048493
We're closing this PR because it hasn't been updated in a while. This isn't a judgement on the merit of the PR in any way. It's just a way of keeping the PR queue manageable.
If you'd like to revive this PR, please reopen it and ask a committer to remove the Stale tag!
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294050220
##########
sql/core/src/test/resources/sql-tests/results/explain.sql.out:
##########
@@ -786,16 +786,20 @@ EXPLAIN FORMATTED
struct<plan:string>
-- !query output
== Physical Plan ==
-* BroadcastHashJoin Inner BuildRight (10)
+* BroadcastHashJoin Inner BuildRight (14)
:- * HashAggregate (6)
: +- Exchange (5)
: +- * HashAggregate (4)
: +- * Filter (3)
: +- * ColumnarToRow (2)
: +- Scan parquet spark_catalog.default.explain_temp1 (1)
-+- BroadcastExchange (9)
- +- * HashAggregate (8)
- +- ReusedExchange (7)
Review Comment:
Looks like this change breaks exchange reuse. We need to look into it. Maybe the new code has bugs and returns different result than the previuos code.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "arnavgupta03 (via GitHub)" <gi...@apache.org>.
arnavgupta03 commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2282745803
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +95,92 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a method that either uses a direct indexed array with the min
+ // and max expression IDs as an offset or a hash map.
+ @transient private lazy val ordinalArrays: (Long => Int, Array[Attribute]) = {
Review Comment:
Would this be separating `exprIdToOrdinal` from `attrsArray` or would this be inside the evaluation of `ordinalArrays`?
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "arnavgupta03 (via GitHub)" <gi...@apache.org>.
arnavgupta03 commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2284056252
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +95,92 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a method that either uses a direct indexed array with the min
+ // and max expression IDs as an offset or a hash map.
+ @transient private lazy val ordinalArrays: (Long => Int, Array[Attribute]) = {
Review Comment:
The `attrsArray` is used in the `apply` method to get the attribute at the index, so we'll still need it there.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294037944
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
Review Comment:
The final array size is `(maxExprId - minExprId + 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: 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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2284741308
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -122,7 +191,8 @@ package object expressions {
* Returns the index of first attribute with a matching expression id, or -1 if no match exists.
*/
def indexOf(exprId: ExprId): Int = {
- Option(exprIdToOrdinal.get(exprId)).getOrElse(-1)
+ val id = exprId.id
+ exprIdToOrdinal(id)
Review Comment:
yea `attrsArray` and `exprIdToOrdinal` should still be `lazy val` and be materialized during the first access here.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2282173214
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +95,92 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a method that either uses a direct indexed array with the min
+ // and max expression IDs as an offset or a hash map.
+ @transient private lazy val ordinalArrays: (Long => Int, Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (_ => -1, Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId <= Long.MaxValue && // prevent overflow
Review Comment:
```suggestion
maxExprId - minExprId <= Int.MaxValue && // prevent overflow
```
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] closed pull request #52046: [SPARK-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables
URL: https://github.com/apache/spark/pull/52046
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2283749621
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +95,92 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a method that either uses a direct indexed array with the min
+ // and max expression IDs as an offset or a hash map.
+ @transient private lazy val ordinalArrays: (Long => Int, Array[Attribute]) = {
Review Comment:
nvm, we are already doing it, but the returned `attrsArray` is not used anywhere, can we remove 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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2303024565
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
Review Comment:
One possible reason that it breaks shuffle reuse: Previous we use `ExprId` as the hash map key, but now we completely ignore `ExprId#jvmId`. We should record the jvmId and return -1 directly in `def indexOf` if the jvmId is different.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "arnavgupta03 (via GitHub)" <gi...@apache.org>.
arnavgupta03 commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294202755
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
+ ) {
+ (Array.empty[Int], attrs.toArray)
Review Comment:
In the fallback case, we might still need `attrsArray` for `AttributeSeq.apply`.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2281310344
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +93,57 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a direct indexed array using the min and max expression IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else {
+ // Create directly indexed array
+ val arraySize = (maxExprId - minExprId + 1).toInt
Review Comment:
will this overflow?
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2281319865
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +93,57 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
Review Comment:
The general idea LGTM, but we should be prepared for the worst case. I think we should fallback to the hash map approach if: 1. `max - min` exceed Int.Max. 2. `max - min` is 50% (or other reasonable ratio) larger than `attrs.length`.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2282179236
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,23 +95,92 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a method that either uses a direct indexed array with the min
+ // and max expression IDs as an offset or a hash map.
+ @transient private lazy val ordinalArrays: (Long => Int, Array[Attribute]) = {
Review Comment:
how about
```
... lazy val exprIdToOrdinal: Long => Int = {
if (attrs.isEmpty) {
exprId => -1
} else if (not overflow and not too parse) {
...
exprId => ...
} else {
... build hash map
exprId => map.getOrElse(exprId, -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: 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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294031548
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
+ ) {
+ (Array.empty[Int], attrs.toArray)
Review Comment:
```suggestion
(Array.empty[Int], Array.empty[Attribute])
```
The fallback case won't use these arrays, so we don't need to waste time converting it to an array.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2288282016
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
- @transient private lazy val exprIdToOrdinal = {
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
+ ) {
+ (Array.empty[Int], attrs.toArray)
+ } else {
+ // Create directly indexed array
+ val arraySize = (maxExprId - minExprId + 1).toInt
+ val ordinalArray = new Array[Int](arraySize)
+ val ordinalAttrsArray = new Array[Attribute](attrs.size)
+ java.util.Arrays.fill(ordinalArray, -1) // -1 indicates no attribute with this ID
+
+ // Populate the array based on expression IDs
+ var i = 0
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ val arrayIndex = (id - minExprId).toInt
+ ordinalArray(arrayIndex) = i
+ ordinalAttrsArray(i) = attr
+ i += 1
+ }
+
+ (ordinalArray, ordinalAttrsArray)
+ }
+ }
+
+ @transient private lazy val exprIdToOrdinal: mutable.LongMap[Int] = {
val arr = attrsArray
- val map = Maps.newHashMapWithExpectedSize[ExprId, Int](arr.length)
- // Iterate over the array in reverse order so that the final map value is the first attribute
- // with a given expression id.
+
+ // Use LongMap to avoid overhead of HashMap while hashing.
+ val map = new mutable.LongMap[Int](_ => -1, arr.length)
+
+ // Iterate over the array in reverse order so that the final map value is the first
+ // attribute with a given expression id.
var index = arr.length - 1
while (index >= 0) {
- map.put(arr(index).exprId, index)
+ map.put(arr(index).exprId.id, index)
index -= 1
}
+
map
}
+ @transient private lazy val exprIdToOrdinalArray: Array[Int] = ordinalArrays._1
+
+
+ // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
Review Comment:
I think this comment shoud belong to https://github.com/apache/spark/pull/52046/files#diff-d5bde7744a0a6c47ac64f41a9638f5841f78d764db61338aa1d8a7d6db790579R127
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -122,7 +180,22 @@ package object expressions {
* Returns the index of first attribute with a matching expression id, or -1 if no match exists.
*/
def indexOf(exprId: ExprId): Int = {
- Option(exprIdToOrdinal.get(exprId)).getOrElse(-1)
+ val id = exprId.id
+
+ // Only use one of array or hash map, trying to use array first if possible
+ if (attrs.isEmpty) {
+ -1
+ }
+ else if (exprIdToOrdinalArray.nonEmpty) {
Review Comment:
```suggestion
} else if (exprIdToOrdinalArray.nonEmpty) {
```
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "arnavgupta03 (via GitHub)" <gi...@apache.org>.
arnavgupta03 commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2284373910
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -122,7 +191,8 @@ package object expressions {
* Returns the index of first attribute with a matching expression id, or -1 if no match exists.
*/
def indexOf(exprId: ExprId): Int = {
- Option(exprIdToOrdinal.get(exprId)).getOrElse(-1)
+ val id = exprId.id
+ exprIdToOrdinal(id)
Review Comment:
Would we still be using lazy evaluation here? If so, the access to `attrsArray` would compute the arrays regardless, right? If not, would we be triggering the first evaluation through some method inside `indexOf`?
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "arnavgupta03 (via GitHub)" <gi...@apache.org>.
arnavgupta03 commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294075519
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
+ ) {
+ (Array.empty[Int], attrs.toArray)
+ } else {
+ // Create directly indexed array
+ val arraySize = (maxExprId - minExprId + 1).toInt
+ val ordinalArray = new Array[Int](arraySize)
+
+ // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
+ // accessing attributes by their ordinals. To avoid this performance penalty, convert
+ // the input to an array.
+ val ordinalAttrsArray = new Array[Attribute](attrs.size)
+ java.util.Arrays.fill(ordinalArray, -1) // -1 indicates no attribute with this ID
+
+ // Populate the array based on expression IDs
+ var i = 0
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ val arrayIndex = (id - minExprId).toInt
+ ordinalArray(arrayIndex) = i
+ ordinalAttrsArray(i) = attr
+ i += 1
+ }
+
+ (ordinalArray, ordinalAttrsArray)
+ }
+ }
- @transient private lazy val exprIdToOrdinal = {
+ @transient private lazy val exprIdToOrdinal: mutable.LongMap[Int] = {
val arr = attrsArray
- val map = Maps.newHashMapWithExpectedSize[ExprId, Int](arr.length)
- // Iterate over the array in reverse order so that the final map value is the first attribute
- // with a given expression id.
+
+ // Use LongMap to avoid overhead of HashMap while hashing.
+ val map = new mutable.LongMap[Int](_ => -1, arr.length)
+
+ // Iterate over the array in reverse order so that the final map value is the first
+ // attribute with a given expression id.
Review Comment:
This is only necessary for the hash map approach since the array is directly indexed so the order we place elements into it shouldn't make a difference.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294056288
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
+ ) {
+ (Array.empty[Int], attrs.toArray)
+ } else {
+ // Create directly indexed array
+ val arraySize = (maxExprId - minExprId + 1).toInt
+ val ordinalArray = new Array[Int](arraySize)
+
+ // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
+ // accessing attributes by their ordinals. To avoid this performance penalty, convert
+ // the input to an array.
+ val ordinalAttrsArray = new Array[Attribute](attrs.size)
+ java.util.Arrays.fill(ordinalArray, -1) // -1 indicates no attribute with this ID
+
+ // Populate the array based on expression IDs
+ var i = 0
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ val arrayIndex = (id - minExprId).toInt
+ ordinalArray(arrayIndex) = i
+ ordinalAttrsArray(i) = attr
+ i += 1
+ }
+
+ (ordinalArray, ordinalAttrsArray)
+ }
+ }
- @transient private lazy val exprIdToOrdinal = {
+ @transient private lazy val exprIdToOrdinal: mutable.LongMap[Int] = {
val arr = attrsArray
- val map = Maps.newHashMapWithExpectedSize[ExprId, Int](arr.length)
- // Iterate over the array in reverse order so that the final map value is the first attribute
- // with a given expression id.
+
+ // Use LongMap to avoid overhead of HashMap while hashing.
+ val map = new mutable.LongMap[Int](_ => -1, arr.length)
+
+ // Iterate over the array in reverse order so that the final map value is the first
+ // attribute with a given expression id.
Review Comment:
Did we follow this semantic in the new array based approach? i.e. when the input attributes have duplicated ExprIds.
--
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-53293][SQL] Modify exprIdToOrdinal implementation for speedup on queries with wide tables [spark]
Posted by "cloud-fan (via GitHub)" <gi...@apache.org>.
cloud-fan commented on code in PR #52046:
URL: https://github.com/apache/spark/pull/52046#discussion_r2294039708
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/package.scala:
##########
@@ -95,24 +95,82 @@ package object expressions {
StructType(attrs.map(a => StructField(a.name, a.dataType, a.nullable, a.metadata)))
}
- // It's possible that `attrs` is a linked list, which can lead to bad O(n) loops when
- // accessing attributes by their ordinals. To avoid this performance penalty, convert the input
- // to an array.
- @transient private lazy val attrsArray = attrs.toArray
+ // Compute min and max expression IDs in a single pass
+ @transient private lazy val minMaxExprId: (Long, Long) = {
+ if (attrs.isEmpty) {
+ (0L, -1L)
+ } else {
+ var min = Long.MaxValue
+ var max = Long.MinValue
+ attrs.foreach { attr =>
+ val id = attr.exprId.id
+ if (id < min) min = id
+ if (id > max) max = id
+ }
+ (min, max)
+ }
+ }
+
+ // Extract as primitive fields to avoid boxing on access
+ @transient private lazy val minExprId: Long = minMaxExprId._1
+ @transient private lazy val maxExprId: Long = minMaxExprId._2
+
+ // Create a directly indexed array with the min and max expression
+ // IDs as an offset.
+ @transient private lazy val ordinalArrays: (Array[Int], Array[Attribute]) = {
+ if (attrs.isEmpty) {
+ (Array.empty[Int], Array.empty[Attribute])
+ } else if (
+ maxExprId - minExprId > Int.MaxValue || // prevent overflow
+ maxExprId - minExprId > 2 * attrs.length // in case of sparse ExprIds
Review Comment:
can we check this condition first? `2 * attrs.length` almost always smaller than `Int.MaxValue`
--
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