Resolve "Query multiple group ancestors at once"

Merged Alex Pooley requested to merge 337818-query-multiple-group-ancestors-at-once into master

What does this MR do?

Introduces a recursive and linear version of self_and_ancestors and self_and_ancestor_ids scopes to Group.

As a secondary, the linear concern also introduces a order_by_depth and normal_select scope.

The primary scopes are placed behind the use_traversal_ids_for_ancestor_scopes feature flag, which is further reliant on the higher level use_traversal_ids feature flag.

self_and_ancestors(include_self: true, hierarchy_order: nil)

These are the method's default arguments.

Linear

SELECT 
  "namespaces".* 
FROM 
  (
    SELECT 
      "namespaces".* 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."id" IN (
        SELECT 
          unnest(traversal_ids) 
        FROM 
          "namespaces" 
        WHERE 
          "namespaces"."id" IN (11681146, 10350969)
      )
  ) namespaces
Time: 5.436 ms  
  - planning: 3.338 ms  
  - execution: 2.098 ms  
    - I/O read: 1.741 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 26 (~208.00 KiB) from the buffer pool  
  - reads: 25 (~200.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0  

https://postgres.ai/console/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21796

Recursive

WITH RECURSIVE "base_and_ancestors" AS (
  (
    SELECT 
      "namespaces".* 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."type" = 'Group' 
      AND "namespaces"."id" IN (11681146, 10350969)
  ) 
  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"
Time: 12.274 ms  
  - planning: 3.910 ms  
  - execution: 8.364 ms  
    - I/O read: 7.513 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 19 (~152.00 KiB) from the buffer pool  
  - reads: 26 (~208.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0  

https://console.postgres.ai/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21800

self_and_ancestors(include_self: false, hierarchy_order: :asc)

These arguments exercise all method paths.

Linear

SELECT 
  "namespaces".* 
FROM 
  (
    SELECT 
      *, 
      array_length(traversal_ids, 1) as depth 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."id" IN (
        SELECT 
          unnest(traversal_ids) 
        FROM 
          "namespaces" 
        WHERE 
          "namespaces"."id" IN (11681146, 10350969)
      ) 
    ORDER BY 
      "depth" DESC, 
      "namespaces"."id" ASC
  ) namespaces 
WHERE 
  "namespaces"."id" NOT IN (
    SELECT 
      namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1) ] AS id 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."type" = 'Group' 
      AND "namespaces"."id" IN (11681146, 10350969)
  )
Time: 5.944 ms  
  - planning: 3.335 ms  
  - execution: 2.609 ms  
    - I/O read: 2.153 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 32 (~256.00 KiB) from the buffer pool  
  - reads: 31 (~248.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0  

https://postgres.ai/console/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21798

Recursive

WITH RECURSIVE "base_and_ancestors" AS (
  (
    SELECT 
      1 as depth, 
      ARRAY[namespaces.id] AS tree_path, 
      false AS tree_cycle, 
      "namespaces".* 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."type" = 'Group' 
      AND "namespaces"."id" IN (11681146, 10350969)
  ) 
  UNION 
    (
      SELECT 
        ("base_and_ancestors"."depth" + 1), 
        tree_path || "namespaces".id, 
        "namespaces".id = ANY(tree_path), 
        "namespaces".* 
      FROM 
        "namespaces", 
        "base_and_ancestors" 
      WHERE 
        "namespaces"."type" = 'Group' 
        AND "namespaces"."id" = "base_and_ancestors"."parent_id" 
        AND "base_and_ancestors"."tree_cycle" = FALSE
    )
) 
SELECT 
  "namespaces".* 
FROM 
  "base_and_ancestors" AS "namespaces" 
WHERE 
  "namespaces"."id" NOT IN (
    SELECT 
      "namespaces"."id" 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."type" = 'Group' 
      AND "namespaces"."id" IN (11681146, 10350969)
  ) 
ORDER BY 
  "depth" ASC
Time: 7.943 ms  
  - planning: 3.630 ms  
  - execution: 4.313 ms  
    - I/O read: 3.478 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 33 (~264.00 KiB) from the buffer pool  
  - reads: 28 (~224.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0 

https://postgres.ai/console/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21802

self_and_ancestor_ids(include_self: true)

Linear

SELECT 
  namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1) ] AS id 
FROM 
  (
    SELECT 
      "namespaces".* 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."id" IN (
        SELECT 
          unnest(traversal_ids) 
        FROM 
          "namespaces" 
        WHERE 
          "namespaces"."id" IN (11681146, 10350969)
      )
  ) namespaces
Time: 5.263 ms  
  - planning: 2.869 ms  
  - execution: 2.394 ms  
    - I/O read: 2.013 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 26 (~208.00 KiB) from the buffer pool  
  - reads: 25 (~200.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0  

https://postgres.ai/console/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21808

Recursive

WITH RECURSIVE "base_and_ancestors" AS (
  (
    SELECT 
      "namespaces".* 
    FROM 
      "namespaces" 
    WHERE 
      "namespaces"."type" = 'Group' 
      AND "namespaces"."id" IN (11681146, 10350969)
  ) 
  UNION 
    (
      SELECT 
        "namespaces".* 
      FROM 
        "namespaces", 
        "base_and_ancestors" 
      WHERE 
        "namespaces"."type" = 'Group' 
        AND "namespaces"."id" = "base_and_ancestors"."parent_id"
    )
) 
SELECT 
  id 
FROM 
  "base_and_ancestors" AS "namespaces"
Time: 5.595 ms  
  - planning: 3.269 ms  
  - execution: 2.326 ms  
    - I/O read: 1.764 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 19 (~152.00 KiB) from the buffer pool  
  - reads: 26 (~208.00 KiB) from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0  

https://postgres.ai/console/gitlab/gitlab-production-tunnel-pg12/sessions/6392/commands/21806

Screenshots or Screencasts (strongly suggested)

How to setup and validate locally (strongly suggested)

Does this MR meet the acceptance criteria?

Conformity

Availability and Testing

Security

Does this MR contain changes to processing or storing of credentials or tokens, authorization and authentication methods or other items described in the security review guidelines? If not, then delete this Security section.

  • Label as security and @ mention @gitlab-com/gl-security/appsec
  • The MR includes necessary changes to maintain consistency between UI, API, email, or other methods
  • Security reports checked/validated by a reviewer from the AppSec team

Related to #337818 (closed)

Edited by Alex Pooley