java-topology/whitepaper/outreach/cockroach.md

CockroachDB — CWE-407 Disclosure Brief

2026-04-13 · Patches available — awaiting upstream merge

Finding

Three O(n²) defects in CockroachDB across the query optimizer index tracking, fingerprint column filtering, and role membership management. All patched. Patches ready for upstream review. Two defects fire during query planning and execution; one fires during role authorization checks.

The Defects

cockroach-0001 (PATCHED — MEDIUM): pkg/sql/opt/exec/execbuilder/builder.go:197

// In IndexesUsed.add() — fires per index reference during query planning:
func (iu *IndexesUsed) add(tableID, indexID cat.StableID) {
    s := struct {
        tableID cat.StableID
        indexID cat.StableID
    }{tableID, indexID}
    if !slices.Contains(iu.indexes, s) {  // O(I) linear scan
        iu.indexes = append(iu.indexes, s)
    }
}

IndexesUsed.add() tracks which indexes a query plan references. slices.Contains scans the accumulated indexes list for every new addition — O(I) per call. For complex queries referencing many indexes (joins across many tables, union plans), this compounds to O(I²).

cockroach-0002 (PATCHED — MEDIUM): pkg/sql/show_fingerprints.go:432,502

// In BuildExperimentalFingerprintQueryForIndex / BuildFingerprintQueryForIndex:
addColumn := func(col catalog.Column) {
    if slices.Contains(ignoredColumns, col.GetName()) {  // O(G) per column
        return
    }
    // ...
}

Both fingerprint query builders iterate all public columns (C) of a table and call slices.Contains(ignoredColumns, col.GetName()) for each — O(C×G) where G = ignored columns. Tables with many columns and many ignored columns (wide tables in schema migrations) compound the cost.

cockroach-0003 (PATCHED — MEDIUM): pkg/sql/authorization.go:564

// In EnsureUserOnlyBelongsToRoles — fires during role authorization:
for role := range currentRoles {
    if !slices.Contains(roles, role) {  // O(D) linear scan
        rolesToRevoke = append(rolesToRevoke, role)
    }
}

EnsureUserOnlyBelongsToRoles computes the diff between current and desired role memberships. For each current role (R), it scans the desired roles slice (D) with slices.Contains — O(R×D). Fires during role authorization checks and user management operations.

Complexity Proof

cockroach-0001: At I=100 index references per query plan:

• Defective: 100 × (100 / 2) = ~5,000 comparisons
• Fixed: 100 × 1 = 100 map lookups
• 50× op reduction.

cockroach-0002: At C=200 columns, G=50 ignored columns:

• Defective: 200 × 50 = 10,000 comparisons per fingerprint query
• Fixed: 200 × 1 = 200 map lookups
• 50× op reduction.

cockroach-0003: At R=100 current roles, D=100 desired roles:

• Defective: 100 × 100 = 10,000 comparisons
• Fixed: 100 + 100 = 200 operations (map build + probe)
• 50× op reduction.

Impact

CockroachDB powers distributed SQL for thousands of production deployments — from startups to Fortune 500 enterprises. cockroach-0001 fires during query planning for every query that references indexes, which means virtually every query. Complex analytical queries joining many tables accumulate index references rapidly. cockroach-0002 fires during SHOW EXPERIMENTAL_FINGERPRINTS and related fingerprint operations used for backup verification and replication validation — operational queries that run in production. cockroach-0003 fires during role authorization, a security-critical path that runs on user management operations.

The Fix

cockroach-0001: Add a seen map[[2]cat.StableID]struct{} field to IndexesUsed for O(1) dedup. Check the map before appending to the slice.

// Before
if !slices.Contains(iu.indexes, s) { ... }

// After
key := [2]cat.StableID{tableID, indexID}
if _, ok := iu.seen[key]; !ok {
    iu.seen[key] = struct{}{}
    iu.indexes = append(iu.indexes, ...)
}

cockroach-0002: Pre-build a map[string]struct{} from ignoredColumns before the column iteration loop.

cockroach-0003: Pre-build a map[username.SQLUsername]struct{} from the desired roles slice for O(1) membership test.

Patch

Fixes available:

• defects/cockroach/patch/cockroach-0001-indexes-used-add-quadratic.patch
• defects/cockroach/patch/cockroach-0002-fingerprint-ignored-columns-quadratic.patch
• defects/cockroach/patch/cockroach-0003-ensure-roles-quadratic.patch

Three patches across builder.go, show_fingerprints.go, and authorization.go.

What We Ask

Patches ready for review.

1. Confirm receipt and assign a GitHub issue reference (cockroachdb/cockroach).
2. Assess severity — cockroach-0001 fires during query planning; cockroach-0002 fires during fingerprint operations; cockroach-0003 fires during role authorization.
3. Coordinate a disclosure date — we target 90 days from first contact.
4. We will credit the CockroachDB team in the public disclosure. Preferred acknowledgment format welcome.

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