From 682a7020137680ca07e57733d9adb521a0474453 Mon Sep 17 00:00:00 2001 From: Douwe Maan Date: Mon, 29 May 2017 15:49:56 +0000 Subject: Merge branch 'rework-authorizations-performance' into 'master' Rework project authorizations and nested groups for better performance See merge request !10885 --- lib/api/entities.rb | 5 +- lib/api/groups.rb | 6 +- lib/api/v3/entities.rb | 5 +- lib/api/v3/groups.rb | 6 +- lib/gitlab/group_hierarchy.rb | 104 +++++++++++++++++ .../project_authorizations/with_nested_groups.rb | 125 +++++++++++++++++++++ .../without_nested_groups.rb | 35 ++++++ lib/gitlab/sql/recursive_cte.rb | 62 ++++++++++ 8 files changed, 344 insertions(+), 4 deletions(-) create mode 100644 lib/gitlab/group_hierarchy.rb create mode 100644 lib/gitlab/project_authorizations/with_nested_groups.rb create mode 100644 lib/gitlab/project_authorizations/without_nested_groups.rb create mode 100644 lib/gitlab/sql/recursive_cte.rb (limited to 'lib') 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 -- cgit v1.2.3