Resolve the projects a settings policy covers

Dominic Bauerrequested to merge
630154-scoped-projects-resolver into master

What does this MR do and why?

Adds Govern::PolicyEngine::ScopedProjectsResolver. It turns the policy_scope document of a policy into the candidate projects for evaluation. The daily check of #630154 needs that list first.

The resolver over-approximates on purpose and applies the cheap dimensions alone. The engine makes the real scope decision from the same document compiled to Rego. A wasted evaluation costs little, and a missed one would skip enforcement. A group-authored policy cannot reach outside its own namespace subtree, whatever the document claims.

Nothing calls the resolver yet. The worker comes next under #630154 and #630148. The code comes from the prototype in !259574, now with specs. No changelog entry, because security_policies_v2 defaults to off.

Database

each_candidate_batch runs each_batch on the primary key, once per inclusion arm. The exclusions filter each yielded batch (slow iteration), so no boundary query includes a user-authored filter of unknown selectivity. The plans below ran on Database Lab (gitlab-production-main, organization 1) with the boundary and body shapes of the first full batch.

The plans drove four choices:

  • The subtree filters load the namespace and group records, because the record-level self_and_descendant_ids reads the namespace_descendants cache. The relation-level scope ends in a seq scan over namespaces.
  • Each inclusion arm batches on its own. Combining them with UNION hides projects.id from the keyset boundary, so every boundary re-reads the arms and sorts them on every column to return one batch of ids; plan 5 compares both shapes. An OR across the arms is worse again, because it makes every boundary query walk the whole primary key, and that run did not finish.
  • A later arm subtracts the earlier ones, so a project that two dimensions name is still yielded once. Every subtraction reads projects.id, which the arm is already ordered by. The group arm comes last for that reason: subtracting the framework arm from it on namespace_id instead drops the boundary off its index onto a range scan over projects, far slower than plan 9.
  • The exclusions moved into the yielded batches, where they touch the rows of one batch alone.

1. Organization-wide policy, batch boundary

-- https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167554
SELECT "projects"."id" FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" >= 1 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

2. Organization-wide policy, batch body

-- https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167555
SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" >= 1 AND "projects"."id" < 196

3. Group-authored policy, batch boundary (gitlab-org subtree)

-- https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167556
SELECT "projects"."id" FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."namespace_id" IN (SELECT "namespaces"."id" FROM UNNEST(
  COALESCE(
    (SELECT ids FROM (SELECT "namespace_descendants"."self_and_descendant_group_ids" AS ids FROM "namespace_descendants" WHERE "namespace_descendants"."outdated_at" IS NULL AND "namespace_descendants"."namespace_id" = 9970) cached_query),
    (SELECT ids FROM (SELECT ARRAY_AGG("namespaces"."id") AS ids FROM (SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id FROM "namespaces" WHERE "namespaces"."type" = 'Group' AND (traversal_ids @> ('{9970}'))) namespaces) consistent_query))
) AS namespaces(id)
) AND "projects"."id" >= 13083 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

4. Group-authored policy, batch body

-- https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167557
SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."namespace_id" IN (SELECT "namespaces"."id" FROM UNNEST(
  COALESCE(
    (SELECT ids FROM (SELECT "namespace_descendants"."self_and_descendant_group_ids" AS ids FROM "namespace_descendants" WHERE "namespace_descendants"."outdated_at" IS NULL AND "namespace_descendants"."namespace_id" = 9970) cached_query),
    (SELECT ids FROM (SELECT ARRAY_AGG("namespaces"."id") AS ids FROM (SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id FROM "namespaces" WHERE "namespaces"."type" = 'Group' AND (traversal_ids @> ('{9970}'))) namespaces) consistent_query))
) AS namespaces(id)
) AND "projects"."id" >= 13083 AND "projects"."id" < 3631141

5. Combined inclusions, late batch boundary (modified)

Two named projects, the gitlab-org subtree, and framework 2024346. The boundary sits late in the id range, which is where the union shape costs the most.

Before, one boundary over the union of the three arms:

SELECT "projects"."id" FROM ((SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (278964, 13083))
UNION
(SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."namespace_id" IN (SELECT "namespaces"."id" FROM ((SELECT "namespaces"."id" FROM UNNEST(
  COALESCE(
    (SELECT ids FROM (SELECT "namespace_descendants"."self_and_descendant_group_ids" AS ids FROM "namespace_descendants" WHERE "namespace_descendants"."outdated_at" IS NULL AND "namespace_descendants"."namespace_id" = 9970) cached_query),
    (SELECT ids FROM (SELECT ARRAY_AGG("namespaces"."id") AS ids FROM (SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id FROM "namespaces" WHERE "namespaces"."type" = 'Group' AND (traversal_ids @> ('{9970}'))) namespaces) consistent_query))
) AS namespaces(id)
)) namespaces))
UNION
(SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346))) projects WHERE "projects"."id" >= 30000000 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

Plan: cold https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169677, warm https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169633 (Unique over a Sort of every column; the Append materializes the whole arm to return one batch.)

After, the same boundary on the compliance framework arm alone:

SELECT "projects"."id" FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346) AND "projects"."id" NOT IN (278964, 13083) AND "projects"."id" >= 30000000 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

Plan: cold https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169627, warm https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169628 (Nested Loop from uniq_idx_project_compliance_framework_on_project_framework probing index_projects_on_organization_id_and_id.)

6. Projects arm, batch body

SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (278964, 13083) AND "projects"."id" >= 13083

Plan: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169681 (Index Scan on index_projects_on_organization_id_and_id. The arm holds only the ids the document names, so it is a single batch.)

7. Compliance framework arm, batch boundary

SELECT "projects"."id" FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346) AND "projects"."id" NOT IN (278964, 13083) AND "projects"."id" >= 16340341 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

Plan: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169682 (Nested Loop; Index Only Scan on uniq_idx_project_compliance_framework_on_project_framework reads the settings rows and probes index_projects_on_organization_id_and_id.)

8. Compliance framework arm, batch body

SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."id" IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346) AND "projects"."id" NOT IN (278964, 13083) AND "projects"."id" >= 16340341 AND "projects"."id" < 18180539

Plan: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169683 (Gather over a parallel Nested Loop from the same index.)

9. Group arm, batch boundary

SELECT "projects"."id" FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."namespace_id" IN (SELECT "namespaces"."id" FROM ((SELECT "namespaces"."id" FROM UNNEST(
  COALESCE(
    (SELECT ids FROM (SELECT "namespace_descendants"."self_and_descendant_group_ids" AS ids FROM "namespace_descendants" WHERE "namespace_descendants"."outdated_at" IS NULL AND "namespace_descendants"."namespace_id" = 9970) cached_query),
    (SELECT ids FROM (SELECT ARRAY_AGG("namespaces"."id") AS ids FROM (SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id FROM "namespaces" WHERE "namespaces"."type" = 'Group' AND (traversal_ids @> ('{9970}'))) namespaces) consistent_query))
) AS namespaces(id)
)) namespaces) AND "projects"."id" NOT IN (278964, 13083) AND "projects"."id" NOT IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346) AND "projects"."id" >= 13764 ORDER BY "projects"."id" ASC LIMIT 1 OFFSET 100

Plan: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169684 (top-N heapsort over an Index Scan on index_projects_on_namespace_id_and_id, hash anti-join against the framework settings. The subtraction adds little over the bare arm.)

10. Group arm, batch body

SELECT "projects".* FROM "projects" WHERE "projects"."organization_id" = 1 AND "projects"."namespace_id" IN (SELECT "namespaces"."id" FROM ((SELECT "namespaces"."id" FROM UNNEST(
  COALESCE(
    (SELECT ids FROM (SELECT "namespace_descendants"."self_and_descendant_group_ids" AS ids FROM "namespace_descendants" WHERE "namespace_descendants"."outdated_at" IS NULL AND "namespace_descendants"."namespace_id" = 9970) cached_query),
    (SELECT ids FROM (SELECT ARRAY_AGG("namespaces"."id") AS ids FROM (SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id FROM "namespaces" WHERE "namespaces"."type" = 'Group' AND (traversal_ids @> ('{9970}'))) namespaces) consistent_query))
) AS namespaces(id)
)) namespaces) AND "projects"."id" NOT IN (278964, 13083) AND "projects"."id" NOT IN (SELECT "project_compliance_framework_settings"."project_id" FROM "project_compliance_framework_settings" WHERE "project_compliance_framework_settings"."framework_id" = 2024346) AND "projects"."id" >= 13764 AND "projects"."id" < 3662568

Plan: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/64581/commands/169685 (Nested Loop on index_projects_on_namespace_id_and_id.)

11. Archived and personal exclusions, applied inside a yielded batch

-- batch with surviving rows: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167603
-- first batch of the organization, empty: https://console.postgres.ai/gitlab/projects/gitlab-production-main/sessions/62391/commands/167573
SELECT "projects".* FROM "projects" LEFT OUTER JOIN "namespaces" ON "namespaces"."type" = 'Group' AND "namespaces"."id" = "projects"."namespace_id" AND "namespaces"."type" = 'Group' WHERE "projects"."organization_id" = 1 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 NOT (EXISTS (SELECT 1 FROM "namespaces" WHERE "namespaces"."id" = "projects"."namespace_id" AND "namespaces"."type" = 'User')) AND "projects"."id" >= 60000000 AND "projects"."id" < 60000151

References

Screenshots or screen recordings

No user-visible change.

How to set up and validate locally

  1. In the Rails console, create an organization-wide policy and list its candidates:

    organization = Organizations::Organization.first
policy = Govern::Policy.create!(organization: organization, name: 'scope-probe',
  trigger_type: :deployment_requested, policy_scope: {})
Govern::PolicyEngine::ScopedProjectsResolver.new(policy).execute.pluck(:full_path)

  2. Name a single group in the document, and the list narrows to that subtree:

    policy.update!(policy_scope: { 'groups' => { 'including' => [{ 'id' => Group.first.id }] } })
Govern::PolicyEngine::ScopedProjectsResolver.new(policy).execute.pluck(:full_path)

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.

Edited by Dominic Bauer

Merge request reports