Skip to content

Resolve "Replace Namespace#ancestors_upto with linear version"

Alex Pooley requested to merge 324750-replace-namespace-ancestors_upto-with-linear-version into master

What does this MR do and why?

Convert Namespace#ancestors_upto from a recursive query to a linear query.

This work is behind the use_traversal_ids and use_traversal_ids_for_ancestors_upto feature flags.

Part of the linear namespace queries line of work.

Query Plan

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 
  unnest(ARRAY[1, 65, 81]) WITH ORDINALITY AS ancestors(id, ord) 
  INNER JOIN namespaces ON namespaces.id = ancestors.id 
WHERE 
  "namespaces"."type" = 'Group' 
ORDER BY 
  "ancestors"."ord" DESC
# set enable_seqscan=off;

                                                                        QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=4.58..4.58 rows=3 width=372) (actual time=0.120..0.121 rows=3 loops=1)
   Sort Key: ancestors.ord DESC
   Sort Method: quicksort  Memory: 25kB
   ->  Nested Loop  (cost=0.15..4.55 rows=3 width=372) (actual time=0.057..0.079 rows=3 loops=1)
         ->  Function Scan on unnest ancestors  (cost=0.00..0.03 rows=3 width=12) (actual time=0.012..0.013 rows=3 loops=1)
         ->  Index Scan using index_namespaces_on_type_and_id on namespaces  (cost=0.14..1.50 rows=1 width=364) (actual time=0.018..0.019 rows=1 loops=3)
               Index Cond: (((type)::text = 'Group'::text) AND (id = ancestors.id))
 Planning Time: 4.827 ms
 Execution Time: 0.225 ms
(9 rows)

How to set up and validate locally

# Create a group hierarchy
> group = FactoryBot.create :group, :with_hierarchy
> leaf = group.descendants.last

# Enable feature flags
> Feature.enable :use_traversal_ids
> Feature.enable :use_traversal_ids_for_ancestors_upto, group

# Execute #ancestors_upto
> leaf.ancestors_upto
=> [#<Group id:81 @group1/group65/group81>, #<Group id:65 @group1/group65>, #<Group id:1 @group1>]
> leaf.ancestors_upto(leaf.parent)
=> [#<Group id:81 @group1/group65/group81>]

MR acceptance checklist

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

Closes #324750 (closed)

Edited by Alex Pooley

Merge request reports