flipp5b opened a new pull request, #57243:
URL: https://github.com/apache/spark/pull/57243
### What changes were proposed in this pull request?
The PR makes `resolveTypeConflicts` to return `IndexedSeq[TypedPartValue]`
(backed by `Vector`) instead of `Seq`. `Vector.apply(index)` is effectively
O(1), reducing the overall complexity to O(nk).
### Why are the changes needed?
For now, `resolvedValues` is a `Seq[Seq[TypedPartValue]]`, where each inner
collection is a linked list. So the `apply` method called there is O(n). This
is called for every partition and every column, making the total complexity
O(n²k), where n = number of partitions and k = number of partition columns.
With thousands of daily partitions, this becomes a real issue: a thread
"indefinitely" spins at the following stack trace:
```
PartitioningUtils.resolvePartitions
- resolvedValues.map(_(index))
- List.apply(index)
- List.drop(index)
- StrictOptimizedLinearSeqOps.loop$2
```
### Does this PR introduce _any_ user-facing change?
No
### How was this patch tested?
Benchmarks were added, see
PartitioningUtilsResolvePartitionsBenchmark-after-fix-jdk21-results.txt,
PartitioningUtilsResolvePartitionsBenchmark-before-fix-jdk21-results.txt
### Was this patch authored or co-authored using generative AI tooling?
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
