Traversal ids queries

What does this MR do?

Closes #230456 (closed)

Currently to query the namespace hierarchy we must use recursive methods through Gitlab::ObjectHierarchy. We can query the namespace hierarchy a lot faster and easier if we store the path from the root ancestor to each namespace as an attribute on the namespace. We will store this on a new traversal_id attribute on Namespaces.

Say we have this Namespace hierarchy...

graph TD;
    gitlab-->backend;
    backend-->create;
    backend-->manage;
    create-->source;
    manage-->access;
    gitlab-->frontend;

Then the path from gitlab to access is gitlab / backend / manage / access. The path from gitlab to source is gitlab / backend / create / source.

We can use this structure for fast queries. If the current namespace is backend then all our descendants match the path gitlab / backend / *, all our ancestors match the path * / backend, and everyone in the same Namespace hierarchy matches gitlab / *.

We store that path using an array of Namespace ids in a new column on Namespace called traversal_ids.

The recursive Namespace query methods have been moved to a module at app/models/concerns/namespace/recursive_traversal.rb. Feature flags have been included to toggle between using recursive and linear querying methods.

Screenshots

Does this MR meet the acceptance criteria?

Conformity

• Changelog entry
• Documentation (if required)
• Code review guidelines
• Merge request performance guidelines
• Style guides
• Database guides
• Separation of EE specific content

Availability and Testing

• Review and add/update tests for this feature/bug. Consider all test levels. See the Test Planning Process.
• Tested in all supported browsers
• Informed Infrastructure department of a default or new setting change, if applicable per definition of done

Security

If this MR contains changes to processing or storing of credentials or tokens, authorization and authentication methods and other items described in the security review guidelines:

• Label as security and @ mention @gitlab-com/gl-security/appsec
• The MR includes necessary changes to maintain consistency between UI, API, email, or other methods
• Security reports checked/validated by a reviewer from the AppSec team

app/models/namespace/traversal_hierarchy.rb

+# frozen_string_literal: true
+#
+# A Namespace::TraversalHierarchy is the collection of namespaces that descend
+# from a root Namespace as defined by the Namespace#traversal_ids attributes.
+#
+# This class provides operations to be performed on the hierarchy itself,
+# rather than individual namespaces.
+#
+# This includes methods for synchronizing traversal_ids attributes to a correct
+# state. We use recursive methods to determine the correct state so we don't
+# have to depend on the integrity of the traversal_ids attribute values
+# themselves.
+#
+class Namespace
+  class TraversalHierarchy
+    attr_accessor :root
+
+    def self.for_namespace(namespace)
+      new(recursive_root_ancestor(namespace))
+    end
+
+    def initialize(root)
+      @root = root
+    end
+
+    # Update all traversal_ids in the current namespace hierarchy.
+    def sync_traversal_ids!
+      # An issue in Rails since 2013 prevents this kind of join based update in
+      # ActiveRecord. https://github.com/rails/rails/issues/13496
+      # Ideally it would be:
+      #   `incorrect_traversal_ids.update_all('traversal_ids = cte.traversal_ids')`
+      sql = """
+            UPDATE namespaces
+            SET traversal_ids = cte.traversal_ids
+            FROM (#{recursive_traversal_ids}) as cte
+            WHERE namespaces.id = cte.id
+              AND namespaces.traversal_ids <> cte.traversal_ids
+            """
+      Namespace.connection.exec_query(sql)
+    end
+
+    # Identify all incorrect traversal_ids in the current namespace hierarchy.
+    def incorrect_traversal_ids
+      Namespace \
+        .joins("INNER JOIN (#{recursive_traversal_ids}) as cte ON namespaces.id = cte.id")
+        .where('namespaces.traversal_ids <> cte.traversal_ids')
+    end
+
+    private
+
+    # Determine traversal_ids for the namespace hierarchy using recursive methods.
+    # Generate a collection of [id, traversal_ids] rows.
+    #
+    # Note that the traversal_ids represent a calculated traversal path for the
+    # namespace and not the value stored within the traversal_ids attribute.
+    def recursive_traversal_ids
+      root_id = Integer(@root.id)
+
+      """
+      WITH RECURSIVE cte(id, traversal_ids, cycle) AS (
+        VALUES(#{root_id}, ARRAY[#{root_id}], false)
+      UNION ALL
+        SELECT n.id, cte.traversal_ids || n.id, n.id = ANY(cte.traversal_ids)
+        FROM namespaces n, cte
+        WHERE n.parent_id = cte.id AND NOT cycle
+      )
+      SELECT id, traversal_ids FROM cte
+      """
+    end
+
+    # This is essentially Namespace#root_ancestor which will soon be rewritten
+    # to use traversal_ids. We replicate here as a reliable way to find the
+    # root using recursive methods.
+    def self.recursive_root_ancestor(namespace)
+      Gitlab::ObjectHierarchy
+        .new(Namespace.where(id: namespace))
+        .base_and_ancestors
+        .reorder(nil)
+        .find_by(parent_id: nil)
+    end
+  end
+end