diff options
author | Jan Provaznik <jprovaznik@gitlab.com> | 2019-07-19 11:16:41 +0300 |
---|---|---|
committer | Heinrich Lee Yu <heinrich@gitlab.com> | 2019-08-05 12:49:04 +0300 |
commit | afbe0b616b1e17f88bacc283a7a8fbe0bece580a (patch) | |
tree | 69c7da09a7d2e36e5f1fb7f73421b4a736c22356 /app/models/concerns/relative_positioning.rb | |
parent | d126df55fde21d2dc8eb9d5f72841a9792bca105 (diff) |
Optimize rebalancing of relative positioning
Moving of neighbour items was done recursively - this
was extremely expensive when multiple items had to be moved.
This change optimizes the code to find nearest possible gap where
items can be moved and moves all of them with single update query.
Diffstat (limited to 'app/models/concerns/relative_positioning.rb')
-rw-r--r-- | app/models/concerns/relative_positioning.rb | 114 |
1 files changed, 89 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 |