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:
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 of daily partitions, this becomes a real issue: a thread "indefinitely" spins at the following stack trace:
PartitioningUtils.resolvePartitions
- resolvedValues.map(_(index))
- List.apply(index)
- List.drop(index)
- StrictOptimizedLinearSeqOps.loop$2
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).
Versions affected
All recent 4.x versions.
Problem
When discovering partitions over a table with many partition directories (e.g., a table partitioned by date spanning several years),
PartitioningUtils.resolvePartitionsexhibits O(n²) CPU complexity, causing the driver to spin for hours on the affected threads.Root cause
At line 403:
values.zipWithIndex.map { case (d, index) => d.copy(typedValues = resolvedValues.map(_(index))) }resolvedValuesis aSeq[Seq[TypedPartValue]], where each inner collection is a linked list. So theapplymethod 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:
Fix
We could change
resolveTypeConflictsto returnIndexedSeq[TypedPartValue](backed byVector) instead ofSeq.Vector.apply(index)is effectively O(1), reducing the overall complexity to O(nk).Versions affected
All recent 4.x versions.