From afbe0b616b1e17f88bacc283a7a8fbe0bece580a Mon Sep 17 00:00:00 2001 From: Jan Provaznik Date: Fri, 19 Jul 2019 10:16:41 +0200 Subject: 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. --- app/models/concerns/relative_positioning.rb | 114 ++++++++++++++++++++++------ 1 file changed, 89 insertions(+), 25 deletions(-) (limited to 'app/models') 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 -- cgit v1.2.3 From 3f9b1ecdb3bbaab6ec35d28d066759985ce25e0e Mon Sep 17 00:00:00 2001 From: Heinrich Lee Yu Date: Wed, 24 Jul 2019 22:36:39 +0800 Subject: Use SQL to find the gap instead of iterating Also removes unnecessary methods causing extra queries --- app/models/concerns/relative_positioning.rb | 157 ++++++++++++---------------- 1 file changed, 66 insertions(+), 91 deletions(-) (limited to 'app/models') diff --git a/app/models/concerns/relative_positioning.rb b/app/models/concerns/relative_positioning.rb index 5395db509b5..6d3c7a7ed68 100644 --- a/app/models/concerns/relative_positioning.rb +++ b/app/models/concerns/relative_positioning.rb @@ -28,13 +28,6 @@ module RelativePositioning START_POSITION = Gitlab::Database::MAX_INT_VALUE / 2 MAX_POSITION = Gitlab::Database::MAX_INT_VALUE IDEAL_DISTANCE = 500 - MAX_SEQUENCE_LIMIT = 1000 - - class GapNotFound < StandardError - def message - 'Could not find a gap in the sequence of relative positions.' - end - end class_methods do def move_nulls_to_end(objects) @@ -117,8 +110,8 @@ module RelativePositioning return move_after(before) unless after return move_before(after) unless before - # 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 + # If there is no place to insert an item we need to create one by moving the item + # before this and all preceding items until there is a gap before, after = after, before if after.relative_position < before.relative_position if (after.relative_position - before.relative_position) < 2 after.move_sequence_before @@ -132,7 +125,7 @@ module RelativePositioning pos_before = before.relative_position pos_after = before.next_relative_position - if before.shift_after? + if pos_after && (pos_after - pos_before) < 2 before.move_sequence_after end @@ -143,7 +136,7 @@ module RelativePositioning pos_after = after.relative_position pos_before = after.prev_relative_position - if after.shift_before? + if pos_before && (pos_after - pos_before) < 2 after.move_sequence_before end @@ -158,29 +151,76 @@ module RelativePositioning self.relative_position = self.class.position_between(min_relative_position || START_POSITION, MIN_POSITION) end - # Indicates if there is an item that should be shifted to free the place - def shift_after? - next_pos = next_relative_position - next_pos && (next_pos - relative_position) == 1 + # Moves the sequence before the current item to the middle of the next gap + # For example, we have 5 11 12 13 14 15 and the current item is 15 + # This moves the sequence 11 12 13 14 to 8 9 10 11 + def move_sequence_before + next_gap = find_next_gap_before + delta = optimum_delta_for_gap(next_gap) + + move_sequence(next_gap[:start], relative_position, -delta) end - # Indicates if there is an item that should be shifted to free the place - def shift_before? - prev_pos = prev_relative_position - prev_pos && (relative_position - prev_pos) == 1 + # Moves the sequence after the current item to the middle of the next gap + # For example, we have 11 12 13 14 15 21 and the current item is 11 + # This moves the sequence 12 13 14 15 to 15 16 17 18 + def move_sequence_after + next_gap = find_next_gap_after + delta = optimum_delta_for_gap(next_gap) + + move_sequence(relative_position, next_gap[:start], delta) end - 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) + private + + # Supposing that we have a sequence of items: 1 5 11 12 13 and the current item is 13 + # This would return: `{ start: 11, end: 5 }` + def find_next_gap_before + items_with_next_pos = scoped_items + .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position DESC) AS next_pos') + .where('relative_position <= ?', relative_position) + .order(relative_position: :desc) + + find_next_gap(items_with_next_pos).tap do |gap| + gap[:end] ||= MIN_POSITION + end end - 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) + # Supposing that we have a sequence of items: 13 14 15 20 24 and the current item is 13 + # This would return: `{ start: 15, end: 20 }` + def find_next_gap_after + items_with_next_pos = scoped_items + .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position ASC) AS next_pos') + .where('relative_position >= ?', relative_position) + .order(:relative_position) + + find_next_gap(items_with_next_pos).tap do |gap| + gap[:end] ||= MAX_POSITION + end end - private + def find_next_gap(items_with_next_pos) + gap = self.class.from(items_with_next_pos, :items_with_next_pos) + .where('ABS(pos - next_pos) > 1 OR next_pos IS NULL') + .limit(1) + .pluck(:pos, :next_pos) + .first + + { start: gap[0], end: gap[1] } + end + + def optimum_delta_for_gap(gap) + delta = ((gap[:start] - gap[:end]) / 2.0).abs.ceil + + [delta, IDEAL_DISTANCE].min + end + + def move_sequence(start_pos, end_pos, delta) + scoped_items + .where.not(id: self.id) + .where('relative_position BETWEEN ? AND ?', start_pos, end_pos) + .update_all("relative_position = relative_position + #{delta}") + end def calculate_relative_position(calculation) # When calculating across projects, this is much more efficient than @@ -202,69 +242,4 @@ module RelativePositioning 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 -- cgit v1.2.3