diff options
Diffstat (limited to 'app/models/namespaces/traversal/linear_scopes.rb')
| -rw-r--r-- | app/models/namespaces/traversal/linear_scopes.rb | 151 |
1 files changed, 114 insertions, 37 deletions
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 |