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: [email protected]
For additional commands, e-mail: [email protected]
