diff options
-rw-r--r-- | app/models/concerns/relative_positioning.rb | 111 | ||||
-rw-r--r-- | changelogs/unreleased/jprovazn-fix-positioning.yml | 5 | ||||
-rw-r--r-- | db/migrate/20190802012622_reorder_issues_project_id_relative_position_index.rb | 24 | ||||
-rw-r--r-- | db/schema.rb | 4 | ||||
-rw-r--r-- | spec/support/shared_examples/relative_positioning_shared_examples.rb | 102 |
5 files changed, 168 insertions, 78 deletions
diff --git a/app/models/concerns/relative_positioning.rb b/app/models/concerns/relative_positioning.rb index 4a1441805fc..6d3c7a7ed68 100644 --- a/app/models/concerns/relative_positioning.rb +++ b/app/models/concerns/relative_positioning.rb @@ -29,10 +29,6 @@ module RelativePositioning MAX_POSITION = Gitlab::Database::MAX_INT_VALUE IDEAL_DISTANCE = 500 - included do - after_save :save_positionable_neighbours - end - class_methods do def move_nulls_to_end(objects) objects = objects.reject(&:relative_position) @@ -114,11 +110,12 @@ 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 - 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) @@ -128,12 +125,8 @@ module RelativePositioning pos_before = before.relative_position 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 + if pos_after && (pos_after - pos_before) < 2 + before.move_sequence_after end self.relative_position = self.class.position_between(pos_before, pos_after) @@ -143,12 +136,8 @@ module RelativePositioning pos_after = after.relative_position 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 + if pos_before && (pos_after - pos_before) < 2 + after.move_sequence_before end self.relative_position = self.class.position_between(pos_before, pos_after) @@ -162,36 +151,82 @@ 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 private - # rubocop:disable Gitlab/ModuleWithInstanceVariables - def save_positionable_neighbours - return unless @positionable_neighbours + # 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 + + # 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) - status = @positionable_neighbours.all? { |item| item.save(touch: false) } - @positionable_neighbours = nil + find_next_gap(items_with_next_pos).tap do |gap| + gap[:end] ||= MAX_POSITION + end + end + + 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 - status + 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 - # rubocop:enable Gitlab/ModuleWithInstanceVariables 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 +238,8 @@ module RelativePositioning .first&. last end + + def scoped_items + self.class.relative_positioning_query_base(self) + 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/db/migrate/20190802012622_reorder_issues_project_id_relative_position_index.rb b/db/migrate/20190802012622_reorder_issues_project_id_relative_position_index.rb new file mode 100644 index 00000000000..12088dd763f --- /dev/null +++ b/db/migrate/20190802012622_reorder_issues_project_id_relative_position_index.rb @@ -0,0 +1,24 @@ +# frozen_string_literal: true + +class ReorderIssuesProjectIdRelativePositionIndex < ActiveRecord::Migration[5.2] + include Gitlab::Database::MigrationHelpers + + DOWNTIME = false + + disable_ddl_transaction! + + OLD_INDEX_NAME = 'index_issues_on_project_id_and_state_and_rel_position_and_id' + NEW_INDEX_NAME = 'index_issues_on_project_id_and_rel_position_and_state_and_id' + + def up + add_concurrent_index :issues, [:project_id, :relative_position, :state, :id], order: { id: :desc }, name: NEW_INDEX_NAME + + remove_concurrent_index_by_name :issues, OLD_INDEX_NAME + end + + def down + add_concurrent_index :issues, [:project_id, :state, :relative_position, :id], order: { id: :desc }, name: OLD_INDEX_NAME + + remove_concurrent_index_by_name :issues, NEW_INDEX_NAME + end +end diff --git a/db/schema.rb b/db/schema.rb index fe3fa597006..a9b7c1930e3 100644 --- a/db/schema.rb +++ b/db/schema.rb @@ -10,7 +10,7 @@ # # It's strongly recommended that you check this file into your version control system. -ActiveRecord::Schema.define(version: 2019_08_01_114109) do +ActiveRecord::Schema.define(version: 2019_08_02_012622) do # These are extensions that must be enabled in order to support this database enable_extension "pg_trgm" @@ -1716,7 +1716,7 @@ ActiveRecord::Schema.define(version: 2019_08_01_114109) do t.index ["project_id", "created_at", "id", "state"], name: "index_issues_on_project_id_and_created_at_and_id_and_state" t.index ["project_id", "due_date", "id", "state"], name: "idx_issues_on_project_id_and_due_date_and_id_and_state_partial", where: "(due_date IS NOT NULL)" t.index ["project_id", "iid"], name: "index_issues_on_project_id_and_iid", unique: true - t.index ["project_id", "state", "relative_position", "id"], name: "index_issues_on_project_id_and_state_and_rel_position_and_id", order: { id: :desc } + t.index ["project_id", "relative_position", "state", "id"], name: "index_issues_on_project_id_and_rel_position_and_state_and_id", order: { id: :desc } t.index ["project_id", "updated_at", "id", "state"], name: "index_issues_on_project_id_and_updated_at_and_id_and_state" t.index ["relative_position"], name: "index_issues_on_relative_position" t.index ["state"], name: "index_issues_on_state" diff --git a/spec/support/shared_examples/relative_positioning_shared_examples.rb b/spec/support/shared_examples/relative_positioning_shared_examples.rb index 1c53e2602eb..9837ba806db 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 @@ -104,46 +110,6 @@ RSpec.shared_examples 'a class that supports relative positioning' do end end - describe '#shift_after?' do - before do - [item1, item2].each do |item1| - item1.move_to_end && item1.save - end - end - - it 'returns true' do - item1.update(relative_position: item2.relative_position - 1) - - expect(item1.shift_after?).to be_truthy - end - - it 'returns false' do - item1.update(relative_position: item2.relative_position - 2) - - expect(item1.shift_after?).to be_falsey - end - end - - describe '#shift_before?' do - before do - [item1, item2].each do |item1| - item1.move_to_end && item1.save - end - end - - it 'returns true' do - item1.update(relative_position: item2.relative_position + 1) - - expect(item1.shift_before?).to be_truthy - end - - it 'returns false' do - item1.update(relative_position: item2.relative_position + 2) - - expect(item1.shift_before?).to be_falsey - end - end - describe '#move_between' do before do [item1, item2].each do |item1| @@ -257,5 +223,61 @@ 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 + 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 end end |