Help us learn about your current experience with the documentation. Take the survey.

群组层次结构查询优化

本文描述了层次缓存优化策略，该策略有助于以最小的开销从大型群组层次结构中加载所有后代（子群组或项目）。此优化在 GitLab 的 epic 中实现。

对于后代数量超过 700（项目和群组）的群组层次结构，该优化会通过 Namespaces::EnableDescendantsCacheCronWorker worker 自动启用。对于较小的群组手动启用此优化可能不会有明显效果。

性能对比

加载 gitlab-org 群组的所有群组 ID，包括其自身和后代。

42 个缓冲区（约 336.00 KiB）来自缓冲池

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" = 22
      ) 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 @> ('{22}'))
        ) namespaces
      ) consistent_query
    )
  )
) AS namespaces(id)

 Function Scan on unnest namespaces  (cost=1296.82..1296.92 rows=10 width=8) (actual time=0.193..0.236 rows=GROUP_COUNT loops=1)
   Buffers: shared hit=42
   I/O Timings: read=0.000 write=0.000
   InitPlan 1 (returns $0)
     ->  Index Scan using namespace_descendants_12_pkey on gitlab_partitions_static.namespace_descendants_12 namespace_descendants  (cost=0.14..3.16 rows=1 width=769) (actual time=0.022..0.023 rows=1 loops=1)
           Index Cond: (namespace_descendants.namespace_id = 9970)
           Filter: (namespace_descendants.outdated_at IS NULL)
           Rows Removed by Filter: 0
           Buffers: shared hit=5
           I/O Timings: read=0.000 write=0.000
   InitPlan 2 (returns $1)
     ->  Aggregate  (cost=1293.62..1293.63 rows=1 width=32) (actual time=0.000..0.000 rows=0 loops=0)
           I/O Timings: read=0.000 write=0.000
           ->  Bitmap Heap Scan on public.namespaces namespaces_1  (cost=62.00..1289.72 rows=781 width=28) (actual time=0.000..0.000 rows=0 loops=0)
                 I/O Timings: read=0.000 write=0.000
                 ->  Bitmap Index Scan using index_namespaces_on_traversal_ids_for_groups  (cost=0.00..61.81 rows=781 width=0) (actual time=0.000..0.000 rows=0 loops=0)
                       Index Cond: (namespaces_1.traversal_ids @> '{9970}'::integer[])
                       I/O Timings: read=0.000 write=0.000
Settings: seq_page_cost = '4', effective_cache_size = '472585MB', jit = 'off', work_mem = '100MB', random_page_cost = '1.5'

1037 个缓冲区（约 8.10 MiB）来自缓冲池

SELECT namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id
FROM "namespaces"
WHERE "namespaces"."type" = 'Group' AND
(traversal_ids @> ('{22}'))

 Bitmap Heap Scan on public.namespaces  (cost=62.00..1291.67 rows=781 width=4) (actual time=0.670..2.273 rows=GROUP_COUNT loops=1)
   Buffers: shared hit=1037
   I/O Timings: read=0.000 write=0.000
   ->  Bitmap Index Scan using index_namespaces_on_traversal_ids_for_groups  (cost=0.00..61.81 rows=781 width=0) (actual time=0.561..0.561 rows=1154 loops=1)
         Index Cond: (namespaces.traversal_ids @> '{9970}'::integer[])
         Buffers: shared hit=34
         I/O Timings: read=0.000 write=0.000
Settings: work_mem = '100MB', random_page_cost = '1.5', seq_page_cost = '4', effective_cache_size = '472585MB', jit = 'off'

如何使用此优化

如果您使用以下 ActiveRecord scope 之一，将自动使用此优化：

# 加载所有群组：
group.self_and_descendants

# 在子查询中使用 ID：
group.self_and_descendant_ids

NamespaceSetting.where(namespace_id: group.self_and_descendant_ids)

# 加载所有项目：
group.all_projects

# 在子查询中使用 ID
MergeRequest.where(target_project_id: group.all_project_ids)

缓存失效

当群组层次结构发生变化时，例如添加新项目或子群组时，缓存会在同一事务中失效。一个名为 Namespaces::ProcessOutdatedNamespaceDescendantsCronWorker 的周期性 worker 会稍后更新缓存。失效机制通过 ActiveRecord callbacks 实现。

在缓存失效期间，层次数据库查询将继续使用未缓存（未优化）的基于 traversal_ids 的查询返回一致的值。

一致性查询

查找查询在 SQL 中实现了 ||（或）功能，允许我们首先检查缓存的值。如果这些值不存在，我们回退到层次结构中所有群组或项目的完整查找。

为简化起见，这是我们在 Ruby 中实现查找的方式：

if cached? && cache_up_to_date?
  return cached_project_ids
else
  return Project.where(...).pluck(:id)
end

在 SQL 中，我们利用 COALESCE 函数，它从表达式列表中返回第一个非 NULL 表达式。如果第一个表达式不是 NULL，则不会评估后续表达式。

SELECT COALESCE(
  (SELECT 1), -- 缓存查询
  (SELECT 2 FROM pg_sleep(5)) -- 非缓存查询
)

上面的查询会立即返回，但如果第一个子查询返回 null，数据库将执行第二个查询：

SELECT COALESCE(
  (SELECT NULL), -- 缓存查询
  (SELECT 2 FROM pg_sleep(5)) -- 非缓存查询
)

`namespace_descendants` 数据库表

缓存的子群组和项目 ID 以数组形式存储在 namespace_descendants 数据库表中，最重要的列有：

namespace_id: 主键，可以是顶级群组 ID 或子群组 ID。
self_and_descendant_group_ids: 所有群组 ID 的数组
all_project_ids: 所有项目 ID 的数组
outdated_at: 表示缓存已过时

缓存数据库查询

查询由三部分组成：

缓存查询
回退，非缓存查询
外部查询，可以在其中进行额外的过滤和数据加载（JOIN）

缓存查询：

SELECT ids -- 一行，ID 数组
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" = 22
) cached_query

当缓存过时或缓存记录不存在时，此查询返回 NULL。

基于 traversal_ids 查找的回退查询：

SELECT ids -- 一行，ID 数组
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 @> ('{22}'))
  ) namespaces
)

最终查询，将查询合并为一个：

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" = 22
      ) 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 @> ('{22}'))
        ) namespaces
      ) consistent_query
    )
  )
) AS namespaces(id)