#26407: Investigate applying transitive reduction to migration graph.
-------------------------------------+-------------------------------------
Reporter: jarekwg | Owner: nobody
Type: | Status: new
Cleanup/optimization |
Component: Migrations | Version: master
Severity: Normal | Resolution:
Keywords: transitive | Triage Stage: Accepted
reduction showmigrations |
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Comment (by MarkusH):
The following simple implementation does not scale for more than ~ 50 to
100 nodes:
{{{#!diff
diff --git a/django/db/migrations/graph.py b/django/db/migrations/graph.py
index 1a7a703..28ed208 100644
--- a/django/db/migrations/graph.py
+++ b/django/db/migrations/graph.py
@@ -260,6 +260,26 @@ class MigrationGraph(object):
"""
[n.raise_error() for n in self.node_map.values() if isinstance(n,
DummyNode)]
+ def reduce(self):
+ for xkey, xnode in six.iteritems(self.node_map):
+ # print('xkey: %s' % (xkey,))
+ for ykey, ynode in six.iteritems(self.node_map):
+ # print('ykey: %s' % (ykey,))
+ if xkey == ykey:
+ continue
+ for zkey, znode in six.iteritems(self.node_map):
+ # print('zkey: %s' % (zkey,))
+ if xkey == zkey or ykey == zkey:
+ continue
+ if znode in xnode.children and ynode in
xnode.children and znode in ynode.children:
+ print("rm %(xkey)s -> %(zkey)s : %(xkey)s ->
%(ykey)s -> %(zkey)s" % {
+ 'xkey': xkey,
+ 'ykey': ykey,
+ 'zkey': zkey,
+ })
+ xnode.children.discard(znode)
+ znode.parents.discard(xnode)
+
def clear_cache(self):
if self.cached:
for node in self.nodes:
@@ -278,6 +298,7 @@ class MigrationGraph(object):
raise NodeNotFoundError("Node %r not a valid node" % (target,
), target)
# Use parent.key instead of parent to speed up the frequent
hashing in ensure_not_cyclic
self.ensure_not_cyclic(target, lambda x: (parent.key for parent
in self.node_map[x].parents))
+ self.reduce()
self.cached = True
node = self.node_map[target]
try:
@@ -298,6 +319,7 @@ class MigrationGraph(object):
raise NodeNotFoundError("Node %r not a valid node" % (target,
), target)
# Use child.key instead of child to speed up the frequent hashing
in ensure_not_cyclic
self.ensure_not_cyclic(target, lambda x: (child.key for child in
self.node_map[x].children))
+ self.reduce()
self.cached = True
node = self.node_map[target]
try:
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/26407#comment:2>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.
--
You received this message because you are subscribed to the Google Groups
"Django updates" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/django-updates/065.9ebbf504d287d6ecc246a5838ede9c78%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.
