# UNDF: UNDF-2026-000000524
# rocksdb-001: LockInfo.txn_ids linear scan — O(T²) shared-lock churn

## Severity: HIGH

## File
`utilities/transactions/lock/point/point_lock_manager.cc`

## Defect

`LockInfo::txn_ids` is an `autovector<TransactionID>` (default 8 inline slots, grows
to heap). Three hot-path functions perform `std::find()` — O(T) linear scan — over
this vector, where T = number of concurrent transactions sharing a read lock on
a single key:

| Line | Function | Call site |
|------|----------|-----------|
| 791  | `PointLockManager::UnLockKey` | called in a loop over all keys held by the unlocking txn |
| 1513 | `PerKeyPointLockManager::AcquireLocked` | shared-lock reentrant check |
| 1706 | `PerKeyPointLockManager::UnLockKey` | called in a loop over all keys held by the unlocking txn |

### Complexity

- Per-key unlock: O(T) scan — T concurrent readers per key
- Per-transaction unlock: O(K × T) — K keys in the transaction, T readers per key
- Under high shared-lock concurrency (OLAP, batch reads, read-committed workloads):
  T can reach hundreds; K can be thousands per transaction
- Overall unlock path becomes O(K × T) = O(N²) in the worst case

### Root cause

```cpp
struct LockInfo {
  autovector<TransactionID> txn_ids;   // ← vector, not set
  ...
};

// In UnLockKey (both lock managers):
auto txn_it = std::find(txns.begin(), txns.end(), txn_id);  // O(T)

// In PerKeyPointLockManager::AcquireLocked:
auto lock_it = std::find(lock_info.txn_ids.begin(),
                         lock_info.txn_ids.end(), my_txn_id); // O(T)
```

## Fix

Replace `autovector<TransactionID> txn_ids` with
`std::unordered_set<TransactionID> txn_ids`.

- `find()` becomes O(1) average
- `push_back()` → `insert()`
- `erase(iterator)` → `erase(value)` (the RemoveTransaction helper disappears)
- `txn_ids[0]` → `*txn_ids.begin()` (exclusive lock path already asserts size==1)
- Iteration in FillWaitIds / deadlock detection remains O(T) — unchanged

## Speedup

Benchmark (unit test): T=1000 concurrent readers, K=1 key unlock
- Slow path (autovector + std::find): O(T) = 1000 ops per unlock
- Fast path (unordered_set): O(1) = 1 op per unlock
- Speedup: ~1000x at T=1000

## Status: PATCHED (unit test)
