Linear with_self_and_ancestors scope

What does this MR do and why?

Provide a linear query scope to find all namespaces that descend from a given set of ancestors.

This MR was specifically created to replace the code at !80665 (diffs). That MR has since closed without merge but the scope itself is still considered useful.

SQL

Time: 7.384 ms  
  - planning: 1.274 ms  
  - execution: 6.110 ms  
    - I/O read: 0.000 ms  
    - I/O write: 0.000 ms  
  
Shared buffers:  
  - hits: 1974 (~15.40 MiB) from the buffer pool  
  - reads: 0 from the OS file cache, including disk I/O  
  - dirtied: 0  
  - writes: 0 

SQL Query

WITH "descendants_base_cte" AS MATERIALIZED (
  SELECT 
    "namespaces"."traversal_ids", 
    LEAD (namespaces.traversal_ids, 1) OVER (
      ORDER BY 
        namespaces.traversal_ids ASC
    ) next_traversal_ids 
  FROM 
    "namespaces" 
  WHERE 
    "namespaces"."type" = 'Group' 
    AND "namespaces"."id" = 9970
), 
"descendants_cte" AS MATERIALIZED (
  SELECT 
    "namespaces"."id", 
    "namespaces"."name", 
    "namespaces"."path", 
    "namespaces"."owner_id", 
    "namespaces"."created_at", 
    "namespaces"."updated_at", 
    "namespaces"."type", 
    "namespaces"."description", 
    "namespaces"."avatar", 
    "namespaces"."membership_lock", 
    "namespaces"."share_with_group_lock", 
    "namespaces"."visibility_level", 
    "namespaces"."request_access_enabled", 
    "namespaces"."ldap_sync_status", 
    "namespaces"."ldap_sync_error", 
    "namespaces"."ldap_sync_last_update_at", 
    "namespaces"."ldap_sync_last_successful_update_at", 
    "namespaces"."ldap_sync_last_sync_at", 
    "namespaces"."description_html", 
    "namespaces"."lfs_enabled", 
    "namespaces"."parent_id", 
    "namespaces"."shared_runners_minutes_limit", 
    "namespaces"."repository_size_limit", 
    "namespaces"."require_two_factor_authentication", 
    "namespaces"."two_factor_grace_period", 
    "namespaces"."cached_markdown_version", 
    "namespaces"."project_creation_level", 
    "namespaces"."runners_token", 
    "namespaces"."file_template_project_id", 
    "namespaces"."saml_discovery_token", 
    "namespaces"."runners_token_encrypted", 
    "namespaces"."custom_project_templates_group_id", 
    "namespaces"."auto_devops_enabled", 
    "namespaces"."extra_shared_runners_minutes_limit", 
    "namespaces"."last_ci_minutes_notification_at", 
    "namespaces"."last_ci_minutes_usage_notification_level", 
    "namespaces"."subgroup_creation_level", 
    "namespaces"."emails_disabled", 
    "namespaces"."max_pages_size", 
    "namespaces"."max_artifacts_size", 
    "namespaces"."mentions_disabled", 
    "namespaces"."default_branch_protection", 
    "namespaces"."unlock_membership_to_ldap", 
    "namespaces"."max_personal_access_token_lifetime", 
    "namespaces"."push_rule_id", 
    "namespaces"."shared_runners_enabled", 
    "namespaces"."allow_descendants_override_disabled_shared_runners", 
    "namespaces"."traversal_ids" 
  FROM 
    "descendants_base_cte", 
    "namespaces" 
  WHERE 
    "namespaces"."type" = 'Group' 
    AND (
      "descendants_base_cte"."next_traversal_ids" IS NULL 
      OR "descendants_base_cte"."next_traversal_ids" > "namespaces"."traversal_ids"
    ) 
    AND next_traversal_ids_sibling(
      "descendants_base_cte"."traversal_ids"
    ) > "namespaces"."traversal_ids" 
    AND "descendants_base_cte"."traversal_ids" <= "namespaces"."traversal_ids"
) 
SELECT 
  "namespaces"."id", 
  "namespaces"."name", 
  "namespaces"."path", 
  "namespaces"."owner_id", 
  "namespaces"."created_at", 
  "namespaces"."updated_at", 
  "namespaces"."type", 
  "namespaces"."description", 
  "namespaces"."avatar", 
  "namespaces"."membership_lock", 
  "namespaces"."share_with_group_lock", 
  "namespaces"."visibility_level", 
  "namespaces"."request_access_enabled", 
  "namespaces"."ldap_sync_status", 
  "namespaces"."ldap_sync_error", 
  "namespaces"."ldap_sync_last_update_at", 
  "namespaces"."ldap_sync_last_successful_update_at", 
  "namespaces"."ldap_sync_last_sync_at", 
  "namespaces"."description_html", 
  "namespaces"."lfs_enabled", 
  "namespaces"."parent_id", 
  "namespaces"."shared_runners_minutes_limit", 
  "namespaces"."repository_size_limit", 
  "namespaces"."require_two_factor_authentication", 
  "namespaces"."two_factor_grace_period", 
  "namespaces"."cached_markdown_version", 
  "namespaces"."project_creation_level", 
  "namespaces"."runners_token", 
  "namespaces"."file_template_project_id", 
  "namespaces"."saml_discovery_token", 
  "namespaces"."runners_token_encrypted", 
  "namespaces"."custom_project_templates_group_id", 
  "namespaces"."auto_devops_enabled", 
  "namespaces"."extra_shared_runners_minutes_limit", 
  "namespaces"."last_ci_minutes_notification_at", 
  "namespaces"."last_ci_minutes_usage_notification_level", 
  "namespaces"."subgroup_creation_level", 
  "namespaces"."emails_disabled", 
  "namespaces"."max_pages_size", 
  "namespaces"."max_artifacts_size", 
  "namespaces"."mentions_disabled", 
  "namespaces"."default_branch_protection", 
  "namespaces"."unlock_membership_to_ldap", 
  "namespaces"."max_personal_access_token_lifetime", 
  "namespaces"."push_rule_id", 
  "namespaces"."shared_runners_enabled", 
  "namespaces"."allow_descendants_override_disabled_shared_runners", 
  "namespaces"."traversal_ids" 
FROM 
  "descendants_cte" AS "namespaces" 
WHERE 
  (
    traversal_ids && ARRAY(
      SELECT 
        "namespaces"."id" 
      FROM 
        "namespaces" 
      WHERE 
        "namespaces"."type" = 'Group' 
        AND "namespaces"."id" = 13220026
    )::int[]
  )

How to set up and validate locally

This generates the above SQL.

• Group 9970 is https://gitlab.com/gitlab-org
• Group 13220026 is https://gitlab.com/gitlab-org/incubation-engineering/mlops/ipynb-test-projects

Feature.enable :use_traversal_ids
Feature.enable :traversal_ids_btree
Feature.enable :use_traversal_ids_for_descendants_scopes

puts Group.where(id: 9970).self_and_descendants.with_self_and_ancestors(Group.where(id: 13220026)).to_sql

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.

Related to #352922 (closed)