diff options
author | GitLab Bot <gitlab-bot@gitlab.com> | 2021-04-21 02:50:22 +0300 |
---|---|---|
committer | GitLab Bot <gitlab-bot@gitlab.com> | 2021-04-21 02:50:22 +0300 |
commit | 9dc93a4519d9d5d7be48ff274127136236a3adb3 (patch) | |
tree | 70467ae3692a0e35e5ea56bcb803eb512a10bedb /app/models/namespaces/traversal/linear.rb | |
parent | 4b0f34b6d759d6299322b3a54453e930c6121ff0 (diff) |
Add latest changes from gitlab-org/gitlab@13-11-stable-eev13.11.0-rc43
Diffstat (limited to 'app/models/namespaces/traversal/linear.rb')
-rw-r--r-- | app/models/namespaces/traversal/linear.rb | 93 |
1 files changed, 93 insertions, 0 deletions
diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb new file mode 100644 index 00000000000..dd9ca8d9bea --- /dev/null +++ b/app/models/namespaces/traversal/linear.rb @@ -0,0 +1,93 @@ +# frozen_string_literal: true +# +# Query a recursively defined namespace hierarchy using linear methods through +# the traversal_ids attribute. +# +# Namespace is a nested hierarchy of one parent to many children. A search +# using only the parent-child relationships is a slow operation. This process +# was previously optimized using Postgresql recursive common table expressions +# (CTE) with acceptable performance. However, it lead to slower than possible +# performance, and resulted in complicated queries that were difficult to make +# performant. +# +# Instead of searching the hierarchy recursively, we store a `traversal_ids` +# attribute on each node. The `traversal_ids` is an ordered array of Namespace +# IDs that define the traversal path from the root Namespace to the current +# Namespace. +# +# For example, suppose we have the following Namespaces: +# +# GitLab (id: 1) > Engineering (id: 2) > Manage (id: 3) > Access (id: 4) +# +# Then `traversal_ids` for group "Access" is [1, 2, 3, 4] +# +# And we can match against other Namespace `traversal_ids` such that: +# +# - Ancestors are [1], [1, 2], [1, 2, 3] +# - Descendants are [1, 2, 3, 4, *] +# - Root is [1] +# - Hierarchy is [1, *] +# +# Note that this search method works so long as the IDs are unique and the +# traversal path is ordered from root to leaf nodes. +# +# We implement this in the database using Postgresql arrays, indexed by a +# generalized inverted index (gin). +module Namespaces + module Traversal + module Linear + extend ActiveSupport::Concern + + UnboundedSearch = Class.new(StandardError) + + included do + after_create :sync_traversal_ids, if: -> { sync_traversal_ids? } + after_update :sync_traversal_ids, if: -> { sync_traversal_ids? && saved_change_to_parent_id? } + + scope :traversal_ids_contains, ->(ids) { where("traversal_ids @> (?)", ids) } + end + + def sync_traversal_ids? + Feature.enabled?(:sync_traversal_ids, root_ancestor, default_enabled: :yaml) + end + + def use_traversal_ids? + Feature.enabled?(:use_traversal_ids, root_ancestor, default_enabled: :yaml) + end + + def self_and_descendants + if use_traversal_ids? + lineage(self) + else + super + end + end + + private + + # Update the traversal_ids for the full hierarchy. + # + # NOTE: self.traversal_ids will be stale. Reload for a fresh record. + def sync_traversal_ids + # Clear any previously memoized root_ancestor as our ancestors have changed. + clear_memoization(:root_ancestor) + + Namespace::TraversalHierarchy.for_namespace(root_ancestor).sync_traversal_ids! + end + + # Make sure we drop the STI `type = 'Group'` condition for better performance. + # Logically equivalent so long as hierarchies remain homogeneous. + def without_sti_condition + self.class.unscope(where: :type) + end + + # Search this namespace's lineage. Bound inclusively by top node. + def lineage(top) + raise UnboundedSearch.new('Must bound search by a top') unless top + + without_sti_condition + .traversal_ids_contains("{#{top.id}}") + end + end + end +end |