Use linear versions of descendants in GroupDescendantsFinder
What does this MR do?
In this MR, we're switching the behavior of two methods in GroupDescendantsFinder to use the linear version. The new behavior is behind the linear_group_descendants_finder feature flag.
How to setup and validate locally (strongly suggested)
- Enable the new method behavior feature flag
Feature.enable(:linear_group_descendants_finder) - In rails console enable the traversal id feature flag
Feature.enable(:use_traversal_ids)
SQL Queries
The namespaces used in these queries have eleven children and the user id used is the one for the gitlab-qa user.
GroupDescendantsFinder#projects_matching_filter
The former sql was:
SELECT *
FROM "projects"
WHERE (EXISTS
(SELECT 1
FROM "project_authorizations"
WHERE "project_authorizations"."user_id" = 1
AND (project_authorizations.project_id = projects.id))
OR projects.visibility_level IN (0,
10,
20))
AND "projects"."id" IN
(SELECT "projects"."id"
FROM "projects"
WHERE "projects"."namespace_id" IN
(WITH RECURSIVE "base_and_descendants" AS (
(SELECT *
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."id" = 9970)
UNION
(SELECT *
FROM "namespaces",
"base_and_descendants"
WHERE "namespaces"."type" = 'Group'
AND "namespaces"."parent_id" = "base_and_descendants"."id")) SELECT "id"
FROM "base_and_descendants" AS "namespaces"))
AND (("projects"."path" ILIKE '%gitlab%'
OR "projects"."name" ILIKE '%gitlab%')
OR "projects"."description" ILIKE '%gitlab%')
AND "projects"."archived" = FALSE
ORDER BY "projects"."id" DESCThis is the plan for the query and the time summary is:
Time: 54.135 ms
- planning: 13.216 ms
- execution: 40.919 ms
- I/O read: 0.000 ms
- I/O write: 0.000 ms
Shared buffers:
- hits: 12764 (~99.70 MiB) from the buffer pool
- reads: 0 from the OS file cache, including disk I/O
- dirtied: 0
- writes: 0The new sql is:
SELECT *
FROM "projects"
WHERE (EXISTS
(SELECT 1
FROM "project_authorizations"
WHERE "project_authorizations"."user_id" = 1
AND (project_authorizations.project_id = projects.id))
OR projects.visibility_level IN (0,
10,
20))
AND "projects"."id" IN
(SELECT "projects"."id"
FROM "projects"
WHERE "projects"."namespace_id" IN
(SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND (traversal_ids @> ('{9970}'))))
AND (("projects"."path" ILIKE '%gitlab%'
OR "projects"."name" ILIKE '%gitlab%')
OR "projects"."description" ILIKE '%gitlab%')
AND "projects"."archived" = FALSE
ORDER BY "projects"."id" DESCThis is the query plan and the time summary is:
Time: 42.190 ms
- planning: 7.861 ms
- execution: 34.329 ms
- I/O read: 0.000 ms
- I/O write: 0.000 ms
Shared buffers:
- hits: 11708 (~91.50 MiB) from the buffer pool
- reads: 0 from the OS file cache, including disk I/O
- dirtied: 0
- writes: 0
GroupDescendantsFinder#all_visible_descendant_groups
The former sql was:
WITH RECURSIVE base_and_descendants AS (
(SELECT namespaces.*
FROM namespaces
WHERE namespaces.type = 'Group'
AND namespaces.id = 2089817)
UNION
(SELECT namespaces.*
FROM namespaces,
base_and_descendants
WHERE namespaces.type = 'Group'
AND namespaces.parent_id = base_and_descendants.id))
SELECT namespaces.*
FROM base_and_descendants AS namespaces
WHERE namespaces.id NOT IN
(SELECT namespaces.id
FROM namespaces
WHERE namespaces.type = 'Group'
AND namespaces.id = 2089817)
AND (namespaces.visibility_level IN (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 = 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'
ORDER BY namespaces.id DESC) authorized
WHERE authorized.id = namespaces.id))This is the query plan and the time summary is:
Time: 22.154 ms
- planning: 17.915 ms
- execution: 4.239 ms
- I/O read: 0.000 ms
- I/O write: 0.000 ms
Shared buffers:
- hits: 3 (~24.00 KiB) from the buffer pool
- reads: 0 from the OS file cache, including disk I/O
- dirtied: 0
- writes: 0The new sql is:
SELECT "namespaces".*
FROM "namespaces"
WHERE "namespaces"."type" = 'Group'
AND (traversal_ids @> ('{9970}'))
AND "namespaces"."id" != 9970
AND ("namespaces"."visibility_level" IN (0,
10,
20)
OR EXISTS
(SELECT 1
FROM
(WITH RECURSIVE "base_and_ancestors" AS (
(SELECT *
FROM (
(WITH "direct_groups" AS MATERIALIZED
(SELECT *
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 *
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 *
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 *
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"))This is the query plan and the time summary:
Planning Time: 15.880 ms
Execution Time: 5.202 msDoes this MR meet the acceptance criteria?
Conformity
-
I have included changelog trailers, or none are needed. (Does this MR need a changelog?) -
I have properly separated EE content from FOSS, or this MR is FOSS only. (Where should EE code go?) -
I have self-reviewed this MR per code review guidelines. -
This MR does not harm performance, or I have asked a reviewer to help assess the performance impact. (Merge request performance guidelines) -
I have followed the style guides. -
This change is backwards compatible across updates, or this does not apply.
Related to #332298 (closed)
Edited by Francisco Javier López