[Django] #36869: Optimise migration graph planning

[Django]

#36869: Optimise migration graph planning
-------------------------------------+-------------------------------------
Reporter: James Fysh | Type:
| Cleanup/optimization
Status: new | Component: Database
| layer (models, ORM)
Version: dev | Severity: Normal
Keywords: migration digraph | Triage Stage:
loader | Unreviewed
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
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.
--
Ticket URL: <https://code.djangoproject.com/ticket/36869>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.

[Django]

#36869: Optimise migration graph planning
-------------------------------------+-------------------------------------

Reporter: James Fysh | Owner: (none)
Type: | Status: new
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: migration digraph | Triage Stage: Accepted
loader |

Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Lily):

* stage: Unreviewed => Accepted

--
Ticket URL: <https://code.djangoproject.com/ticket/36869#comment:1>

[Django]

#36869: Optimise migration graph planning
-------------------------------------+-------------------------------------
Reporter: James Fysh | Owner: (none)
Type: | Status: new
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: migration digraph | Triage Stage: Accepted
loader |

Has patch: 1 | Needs documentation: 0

Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------
Changes (by Lily):

* has_patch: 0 => 1

--
Ticket URL: <https://code.djangoproject.com/ticket/36869#comment:2>

[Django]

#36869: Optimise migration graph planning
-------------------------------------+-------------------------------------
Reporter: James Fysh | Owner: (none)
Type: | Status: new
Cleanup/optimization |
Component: Database layer | Version: dev
(models, ORM) |
Severity: Normal | Resolution:
Keywords: migration digraph | Triage Stage: Accepted
loader |
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
-------------------------------------+-------------------------------------

Changes (by Natalia Bidart):

* cc: Nick Pope (added)

Comment:

I started the triage for this ticket and I truly wanted to see the
numbers. I built a benchmarking script, and got this numbers:

* code from `main`:
{{{
compare 100 against 200 migrations (2.0x size): 2.92x time
compare 200 against 400 migrations (2.0x size): 3.40x time
compare 400 against 800 migrations (2.0x size): 3.75x time
compare 800 against 1600 migrations (2.0x size): 3.69x time
compare 1600 against 3200 migrations (2.0x size): 3.96x time
}}}

* code from the proposed PR:
{{{
compare 100 against 200 migrations (2.0x size): 1.87x time
compare 200 against 400 migrations (2.0x size): 2.01x time
compare 400 against 800 migrations (2.0x size): 2.06x time
compare 800 against 1600 migrations (2.0x size): 2.10x time
compare 1600 against 3200 migrations (2.0x size): 1.97x time
}}}

* code proposed from Nick:
{{{
compare 100 against 200 migrations (2.0x size): 1.75x time
compare 200 against 400 migrations (2.0x size): 2.22x time
compare 400 against 800 migrations (2.0x size): 2.12x time
compare 800 against 1600 migrations (2.0x size): 1.77x time
compare 1600 against 3200 migrations (2.0x size): 2.13x time
}}}

Perhaps we should consider Nick's suggestion to keep the logic a little
more straightforward?
--
Ticket URL: <https://code.djangoproject.com/ticket/36869#comment:3>