[Django] #27845: Possible Migration Optimizer Strategy Improvement

[Django]

#27845: Possible Migration Optimizer Strategy Improvement
+
   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: 
Django 
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 django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/django-updates/047.a3460c3885cc91153c13a81fecf54a43%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.

Re: [Django] #27845: Possible Migration Optimizer Strategy Improvement

[Django]

#27845: Possible Migration Optimizer Strategy Improvement
-+-
 Reporter:  Raphael Gaschignard  |Owner:  Simon
 Type:   |  Charette
  Cleanup/optimization   |   Status:  closed
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 ):

 * 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: 
Django 
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 django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/django-updates/062.db08081e9abc2e726fc8843ad4a7a47e%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.

Re: [Django] #27845: Possible Migration Optimizer Strategy Improvement

[Django]

#27845: Possible Migration Optimizer Strategy Improvement
--+
 Reporter:  Raphael Gaschignard   |Owner:  nobody
 Type:  Cleanup/optimization  |   Status:  new
Component:  Migrations|  Version:  master
 Severity:  Normal|   Resolution:
 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: 
Django 
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 django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/django-updates/062.9b266c8fc6283043e36b7de94d6ae9e7%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.

Re: [Django] #27845: Possible Migration Optimizer Strategy Improvement

[Django]

#27845: Possible Migration Optimizer Strategy Improvement
-+-
 Reporter:  Raphael Gaschignard  |Owner:  Simon
 Type:   |  Charette
  Cleanup/optimization   |   Status:  assigned
Component:  Migrations   |  Version:  master
 Severity:  Normal   |   Resolution:
 Keywords:   | Triage Stage:  Accepted
Has patch:  1|  Needs documentation:  0
  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: 
Django 
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 django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/django-updates/062.a3077e6cff14a6ed685c044cbcc68e02%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.

Re: [Django] #27845: Possible Migration Optimizer Strategy Improvement

[Django]

#27845: Possible Migration Optimizer Strategy Improvement
-+-
 Reporter:  Raphael Gaschignard  |Owner:  Simon
 Type:   |  Charette
  Cleanup/optimization   |   Status:  assigned
Component:  Migrations   |  Version:  master
 Severity:  Normal   |   Resolution:
 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):

 * needs_better_patch:  0 => 1


Comment:

 As far as I can tell, the PR is awaiting an update from Simon.

--
Ticket URL: 
Django 
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 django-updates+unsubscr...@googlegroups.com.
To post to this group, send email to django-updates@googlegroups.com.
To view this discussion on the web visit 
https://groups.google.com/d/msgid/django-updates/062.47df860515175b86aa7677fdcfe10030%40djangoproject.com.
For more options, visit https://groups.google.com/d/optout.