[
https://issues.apache.org/jira/browse/SPARK-58100?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Daniil Filippov updated SPARK-58100:
------------------------------------
Description:
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).
was:
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).
> 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
>
> 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]
