Resolve "Insulate linear descendant queries"

The PG optimizer can produce an awful plan #339434 (closed) (comment 748505298)

The solution is to wrap the descendant query in to a CTE where the PG optimizer will optimize the CTE as an opaque black box separate from the main query.

This work is behind the traversal_ids_btree feature flag which is currently 100% enabled.

SQL Changes

Query plan

How to set up and validate locally

Using the ruby code:

Feature.enable :use_traversal_ids
Feature.enable :traversal_ids_btree
Group.where(id: [1,86,171]).self_and_descendants.count

New Query

WITH "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" IN (1, 86, 171)
), 
"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 
    "base_cte", 
    "namespaces" 
  WHERE 
    "namespaces"."type" = 'Group' 
    AND (
      "base_cte"."next_traversal_ids" IS NULL 
      OR "base_cte"."next_traversal_ids" > "namespaces"."traversal_ids"
    ) 
    AND next_traversal_ids_sibling("base_cte"."traversal_ids") > "namespaces"."traversal_ids" 
    AND "base_cte"."traversal_ids" <= "namespaces"."traversal_ids"
) 
SELECT 
  COUNT(*) 
FROM 
  "descendants_cte" AS "namespaces"

Old Query

WITH "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" IN (1, 86, 171)
) 
SELECT 
  COUNT(*) 
FROM 
  "base_cte", 
  "namespaces" 
WHERE 
  "namespaces"."type" = 'Group' 
  AND (
    "base_cte"."next_traversal_ids" IS NULL 
    OR "base_cte"."next_traversal_ids" > "namespaces"."traversal_ids"
  ) 
  AND next_traversal_ids_sibling("base_cte"."traversal_ids") > "namespaces"."traversal_ids" 
  AND "base_cte"."traversal_ids" <= "namespaces"."traversal_ids"

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 #346877 (closed)]