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

## Finding

Eight O(n²) defects in TiDB's query planner. All use `slices.Contains` on slices in hot paths across merge join, predicate simplification, join key deduplication, partition pruning, aggregate pushdown, index merge path selection, and expression rewriting. Measured at 188× each. Patches ready for upstream review.

## The Defects

All eight defects follow the same pattern in `planner/core/`:

**tidb-0001:** `slices.Contains` on merge join key offsets in `getEnforcedMergeJoin()` — O(n) per join key check.

**tidb-0002:** `slices.Contains` in `mergeInAndNotEQLists removeValues` — O(N²) predicate simplification.

**tidb-0003:** `slices.Contains` in join key deduplication paths — O(n) per duplicate check.

**tidb-0004:** `slices.Contains` in predicate simplification — O(n) per predicate per simplification step.

**tidb-0005:** `slices.Contains` in partition pruning — O(n) per partition per prune step.

**tidb-0006:** `slices.Contains` in aggregate pushdown — O(n) per aggregate per pushdown.

**tidb-0007:** `slices.Contains` in index merge path selection — O(n) per path per merge step.

**tidb-0008:** `slices.Contains` in expression rewriter — O(n) per expression per rewrite.

All located in `planner/core/` package. **Measured ratio: 188× at each site.**

## Complexity Proof

For N=188 entries per slice at each site:
- `slices.Contains`: O(N) linear scan
- Fixed: `map[type]struct{}` → O(1) per check
- 8 sites × 188× = compounding query planning overhead
- **188× measured ratio** at each individual site.

## Impact

All TiDB deployments. TiDB is a distributed, MySQL-compatible NewSQL database used in large-scale OLAP/OLTP workloads at major technology companies. All eight defects fire during query planning — which runs on every SQL statement. Complex analytical queries that exercise merge joins, predicates, partition pruning, and aggregate pushdown activate multiple defects simultaneously.

## The Fix

Replace `slices.Contains` with `map[T]struct{}` at all eight sites in `planner/core/`:

```go
// Before (representative — all 8 sites follow this pattern)
if slices.Contains(keyOffsets, offset) { ... }  // O(n)

// After
// CWE-407 fix: map[int]struct{} for O(1) contains instead of O(n) slices.Contains.
if _, ok := keyOffsetSet[offset]; ok { ... }
```

## Patch

`defects/tidb/patch/tidb-0001-through-0008-planner-slices-map.patch`

## What We Ask

1. Confirm receipt and assign a GitHub Security Advisory or issue reference.
2. Validate the patch against your query planner test suite.
3. Assess CVE eligibility — all 8 defects fire during query planning with a 188× overhead each.
4. Coordinate a disclosure date — we are targeting 90 days from first contact.

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