[
https://issues.apache.org/jira/browse/SPARK-58100?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Cheng Pan resolved SPARK-58100.
-------------------------------
Fix Version/s: 4.0.5
4.1.4
4.2.1
4.3.0
Resolution: Fixed
Issue resolved by pull request 57243
[https://github.com/apache/spark/pull/57243]
> CPU burn in PartitioningUtils.resolvePartitions for large numbers of
> partition directories
> ------------------------------------------------------------------------------------------
>
> Key: SPARK-58100
> URL: https://issues.apache.org/jira/browse/SPARK-58100
> Project: Spark
> Issue Type: Bug
> Components: SQL
> Affects Versions: 4.1.2, 4.0.3
> Reporter: Daniil Filippov
> Priority: Major
> Labels: pull-request-available
> Fix For: 4.0.5, 4.1.4, 4.2.1, 4.3.0
>
>
> h3. Problem
> When discovering partitions over a table with many partition directories
> (e.g., a table partitioned by date spanning several years),
> {{PartitioningUtils.resolvePartitions}} exhibits O(n²) CPU complexity,
> causing the driver to spin for hours on the affected threads.
> h3. Root cause
> At line 403:
> {code:scala}
> values.zipWithIndex.map { case (d, index) =>
> d.copy(typedValues = resolvedValues.map(_(index)))
> }
> {code}
> {{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:
> {code:java}
> PartitioningUtils.resolvePartitions
> - resolvedValues.map(_(index))
> - List.apply(index)
> - List.drop(index)
> - StrictOptimizedLinearSeqOps.loop$2
> {code}
> h3. Fix
> We could change {{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).
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
