Introduce linear ancestors upto in GroupDescendantsFinder
What does this MR do and why?
In this MR, we're switching the behavior of one method in GroupDescendantsFinder to use the linear version. The new behavior is behind the linear_group_descendants_finder_upto feature flag.
How to set up and validate locally
- Enable global traversal ids ff:
Feature.enable(:use_traversal_ids)- Enable specific ff:
Feature.enable(:linear_group_descendants_finder_upto)- Execute the following command:
user = User.first # User with groups
group = user.groups.first.root_ancestor
GroupDescendantsFinder.new(current_user: user, parent_group: group, params: { filter: 'test' }}.executeSQL queries
The former query was:
WITH RECURSIVE "base_and_ancestors" AS (
(SELECT "namespaces".*
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" IN
(SELECT "namespaces"."id"
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND (traversal_ids @> ('{22}'))
AND "namespaces"."id" != 22
AND ("namespaces"."visibility_level" IN (0,
10,
20)
OR EXISTS
(SELECT 1
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" = 1
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" = 1)) 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')
UNION
(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" = 1
AND "members"."access_level" = 5)) 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" = 1
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'
ORDER BY "namespaces"."id" DESC) authorized
WHERE authorized."id" = "namespaces"."id"))
AND "namespaces"."type" != 'Project'
AND ("namespaces"."path" ILIKE '%test%'
OR "namespaces"."name" ILIKE '%test%')
ORDER BY LOWER("namespaces"."name") ASC))
UNION
(SELECT "namespaces".*
FROM "namespaces",
"base_and_ancestors"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" = "base_and_ancestors"."parent_id"
AND "base_and_ancestors"."parent_id" != 22))
SELECT "namespaces".*
FROM "base_and_ancestors" AS "namespaces"The query plan is this and the times (for a heavy group with 3k children) are:
Time: 194.414 ms
- planning: 23.781 ms
- execution: 170.633 ms
- I/O read: 0.000 ms
- I/O write: 0.000 ms
Shared buffers:
- hits: 12724 (~99.40 MiB) from the buffer pool
- reads: 0 from the OS file cache, including disk I/O
- dirtied: 0
- writes: 0The new query is:
WITH "base_ancestors_cte" AS MATERIALIZED
(SELECT "namespaces"."id", "namespaces"."traversal_ids"
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" IN
(SELECT "namespaces"."id"
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND (traversal_ids @> ('{4909902}'))
AND "namespaces"."id" != 4909902
AND ("namespaces"."visibility_level" IN (0, 10, 20)
OR EXISTS
(SELECT 1
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" = 1
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" = 1)) 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')
UNION
(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" = 1
AND "members"."access_level" = 5)) 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" = 1
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'
ORDER BY "namespaces"."id" DESC) authorized
WHERE authorized."id" = "namespaces"."id"))
AND "namespaces"."type" != 'Project'
AND ("namespaces"."path" ILIKE '%test%'
OR "namespaces"."name" ILIKE '%test%')
ORDER BY LOWER("namespaces"."name") ASC)),
"ancestors_cte" AS MATERIALIZED
(SELECT id AS base_id, unnest(traversal_ids) AS ancestor_id
FROM "base_ancestors_cte")
SELECT DISTINCT "namespaces".*
FROM "ancestors_cte",
"namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" = "ancestors_cte"."ancestor_id"
AND "namespaces"."id" NOT IN
(SELECT unnest(traversal_ids)
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" = 4909902)The query plan is this and the times (for the same heavy group) are:
Time: 175.920 ms
- planning: 21.177 ms
- execution: 154.743 ms
- I/O read: 0.000 ms
- I/O write: 0.000 ms
Shared buffers:
- hits: 31703 (~247.70 MiB) from the buffer pool
- reads: 0 from the OS file cache, including disk I/O
- dirtied: 0
- writes: 0MR 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.
Related to #348293 (closed)
Edited by Francisco Javier López (ex-Gitlab)