Use GroupTree ancestors linear scopes
What does this MR do and why?
In this MR, we're switching the behavior of the method GroupTree#filtered_groups_with_ancestors
to use the linear version. The new behavior is behind the linear_group_tree_ancestor_scopes
feature flag.
Refs #339228 (closed)
Database queries
Disclaimer: The queries shown here are a simplification. The full queries can be found in https://gitlab.com/gitlab-org/gitlab/-/snippets/2176552. The user used to perform the query against is one of our more heavy ones, the gitlab-qa
user with around 6k groups.
The original (recursive) query is:
WITH RECURSIVE base_and_ancestors AS (
(SELECT namespaces.*
FROM namespaces
WHERE namespaces.type = 'Group'
AND namespaces.id IN
(SELECT namespaces.id
FROM (
(WITH RECURSIVE base_and_ancestors AS (
(SELECT namespaces.*
FROM (
(WITH direct_groups AS MATERIALIZED
(SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM namespaces
INNER JOIN members ON namespaces.id = members.source_id
WHERE members.type = 'GroupMember'
AND members.source_type = 'Namespace'
AND namespaces.type = 'Group'
AND members.user_id = 1614863
AND members.requested_at IS NULL
AND (access_level >= 10))
UNION
(SELECT namespaces.*
FROM projects
INNER JOIN project_authorizations ON projects.id = project_authorizations.project_id
INNER JOIN namespaces ON namespaces.id = projects.namespace_id
WHERE project_authorizations.user_id = 1614863)) namespaces
WHERE namespaces.type = 'Group') SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM direct_groups namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces
INNER JOIN group_group_links ON group_group_links.shared_group_id = namespaces.id
WHERE namespaces.type = 'Group'
AND group_group_links.shared_with_group_id IN
(SELECT namespaces.id
FROM direct_groups namespaces
WHERE namespaces.type = 'Group'))) namespaces
WHERE namespaces.type = 'Group')) namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_ancestors
WHERE namespaces.type = 'Group'
AND namespaces.id = base_and_ancestors.parent_id)),
base_and_descendants AS (
(SELECT namespaces.*
FROM namespaces
INNER JOIN members ON namespaces.id = members.source_id
WHERE members.type = 'GroupMember'
AND members.source_type = 'Namespace'
AND namespaces.type = 'Group'
AND members.user_id = 1614863
AND members.requested_at IS NULL
AND (access_level >= 10))
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_descendants
WHERE namespaces.type = 'Group'
AND namespaces.parent_id = base_and_descendants.id)) SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM base_and_ancestors AS namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM base_and_descendants AS namespaces
WHERE namespaces.type = 'Group')) namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces
WHERE namespaces.type = 'Group'
AND namespaces.visibility_level IN (10,
20))) namespaces
WHERE namespaces.type = 'Group'
AND (namespaces.path ILIKE '%git%'
OR namespaces.name ILIKE '%git%')
ORDER BY namespaces.id DESC
LIMIT 20
OFFSET 0))
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_ancestors
WHERE namespaces.type = 'Group'
AND namespaces.id = base_and_ancestors.parent_id))
SELECT namespaces.*
FROM base_and_ancestors AS namespaces
This is the query plan and the times are:
Planning Time: 12.539 ms
Execution Time: 1134.158 ms
The new linear query is:
SELECT namespaces.*
FROM
(SELECT namespaces.*
FROM namespaces
WHERE namespaces.id IN
(SELECT unnest(traversal_ids)
FROM namespaces
WHERE namespaces.id IN
(SELECT namespaces.id
FROM (
(WITH RECURSIVE base_and_ancestors AS (
(SELECT namespaces.*
FROM (
(WITH direct_groups AS MATERIALIZED
(SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM namespaces
INNER JOIN members ON namespaces.id = members.source_id
WHERE members.type = 'GroupMember'
AND members.source_type = 'Namespace'
AND namespaces.type = 'Group'
AND members.user_id = 1614863
AND members.requested_at IS NULL
AND (access_level >= 10))
UNION
(SELECT namespaces.*
FROM projects
INNER JOIN project_authorizations ON projects.id = project_authorizations.project_id
INNER JOIN namespaces ON namespaces.id = projects.namespace_id
WHERE project_authorizations.user_id = 1614863)) namespaces
WHERE namespaces.type = 'Group') SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM direct_groups namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces
INNER JOIN group_group_links ON group_group_links.shared_group_id = namespaces.id
WHERE namespaces.type = 'Group'
AND group_group_links.shared_with_group_id IN
(SELECT namespaces.id
FROM direct_groups namespaces
WHERE namespaces.type = 'Group'))) namespaces
WHERE namespaces.type = 'Group')) namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_ancestors
WHERE namespaces.type = 'Group'
AND namespaces.id = base_and_ancestors.parent_id)),
base_and_descendants AS (
(SELECT namespaces.*
INNER JOIN members ON namespaces.id = members.source_id
WHERE members.type = 'GroupMember'
AND members.source_type = 'Namespace'
AND namespaces.type = 'Group'
AND members.user_id = 1614863
AND members.requested_at IS NULL
AND (access_level >= 10))
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_descendants
WHERE namespaces.type = 'Group'
AND namespaces.parent_id = base_and_descendants.id)) SELECT namespaces.*
FROM (
(SELECT namespaces.*
FROM base_and_ancestors AS namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM base_and_descendants AS namespaces
WHERE namespaces.type = 'Group')) namespaces
WHERE namespaces.type = 'Group')
UNION
(SELECT namespaces.*
FROM namespaces
WHERE namespaces.type = 'Group'
AND namespaces.visibility_level IN (10,
20))) namespaces
WHERE namespaces.type = 'Group'
AND (namespaces.path ILIKE '%git%'
OR namespaces.name ILIKE '%git%')
ORDER BY namespaces.id DESC
LIMIT 20
OFFSET 0))) namespaces
This is the query plan and the times are:
Planning Time: 9.953 ms
Execution Time: 933.328 ms
How to set up and validate locally
-
Enable the feature flag for linear scopes
Feature.enable(:use_traversal_ids)
-
Enable the feature flag for linear ancestors scopes
Feature.enable(:use_traversal_ids_for_ancestor_scopes)
-
Enable the feature flag for
Ci::Runner
linear ancestors scopesFeature.enable(:linear_group_tree_ancestor_scopes)
-
Go to the page
http://127.0.0.1:3000/dashboard/groups
-
Set a filter in the group search box:
MR acceptance checklist
This checklist encourages us to confirm any changes have been analyzed to reduce risks in quality, performance, reliability, security, and maintainability.
-
I have evaluated the MR acceptance checklist for this MR.