RelativePositioning concern could be more efficient
Everyone can contribute. Help move this issue forward while earning points, leveling up and collecting rewards.
Summary
We have a re-usable concern for implementing ordered collections (RelativePositioning) which relies on the presence of column on the including datatype of the form: relative_position: integer.
There are some improvements we could make to this re-usable module:
Improvements
Default Gap Size
The default gap size is not a factor of 2 + 1, but has the value 500, which is not optimal. We should set the ideal gap size to some value of 2^n + 1 where n is the number of divisions we want to allow.
If we consider a game of leap-frogging two elements a and b, initially positioned at 0 and 500 with one (c) at 1000, where at each step we take the element in position a and move it to between b and c, then the sequence of steps is:
| step | a | b | c |
|---|---|---|---|
| 0 | 0 | 500 | 1000 |
| 1 | 500 | 750 | 1000 |
| 2 | 750 | 875 | 1000 |
| 3 | 875 | 934 | 1000 |
| 4 | 934 | 967 | 1000 |
| 5 | 967 | 984 | 1000 |
| 6 | 984 | 992 | 1000 |
| 7 | 992 | 996 | 1000 |
| 8 | 996 | 998 | 1000 |
| 9 | 998 | 999 | 1000 |
After this point we have to create space to continue leap-frogging.
However, if the default gap is 256 + 1:
| step | a | b | c |
|---|---|---|---|
| 0 | 0 | 257 | 514 |
| 1 | 257 | 385 | 514 |
| 2 | 385 | 449 | 514 |
| 3 | 449 | 481 | 514 |
| 4 | 481 | 497 | 514 |
| 5 | 497 | 505 | 514 |
| 6 | 505 | 509 | 514 |
| 7 | 509 | 511 | 514 |
| 8 | 511 | 512 | 514 |
| 9 | 512 | 513 | 514 |
ie. we get the same number of leap-frogging in half the space. If we set this to
512 + 1 we get one more round of leap-frogging.
Incorrect MIN value
The minimum position is set to 0, which is non-sensical. This wastes all the
negative integers and means every time we want to place elements to the left of
0 we have to re-position elements, which means extra DB calls.
Missing bounds checks
The current code does not check that elements placed at the end or the start are in bounds (resulting in undefined behaviour, but which in practice means many elements all stacked up at the end). We always need to check when moving elements that they are in bounds, and rebalance if necessary
Inefficient move-nulls logic
We currently perform a separate update for each element we move. Since we can calculate the positions statically, we should be able to reduce this from N DB calls to 1
Risks
This could cause problems with re-ordering components, so needs to be thoroughly tested.
Involved components
- spec/support/shared_examples/models/relative_positioning_shared_examples.rb
- app/models/concerns/relative_positioning.rb
- app/models/concerns/analytics/cycle_analytics/stage.rb
- app/models/issue.rb
- ee/app/models/concerns/epic_tree_sorting.rb
Optional: Intended side effects
Better performance via fewer gap readjustments.