Skip to content

Use GroupTree ancestors linear scopes

Francisco Javier López (ex-Gitlab) requested to merge 70495-fj-use-group_tree-ancestors_linear_scopes into master

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

  1. Enable the feature flag for linear scopes

    Feature.enable(:use_traversal_ids)

  2. Enable the feature flag for linear ancestors scopes

    Feature.enable(:use_traversal_ids_for_ancestor_scopes)

  3. Enable the feature flag for Ci::Runner linear ancestors scopes

    Feature.enable(:linear_group_tree_ancestor_scopes)

  4. Go to the page http://127.0.0.1:3000/dashboard/groups

  5. Set a filter in the group search box:

image

MR acceptance checklist

This checklist encourages us to confirm any changes have been analyzed to reduce risks in quality, performance, reliability, security, and maintainability.

Edited by Francisco Javier López (ex-Gitlab)

Merge request reports