## Summary Provide a set of linear Namespace querying methods to replace recursive CTE queries. The linear methods are faster and more simple to work with. Currently Groups are nested in a parent-child hierarchy. To find groups relative to another group we have to walk the tree recursively. This is implemented through a recursive CTE with generally acceptable query performance. However building queries around the recursive CTE can be complex and result in slow queries. Some related issues include: - https://gitlab.com/gitlab-org/gitlab/-/merge_requests/22046 - https://gitlab.com/gitlab-org/gitlab/-/issues/217327 - https://gitlab.com/gitlab-org/gitlab/-/issues/11539 - https://gitlab.com/gitlab-org/gitlab/-/issues/217937 We can query the namespace hierarchy a lot faster and easier if we store the path from the root ancestor to each namespace as an attribute on the namespace. We will store this on a new `traversal_id` attribute on `Namespaces`. Say we have this Namespace hierarchy... ```mermaid graph TD; gitlab-->backend; backend-->create; backend-->manage; create-->source; manage-->access; gitlab-->frontend; ``` Then the path from `gitlab` to `access` is `gitlab / backend / manage / access`. The path from `gitlab` to `source` is `gitlab / backend / create / source`. We can use this structure for fast queries. If the current namespace is `backend` then all our descendants match the path `gitlab / backend / *`, all our ancestors match the path `* / backend`, and everyone in the same Namespace hierarchy matches `gitlab / *`. We store that path using an array of Namespace ids in a new column on Namespace called `traversal_ids`. ## Improvements Faster group hierarchy querying. Simpler queries. Easier to work with. ## Risks Failing to keep the `traversal_id` column in sync with the hierarchy. ## Involved components `app/models/namespace.rb` ## Exit Criteria Goal 1) Reduce slow log recursive Namespace queries to 0% for 7-day period https://log.gprd.gitlab.net/app/lens#/edit/765eb580-df78-11eb-bfb9-1fcb9ca7f31a?_g=h@d01ba18 Goal 2) Remove all recursive Namespace queries (code analysis)