Optimize SeparateDatabaseAndState.database_backwards() by caching intermediate state

[Amos Onn]

The database_backwards of SeparateDatabaseAndState runs at O(n²) where n is the number of database_operations. For each operation, it regenerates the state up to it from the first operation. Instead, we could cache all the intermediate states, similar to the implementation of _migrate_all_backwards in the migration executor (or migrate in django 1.8.x).

[Tim Graham]

​PR

[Tim Graham <timograham@…>]

In bd3c2900:

Fixed #25892 -- Optimized SeparateDatabaseAndState.database_backwards().

Now intermediate states in the database_backwards are cached, similar to
the executor's migrate() (or _migrate_all_backwards()). This makes the
migration run much faster (O(n) instead of O(n^{2) over number of
database_operations).}