[Django] #27845: Possible Migration Optimizer Strategy Improvement
Django
------------------------------------------------+------------------------
Reporter: Raphael Gaschignard | Owner: nobody
Type: Cleanup/optimization | Status: new
Component: Migrations | Version: master
Severity: Normal | Keywords:
Triage Stage: Unreviewed | Has patch: 0
Needs documentation: 0 | Needs tests: 0
Patch needs improvement: 0 | Easy pickings: 0
UI/UX: 0 |
------------------------------------------------+------------------------
The migration optimizer works by taking pairs of operations and trying to
reduce them by fusing or eliminating the operations. For example, turning
an {{{AddModel}}} and an {{{AddField}}} into a single {{{AddModel}}} with
the extra field.
The current optimization strategy if you have {{{[A,B,C,D,E]}}} is:
- try and reduce A and B
- try and reduce A and C (with B in between)
- try and reduce A and D (with B and C in between)
etc.
if (for example) D refers to A and cannot reduce, then we break out of
the loop (because even if A and E could reduce, D refers to A).
But sometimes, D referring to A doesn't mean that A and E cannot be
reduced! Simply that they cannot be reduced in a way that removes A. This
reference issue prevents a lot of straightforward optimizations. This is a
proposal for a new optimizer strategy that would help to unlock some of
this potential.
In a new strategy, we would add a notion of preceding and depending.
- B depending on A means that A must be before B in the chain of
operations, because B must happen after A.
For example: AddField(m, f) is dependent on CreateModel(m) because m needs
to be created before a field is added to it
- B preceding C means that C must follow B in the chain of operations,
because (ultimately) C depends on B.
For example, {{{CreateModel(m)}}} precedes {{{AddField(m',
ForeignKey(m))}}} because, in order to create a foreign key to m, we need
m to exist!
In this new strategy, we would have two optimization passes. Firstly, we
would "backwards optimize". This involves taking operations like {{{[A, B,
C, D]}}}, and attempting to reduce A and C by bringing C towards A
(resulting in {{{[A+C, B, D]}}}) .
If you have [A, B, ..., Y, Z], you can backwards optimize Z into A if no
operation in [B, ..., Y] precedes Z (that is to say, Z does not depend on
anything in [B, ..., Y]). In this first pass, references to A are not
important, because A cannot be removed.
Example of allowed reductions in the backwards optimization:
- CreateModel + AddField of the same model
- AddField + Alter Field for the same field
Example of a reduction that would ''not'' be used in backwards
optimization:
- CreateModel + RemoveModel (because both operations would be removed)
The second pass would be a "forwards optimization" step. In this step,
we're looking to take {{{[A, B, C, D]}}} and bring elements forward (for
example to {{{[B, C, A+D]}}}.
In this optimization pass, we can forward optimize A and Z in
{{{[A,B,C...,Y,Z]}}} if no operation in [B,C,...,Y] depends on A. This is
a bit closer to the current optimization strategy (which checks if [B,C,
... ,Y] reference A). This could include all existing reductions,
including those that remove operations entirely.
Because the second optimization pass works like the old strategy, this new
strategy mainly consists in adding the first step, and whitelisting
reduction operations. The optimizer currently has a "references" check
that can be also be re-used as a dependency check.
I'm not sure if there are any holes in this optimizing strategy, but
running through it in some real world examples seems to hold up.
--
Ticket URL: <https://code.djangoproject.com/ticket/27845>
Django <https://code.djangoproject.com/>
The Web framework for perfectionists with deadlines.
Django
Reporter: Raphael Gaschignard | Owner: nobody
Type: Cleanup/optimization | Status: new
Component: Migrations | Version: master
Keywords: | Triage Stage: Accepted
Has patch: 0 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
Changes (by Simon Charette):
* cc: Simon Charette (added)
* stage: Unreviewed => Accepted
Comment:
See [https://github.com/django/django/pull/7999/files this PR] for
`references_(model|field)` adjustments.
--
Ticket URL: <https://code.djangoproject.com/ticket/27845#comment:1>
Django
Reporter: Raphael Gaschignard | Owner: Simon
Type: | Charette
Cleanup/optimization | Status: assigned
Component: Migrations | Version: master
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 0
Easy pickings: 0 | UI/UX: 0
Changes (by Simon Charette):
* status: new => assigned
* owner: nobody => Simon Charette
* has_patch: 0 => 1
Comment:
[https://github.com/django/django/pull/7999 PR]
--
Ticket URL: <https://code.djangoproject.com/ticket/27845#comment:2>
Django
Reporter: Raphael Gaschignard | Owner: Simon
Type: | Charette
Cleanup/optimization | Status: assigned
Severity: Normal | Resolution:
Keywords: | Triage Stage: Accepted
Needs tests: 0 | Patch needs improvement: 1
Easy pickings: 0 | UI/UX: 0
Changes (by Tim Graham):
* needs_better_patch: 0 => 1
Comment:
As far as I can tell, the PR is awaiting an update from Simon.
--
Ticket URL: <https://code.djangoproject.com/ticket/27845#comment:3>
Django
Reporter: Raphael Gaschignard | Owner: Simon
Type: | Charette
Component: Migrations | Version: master
Severity: Normal | Resolution: fixed
Keywords: | Triage Stage: Accepted
Has patch: 1 | Needs documentation: 0
Needs tests: 0 | Patch needs improvement: 1
Easy pickings: 0 | UI/UX: 0
Changes (by Tim Graham <timograham@…>):
* status: assigned => closed
* resolution: => fixed
Comment:
In [changeset:"37cafbfb791b2295b8c36cdabbdef0e5d951a64e" 37cafbfb]:
{{{
#!CommitTicketReference repository=""
revision="37cafbfb791b2295b8c36cdabbdef0e5d951a64e"
Fixed #27845 -- Allowed both right and left optimizations of operations.
Thanks Raphael Gaschignard for the suggestion.
}}}
--
Ticket URL: <https://code.djangoproject.com/ticket/27845#comment:4>