Fixed #25892 -- Optimized SeparateDatabaseAndState.database_backwards().

Now intermediate states in the database_backwards are cached, similar to
the executor's migrate() (or _migrate_all_backwards()). This makes the
migration run much faster (O(n) instead of O(n^2) over number of
database_operations).

1 files changed, 11 insertions, 7 deletions

diff --git a/django/db/migrations/operations/special.py b/django/db/migrations/operations/special.py
index 6bbae602db..95da11f5d2 100644
--- a/django/db/migrations/operations/special.py
+++ b/django/db/migrations/operations/special.py
@@ -45,13 +45,17 @@ class SeparateDatabaseAndState(Operation):
 
     def database_backwards(self, app_label, schema_editor, from_state, to_state):
         # We calculate state separately in here since our state functions aren't useful
-        base_state = to_state
-        for pos, database_operation in enumerate(reversed(self.database_operations)):
-            to_state = base_state.clone()
-            for dbop in self.database_operations[:-(pos + 1)]:
-                dbop.state_forwards(app_label, to_state)
-            from_state = to_state.clone()
-            database_operation.state_forwards(app_label, from_state)
+        to_states = {}
+        for dbop in self.database_operations:
+            to_states[dbop] = to_state
+            to_state = to_state.clone()
+            dbop.state_forwards(app_label, to_state)
+        # to_state now has the states of all the database_operations applied
+        # which is the from_state for the backwards migration of the last
+        # operation.
+        for database_operation in reversed(self.database_operations):
+            from_state = to_state
+            to_state = to_states[database_operation]
             database_operation.database_backwards(app_label, schema_editor, from_state, to_state)
 
     def describe(self):