flipp5b opened a new issue, #57220:
URL: https://github.com/apache/spark/issues/57220
### 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.
### Root cause
At line 403:
```scala
values.zipWithIndex.map { case (d, index) =>
d.copy(typedValues = resolvedValues.map(_(index)))
}
```
`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 daily partitions and 3 partition columns, this becomes a real
issue: threads look stucked .
Stack trace (observed)
PartitioningUtils.resolvePartitions (line 403)
→ resolvedValues.map(_(index))
→ List.apply(index)
→ List.drop(index)
→ StrictOptimizedLinearSeqOps.loop$2 ← spinning here
### Fix
Change resolveTypeConflicts to return IndexedSeq[TypedPartValue] (backed by
Vector) instead of Seq. Vector.apply(index) is O(effectively 1), reducing the
overall complexity to O(n × k).
// Before
private def resolveTypeConflicts(typedValues: Seq[TypedPartValue]):
Seq[TypedPartValue] = {
val desiredType =
typedValues.map(_.dataType).reduce(findWiderTypeForPartitionColumn)
typedValues.map(tv => tv.copy(dataType = desiredType))
}
// After
private def resolveTypeConflicts(typedValues: Seq[TypedPartValue]):
IndexedSeq[TypedPartValue] = {
val desiredType =
typedValues.map(_.dataType).reduce(findWiderTypeForPartitionColumn)
typedValues.view.map(tv => tv.copy(dataType = desiredType)).toIndexedSeq
}
The call site also needs a type annotation to preserve the IndexedSeq
element type at compile time:
val resolvedValues: Seq[IndexedSeq[TypedPartValue]] = (0 until
columnCount).map { i =>
resolveTypeConflicts(values.map(_.typedValues(i)))
}
### How to reproduce
Run a Spark SQL job that reads a Parquet table with 2,000+ date partitions.
Monitor the driver with a thread dump — all partition-discovery threads will be
stuck in StrictOptimizedLinearSeqOps.loop$2 and the job will not progress.
Impact
•
Driver CPU pegged at 100% for hours
•
Partition discovery never completes; job hangs indefinitely
•
Affects any table with O(thousands) of partition directories (common for
date-partitioned production tables)
Versions affected
All versions containing resolvePartitions in PartitioningUtils with a
Seq-typed return from resolveTypeConflicts.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
