[1.8.x] Fixed #24554 -- Sped up migrations by rendering initial apps when they are first needed

Calling Migration.mutate_state() now also allows to do in_place
mutations in case an intermediate state is thrown away later.

Thanks Anssi Kääriäinen for the idea, Ryan Hall for parts of the patch,
and Claude Paroz and Tim Graham for the review

Backport of 57dc8dd3fa3c3adf133c522ecadb501d94bacd52 from master

4 files changed, 28 insertions, 11 deletions

diff --git a/django/db/migrations/executor.py b/django/db/migrations/executor.py
index 57b1e297a5..d1da524aeb 100644
--- a/django/db/migrations/executor.py
+++ b/django/db/migrations/executor.py
@@ -74,20 +74,27 @@ class MigrationExecutor(object):
         migrations_to_run = {m[0] for m in plan}
         # Create the forwards plan Django would follow on an empty database
         full_plan = self.migration_plan(self.loader.graph.leaf_nodes(), clean_start=True)
-        # Holds all states right before and right after a migration is applied
+        # Holds all states right before a migration is applied
         # if the migration is being run.
         states = {}
         state = ProjectState(real_apps=list(self.loader.unmigrated_apps))
         if self.progress_callback:
             self.progress_callback("render_start")
-        state.apps  # Render all real_apps -- performance critical
-        if self.progress_callback:
-            self.progress_callback("render_success")
-        # Phase 1 -- Store all required states
+        # Phase 1 -- Store all project states of migrations right before they
+        # are applied. The first migration that will be applied in phase 2 will
+        # trigger the rendering of the initial project state. From this time on
+        # models will be recursively reloaded as explained in
+        # `django.db.migrations.state.get_related_models_recursive()`.
         for migration, _ in full_plan:
-            if migration in migrations_to_run:
+            do_run = migration in migrations_to_run
+            if do_run:
+                if 'apps' not in state.__dict__:
+                    state.apps  # Render all real_apps -- performance critical
                 states[migration] = state.clone()
-            state = migration.mutate_state(state)  # state is cloned inside
+            # Only preserve the state if the migration is being run later
+            state = migration.mutate_state(state, preserve=do_run)
+        if self.progress_callback:
+            self.progress_callback("render_success")
         # Phase 2 -- Run the migrations
         for migration, backwards in plan:
             if not backwards:
diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index 250c11351d..b47c768de8 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -228,7 +228,7 @@ class MigrationGraph(object):
                     plan.append(migration)
         project_state = ProjectState(real_apps=real_apps)
         for node in plan:
-            project_state = self.nodes[node].mutate_state(project_state)
+            project_state = self.nodes[node].mutate_state(project_state, preserve=False)
         return project_state
 
     def __contains__(self, node):
diff --git a/django/db/migrations/migration.py b/django/db/migrations/migration.py
index 1c3f560d6e..1e84429e9b 100644
--- a/django/db/migrations/migration.py
+++ b/django/db/migrations/migration.py
@@ -69,12 +69,16 @@ class Migration(object):
     def __hash__(self):
         return hash("%s.%s" % (self.app_label, self.name))
 
-    def mutate_state(self, project_state):
+    def mutate_state(self, project_state, preserve=True):
         """
         Takes a ProjectState and returns a new one with the migration's
-        operations applied to it.
+        operations applied to it. Preserves the original object state by
+        default and will return a mutated state from a copy.
         """
-        new_state = project_state.clone()
+        new_state = project_state
+        if preserve:
+            new_state = project_state.clone()
+
         for operation in self.operations:
             operation.state_forwards(self.app_label, new_state)
         return new_state
diff --git a/django/db/migrations/state.py b/django/db/migrations/state.py
index 7c5f9ed776..136b63ae8e 100644
--- a/django/db/migrations/state.py
+++ b/django/db/migrations/state.py
@@ -35,6 +35,12 @@ def get_related_models_recursive(model):
     """
     Returns all models that have a direct or indirect relationship
     to the given model.
+
+    Relationships are either defined by explicit relational fields, like
+    ForeignKey, ManyToManyField or OneToOneField, or by inheriting from another
+    model (a superclass is related to its subclasses, but not vice versa). Note,
+    however, that a model inheriting from a concrete model is also related to
+    its superclass through the implicit *_ptr OneToOneField on the subclass.
     """
     def _related_models(m):
         return [