id	summary	reporter	owner	description	type	status	component	version	severity	resolution	keywords	cc	stage	has_patch	needs_docs	needs_tests	needs_better_patch	easy	ui_ux
36869	Optimise migration graph planning	James Fysh	nessita <124304+nessita@…>	"When django needs to work with migrations - making & applying migrations, running checks - it loads available migrations from disk and builds up an in-memory digraph.

The django project that I work on has managed to accumulate a large number of django apps and associated migrations.  I'm going to leave the obvious discussion around migration squashing out of this - let's just assume it is not practical to do in the near term.

Anecdotally, starting the django application, eg. when running management commands or simply launching the server is noticeably slow.  Profiling has revealed that a significant portion of startup time is spent running migration checks.

To cut a long story short, MigrationGraph._generate_plan() currently runs in O(n*n), and with a ~3 line patch we can reduce this to O(n).

For small django projects I believe this will not result in any change in performance.  For large projects such as ours, this can result in a very significant reduction in startup time.  Given the nature of the change (simple and arguably low-risk) I think it would be a reasonable change to make."	Cleanup/optimization	closed	Database layer (models, ORM)	dev	Normal	fixed	migration digraph loader	Nick Pope	Ready for checkin	1	0	0	0	0	0