Refactor CTE part of big query to joins [RUN ALL RSPEC] [RUN AS-IF-FOSS]
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 ASCExecution 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=52130Statistics
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: 0Compared 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 ASCExecution 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=2772Statistics
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: 0According 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