Query descendants through superset

What does this MR do and why?

Enabling the use_traversal_ids_for_descendants_scopes feature flag creates a QA pipeline failure due to a database query timeout.

Given the group hierarchy:

graph TD
  A --> B
  A --> C

  B --> D
  B --> E

  C --> F
  C --> G

We sometimes want to find all descendants of groups A, B, and C. E.g. Group.where(id: [A,B,C]).self_and_descendants

graph TD
  classDef baseQuery fill:red;

  A --> B
  A --> C

  B --> D
  B --> E

  C --> F
  C --> G

  class A,B,C baseQuery;

Which returns self and descendants of:

graph TD
  classDef baseQuery fill:red;
  classDef result fill:green;

  A --> B
  A --> C

  B --> D
  B --> E

  C --> F
  C --> G

  class A,B,C baseQuery;
  class D,E,F,G result;

The query Group.where(id: [A,B,C]).self_and_descendants and Group.where(id: [A]).self_and_descendants are the same because B and C are descendants of A.

graph TD
  classDef baseQuery fill:red;
  classDef result fill:green;

  A --> B
  A --> C

  B --> D
  B --> E

  C --> F
  C --> G

  class A baseQuery;
  class B,C,D,E,F,G result;

But Group.where(id: [A,B,C]).self_and_descendants can take much longer to query than Group.where(id: [A]).self_and_descendants.

As the amount of redundancy in the base query grows so does the query performance degradation. There are queries where base query size can vary by magnitudes when we remove redundancy.

This MR generates the superset CTE to remove all the redundant namespaces from the base query.

This work is behind the linear_scopes_superset feature flag.

Generate Query

Feature.enable(:use_traversal_ids)
Feature.enable(:use_traversal_ids_for_descendants_scopes)
Feature.enable(:traversal_ids_btree)
Feature.enable(:linear_scopes_superset)

Group.where(id: 9970).self_and_descendants

Query Plans

# Generate the query
Feature.enable(:use_traversal_ids)
Feature.enable(:traversal_ids_btree)
Feature.enable(:use_traversal_ids_for_descendants_scopes)
Feature.enable(:linear_scopes_superset)

user = User.find(1614863)
user.can?(:create_fork)

• with superset
• without superset
• without linear queries

Numbered steps to set up and validate the change are strongly suggested.

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.

Closes #361741 (closed)