Linear group queries

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:

• !22046 (closed)
• #217327 (closed)
• #11539 (closed)
• #217937 (closed)

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...

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