Module: Namespaces

Defined in:

app/finders/namespaces/projects_finder.rb,
app/models/namespaces/ldap_setting.rb,
app/models/namespaces/user_namespace.rb,
app/models/namespaces/traversal/linear.rb,
app/models/namespaces/project_namespace.rb,
app/models/namespaces/traversal/recursive.rb,
app/models/namespaces/randomized_suffix_path.rb,
app/models/namespaces/traversal/linear_scopes.rb,
app/policies/namespaces/user_namespace_policy.rb,
app/workers/namespaces/root_statistics_worker.rb,
app/models/namespaces/traversal/recursive_scopes.rb,
app/policies/namespaces/project_namespace_policy.rb,
app/workers/namespaces/process_sync_events_worker.rb,
app/workers/namespaces/schedule_aggregation_worker.rb,
app/services/namespaces/statistics_refresher_service.rb,
app/workers/namespaces/update_root_statistics_worker.rb,
app/services/namespaces/package_settings/update_service.rb,
app/workers/namespaces/prune_aggregation_schedules_worker.rb,
app/services/namespaces/in_product_marketing_emails_service.rb,
app/policies/namespaces/group_project_namespace_shared_policy.rb

Overview

Query a recursively defined namespace hierarchy using linear methods through the traversal_ids attribute.

Namespace is a nested hierarchy of one parent to many children. A search using only the parent-child relationships is a slow operation. This process was previously optimized using Postgresql recursive common table expressions (CTE) with acceptable performance. However, it lead to slower than possible performance, and resulted in complicated queries that were difficult to make performant.

Instead of searching the hierarchy recursively, we store a ‘traversal_ids` attribute on each node. The `traversal_ids` is an ordered array of Namespace IDs that define the traversal path from the root Namespace to the current Namespace.

For example, suppose we have the following Namespaces:

GitLab (id: 1) > Engineering (id: 2) > Manage (id: 3) > Access (id: 4)

Then ‘traversal_ids` for group “Access” is [1, 2, 3, 4]

And we can match against other Namespace ‘traversal_ids` such that:

• Ancestors are [1], [1, 2], [1, 2, 3]

• Descendants are [1, 2, 3, 4, *]

• Root is [1]

• Hierarchy is [1, *]

Note that this search method works so long as the IDs are unique and the traversal path is ordered from root to leaf nodes.

We implement this in the database using Postgresql arrays, indexed by a generalized inverted index (gin).

Defined Under Namespace

Modules: PackageSettings, Traversal Classes: GroupProjectNamespaceSharedPolicy, InProductMarketingEmailsService, LdapSetting, ProcessSyncEventsWorker, ProjectNamespace, ProjectNamespacePolicy, ProjectsFinder, PruneAggregationSchedulesWorker, RandomizedSuffixPath, RootStatisticsWorker, ScheduleAggregationWorker, StatisticsRefresherService, SyncEvent, UpdateRootStatisticsWorker, UserNamespace, UserNamespacePolicy