[jira] [Resolved] (SPARK-58100) CPU burn in PartitioningUtils.resolvePartitions for large numbers of partition directories

["Cheng Pan (Jira)" <ji...@apache.org>]

     [ 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: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org