# UNDF: UNDF-2026-000000577
# yugabyte-0001 — GetXReplStreamsForTable: std::find on table_id list inside per-table loop

**Project:** YugabyteDB
**File:** `src/yb/master/xrepl_catalog_manager.cc`
**Function:** `GetXReplStreamsForTable` / `DropXClusterStreamsOfTables`
**Severity:** HIGH
**CWE:** CWE-407 (Inefficient Algorithmic Complexity)

## Defect

`GetXReplStreamsForTable` iterates over the entire `cdc_stream_map_` (M streams), and
for each stream performs `std::find` on `ltm->table_id()` — a protobuf repeated field
backed by a `RepeatedPtrField` which is a linear array of string IDs (T entries):

```cpp
std::vector<CDCStreamInfoPtr> CatalogManager::GetXReplStreamsForTable(
    const TableId& table_id, ...) const {
  std::vector<CDCStreamInfoPtr> streams;
  for (const auto& entry : cdc_stream_map_) {            // O(M) — all streams
    auto ltm = entry.second->LockForRead();
    if (!ltm->table_id().empty() &&
        (std::find(ltm->table_id().begin(), ltm->table_id().end(), table_id)  // O(T)
             != ltm->table_id().end()) && ...) {
      streams.push_back(entry.second);
    }
  }
  return streams;
}
```

`DropXClusterStreamsOfTables` calls this function inside a loop over all dropped
table IDs (D tables):

```cpp
for (const auto& tid : table_ids) {           // O(D)
    auto table_streams = GetXReplStreamsForTable(tid, cdc::XCLUSTER);  // O(M × T)
    streams.insert(...);
}
```

Total: **O(D × M × T)** where:
- D = number of dropped tables (can be the full table set during schema migration)
- M = total CDC/XCluster streams (grows with replication topology)
- T = tables tracked per stream (grows with multi-table replication)

This is cubic in the worst case. At D=100 tables, M=50 streams, T=20 tables/stream,
that is 100,000 string comparisons where 100 would suffice.

The same pattern appears at lines 2044–2049 (AddTableToXReplStream) and 2162
(GetNonUserTablesInStream), compounding the impact.

## Fix

Build an inverted index from `TableId → set<CDCStreamInfoPtr>` once (on load and on
stream creation/deletion) and perform O(1) lookups instead of O(M×T) full scans.

Alternatively, for the `DropXClusterStreamsOfTables` hot path, batch all table IDs
and iterate `cdc_stream_map_` once:

```cpp
Status CatalogManager::DropXClusterStreamsOfTables(
    const std::unordered_set<TableId>& table_ids) {
  if (table_ids.empty()) return Status::OK();

  std::vector<CDCStreamInfoPtr> streams;
  {
    SharedLock lock(mutex_);
    for (const auto& [_, stream_info] : cdc_stream_map_) {   // O(M) — one pass
      auto ltm = stream_info->LockForRead();
      if (ltm->is_deleting() || ltm->namespace_id().empty()) continue;
      // O(T) per stream but only one pass over M streams total
      for (const auto& tid : ltm->table_id()) {
        if (table_ids.count(tid)) {                           // O(1) hash lookup
          streams.push_back(stream_info);
          break;
        }
      }
    }
  }
  ...
}
```

With this pattern: **O(M × T)** total instead of **O(D × M × T)**.
For the long-term fix, maintain a `std::unordered_multimap<TableId, CDCStreamInfoPtr>`
as a secondary index, giving O(D) lookup.

## Impact

During table drops in a namespace with active CDC streams, the master leader stalls
proportionally to D×M×T. In a large multi-tenant deployment with hundreds of tables
and dozens of replication streams each tracking tens of tables, this causes
multi-second stalls in master processing, delaying tablet cleanup and potentially
triggering master step-down timeouts.

## Location

```
src/yb/master/xrepl_catalog_manager.cc
  GetXReplStreamsForTable()          lines 790–814
  DropXClusterStreamsOfTables()      lines 606–618 (calls GetXReplStreamsForTable in loop)
  AddTableToXReplStream()            lines 2029–2050 (same pattern)
  GetNonUserTablesInStream context   lines 2154–2165 (same pattern)
```
