diff options
| -rw-r--r-- | app/models/concerns/relative_positioning.rb | 114 | ||||
| -rw-r--r-- | changelogs/unreleased/jprovazn-fix-positioning.yml | 5 | ||||
| -rw-r--r-- | spec/support/shared_examples/relative_positioning_shared_examples.rb | 76 |
3 files changed, 170 insertions, 25 deletions
diff --git a/app/models/concerns/relative_positioning.rb b/app/models/concerns/relative_positioning.rb index 4a1441805fc..5395db509b5 100644 --- a/app/models/concerns/relative_positioning.rb +++ b/app/models/concerns/relative_positioning.rb @@ -28,9 +28,12 @@ module RelativePositioning START_POSITION = Gitlab::Database::MAX_INT_VALUE / 2 MAX_POSITION = Gitlab::Database::MAX_INT_VALUE IDEAL_DISTANCE = 500 + MAX_SEQUENCE_LIMIT = 1000 - included do - after_save :save_positionable_neighbours + class GapNotFound < StandardError + def message + 'Could not find a gap in the sequence of relative positions.' + end end class_methods do @@ -116,9 +119,10 @@ module RelativePositioning # If there is no place to insert an item we need to create one by moving the before item closer # to its predecessor. This process will recursively move all the predecessors until we have a place + before, after = after, before if after.relative_position < before.relative_position if (after.relative_position - before.relative_position) < 2 - before.move_before - @positionable_neighbours = [before] # rubocop:disable Gitlab/ModuleWithInstanceVariables + after.move_sequence_before + before.reset end self.relative_position = self.class.position_between(before.relative_position, after.relative_position) @@ -129,11 +133,7 @@ module RelativePositioning pos_after = before.next_relative_position if before.shift_after? - item_to_move = self.class.relative_positioning_query_base(self).find_by!(relative_position: pos_after) - item_to_move.move_after - @positionable_neighbours = [item_to_move] # rubocop:disable Gitlab/ModuleWithInstanceVariables - - pos_after = item_to_move.relative_position + before.move_sequence_after end self.relative_position = self.class.position_between(pos_before, pos_after) @@ -144,11 +144,7 @@ module RelativePositioning pos_before = after.prev_relative_position if after.shift_before? - item_to_move = self.class.relative_positioning_query_base(self).find_by!(relative_position: pos_before) - item_to_move.move_before - @positionable_neighbours = [item_to_move] # rubocop:disable Gitlab/ModuleWithInstanceVariables - - pos_before = item_to_move.relative_position + after.move_sequence_before end self.relative_position = self.class.position_between(pos_before, pos_after) @@ -174,24 +170,23 @@ module RelativePositioning prev_pos && (relative_position - prev_pos) == 1 end - private - - # rubocop:disable Gitlab/ModuleWithInstanceVariables - def save_positionable_neighbours - return unless @positionable_neighbours - - status = @positionable_neighbours.all? { |item| item.save(touch: false) } - @positionable_neighbours = nil + def move_sequence_before + items_to_move = scoped_items_batch.where('relative_position <= ?', relative_position).order('relative_position DESC') + move_nearest_sequence(items_to_move, MIN_POSITION) + end - status + def move_sequence_after + items_to_move = scoped_items_batch.where('relative_position >= ?', relative_position).order(:relative_position) + move_nearest_sequence(items_to_move, MAX_POSITION) end - # rubocop:enable Gitlab/ModuleWithInstanceVariables + + private def calculate_relative_position(calculation) # When calculating across projects, this is much more efficient than # MAX(relative_position) without the GROUP BY, due to index usage: # https://gitlab.com/gitlab-org/gitlab-ce/issues/54276#note_119340977 - relation = self.class.relative_positioning_query_base(self) + relation = scoped_items .order(Gitlab::Database.nulls_last_order('position', 'DESC')) .group(self.class.relative_positioning_parent_column) .limit(1) @@ -203,4 +198,73 @@ module RelativePositioning .first&. last end + + def scoped_items + self.class.relative_positioning_query_base(self) + end + + def scoped_items_batch + scoped_items.limit(MAX_SEQUENCE_LIMIT).select(:id, :relative_position).where.not(id: self.id) + end + + # Supposing that we have a sequence of positions: 5 11 12 13 14 15, + # and we want to move another item between 14 and 15, then + # we shift previous positions at least by one item, but ideally to the middle + # of the nearest gap. In this case gap is between 5 and 11 so + # this would move 11 12 13 14 to 8 9 10 11. + def move_nearest_sequence(items, end_position) + gap_idx, gap_size = find_gap_in_sequence(items) + + # If we didn't find a gap in the sequence, it's still possible that there + # are some free positions before the first item + if gap_idx.nil? && !items.empty? && items.size < MAX_SEQUENCE_LIMIT && + items.last.relative_position != end_position + + gap_idx = items.size + gap_size = end_position - items.last.relative_position + end + + # The chance that there is a sequence of 1000 positions w/o gap is really + # low, but it would be good to rebalance all positions in the scope instead + # of raising an exception: + # https://gitlab.com/gitlab-org/gitlab-ce/issues/64514#note_192657097 + raise GapNotFound if gap_idx.nil? + # No shift is needed if gap is next to the item being moved + return true if gap_idx == 0 + + delta = max_delta_for_sequence(gap_size) + sequence_ids = items.first(gap_idx).map(&:id) + move_ids_by_delta(sequence_ids, delta) + end + + def max_delta_for_sequence(gap_size) + delta = gap_size / 2 + + if delta.abs > IDEAL_DISTANCE + delta = delta < 0 ? -IDEAL_DISTANCE : IDEAL_DISTANCE + end + + delta + end + + def move_ids_by_delta(ids, delta) + self.class.where(id: ids).update_all("relative_position=relative_position+#{delta}") + end + + def find_gap_in_sequence(items) + prev = relative_position + gap = nil + + items.each_with_index do |rec, idx| + size = rec.relative_position - prev + if size.abs > 1 + gap = [idx, size] + break + end + + prev = rec.relative_position + end + + gap + end end diff --git a/changelogs/unreleased/jprovazn-fix-positioning.yml b/changelogs/unreleased/jprovazn-fix-positioning.yml new file mode 100644 index 00000000000..5d703008bba --- /dev/null +++ b/changelogs/unreleased/jprovazn-fix-positioning.yml @@ -0,0 +1,5 @@ +--- +title: Optimize relative re-positioning when moving issues. +merge_request: 30938 +author: +type: fixed diff --git a/spec/support/shared_examples/relative_positioning_shared_examples.rb b/spec/support/shared_examples/relative_positioning_shared_examples.rb index 1c53e2602eb..417ef4f315b 100644 --- a/spec/support/shared_examples/relative_positioning_shared_examples.rb +++ b/spec/support/shared_examples/relative_positioning_shared_examples.rb @@ -9,6 +9,12 @@ RSpec.shared_examples 'a class that supports relative positioning' do create(factory, params.merge(default_params)) end + def create_items_with_positions(positions) + positions.map do |position| + create_item(relative_position: position) + end + end + describe '.move_nulls_to_end' do it 'moves items with null relative_position to the end' do skip("#{item1} has a default relative position") if item1.relative_position @@ -257,5 +263,75 @@ RSpec.shared_examples 'a class that supports relative positioning' do expect(new_item.relative_position).to be(100) end + + it 'avoids N+1 queries when rebalancing other items' do + items = create_items_with_positions([100, 101, 102]) + + count = ActiveRecord::QueryRecorder.new do + new_item.move_between(items[-2], items[-1]) + end + + items = create_items_with_positions([150, 151, 152, 153, 154]) + + expect { new_item.move_between(items[-2], items[-1]) }.not_to exceed_query_limit(count) + end + end + + describe '#move_sequence_before' do + it 'moves the whole sequence of items to the middle of the nearest gap' do + items = create_items_with_positions([90, 100, 101, 102]) + + items.last.move_sequence_before + items.last.save! + + positions = items.map { |item| item.reload.relative_position } + expect(positions).to eq([90, 95, 96, 102]) + end + + it 'finds a gap if there are unused positions' do + items = create_items_with_positions([100, 101, 102]) + + items.last.move_sequence_before + items.last.save! + + positions = items.map { |item| item.reload.relative_position } + expect(positions).to eq([50, 51, 102]) + end + + it 'if raises an exception if gap is not found' do + stub_const('RelativePositioning::MAX_SEQUENCE_LIMIT', 2) + items = create_items_with_positions([100, 101, 102]) + + expect { items.last.move_sequence_before }.to raise_error(RelativePositioning::GapNotFound) + end + end + + describe '#move_sequence_after' do + it 'moves the whole sequence of items to the middle of the nearest gap' do + items = create_items_with_positions([100, 101, 102, 110]) + + items.first.move_sequence_after + items.first.save! + + positions = items.map { |item| item.reload.relative_position } + expect(positions).to eq([100, 105, 106, 110]) + end + + it 'finds a gap if there are unused positions' do + items = create_items_with_positions([100, 101, 102]) + + items.first.move_sequence_after + items.first.save! + + positions = items.map { |item| item.reload.relative_position } + expect(positions).to eq([100, 601, 602]) + end + + it 'if raises an exception if gap is not found' do + stub_const('RelativePositioning::MAX_SEQUENCE_LIMIT', 2) + items = create_items_with_positions([100, 101, 102]) + + expect { items.first.move_sequence_after }.to raise_error(RelativePositioning::GapNotFound) + end end end |