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
26407	Investigate applying transitive reduction to migration graph.	Jarek Glowacki	nobody	"This stemmed from a discussion between @markush and myself in [https://github.com/django/django/pull/6254].

We should investigate migration loading performance for the following:
- Requiring the migration graph to always have the minimum number of edges. This would mean enforcing transitive reduction whenever a new edge is added. This would be a trade off between the additional computation to ensure the graph is minimal versus the reduced computation in traversing the graph for ancestors/descendants/etc.
- Performing a single transitive reduction step once the graph has been built. Again, this would be to simplify any later traversal.

Closely related to this is the `showmigrations` command, with the `--plan` flag at verbosity 2. This adds a lists of migration dependencies in brackets next to every migration in the plan. Currently each list of dependencies is constructed from the original `Migration` object's `dependencies` list, with:
- appropriate replacements made for migrations that have been replaced by squash migrations, and
- additional dependencies added based on any `run_before` declarations.
So what this shows is the list of dependencies, somewhat rawly, as set by the user in their migration files. If the user declares redundant dependencies, then these bleed into the migration graph, which propagates to the list of dependencies printed by `showmigrations`. The question is what do we want it to show? This raw list may help the user with debugging, but it could get cluttered if there is an abundance of superfluous dependencies. So what we could do is print dependencies that come from the migration graph after it has been transitively reduced. This would improve the brevity, though whether it would be helpful to the user is up for debate. We could also try using both reduced and unreduced migration graphs to emphasise superfluous dependencies to the user.

TLDR:
1) Investigate migration performance with transitive reduction:
- at every edge addition
- after graph is built

2) Decide what would be most useful to list for `showmigrations --plan -v2`:
- [current] Raw dependencies (with changes to account for replacements and `run_before`).
- Only critical dependencies (by using reduced graph).
- Raw dependencies with superfluous edges somehow emphasised.

To be clear, I don't see a problem with the current system, but thought this might be worth investigating/discussing."	Cleanup/optimization	new	Migrations	dev	Normal		transitive reduction showmigrations	Markus Holtermann emorley@… Ülgen Sarıkavak	Accepted	0	0	0	0	0	0