Refactor CTE part of big query to joins [RUN ALL RSPEC] [RUN AS-IF-FOSS]

Merged Alex Buijs requested to merge refactor-qutoa-cte-to-joins into master

What does this MR do?

This is based on the ongoing work on linear namespace queries (epic).

It converts the CTE part of the query where the quota are calculated to a joins with an additional where clause.

The details for the joins version of the query (link to postgres.ai):

SQL
SELECT
  "ci_builds".*
FROM
  "ci_builds"
  INNER JOIN "projects" ON "projects"."id" = "ci_builds"."project_id"
  LEFT JOIN project_features ON ci_builds.project_id = project_features.project_id
  LEFT JOIN (
    SELECT
      "ci_builds"."project_id",
      count(*) AS running_builds
    FROM
      "ci_builds"
    WHERE
      "ci_builds"."type" = 'Ci::Build'
      AND ("ci_builds"."status" IN ('running'))
      AND "ci_builds"."runner_id" IN (
        SELECT
          "ci_runners"."id"
        FROM
          "ci_runners"
        WHERE
          "ci_runners"."runner_type" = 1
      )
    GROUP BY
      "ci_builds"."project_id"
  ) AS project_builds ON ci_builds.project_id = project_builds.project_id
WHERE
  ("ci_builds"."status" IN ('pending'))
  AND "ci_builds"."runner_id" IS NULL
  AND "projects"."shared_runners_enabled" = TRUE
  AND "projects"."pending_delete" = FALSE
  AND (
    project_features.builds_access_level IS NULL
    or project_features.builds_access_level > 0
  )
  AND "ci_builds"."type" = 'Ci::Build'
  AND (
    "projects"."visibility_level" = 20
    OR (
      EXISTS (
        SELECT
          1
        FROM
          "namespaces"
          INNER JOIN namespaces as project_namespaces ON project_namespaces.id = projects.namespace_id
          LEFT JOIN namespace_statistics ON namespace_statistics.namespace_id = namespaces.id
        WHERE
          (
            namespaces.id = project_namespaces.traversal_ids [1]
          )
          AND (
            COALESCE(namespaces.shared_runners_minutes_limit, 0, 0) = 0
            OR COALESCE(namespace_statistics.shared_runners_seconds, 0) < COALESCE(
              (
                namespaces.shared_runners_minutes_limit + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)
              ),
              (
                0 + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)
              ),
              0
            ) * 60
          )
      )
    )
  )
ORDER BY
  COALESCE(project_builds.running_builds, 0) ASC,
  ci_builds.id ASC
Execution plan
 Sort  (cost=1666592.21..1666762.00 rows=67917 width=1270) (actual time=540.908..549.406 rows=11783 loops=1)
   Sort Key: (COALESCE(project_builds.running_builds, '0'::bigint)), ci_builds.id
   Sort Method: quicksort  Memory: 13138kB
   Buffers: shared hit=403241 read=1
   I/O Timings: read=0.727
   ->  Nested Loop  (cost=1227.95..1661141.36 rows=67917 width=1270) (actual time=10.785..503.806 rows=11783 loops=1)
         Buffers: shared hit=403235 read=1
         I/O Timings: read=0.727
         ->  Gather  (cost=1227.39..353724.22 rows=124979 width=1270) (actual time=10.668..71.824 rows=20146 loops=1)
               Workers Planned: 2
               Workers Launched: 2
               Buffers: shared hit=144910 read=1
               I/O Timings: read=0.727
               ->  Hash Left Join  (cost=227.39..340226.32 rows=52075 width=1270) (actual time=9.753..173.832 rows=6715 loops=3)
                     Hash Cond: (ci_builds.project_id = project_builds.project_id)
                     Buffers: shared hit=144910 read=1
                     I/O Timings: read=0.727
                     ->  Nested Loop Left Join  (cost=1.26..339863.49 rows=52075 width=1262) (actual time=0.099..157.165 rows=6715 loops=3)
                           Filter: ((project_features.builds_access_level IS NULL) OR (project_features.builds_access_level > 0))
                           Rows Removed by Filter: 3
                           Buffers: shared hit=136486 read=1
                           I/O Timings: read=0.727
                           ->  Parallel Index Scan using index_ci_builds_on_status_and_type_and_runner_id on public.ci_builds  (cost=0.70..183217.28 rows=53375 width=1262) (actual time=0.062..94.907 rows=6718 loops=3)
                                 Index Cond: (((ci_builds.status)::text = 'pending'::text) AND ((ci_builds.type)::text = 'Ci::Build'::text) AND (ci_builds.runner_id IS NULL))
                                 Buffers: shared hit=35619 read=1
                                 I/O Timings: read=0.727
                           ->  Index Scan using index_project_features_on_project_id on public.project_features  (cost=0.56..2.92 rows=1 width=8) (actual time=0.008..0.008 rows=1 loops=20155)
                                 Index Cond: (ci_builds.project_id = project_features.project_id)
                                 Buffers: shared hit=100867
                     ->  Hash  (cost=226.09..226.09 rows=3 width=12) (actual time=9.595..9.600 rows=588 loops=3)
                           Buckets: 1024  Batches: 1  Memory Usage: 34kB
                           Buffers: shared hit=8404
                           ->  Subquery Scan on project_builds  (cost=226.01..226.09 rows=3 width=12) (actual time=8.736..9.432 rows=588 loops=3)
                                 Buffers: shared hit=8404
                                 ->  Aggregate  (cost=226.01..226.06 rows=3 width=12) (actual time=8.734..9.296 rows=588 loops=3)
                                       Group Key: ci_builds_1.project_id
                                       Buffers: shared hit=8404
                                       ->  Sort  (cost=226.01..226.02 rows=3 width=4) (actual time=8.727..8.850 rows=1215 loops=3)
                                             Sort Key: ci_builds_1.project_id
                                             Sort Method: quicksort  Memory: 105kB
                                             Buffers: shared hit=8404
                                             ->  Nested Loop  (cost=1.25..225.99 rows=3 width=4) (actual time=0.097..8.254 rows=1215 loops=3)
                                                   Buffers: shared hit=8386
                                                   ->  Index Scan using index_ci_runners_on_runner_type on public.ci_runners  (cost=0.55..44.01 rows=28 width=4) (actual time=0.050..0.085 rows=15 loops=3)
                                                         Index Cond: (ci_runners.runner_type = 1)
                                                         Buffers: shared hit=68
                                                   ->  Index Scan using index_ci_builds_on_status_and_type_and_runner_id on public.ci_builds ci_builds_1  (cost=0.70..6.47 rows=3 width=8) (actual time=0.025..0.528 rows=81 loops=45)
                                                         Index Cond: (((ci_builds_1.status)::text = 'running'::text) AND ((ci_builds_1.type)::text = 'Ci::Build'::text) AND (ci_builds_1.runner_id = ci_runners.id))
                                                         Buffers: shared hit=8318
         ->  Index Scan using projects_pkey on public.projects  (cost=0.56..10.46 rows=1 width=4) (actual time=0.020..0.020 rows=1 loops=20146)
               Index Cond: (projects.id = ci_builds.project_id)
               Filter: (projects.shared_runners_enabled AND (NOT projects.pending_delete) AND ((projects.visibility_level = 20) OR (SubPlan 1)))
               Rows Removed by Filter: 0
               Buffers: shared hit=258325
               SubPlan 1
                 ->  Nested Loop Left Join  (cost=1.30..7.38 rows=1 width=0) (actual time=0.019..0.019 rows=1 loops=13172)
                       Filter: ((COALESCE(namespaces.shared_runners_minutes_limit, 0) = 0) OR (COALESCE(namespace_statistics.shared_runners_seconds, 0) < (COALESCE((namespaces.shared_runners_minutes_limit + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)), (0 + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)), 0) * 60)))
                       Rows Removed by Filter: 0
                       Buffers: shared hit=157508
                       ->  Nested Loop  (cost=0.88..6.91 rows=1 width=12) (actual time=0.012..0.012 rows=1 loops=13172)
                             Buffers: shared hit=105378
                             ->  Index Scan using namespaces_pkey on public.namespaces project_namespaces  (cost=0.44..3.46 rows=1 width=13) (actual time=0.006..0.006 rows=1 loops=13172)
                                   Index Cond: (project_namespaces.id = projects.namespace_id)
                                   Buffers: shared hit=52690
                             ->  Index Scan using namespaces_pkey on public.namespaces  (cost=0.44..3.46 rows=1 width=12) (actual time=0.004..0.004 rows=1 loops=13172)
                                   Index Cond: (namespaces.id = (project_namespaces.traversal_ids)[1])
                                   Buffers: shared hit=52688
                       ->  Index Scan using index_namespace_statistics_on_namespace_id on public.namespace_statistics  (cost=0.42..0.44 rows=1 width=8) (actual time=0.005..0.005 rows=1 loops=13172)
                             Index Cond: (namespace_statistics.namespace_id = namespaces.id)
                             Buffers: shared hit=52130
Statistics
Time: 561.511 ms
  - planning: 3.489 ms
  - execution: 558.022 ms
    - I/O read: 0.727 ms
    - I/O write: N/A

Shared buffers:
  - hits: 403241 (~3.10 GiB) from the buffer pool
  - reads: 1 (~8.00 KiB) from the OS file cache, including disk I/O
  - dirtied: 0
  - writes: 0

Compared to the old CTE version of the query (link to postgres.ai):

SQL
SELECT
  "ci_builds".*
FROM
  "ci_builds"
  INNER JOIN "projects" ON "projects"."id" = "ci_builds"."project_id"
  LEFT JOIN project_features ON ci_builds.project_id = project_features.project_id
  LEFT JOIN (
    SELECT
      "ci_builds"."project_id",
      count(*) AS running_builds
    FROM
      "ci_builds"
    WHERE
      "ci_builds"."type" = 'Ci::Build'
      AND ("ci_builds"."status" IN ('running'))
      AND "ci_builds"."runner_id" IN (
        SELECT
          "ci_runners"."id"
        FROM
          "ci_runners"
        WHERE
          "ci_runners"."runner_type" = 1
      )
    GROUP BY
      "ci_builds"."project_id"
  ) AS project_builds ON ci_builds.project_id = project_builds.project_id
WHERE
  ("ci_builds"."status" IN ('pending'))
  AND "ci_builds"."runner_id" IS NULL
  AND "projects"."shared_runners_enabled" = TRUE
  AND "projects"."pending_delete" = FALSE
  AND (
    project_features.builds_access_level IS NULL
    or project_features.builds_access_level > 0
  )
  AND "ci_builds"."type" = 'Ci::Build'
  AND (
    "projects"."visibility_level" = 20
    OR (
      EXISTS (
        WITH RECURSIVE "base_and_ancestors" AS (
          (
            SELECT
              "namespaces".*
            FROM
              "namespaces"
            WHERE
              (namespaces.id = projects.namespace_id)
          )
          UNION
          (
            SELECT
              "namespaces".*
            FROM
              "namespaces",
              "base_and_ancestors"
            WHERE
              "namespaces"."id" = "base_and_ancestors"."parent_id"
          )
        )
        SELECT
          1
        FROM
          "base_and_ancestors" AS "namespaces"
          LEFT JOIN namespace_statistics ON namespace_statistics.namespace_id = namespaces.id
        WHERE
          "namespaces"."parent_id" IS NULL
          AND (
            COALESCE(namespaces.shared_runners_minutes_limit, 10, 0) = 0
            OR COALESCE(namespace_statistics.shared_runners_seconds, 0) < COALESCE(
              (
                namespaces.shared_runners_minutes_limit + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)
              ),
              (
                10 + COALESCE(namespaces.extra_shared_runners_minutes_limit, 0)
              ),
              0
            ) * 60
          )
      )
    )
  )
ORDER BY
  COALESCE(project_builds.running_builds, 0) ASC,
  ci_builds.id ASC
Execution plan
 Sort  (cost=45751319.55..45751489.34 rows=67917 width=1270) (actual time=682.423..683.790 rows=11783 loops=1)
   Sort Key: (COALESCE(project_builds.running_builds, '0'::bigint)), ci_builds.id
   Sort Method: quicksort  Memory: 13138kB
   Buffers: shared hit=356779
   ->  Hash Left Join  (cost=227.95..45745868.71 rows=67917 width=1270) (actual time=10.914..644.990 rows=11783 loops=1)
         Hash Cond: (ci_builds.project_id = project_builds.project_id)
         Buffers: shared hit=356773
         ->  Nested Loop  (cost=1.82..45745464.29 rows=67917 width=1262) (actual time=0.221..623.824 rows=11783 loops=1)
               Buffers: shared hit=353979
               ->  Nested Loop Left Join  (cost=1.26..559918.38 rows=124979 width=1262) (actual time=0.081..250.098 rows=20146 loops=1)
                     Filter: ((project_features.builds_access_level IS NULL) OR (project_features.builds_access_level > 0))
                     Rows Removed by Filter: 9
                     Buffers: shared hit=136483
                     ->  Index Scan using index_ci_builds_on_status_and_type_and_runner_id on public.ci_builds  (cost=0.70..183964.54 rows=128101 width=1262) (actual time=0.056..125.270 rows=20155 loops=1)
                           Index Cond: (((ci_builds.status)::text = 'pending'::text) AND ((ci_builds.type)::text = 'Ci::Build'::text) AND (ci_builds.runner_id IS NULL))
                           Buffers: shared hit=35618
                     ->  Index Scan using index_project_features_on_project_id on public.project_features  (cost=0.56..2.92 rows=1 width=8) (actual time=0.005..0.005 rows=1 loops=20155)
                           Index Cond: (ci_builds.project_id = project_features.project_id)
                           Buffers: shared hit=100865
               ->  Index Scan using projects_pkey on public.projects  (cost=0.56..361.55 rows=1 width=4) (actual time=0.018..0.018 rows=1 loops=20146)
                     Index Cond: (projects.id = ci_builds.project_id)
                     Filter: (projects.shared_runners_enabled AND (NOT projects.pending_delete) AND ((projects.visibility_level = 20) OR (SubPlan 2)))
                     Rows Removed by Filter: 0
                     Buffers: shared hit=217496
                     SubPlan 2
                       ->  Nested Loop Left Join  (cost=353.40..358.46 rows=1 width=0) (actual time=0.018..0.018 rows=1 loops=13172)
                             Filter: ((COALESCE(namespaces_2.shared_runners_minutes_limit, 0) = 0) OR (COALESCE(namespace_statistics.shared_runners_seconds, 0) < (COALESCE((namespaces_2.shared_runners_minutes_limit + COALESCE(namespaces_2.extra_shared_runners_minutes_limit, 0)), (0 + COALESCE(namespaces_2.extra_shared_runners_minutes_limit, 0)), 0) * 60)))
                             Rows Removed by Filter: 0
                             Buffers: shared hit=116679
                             CTE base_and_ancestors
                               ->  Recursive Union  (cost=0.44..352.98 rows=101 width=344) (actual time=0.008..0.011 rows=1 loops=13172)
                                     Buffers: shared hit=64549
                                     ->  Index Scan using namespaces_pkey on public.namespaces  (cost=0.44..3.46 rows=1 width=344) (actual time=0.005..0.006 rows=1 loops=13172)
                                           Index Cond: (namespaces.id = projects.namespace_id)
                                           Buffers: shared hit=52697
                                     ->  Nested Loop  (cost=0.44..34.75 rows=10 width=344) (actual time=0.004..0.004 rows=1 loops=5670)
                                           Buffers: shared hit=11852
                                           ->  WorkTable Scan on base_and_ancestors  (cost=0.00..0.20 rows=10 width=4) (actual time=0.000..0.000 rows=1 loops=5670)
                                           ->  Index Scan using namespaces_pkey on public.namespaces namespaces_1  (cost=0.44..3.46 rows=1 width=344) (actual time=0.003..0.003 rows=1 loops=5670)
                                                 Index Cond: (namespaces_1.id = base_and_ancestors.parent_id)
                                                 Buffers: shared hit=11852
                             ->  CTE Scan on base_and_ancestors namespaces_2  (cost=0.00..2.02 rows=1 width=12) (actual time=0.013..0.013 rows=1 loops=13172)
                                   Filter: (namespaces_2.parent_id IS NULL)
                                   Rows Removed by Filter: 0
                                   Buffers: shared hit=64549
                             ->  Index Scan using index_namespace_statistics_on_namespace_id on public.namespace_statistics  (cost=0.42..3.44 rows=1 width=8) (actual time=0.004..0.004 rows=1 loops=13172)
                                   Index Cond: (namespace_statistics.namespace_id = namespaces_2.id)
                                   Buffers: shared hit=52130
         ->  Hash  (cost=226.09..226.09 rows=3 width=12) (actual time=10.659..10.663 rows=588 loops=1)
               Buckets: 1024  Batches: 1  Memory Usage: 34kB
               Buffers: shared hit=2794
               ->  Subquery Scan on project_builds  (cost=226.01..226.09 rows=3 width=12) (actual time=9.785..10.474 rows=588 loops=1)
                     Buffers: shared hit=2794
                     ->  Aggregate  (cost=226.01..226.06 rows=3 width=12) (actual time=9.784..10.337 rows=588 loops=1)
                           Group Key: ci_builds_1.project_id
                           Buffers: shared hit=2794
                           ->  Sort  (cost=226.01..226.02 rows=3 width=4) (actual time=9.776..9.897 rows=1215 loops=1)
                                 Sort Key: ci_builds_1.project_id
                                 Sort Method: quicksort  Memory: 105kB
                                 Buffers: shared hit=2794
                                 ->  Nested Loop  (cost=1.25..225.99 rows=3 width=4) (actual time=0.085..9.315 rows=1215 loops=1)
                                       Buffers: shared hit=2794
                                       ->  Index Scan using index_ci_runners_on_runner_type on public.ci_runners  (cost=0.55..44.01 rows=28 width=4) (actual time=0.053..0.093 rows=15 loops=1)
                                             Index Cond: (ci_runners.runner_type = 1)
                                             Buffers: shared hit=22
                                       ->  Index Scan using index_ci_builds_on_status_and_type_and_runner_id on public.ci_builds ci_builds_1  (cost=0.70..6.47 rows=3 width=8) (actual time=0.026..0.598 rows=81 loops=15)
                                             Index Cond: (((ci_builds_1.status)::text = 'running'::text) AND ((ci_builds_1.type)::text = 'Ci::Build'::text) AND (ci_builds_1.runner_id = ci_runners.id))
                                             Buffers: shared hit=2772
Statistics
Time: 694.917 ms
  - planning: 4.034 ms
  - execution: 690.883 ms
    - I/O read: N/A
    - I/O write: N/A

Shared buffers:
  - hits: 356779 (~2.70 GiB) from the buffer pool
  - reads: 0 from the OS file cache, including disk I/O
  - dirtied: 0
  - writes: 0

According to these plans, the new query performs about 20% faster than the CTE version on postgres.ai, with all traversal_ids manually migrated with the following queries:

Migration queries
CREATE INDEX index_namespaces_on_traversal_ids ON namespaces USING gin (traversal_ids);
UPDATE namespaces SET traversal_ids = array[]::bigint[];
WITH RECURSIVE cte(id, traversal_ids, cycle) AS (
  SELECT n.id, ARRAY[n.id::bigint], FALSE FROM (
    SELECT id FROM namespaces WHERE parent_id IS NULL AND cardinality(traversal_ids)=0
  ) as n
  UNION ALL
  SELECT
    namespaces.id,
    cte.traversal_ids || namespaces.id::bigint,
    namespaces.id = ANY(cte.traversal_ids)
  FROM
    namespaces,
    cte
  WHERE
    namespaces.parent_id = cte.id
    AND NOT cycle
)
UPDATE namespaces
SET traversal_ids=cte.traversal_ids
FROM cte
WHERE namespaces.id=cte.id;
Edited by Alex Buijs