Improve projects membership query performance

What does this MR do and why?

GET /api/v4/projects?membership=true&order_by=name times out (QueryCanceled, returned as a 500) for many users, including users with only a few projects. Customers calls this endpoint when importing projects, so the integration fails for affected customers.

Root cause: PostgreSQL estimates that every user has about 17,700 rows in project_authorizations. The real average is about 225. Because of this estimate, the planner reads projects in name order through index_projects_on_name_and_id and checks project_authorizations for each project, expecting to find 20 matches quickly. A user with few projects never reaches 20 matches, so the query reads most of the roughly 22 million projects and hits the statement timeout. The same happens for order_by=path, updated_at and last_activity_at, which also have (column, id) indexes.

The fix (suggested by the Database team): for membership requests sorted by one of these columns, sort by an expression that orders exactly like the column but does not match any index:

• name, path: ('' || projects.name)
• updated_at, last_activity_at: (projects.updated_at + interval '0')

PostgreSQL can no longer walk the index, so it reads the user's own rows in project_authorizations, looks up those projects, and sorts them. In the plans below, PostgreSQL also runs the checks for archived parent groups and deletion state only for the rows on the page (loops=20), after sorting.

Only the ORDER BY changes. Filters and the pagination count query (which has no ORDER BY) are unchanged. order_by=id (and created_at, which the API maps to id) and star_count are unchanged: they are already fast.

The change is behind the sort_membership_projects_without_index feature flag (gitlab_com_derisk, disabled by default).

Alternatives considered

• !253957 (closed) used a materialized CTE of the user's project IDs. It fixed small users, but order_by=id then scanned the whole projects primary key, so it was closed.
• Overriding n_distinct on project_authorizations.user_id fixed the estimate, but it changes plans for every query on this table, and the right value differs on self-managed instances.
• A LATERAL rewrite that sorts in a fenced subquery gave the same page cost as this change (gitlab-bot: 158,056 buffers, 323 ms, plan). However, it needs a new query shape in ProjectsFinder, it made the pagination count about 35% more expensive (326,690 buffers, 383 ms, plan), and it slowed down order_by=id (5 ms to 264 ms, plan).

Database queries

The query is the same for all four columns; only the ORDER BY changes.

Before

SELECT projects.*
FROM projects
INNER JOIN project_authorizations ON projects.id = project_authorizations.project_id
LEFT OUTER JOIN namespaces ON namespaces.type = 'Group' AND namespaces.id = projects.namespace_id AND namespaces.type = 'Group'
WHERE project_authorizations.user_id = 1786152
  AND NOT (EXISTS (SELECT 1 FROM namespaces WHERE namespaces.id = projects.project_namespace_id AND namespaces.state = 4))
  AND projects.archived = FALSE
  AND NOT (EXISTS (SELECT 1 FROM namespace_settings WHERE namespace_settings.namespace_id = ANY (namespaces.traversal_ids) AND namespace_settings.archived = TRUE))
  AND projects.hidden = FALSE
ORDER BY projects.name ASC, projects.id ASC
LIMIT 20 OFFSET 0

After

SELECT projects.*
FROM projects
INNER JOIN project_authorizations ON projects.id = project_authorizations.project_id
LEFT OUTER JOIN namespaces ON namespaces.type = 'Group' AND namespaces.id = projects.namespace_id AND namespaces.type = 'Group'
WHERE project_authorizations.user_id = 1786152
  AND NOT (EXISTS (SELECT 1 FROM namespaces WHERE namespaces.id = projects.project_namespace_id AND namespaces.state = 4))
  AND projects.archived = FALSE
  AND NOT (EXISTS (SELECT 1 FROM namespace_settings WHERE namespace_settings.namespace_id = ANY (namespaces.traversal_ids) AND namespace_settings.archived = TRUE))
  AND projects.hidden = FALSE
ORDER BY ('' || projects.name) ASC, projects.id ASC
LIMIT 20 OFFSET 0

Results

membership=true&order_by=name&archived=false (customer request), with data in memory:

User	Authorizations	Before	After
Small user	16	timeout	about 290 buffers, 5 ms
gitlab-qa	4,628	timeout	27,067 buffers, 45 ms (plan)
gitlab-bot	27,851	1.6 million buffers, 2 min; it read 319,587 projects to find 20 (plan)	158,101 buffers, 152 ms (plan)

Pagination count query (unchanged by this MR): gitlab-bot 242,454 buffers, 212 ms (plan).

If PostgreSQL decided to run the namespace checks for every authorized project before sorting, the query would still read the user's authorizations first. We measured that plan shape during the investigation: about 600 ms for gitlab-qa and about 5.6 s for gitlab-bot, which is still well under the statement timeout.

References

• Related to #605822 (closed)

MR acceptance checklist

Evaluate this MR against the MR acceptance checklist. It helps you analyze changes to reduce risks in quality, performance, reliability, security, and maintainability.

Related to #605822 (closed)