Why Spark’s compatiblePartitions Causes CPU Spikes and How to Fix It

At the beginning of the year a client reported abnormal CPU usage on a server; remote debugging revealed that the Spark driver was consuming most of the CPU. Using

jstack

the problematic threads were identified as executing a rule called "transpose window" within the method

compatiblePartitions

.

<code>private def compatiblePartitions(ps1: Seq[Expression], ps2: Seq[Expression]): Boolean = {
  ps1.length < ps2.length && ps2.take(ps1.length).permutations.exists(
    ps1.zip(_).forall {
      case (l, r) => l.semanticEquals(r)
    })
}
</code>

The method uses

permutations

, which generates all permutations of an array. For an array of n distinct elements this results in n! possibilities, leading to O(n!) time complexity and potentially causing the observed CPU spikes.

Monitoring showed a step‑wise increase in driver CPU, corresponding to the submission times of tasks involving window functions. An ETL job was identified where each run added an extra CPU core that was not released. The ETL’s logic was simplified to two window‑function calculations with many

PARTITION BY

fields, and reproduced in

spark-shell

:

<code>val df = spark.range(10).selectExpr(
  "id AS a1", "id AS a2", "id AS a3", "id AS a4", "id AS a5", "id AS a6", "id AS a7", "id AS a8", "id AS a9", "id AS a10", "id AS a11", "id AS a12", "id AS a13", "id AS a14", "id AS a15", "id AS a16")

df.selectExpr(
  "sum(`a16`) OVER(PARTITION BY `a1`,`a2`,`a3`,`a4`,`a5`,`a6`,`a7`,`a8`,`a9`,`a10`,`a11`,`a12`,`a13`,`a14`,`a15`) as p1",
  "sum(`a16`) OVER(PARTITION BY `a14`,`a2`,`a3`,`a4`,`a5`,`a6`,`a7`,`a8`,`a9`,`a10`,`a11`,`a12`,`a13`,`a1`) as p2"
).explain
</code>

Running this code on Spark 3.0+ makes the shell hang exactly at the

compatiblePartitions

method, confirming that the permutation‑based check is the bottleneck.

To avoid the exponential cost, a new implementation was proposed that checks compatibility by ensuring every expression in the first partition list exists in the second list, without generating permutations:

<code>private def compatiblePartitions(ps1: Seq[Expression], ps2: Seq[Expression]): Boolean = {
  ps1.length < ps2.length && ps1.forall { expr1 =>
    ps2.exists(expr1.semanticEquals)
  }
}
</code>

This version eliminates the heavy permutation step, reduces complexity, and broadens the cases where transpose window optimization can be applied.

The change was submitted to the Apache Spark community, referenced in SPARK-38034 and merged via PR 35334 . After the merge, upgrading to the official Spark release resolves the CPU issue without further intervention.

Thus, by simplifying the compatibility check, the Spark driver no longer suffers from O(n!) CPU spikes when processing window functions with many partition columns.