diff options
Diffstat (limited to 'app/models/namespaces')
| -rw-r--r-- | app/models/namespaces/project_namespace.rb | 7 | ||||
| -rw-r--r-- | app/models/namespaces/traversal/linear.rb | 10 | ||||
| -rw-r--r-- | app/models/namespaces/traversal/linear_scopes.rb | 151 | ||||
| -rw-r--r-- | app/models/namespaces/traversal/recursive.rb | 8 |
4 files changed, 127 insertions, 49 deletions
diff --git a/app/models/namespaces/project_namespace.rb b/app/models/namespaces/project_namespace.rb index fbd87e3232d..2a2ea11ddc5 100644 --- a/app/models/namespaces/project_namespace.rb +++ b/app/models/namespaces/project_namespace.rb @@ -2,6 +2,13 @@ module Namespaces class ProjectNamespace < Namespace + # These aliases are added to make it easier to sync parent/parent_id attribute with + # project.namespace/project.namespace_id attribute. + # + # TODO: we can remove these attribute aliases when we no longer need to sync these with project model, + # see project#sync_attributes + alias_attribute :namespace, :parent + alias_attribute :namespace_id, :parent_id has_one :project, foreign_key: :project_namespace_id, inverse_of: :project_namespace def self.sti_name diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb index b0350b0288f..687fa6a5334 100644 --- a/app/models/namespaces/traversal/linear.rb +++ b/app/models/namespaces/traversal/linear.rb @@ -42,11 +42,11 @@ module Namespaces UnboundedSearch = Class.new(StandardError) included do - before_update :lock_both_roots, if: -> { sync_traversal_ids? && parent_id_changed? } - after_update :sync_traversal_ids, if: -> { sync_traversal_ids? && saved_change_to_parent_id? } + before_update :lock_both_roots, if: -> { parent_id_changed? } + after_update :sync_traversal_ids, if: -> { saved_change_to_parent_id? } # This uses rails internal before_commit API to sync traversal_ids on namespace create, right before transaction is committed. # This helps reduce the time during which the root namespace record is locked to ensure updated traversal_ids are valid - before_commit :sync_traversal_ids, on: [:create], if: -> { sync_traversal_ids? } + before_commit :sync_traversal_ids, on: [:create] end class_methods do @@ -76,10 +76,6 @@ module Namespaces end end - def sync_traversal_ids? - Feature.enabled?(:sync_traversal_ids, root_ancestor) - end - def use_traversal_ids? return false unless Feature.enabled?(:use_traversal_ids) diff --git a/app/models/namespaces/traversal/linear_scopes.rb b/app/models/namespaces/traversal/linear_scopes.rb index f0e9a8feeb2..6f404ec12d0 100644 --- a/app/models/namespaces/traversal/linear_scopes.rb +++ b/app/models/namespaces/traversal/linear_scopes.rb @@ -5,6 +5,8 @@ module Namespaces module LinearScopes extend ActiveSupport::Concern + include AsCte + class_methods do # When filtering namespaces by the traversal_ids column to compile a # list of namespace IDs, it can be faster to reference the ID in @@ -25,25 +27,15 @@ module Namespaces def self_and_ancestors(include_self: true, upto: nil, hierarchy_order: nil) return super unless use_traversal_ids_for_ancestor_scopes? - ancestors_cte, base_cte = ancestor_ctes - namespaces = Arel::Table.new(:namespaces) - - records = unscoped - .with(base_cte.to_arel, ancestors_cte.to_arel) - .distinct - .from([ancestors_cte.table, namespaces]) - .where(namespaces[:id].eq(ancestors_cte.table[:ancestor_id])) - .order_by_depth(hierarchy_order) - - unless include_self - records = records.where(ancestors_cte.table[:base_id].not_eq(ancestors_cte.table[:ancestor_id])) - end - - if upto - records = records.where.not(id: unscoped.where(id: upto).select('unnest(traversal_ids)')) + if Feature.enabled?(:use_traversal_ids_for_ancestor_scopes_with_inner_join) + self_and_ancestors_from_inner_join(include_self: include_self, + upto: upto, hierarchy_order: + hierarchy_order) + else + self_and_ancestors_from_ancestors_cte(include_self: include_self, + upto: upto, + hierarchy_order: hierarchy_order) end - - records end def self_and_ancestor_ids(include_self: true) @@ -87,7 +79,7 @@ module Namespaces depth_order = hierarchy_order == :asc ? :desc : :asc all - .select(Arel.star, 'array_length(traversal_ids, 1) as depth') + .select(Namespace.default_select_columns, 'array_length(traversal_ids, 1) as depth') .order(depth: depth_order, id: :asc) end @@ -125,26 +117,106 @@ module Namespaces use_traversal_ids? end + def self_and_ancestors_from_ancestors_cte(include_self: true, upto: nil, hierarchy_order: nil) + base_cte = all.select('namespaces.id', 'namespaces.traversal_ids').as_cte(:base_ancestors_cte) + + # We have to alias id with 'AS' to avoid ambiguous column references by calling methods. + ancestors_cte = unscoped + .unscope(where: [:type]) + .select('id as base_id', + "#{unnest_func(base_cte.table['traversal_ids']).to_sql} as ancestor_id") + .from(base_cte.table) + .as_cte(:ancestors_cte) + + namespaces = Arel::Table.new(:namespaces) + + records = unscoped + .with(base_cte.to_arel, ancestors_cte.to_arel) + .distinct + .from([ancestors_cte.table, namespaces]) + .where(namespaces[:id].eq(ancestors_cte.table[:ancestor_id])) + .order_by_depth(hierarchy_order) + + unless include_self + records = records.where(ancestors_cte.table[:base_id].not_eq(ancestors_cte.table[:ancestor_id])) + end + + if upto + records = records.where.not(id: unscoped.where(id: upto).select('unnest(traversal_ids)')) + end + + records + end + + def self_and_ancestors_from_inner_join(include_self: true, upto: nil, hierarchy_order: nil) + base_cte = all.reselect('namespaces.traversal_ids').as_cte(:base_ancestors_cte) + + unnest = if include_self + base_cte.table[:traversal_ids] + else + base_cte_traversal_ids = 'base_ancestors_cte.traversal_ids' + traversal_ids_range = "1:array_length(#{base_cte_traversal_ids},1)-1" + Arel.sql("#{base_cte_traversal_ids}[#{traversal_ids_range}]") + end + + ancestor_subselect = "SELECT DISTINCT #{unnest_func(unnest).to_sql} FROM base_ancestors_cte" + ancestors_join = <<~SQL + INNER JOIN (#{ancestor_subselect}) AS ancestors(ancestor_id) ON namespaces.id = ancestors.ancestor_id + SQL + + namespaces = Arel::Table.new(:namespaces) + + records = unscoped + .with(base_cte.to_arel) + .from(namespaces) + .joins(ancestors_join) + .order_by_depth(hierarchy_order) + + if upto + upto_ancestor_ids = unscoped.where(id: upto).select(unnest_func(Arel.sql('traversal_ids'))) + records = records.where.not(id: upto_ancestor_ids) + end + + records + end + def self_and_descendants_with_comparison_operators(include_self: true) base = all.select(:traversal_ids) - base_cte = Gitlab::SQL::CTE.new(:descendants_base_cte, base) + base = base.select(:id) if Feature.enabled?(:linear_scopes_superset) + base_cte = base.as_cte(:descendants_base_cte) namespaces = Arel::Table.new(:namespaces) + withs = [base_cte.to_arel] + froms = [] + + if Feature.enabled?(:linear_scopes_superset) + superset_cte = self.superset_cte(base_cte.table.name) + withs += [superset_cte.to_arel] + froms = [superset_cte.table] + else + froms = [base_cte.table] + end + + # Order is important. namespace should be last to handle future joins. + froms += [namespaces] + + base_ref = froms.first + # Bound the search space to ourselves (optional) and descendants. # # WHERE next_traversal_ids_sibling(base_cte.traversal_ids) > namespaces.traversal_ids records = unscoped .distinct - .with(base_cte.to_arel) - .from([base_cte.table, namespaces]) - .where(next_sibling_func(base_cte.table[:traversal_ids]).gt(namespaces[:traversal_ids])) + .with(*withs) + .from(froms) + .where(next_sibling_func(base_ref[:traversal_ids]).gt(namespaces[:traversal_ids])) # AND base_cte.traversal_ids <= namespaces.traversal_ids if include_self - records.where(base_cte.table[:traversal_ids].lteq(namespaces[:traversal_ids])) + records.where(base_ref[:traversal_ids].lteq(namespaces[:traversal_ids])) else - records.where(base_cte.table[:traversal_ids].lt(namespaces[:traversal_ids])) + records.where(base_ref[:traversal_ids].lt(namespaces[:traversal_ids])) end end @@ -152,6 +224,10 @@ module Namespaces Arel::Nodes::NamedFunction.new('next_traversal_ids_sibling', args) end + def unnest_func(*args) + Arel::Nodes::NamedFunction.new('unnest', args) + end + def self_and_descendants_with_duplicates_with_array_operator(include_self: true) base_ids = select(:id) @@ -166,18 +242,19 @@ module Namespaces end end - def ancestor_ctes - base_scope = all.select('namespaces.id', 'namespaces.traversal_ids') - base_cte = Gitlab::SQL::CTE.new(:base_ancestors_cte, base_scope) - - # We have to alias id with 'AS' to avoid ambiguous column references by calling methods. - ancestors_scope = unscoped - .unscope(where: [:type]) - .select('id as base_id', 'unnest(traversal_ids) as ancestor_id') - .from(base_cte.table) - ancestors_cte = Gitlab::SQL::CTE.new(:ancestors_cte, ancestors_scope) - - [ancestors_cte, base_cte] + def superset_cte(base_name) + superset_sql = <<~SQL + SELECT d1.traversal_ids + FROM #{base_name} d1 + WHERE NOT EXISTS ( + SELECT 1 + FROM #{base_name} d2 + WHERE d2.id = ANY(d1.traversal_ids) + AND d2.id <> d1.id + ) + SQL + + Gitlab::SQL::CTE.new(:superset, superset_sql, materialized: false) end end end diff --git a/app/models/namespaces/traversal/recursive.rb b/app/models/namespaces/traversal/recursive.rb index 53eac27aa54..1c5d395cb3c 100644 --- a/app/models/namespaces/traversal/recursive.rb +++ b/app/models/namespaces/traversal/recursive.rb @@ -63,19 +63,17 @@ module Namespaces # Returns all the descendants of the current namespace. def descendants - object_hierarchy(self.class.where(parent_id: id)) - .base_and_descendants + object_hierarchy(self.class.where(parent_id: id)).base_and_descendants end alias_method :recursive_descendants, :descendants def self_and_descendants - object_hierarchy(self.class.where(id: id)) - .base_and_descendants + object_hierarchy(self.class.where(id: id)).base_and_descendants end alias_method :recursive_self_and_descendants, :self_and_descendants def self_and_descendant_ids - recursive_self_and_descendants.select(:id) + object_hierarchy(self.class.where(id: id)).base_and_descendant_ids end alias_method :recursive_self_and_descendant_ids, :self_and_descendant_ids |