From 980dfca7174a3e00a214ad554bb9199529139796 Mon Sep 17 00:00:00 2001 From: Marten Kenbeek Date: Fri, 20 Feb 2015 05:43:45 +0100 Subject: [1.8.x] Fixed #24366 -- Optimized traversal of large migration dependency graphs. Switched from an adjancency list and uncached, iterative depth-first search to a Node-based design with direct parent/child links and a cached, recursive depth-first search. With this change, calculating a migration plan for a large graph takes several seconds instead of several hours. Marked test `migrations.test_graph.GraphTests.test_dfs` as an expected failure due to reaching the maximum recursion depth. Backport of 78d43a5e1064b63db1c486516c4263ef1c4c975c from master --- django/db/migrations/executor.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'django/db/migrations/executor.py') diff --git a/django/db/migrations/executor.py b/django/db/migrations/executor.py index d1a8dd64dc..57b1e297a5 100644 --- a/django/db/migrations/executor.py +++ b/django/db/migrations/executor.py @@ -47,7 +47,7 @@ class MigrationExecutor(object): # child(ren) in the same app, and no further. next_in_app = sorted( n for n in - self.loader.graph.dependents.get(target, set()) + self.loader.graph.node_map[target].children if n[0] == target[0] ) for node in next_in_app: -- cgit v1.3