Fixed #36869 -- Optimized MigrationGraph._generate_plan membership checks.

Previously, `_generate_plan()` relied on list membership checks,
resulting in quadratic behavior as the plan grew. On large migration
graphs this became a significant performance bottleneck.

This change uses `OrderedSet` for the plan, reducing the complexity to
linear while preserving insertion order and behavior.

Co-authored-by: Nick Pope <nick@nickpope.me.uk>

1 files changed, 4 insertions, 3 deletions

diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index ff5ecbc8b4..cc06dde11f 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -1,6 +1,7 @@
 from functools import total_ordering
 
 from django.db.migrations.state import ProjectState
+from django.utils.datastructures import OrderedSet
 
 from .exceptions import CircularDependencyError, NodeNotFoundError
 
@@ -305,12 +306,12 @@ class MigrationGraph:
         )
 
     def _generate_plan(self, nodes, at_end):
-        plan = []
+        plan = OrderedSet()
         for node in nodes:
             for migration in self.forwards_plan(node):
                 if migration not in plan and (at_end or migration not in nodes):
-                    plan.append(migration)
-        return plan
+                    plan.add(migration)
+        return list(plan)
 
     def make_state(self, nodes=None, at_end=True, real_apps=None):
         """