Merge branch 'rework-authorizations-performance' into 'master'

Rework project authorizations and nested groups for better performance

See merge request !10885

8 files changed, 344 insertions, 4 deletions

diff --git a/lib/api/entities.rb b/lib/api/entities.rb
index f8f5548d23d..9f8304f7690 100644
--- a/lib/api/entities.rb
+++ b/lib/api/entities.rb
@@ -145,7 +145,10 @@ module API
       expose :web_url
       expose :request_access_enabled
       expose :full_name, :full_path
-      expose :parent_id
+
+      if ::Group.supports_nested_groups?
+        expose :parent_id
+      end
 
       expose :statistics, if: :statistics do
         with_options format_with: -> (value) { value.to_i } do
diff --git a/lib/api/groups.rb b/lib/api/groups.rb
index 9ccc75681f9..2c09725601e 100644
--- a/lib/api/groups.rb
+++ b/lib/api/groups.rb
@@ -70,7 +70,11 @@ module API
       params do
         requires :name, type: String, desc: 'The name of the group'
         requires :path, type: String, desc: 'The path of the group'
-        optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+
+        if ::Group.supports_nested_groups?
+          optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+        end
+
         use :optional_params
       end
       post do
diff --git a/lib/api/v3/entities.rb b/lib/api/v3/entities.rb
index 7c8be7e51db..1c08e25c00c 100644
--- a/lib/api/v3/entities.rb
+++ b/lib/api/v3/entities.rb
@@ -133,7 +133,10 @@ module API
         expose :web_url
         expose :request_access_enabled
         expose :full_name, :full_path
-        expose :parent_id
+
+        if ::Group.supports_nested_groups?
+          expose :parent_id
+        end
 
         expose :statistics, if: :statistics do
           with_options format_with: -> (value) { value.to_i } do
diff --git a/lib/api/v3/groups.rb b/lib/api/v3/groups.rb
index dbf7a3cf785..42922df6e29 100644
--- a/lib/api/v3/groups.rb
+++ b/lib/api/v3/groups.rb
@@ -74,7 +74,11 @@ module API
         params do
           requires :name, type: String, desc: 'The name of the group'
           requires :path, type: String, desc: 'The path of the group'
-          optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+
+          if ::Group.supports_nested_groups?
+            optional :parent_id, type: Integer, desc: 'The parent group id for creating nested group'
+          end
+
           use :optional_params
         end
         post do
diff --git a/lib/gitlab/group_hierarchy.rb b/lib/gitlab/group_hierarchy.rb
new file mode 100644
index 00000000000..e9d5d52cabb
--- /dev/null
+++ b/lib/gitlab/group_hierarchy.rb
@@ -0,0 +1,104 @@
+module Gitlab
+  # Retrieving of parent or child groups based on a base ActiveRecord relation.
+  #
+  # This class uses recursive CTEs and as a result will only work on PostgreSQL.
+  class GroupHierarchy
+    attr_reader :base, :model
+
+    # base - An instance of ActiveRecord::Relation for which to get parent or
+    #        child groups.
+    def initialize(base)
+      @base = base
+      @model = base.model
+    end
+
+    # Returns a relation that includes the base set of groups and all their
+    # ancestors (recursively).
+    def base_and_ancestors
+      return model.none unless Group.supports_nested_groups?
+
+      base_and_ancestors_cte.apply_to(model.all)
+    end
+
+    # Returns a relation that includes the base set of groups and all their
+    # descendants (recursively).
+    def base_and_descendants
+      return model.none unless Group.supports_nested_groups?
+
+      base_and_descendants_cte.apply_to(model.all)
+    end
+
+    # Returns a relation that includes the base groups, their ancestors, and the
+    # descendants of the base groups.
+    #
+    # The resulting query will roughly look like the following:
+    #
+    #     WITH RECURSIVE ancestors AS ( ... ),
+    #       descendants AS ( ... )
+    #     SELECT *
+    #     FROM (
+    #       SELECT *
+    #       FROM ancestors namespaces
+    #
+    #       UNION
+    #
+    #       SELECT *
+    #       FROM descendants namespaces
+    #     ) groups;
+    #
+    # Using this approach allows us to further add criteria to the relation with
+    # Rails thinking it's selecting data the usual way.
+    def all_groups
+      return base unless Group.supports_nested_groups?
+
+      ancestors = base_and_ancestors_cte
+      descendants = base_and_descendants_cte
+
+      ancestors_table = ancestors.alias_to(groups_table)
+      descendants_table = descendants.alias_to(groups_table)
+
+      union = SQL::Union.new([model.unscoped.from(ancestors_table),
+                              model.unscoped.from(descendants_table)])
+
+      model.
+        unscoped.
+        with.
+        recursive(ancestors.to_arel, descendants.to_arel).
+        from("(#{union.to_sql}) #{model.table_name}")
+    end
+
+    private
+
+    def base_and_ancestors_cte
+      cte = SQL::RecursiveCTE.new(:base_and_ancestors)
+
+      cte << base.except(:order)
+
+      # Recursively get all the ancestors of the base set.
+      cte << model.
+        from([groups_table, cte.table]).
+        where(groups_table[:id].eq(cte.table[:parent_id])).
+        except(:order)
+
+      cte
+    end
+
+    def base_and_descendants_cte
+      cte = SQL::RecursiveCTE.new(:base_and_descendants)
+
+      cte << base.except(:order)
+
+      # Recursively get all the descendants of the base set.
+      cte << model.
+        from([groups_table, cte.table]).
+        where(groups_table[:parent_id].eq(cte.table[:id])).
+        except(:order)
+
+      cte
+    end
+
+    def groups_table
+      model.arel_table
+    end
+  end
+end
diff --git a/lib/gitlab/project_authorizations/with_nested_groups.rb b/lib/gitlab/project_authorizations/with_nested_groups.rb
new file mode 100644
index 00000000000..bb0df1e3dad
--- /dev/null
+++ b/lib/gitlab/project_authorizations/with_nested_groups.rb
@@ -0,0 +1,125 @@
+module Gitlab
+  module ProjectAuthorizations
+    # Calculating new project authorizations when supporting nested groups.
+    #
+    # This class relies on Common Table Expressions to efficiently get all data,
+    # including data for nested groups. As a result this class can only be used
+    # on PostgreSQL.
+    class WithNestedGroups
+      attr_reader :user
+
+      # user - The User object for which to calculate the authorizations.
+      def initialize(user)
+        @user = user
+      end
+
+      def calculate
+        cte = recursive_cte
+        cte_alias = cte.table.alias(Group.table_name)
+        projects = Project.arel_table
+        links = ProjectGroupLink.arel_table
+
+        relations = [
+          # The project a user has direct access to.
+          user.projects.select_for_project_authorization,
+
+          # The personal projects of the user.
+          user.personal_projects.select_as_master_for_project_authorization,
+
+          # Projects that belong directly to any of the groups the user has
+          # access to.
+          Namespace.
+            unscoped.
+            select([alias_as_column(projects[:id], 'project_id'),
+                    cte_alias[:access_level]]).
+            from(cte_alias).
+            joins(:projects),
+
+          # Projects shared with any of the namespaces the user has access to.
+          Namespace.
+            unscoped.
+            select([links[:project_id],
+                    least(cte_alias[:access_level],
+                          links[:group_access],
+                          'access_level')]).
+            from(cte_alias).
+            joins('INNER JOIN project_group_links ON project_group_links.group_id = namespaces.id').
+            joins('INNER JOIN projects ON projects.id = project_group_links.project_id').
+            joins('INNER JOIN namespaces p_ns ON p_ns.id = projects.namespace_id').
+            where('p_ns.share_with_group_lock IS FALSE')
+        ]
+
+        union = Gitlab::SQL::Union.new(relations)
+
+        ProjectAuthorization.
+          unscoped.
+          with.
+          recursive(cte.to_arel).
+          select_from_union(union)
+      end
+
+      private
+
+      # Builds a recursive CTE that gets all the groups the current user has
+      # access to, including any nested groups.
+      def recursive_cte
+        cte = Gitlab::SQL::RecursiveCTE.new(:namespaces_cte)
+        members = Member.arel_table
+        namespaces = Namespace.arel_table
+
+        # Namespaces the user is a member of.
+        cte << user.groups.
+          select([namespaces[:id], members[:access_level]]).
+          except(:order)
+
+        # Sub groups of any groups the user is a member of.
+        cte << Group.select([namespaces[:id],
+                             greatest(members[:access_level],
+                                      cte.table[:access_level], 'access_level')]).
+          joins(join_cte(cte)).
+          joins(join_members).
+          except(:order)
+
+        cte
+      end
+
+      # Builds a LEFT JOIN to join optional memberships onto the CTE.
+      def join_members
+        members = Member.arel_table
+        namespaces = Namespace.arel_table
+
+        cond = members[:source_id].
+          eq(namespaces[:id]).
+          and(members[:source_type].eq('Namespace')).
+          and(members[:requested_at].eq(nil)).
+          and(members[:user_id].eq(user.id))
+
+        Arel::Nodes::OuterJoin.new(members, Arel::Nodes::On.new(cond))
+      end
+
+      # Builds an INNER JOIN to join namespaces onto the CTE.
+      def join_cte(cte)
+        namespaces = Namespace.arel_table
+        cond = cte.table[:id].eq(namespaces[:parent_id])
+
+        Arel::Nodes::InnerJoin.new(cte.table, Arel::Nodes::On.new(cond))
+      end
+
+      def greatest(left, right, column_alias)
+        sql_function('GREATEST', [left, right], column_alias)
+      end
+
+      def least(left, right, column_alias)
+        sql_function('LEAST', [left, right], column_alias)
+      end
+
+      def sql_function(name, args, column_alias)
+        alias_as_column(Arel::Nodes::NamedFunction.new(name, args), column_alias)
+      end
+
+      def alias_as_column(value, alias_to)
+        Arel::Nodes::As.new(value, Arel::Nodes::SqlLiteral.new(alias_to))
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/project_authorizations/without_nested_groups.rb b/lib/gitlab/project_authorizations/without_nested_groups.rb
new file mode 100644
index 00000000000..627e8c5fba2
--- /dev/null
+++ b/lib/gitlab/project_authorizations/without_nested_groups.rb
@@ -0,0 +1,35 @@
+module Gitlab
+  module ProjectAuthorizations
+    # Calculating new project authorizations when not supporting nested groups.
+    class WithoutNestedGroups
+      attr_reader :user
+
+      # user - The User object for which to calculate the authorizations.
+      def initialize(user)
+        @user = user
+      end
+
+      def calculate
+        relations = [
+          # Projects the user is a direct member of
+          user.projects.select_for_project_authorization,
+
+          # Personal projects
+          user.personal_projects.select_as_master_for_project_authorization,
+
+          # Projects of groups the user is a member of
+          user.groups_projects.select_for_project_authorization,
+
+          # Projects shared with groups the user is a member of
+          user.groups.joins(:shared_projects).select_for_project_authorization
+        ]
+
+        union = Gitlab::SQL::Union.new(relations)
+
+        ProjectAuthorization.
+          unscoped.
+          select_from_union(union)
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/sql/recursive_cte.rb b/lib/gitlab/sql/recursive_cte.rb
new file mode 100644
index 00000000000..5b1b03820a3
--- /dev/null
+++ b/lib/gitlab/sql/recursive_cte.rb
@@ -0,0 +1,62 @@
+module Gitlab
+  module SQL
+    # Class for easily building recursive CTE statements.
+    #
+    # Example:
+    #
+    #     cte = RecursiveCTE.new(:my_cte_name)
+    #     ns = Arel::Table.new(:namespaces)
+    #
+    #     cte << Namespace.
+    #       where(ns[:parent_id].eq(some_namespace_id))
+    #
+    #     cte << Namespace.
+    #       from([ns, cte.table]).
+    #       where(ns[:parent_id].eq(cte.table[:id]))
+    #
+    #     Namespace.with.
+    #       recursive(cte.to_arel).
+    #       from(cte.alias_to(ns))
+    class RecursiveCTE
+      attr_reader :table
+
+      # name - The name of the CTE as a String or Symbol.
+      def initialize(name)
+        @table = Arel::Table.new(name)
+        @queries = []
+      end
+
+      # Adds a query to the body of the CTE.
+      #
+      # relation - The relation object to add to the body of the CTE.
+      def <<(relation)
+        @queries << relation
+      end
+
+      # Returns the Arel relation for this CTE.
+      def to_arel
+        sql = Arel::Nodes::SqlLiteral.new(Union.new(@queries).to_sql)
+
+        Arel::Nodes::As.new(table, Arel::Nodes::Grouping.new(sql))
+      end
+
+      # Returns an "AS" statement that aliases the CTE name as the given table
+      # name. This allows one to trick ActiveRecord into thinking it's selecting
+      # from an actual table, when in reality it's selecting from a CTE.
+      #
+      # alias_table - The Arel table to use as the alias.
+      def alias_to(alias_table)
+        Arel::Nodes::As.new(table, alias_table)
+      end
+
+      # Applies the CTE to the given relation, returning a new one that will
+      # query from it.
+      def apply_to(relation)
+        relation.except(:where).
+          with.
+          recursive(to_arel).
+          from(alias_to(relation.model.arel_table))
+      end
+    end
+  end
+end