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

["Daniil Filippov (Jira)" <ji...@apache.org>]

Daniil Filippov created SPARK-58100:
---------------------------------------

             Summary: 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.0.3, 4.1.2
            Reporter: Daniil Filippov


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