# UNDF: UNDF-2026-000000379
# django-0006: remove_from_added / remove_from_removed lists → sets in create_altered_indexes()

## Severity
MEDIUM

## Location
`django/db/migrations/autodetector.py` — `create_altered_indexes()`

## Description
`remove_from_added` and `remove_from_removed` are built as plain `list`s and
appended to inside a double `for new_index / for old_index` loop.  At the end,
two list-comprehension filters test `idx not in remove_from_added` and
`idx not in remove_from_removed` by scanning those lists linearly.

Worst-case per model: I added indexes × I removed indexes inner loop
produces up to I entries in each removal list; the two final comprehensions
then scan them O(I) per candidate → O(I²) total per model, O(N × I²) overall.

In a large monorepo with many indexes per model the autodetector fires on
every `makemigrations` invocation.

## Defective code (lines 1394–1456)
```python
remove_from_added = []              # ← plain list
remove_from_removed = []            # ← plain list
for new_index in added_indexes:
    ...
    for old_index in removed_indexes:
        ...
        if ...:
            remove_from_added.append(new_index)    # ← appended
            remove_from_removed.append(old_index)  # ← appended

added_indexes = [
    idx for idx in added_indexes if idx not in remove_from_added    # ← O(R) scan
]
removed_indexes = [
    idx for idx in removed_indexes if idx not in remove_from_removed  # ← O(R) scan
]
```

## Fix
```diff
--- a/django/db/migrations/autodetector.py
+++ b/django/db/migrations/autodetector.py
@@ -1394,8 +1394,8 @@ class MigrationAutodetector:
-            remove_from_added = []
-            remove_from_removed = []
+            remove_from_added = set()
+            remove_from_removed = set()
 ...
-                        remove_from_added.append(new_index)
-                        remove_from_removed.append(old_index)
+                        remove_from_added.add(new_index)
+                        remove_from_removed.add(old_index)
```

## Complexity
- Before: O(N × I² × I) = O(N × I³)  (index objects must be hashable — they implement __hash__ via Index.name)
- After:  O(N × I²) — membership tests drop to O(1)
