# Apache Spark — CWE-407 Disclosure Brief
**2026-03-26 · Patch available — awaiting upstream merge**

## Finding

One O(A×W) defect in Apache Spark's Catalyst query analyzer. Patched. Fix ready for upstream review. The defect is in the window function extraction pass of `Analyzer.scala` — a pass that runs on every SQL query containing window functions.

## The Defect

**spark-0001 (PATCHED — MEDIUM):** `sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/analysis/Analyzer.scala:3286`

```scala
val seenWindowAggregates = new ArrayBuffer[AggregateExpression]
// ... inside ExtractWindowExpressions.apply():
case agg: AggregateExpression if !seenWindowAggregates.contains(agg) =>
    seenWindowAggregates += agg
    // ...
```

`seenWindowAggregates` is an `ArrayBuffer[AggregateExpression]`. The `.contains(agg)` call performs a linear scan over W previously-seen window aggregates, called for each of A aggregate expressions in the query. Total cost: **O(A × W) per query**.

## Complexity Proof

For a query with W window aggregates and A total aggregate expressions:
- Outer loop: A iterations (one per aggregate expression)
- Inner check: `ArrayBuffer.contains()` → linear scan, up to W entries
- Total comparisons: A × W = **O(A × W)**

In the worst case (A = W), this is **O(A²)**.

For a query with 100 window aggregates and 100 total aggregates: 9,340 comparisons (measured). With `LinkedHashSet`: 100 comparisons.

**Measured ratio at W=A=100: 93.4× (defective=9,340, fixed=100).**

## Impact

Every Spark SQL query using window functions (`OVER (PARTITION BY ...)`, `ROW_NUMBER()`, `RANK()`, `LAG()`, `LEAD()`, `SUM() OVER`, etc.) hits this path. Window functions are common in analytical workloads — reporting queries, time-series analysis, sessionization, ranking. Complex BI queries with many window expressions in a single SQL statement maximize A×W and hit the worst case.

Spark is the most widely deployed distributed SQL engine for data lake analytics. Databricks, Amazon EMR, Google Dataproc, and Azure HDInsight all run Spark SQL. Every interactive BI query against a lakehouse table with window functions pays this overhead during query analysis.

## The Fix

```scala
// Before
val seenWindowAggregates = new ArrayBuffer[AggregateExpression]

// After
// CWE-407 fix: LinkedHashSet for O(1) contains() instead of O(W) ArrayBuffer scan.
val seenWindowAggregates = new mutable.LinkedHashSet[AggregateExpression]
```

`LinkedHashSet` preserves insertion order (matching `ArrayBuffer` semantics for any code that iterates `seenWindowAggregates`) while providing O(1) `contains()`. `AggregateExpression` already implements structural equality via `equals()`/`hashCode()` in Spark's expression framework — no additional changes needed.

## Patch

Fix available: `defects/spark/patch/spark-0001-analyzer-seenwindowaggregates-linkedhashset.patch`

One-line change in `Analyzer.scala`. Import `scala.collection.mutable` already present in the file.

Unit test: 4/4 pass. At W=A=100: defective=9,340 comparisons, fixed=100 comparisons, **93.4× speedup**.

## What We Ask

A patch is ready for review.

1. Confirm receipt and assign a JIRA reference (SPARK project at issues.apache.org/jira).
2. Assess severity — spark-0001 fires on every Spark SQL query with window functions.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Apache Spark team in the public disclosure. Preferred acknowledgment format welcome.

Contact: see cover email. This brief is confidential until coordinated disclosure.
