이 문서는 IN SQL 연산자로 효율적인 정렬 데이터베이스 쿼리를 만드는 기법과, 이 기법 적용을 돕는 GitLab 유틸리티 모듈의 사용법을 설명합니다.

동기#

GitLab 에서 Issue 같은 많은 도메인 객체는 프로젝트와 그룹의 중첩 계층 아래에 존재합니다. 그룹 수준에서 도메인 객체의 중첩된 데이터베이스 레코드를 가져오기 위해 IN SQL 연산자를 사용한 쿼리를 자주 실행합니다. 일반적으로 일부 속성으로 레코드를 정렬하고, 성능을 위해 ORDER BY 와 LIMIT 절로 레코드 수를 제한합니다. 이어지는 레코드를 가져오기 위해 페이지네이션을 사용할 수 있습니다.

그룹 수준에서 중첩된 도메인 객체를 쿼리해야 하는 작업의 예는 다음과 같습니다.

• 그룹 gitlab-org 에서 생성일 또는 기한 기준으로 처음 20개의 이슈를 표시합니다.
• 그룹 gitlab-com 에서 머지된 날짜 기준으로 처음 20개의 머지 리퀘스트를 표시합니다.

안타깝게도 정렬된 그룹 수준 쿼리는 실행에 많은 I/O, 메모리, 연산이 필요하므로 일반적으로 성능이 좋지 않습니다. 이러한 쿼리 하나의 실행 과정을 자세히 살펴보겠습니다.

IN 쿼리의 성능 문제#

그룹 gitlab-org 에서 가장 오래 전에 생성된 이슈 20개를 가져오는 작업을 다음 쿼리로 살펴보겠습니다.

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" IN
    (SELECT "projects"."id"
     FROM "projects"
     WHERE "projects"."namespace_id" IN
         (SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
          FROM "namespaces"
          WHERE (traversal_ids @> ('{9970}'))))
ORDER BY "issues"."created_at" ASC,
         "issues"."id" ASC
LIMIT 20

쿼리 실행은 크게 세 단계로 나눌 수 있습니다.

1. 데이터베이스가 namespaces 와 projects 테이블에 모두 접근하여 그룹 계층 안의 모든 그룹에 속한 모든 프로젝트를 찾습니다.
2. 데이터베이스가 각 프로젝트의 issues 레코드를 가져오며, 이때 디스크 I/O 가 많이 발생합니다. 이상적으로는 적절한 인덱스 구성이 이 과정을 최적화해야 합니다.
3. 데이터베이스가 issues 행을 created_at 기준으로 메모리에서 정렬하고 LIMIT 20 만큼의 행을 최종 사용자에게 반환합니다. 큰 그룹에서는 이 마지막 단계에 많은 메모리와 CPU 리소스가 필요합니다.

이 데이터베이스(DB) 쿼리의 실행 계획은 다음과 같습니다.

 Limit  (cost=90170.07..90170.12 rows=20 width=1329) (actual time=967.597..967.607 rows=20 loops=1)
   Buffers: shared hit=239127 read=3060
   I/O Timings: read=336.879
   ->  Sort  (cost=90170.07..90224.02 rows=21578 width=1329) (actual time=967.596..967.603 rows=20 loops=1)
         Sort Key: issues.created_at, issues.id
         Sort Method: top-N heapsort  Memory: 74kB
         Buffers: shared hit=239127 read=3060
         I/O Timings: read=336.879
         ->  Nested Loop  (cost=1305.66..89595.89 rows=21578 width=1329) (actual time=4.709..797.659 rows=241534 loops=1)
               Buffers: shared hit=239121 read=3060
               I/O Timings: read=336.879
               ->  HashAggregate  (cost=1305.10..1360.22 rows=5512 width=4) (actual time=4.657..5.370 rows=1528 loops=1)
                     Group Key: projects.id
                     Buffers: shared hit=2597
                     ->  Nested Loop  (cost=576.76..1291.32 rows=5512 width=4) (actual time=2.427..4.244 rows=1528 loops=1)
                           Buffers: shared hit=2597
                           ->  HashAggregate  (cost=576.32..579.06 rows=274 width=25) (actual time=2.406..2.447 rows=265 loops=1)
                                 Group Key: namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)]
                                 Buffers: shared hit=334
                                 ->  Bitmap Heap Scan on namespaces  (cost=141.62..575.63 rows=274 width=25) (actual time=1.933..2.330 rows=265 loops=1)
                                       Recheck Cond: (traversal_ids @> '{9970}'::integer[])
                                       Heap Blocks: exact=243
                                       Buffers: shared hit=334
                                       ->  Bitmap Index Scan on index_namespaces_on_traversal_ids  (cost=0.00..141.55 rows=274 width=0) (actual time=1.897..1.898 rows=265 loops=1)
                                             Index Cond: (traversal_ids @> '{9970}'::integer[])
                                             Buffers: shared hit=91
                           ->  Index Only Scan using index_projects_on_namespace_id_and_id on projects  (cost=0.44..2.40 rows=20 width=8) (actual time=0.004..0.006 rows=6 loops=265)
                                 Index Cond: (namespace_id = (namespaces.traversal_ids)[array_length(namespaces.traversal_ids, 1)])
                                 Heap Fetches: 51
                                 Buffers: shared hit=2263
               ->  Index Scan using index_issues_on_project_id_and_iid on issues  (cost=0.57..10.57 rows=544 width=1329) (actual time=0.114..0.484 rows=158 loops=1528)
                     Index Cond: (project_id = projects.id)
                     Buffers: shared hit=236524 read=3060
                     I/O Timings: read=336.879
 Planning Time: 7.750 ms
 Execution Time: 967.973 ms
(36 rows)

쿼리 성능은 데이터베이스의 행 수에 따라 달라집니다. 평균적으로 다음과 같이 말할 수 있습니다.

• 그룹 계층 안의 그룹 수: 1 000 미만
• 프로젝트 수: 5 000 미만
• 이슈 수: 100 000 미만

목록을 보면 issues 레코드 수가 성능에 가장 큰 영향을 미친다는 점이 분명합니다. 일반적인 사용 방식에서는 이슈 레코드 수가 namespaces 및 projects 레코드보다 더 빠르게 증가합니다.

이 문제는 그룹 수준 이슈, 머지 리퀘스트 페이지, API 처럼 레코드를 특정 순서로 나열하는 대부분의 그룹 수준 기능에 영향을 줍니다. 매우 큰 그룹에서는 데이터베이스 쿼리가 쉽게 시간 초과되어 HTTP 500 오류가 발생할 수 있습니다.

정렬된 IN 쿼리 최적화#

강연 "How to teach an elephant to dance rock and roll"에서 Maxim Boguk 은 정렬된 그룹 수준 쿼리와 같은 특정 부류의 정렬된 IN 쿼리를 최적화하는 기법을 소개했습니다.

일반적인 정렬된 IN 쿼리는 다음과 같습니다.

SELECT t.* FROM t
WHERE t.fkey IN (value_set)
ORDER BY t.pkey
LIMIT N;

이 기법의 핵심 통찰은 다음과 같습니다. 조건 t.fkey IN value_set 을 만족하는 모든 레코드를 가져오는 대신, 최대 |value_set| + N 번의 레코드 조회만 필요합니다(|value_set| 은 value_set 에 있는 값의 수입니다).

GitLab 에서는 효율적인 IN 쿼리 구성을 돕기 위해 Gitlab::Pagination::Keyset::InOperatorOptimization 클래스에 유틸리티를 구현하여 이 기법을 채택하고 일반화했습니다.

요구 사항#

이 기법은 IN 연산자를 사용하는 기존 그룹 수준 쿼리를 그대로 대체하는 방식이 아닙니다. 다음 요구 사항을 만족하는 IN 쿼리만 최적화할 수 있습니다.

• LIMIT 이 있어야 하며, 이는 보통 쿼리가 페이지네이션(오프셋 또는 키셋 페이지네이션)됨을 의미합니다.
• IN 쿼리에 사용된 칼럼과 ORDER BY 절의 칼럼이 데이터베이스 인덱스에 포함되어야 합니다. 인덱스의 칼럼은 column_for_the_in_query, order by column 1, order by column 2 순서여야 합니다.
• ORDER BY 절의 칼럼은 고유해야 합니다 (칼럼의 조합이 테이블의 특정 행 하나를 고유하게 식별해야 합니다).

InOperatorOptimization 모듈#

Gitlab::Pagination::Keyset::InOperatorOptimization 모듈은 이전 절에서 설명한 효율적인 IN 쿼리 기법의 일반화된 버전을 적용하는 유틸리티를 구현합니다.

요구 사항을 충족하는 최적화된 정렬 IN 쿼리를 만들려면 이 모듈의 유틸리티 클래스 QueryBuilder 를 사용합니다.

QueryBuilder 기본 사용법#

기본 사용법을 보여 주기 위해, 그룹 gitlab-org 에서 created_at 이 가장 오래된 이슈 20개를 가져오는 쿼리를 만듭니다.

다음 ActiveRecord 쿼리는 앞에서 살펴본 최적화되지 않은 쿼리와 비슷한 쿼리를 생성합니다.

scope = Issue
  .where(project_id: Group.find(9970).all_projects.select(:id)) # `gitlab-org` group and its subgroups
  .order(:created_at, :id)
  .limit(20)

대신 쿼리 빌더 InOperatorOptimization::QueryBuilder 를 사용하여 최적화된 버전을 생성합니다.

scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }

Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
  scope: scope,
  array_scope: array_scope,
  array_mapping_scope: array_mapping_scope,
  finder_query: finder_query
).execute.limit(20)

• scope 는 IN 쿼리가 없는 원래의 ActiveRecord::Relation 객체를 나타냅니다. 이 relation 은 키셋 페이지네이션 라이브러리가 지원하는 정렬을 정의해야 합니다.
• array_scope 는 원래의 IN (subquery) 를 나타내는 ActiveRecord::Relation 객체를 담습니다. select 값에는 서브쿼리를 메인 쿼리와 "연결"하는 칼럼, 즉 프로젝트 레코드의 id 가 포함되어야 합니다.
• array_mapping_scope 는 ActiveRecord::Relation 객체를 반환하는 람다를 정의합니다. 이 람다는 array_scope 의 단일 select 값과 일치(=)시킵니다. 람다는 array_scope 에 정의된 select 값의 수만큼 인수를 넘겨받으며, 인수는 Arel SQL 표현식입니다.
• finder_query 는 데이터베이스에서 실제 레코드 행을 로드합니다. 이 역시 람다여야 하며, 레코드를 찾을 수 있도록 order by 칼럼 표현식이 전달됩니다. 이 예에서 전달되는 값은 created_at 과 id SQL 표현식입니다. 기본 키로 레코드를 찾는 것은 매우 빠르므로 created_at 값은 사용하지 않습니다. finder_query 람다 제공은 선택 사항입니다. 제공하지 않으면 IN 연산자 최적화는 전체 데이터베이스 행이 아니라 ORDER BY 칼럼만 최종 사용자에게 제공합니다.

쿼리가 효율적으로 실행되려면 issues 테이블에 다음 데이터베이스 인덱스가 있어야 합니다.

"idx_issues_on_project_id_and_created_at_and_id" btree (project_id, created_at, id)

SQL 쿼리는 다음과 같습니다.

SELECT "issues".*
FROM
  (WITH RECURSIVE "array_cte" AS MATERIALIZED
     (SELECT "projects"."id"
 FROM "projects"
 WHERE "projects"."namespace_id" IN
     (SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
      FROM "namespaces"
      WHERE (traversal_ids @> ('{9970}')))),
                  "recursive_keyset_cte" AS (  -- initializer row start
                                               (SELECT NULL::issues AS records,
                                                       array_cte_id_array,
                                                       issues_created_at_array,
                                                       issues_id_array,
                                                       0::bigint AS COUNT
                                                FROM
                                                  (SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
                                                          ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
                                                          ARRAY_AGG("issues"."id") AS issues_id_array
                                                   FROM
                                                     (SELECT "array_cte"."id"
                                                      FROM array_cte) array_cte
                                                   LEFT JOIN LATERAL
                                                     (SELECT "issues"."created_at",
                                                             "issues"."id"
                                                      FROM "issues"
                                                      WHERE "issues"."project_id" = "array_cte"."id"
                                                      ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
                                                      LIMIT 1) issues ON TRUE
                                                   WHERE "issues"."created_at" IS NOT NULL
                                                     AND "issues"."id" IS NOT NULL) array_scope_lateral_query
                                                LIMIT 1)
                                                -- initializer row finished
                                             UNION ALL
                                               (SELECT
                                                  -- result row start
                                                  (SELECT issues -- record finder query as the first column
                                                   FROM "issues"
                                                   WHERE "issues"."id" = recursive_keyset_cte.issues_id_array[position]
                                                   LIMIT 1),
                                                   array_cte_id_array,
                                                   recursive_keyset_cte.issues_created_at_array[:position_query.position-1]||next_cursor_values.created_at||recursive_keyset_cte.issues_created_at_array[position_query.position+1:],
                                                   recursive_keyset_cte.issues_id_array[:position_query.position-1]||next_cursor_values.id||recursive_keyset_cte.issues_id_array[position_query.position+1:],
                                                   recursive_keyset_cte.count + 1
                                                -- result row finished
                                                FROM recursive_keyset_cte,
                                                     LATERAL
                                                  -- finding the cursor values of the next record start
                                                  (SELECT created_at,
                                                          id,
                                                          position
                                                   FROM UNNEST(issues_created_at_array, issues_id_array) WITH
                                                   ORDINALITY AS u(created_at, id, position)
                                                   WHERE created_at IS NOT NULL
                                                     AND id IS NOT NULL
                                                   ORDER BY "created_at" ASC, "id" ASC
                                                   LIMIT 1) AS position_query,
                                                  -- finding the cursor values of the next record end
                                                  -- finding the next cursor values (next_cursor_values_query) start
                                                             LATERAL
                                                  (SELECT "record"."created_at",
                                                          "record"."id"
                                                   FROM (
                                                         VALUES (NULL,
                                                                 NULL)) AS nulls
                                                   LEFT JOIN
                                                     (SELECT "issues"."created_at",
                                                             "issues"."id"
                                                      FROM (
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
                                                                 AND recursive_keyset_cte.issues_created_at_array[position] IS NULL
                                                                 AND "issues"."created_at" IS NULL
                                                                 AND "issues"."id" > recursive_keyset_cte.issues_id_array[position]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
                                                                 AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
                                                                 AND "issues"."created_at" IS NULL
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
                                                                 AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
                                                                 AND "issues"."created_at" > recursive_keyset_cte.issues_created_at_array[position]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[position]
                                                                 AND recursive_keyset_cte.issues_created_at_array[position] IS NOT NULL
                                                                 AND "issues"."created_at" = recursive_keyset_cte.issues_created_at_array[position]
                                                                 AND "issues"."id" > recursive_keyset_cte.issues_id_array[position]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)) issues
                                                      ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
                                                      LIMIT 1) record ON TRUE
                                                   LIMIT 1) AS next_cursor_values))
                                                  -- finding the next cursor values (next_cursor_values_query) END
SELECT (records).*
   FROM "recursive_keyset_cte" AS "issues"
   WHERE (COUNT <> 0)) issues -- filtering out the initializer row
LIMIT 20

IN 쿼리 최적화 사용#

필터 추가#

이 예에서는 milestone_id 필터를 추가로 적용해 보겠습니다.

쿼리에 필터를 추가할 때는 주의해야 합니다. 해당 칼럼이 같은 인덱스에 포함되지 않으면 최적화되지 않은 쿼리보다 성능이 나빠질 수 있습니다. issues 테이블의 milestone_id 칼럼은 현재 다른 인덱스에 포함되어 있습니다.

"index_issues_on_milestone_id" btree (milestone_id)

scope 인수 또는 최적화된 scope 에 milestone_id = X 필터를 추가하면 성능이 나빠집니다.

나쁜 예:

Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
  scope: scope,
  array_scope: array_scope,
  array_mapping_scope: array_mapping_scope,
  finder_query: finder_query
).execute
  .where(milestone_id: 5)
  .limit(20)

이 문제를 해결하기 위해 다른 인덱스를 정의할 수 있습니다.

"idx_issues_on_project_id_and_milestone_id_and_created_at_and_id" btree (project_id, milestone_id, created_at, id)

issues 테이블에 인덱스를 더 추가하면 UPDATE 쿼리 성능에 크게 영향을 줄 수 있습니다. 이 경우에는 원래 쿼리를 사용하는 편이 낫습니다. 즉, 필터가 없는 페이지에 이 최적화를 사용하려면 애플리케이션 코드에 추가 로직이 필요합니다.

if optimization_possible? # no extra params or params covered with the same index as the ORDER BY clause
  run_optimized_query
else
  run_normal_in_query
end

여러 IN 쿼리#

그룹 수준 쿼리를 확장하여 인시던트와 테스트 케이스 이슈 유형만 포함하려 한다고 가정하겠습니다.

원래의 ActiveRecord 쿼리는 다음과 같습니다.

scope = Issue
  .where(project_id: Group.find(9970).all_projects.select(:id)) # `gitlab-org` group and its subgroups
  .where(issue_type: [:incident, :test_case]) # 1, 2
  .order(:created_at, :id)
  .limit(20)

array scope 를 구성하려면 project_id IN 쿼리와 issue_type IN 쿼리의 데카르트 곱을 구해야 합니다. issue_type 은 ActiveRecord enum 이므로 다음 테이블을 구성해야 합니다.

issue_types 쿼리에는 테이블을 쿼리하지 않고 값 목록을 구성할 수 있습니다.

value_list = Arel::Nodes::ValuesList.new([[WorkItems::Type.base_types[:incident]],[WorkItems::Type.base_types[:test_case]]])
issue_type_values = Arel::Nodes::Grouping.new(value_list).as('issue_type_values (value)').to_sql

array_scope = Group
  .find(9970)
  .all_projects
  .from("#{Project.table_name}, #{issue_type_values}")
  .select(:id, :value)

array_mapping_scope 쿼리를 만들려면 id 와 issue_type_value 두 인수가 필요합니다.

array_mapping_scope = -> (id_expression, issue_type_value_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)).where(Issue.arel_table[:issue_type].eq(issue_type_value_expression)) }

scope 와 finder 쿼리는 변경되지 않습니다.

scope = Issue.order(:created_at, :id)
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }

Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
  scope: scope,
  array_scope: array_scope,
  array_mapping_scope: array_mapping_scope,
  finder_query: finder_query
).execute.limit(20)

SQL 쿼리는 다음과 같습니다.

SELECT "issues".*
FROM
  (WITH RECURSIVE "array_cte" AS MATERIALIZED
     (SELECT "projects"."id", "value"
      FROM projects, (
                      VALUES (1), (2)) AS issue_type_values (value)
      WHERE "projects"."namespace_id" IN
          (WITH RECURSIVE "base_and_descendants" AS (
                                                       (SELECT "namespaces".*
                                                        FROM "namespaces"
                                                        WHERE "namespaces"."type" = 'Group'
                                                          AND "namespaces"."id" = 9970)
                                                     UNION
                                                       (SELECT "namespaces".*
                                                        FROM "namespaces", "base_and_descendants"
                                                        WHERE "namespaces"."type" = 'Group'
                                                          AND "namespaces"."parent_id" = "base_and_descendants"."id")) SELECT "id"
           FROM "base_and_descendants" AS "namespaces")),
                  "recursive_keyset_cte" AS (
                                               (SELECT NULL::issues AS records,
                                                       array_cte_id_array,
                                                       array_cte_value_array,
                                                       issues_created_at_array,
                                                       issues_id_array,
                                                       0::bigint AS COUNT
                                                FROM
                                                  (SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
                                                          ARRAY_AGG("array_cte"."value") AS array_cte_value_array,
                                                          ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
                                                          ARRAY_AGG("issues"."id") AS issues_id_array
                                                   FROM
                                                     (SELECT "array_cte"."id",
                                                             "array_cte"."value"
                                                      FROM array_cte) array_cte
                                                   LEFT JOIN LATERAL
                                                     (SELECT "issues"."created_at",
                                                             "issues"."id"
                                                      FROM "issues"
                                                      WHERE "issues"."project_id" = "array_cte"."id"
                                                        AND "issues"."issue_type" = "array_cte"."value"
                                                      ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
                                                      LIMIT 1) issues ON TRUE
                                                   WHERE "issues"."created_at" IS NOT NULL
                                                     AND "issues"."id" IS NOT NULL) array_scope_lateral_query
                                                LIMIT 1)
                                             UNION ALL
                                               (SELECT
                                                  (SELECT issues
                                                   FROM "issues"
                                                   WHERE "issues"."id" = recursive_keyset_cte.issues_id_array[POSITION]
                                                   LIMIT 1), array_cte_id_array,
                                                             array_cte_value_array,
                                                             recursive_keyset_cte.issues_created_at_array[:position_query.position-1]||next_cursor_values.created_at||recursive_keyset_cte.issues_created_at_array[position_query.position+1:], recursive_keyset_cte.issues_id_array[:position_query.position-1]||next_cursor_values.id||recursive_keyset_cte.issues_id_array[position_query.position+1:], recursive_keyset_cte.count + 1
                                                FROM recursive_keyset_cte,
                                                     LATERAL
                                                  (SELECT created_at,
                                                          id,
                                                          POSITION
                                                   FROM UNNEST(issues_created_at_array, issues_id_array) WITH
                                                   ORDINALITY AS u(created_at, id, POSITION)
                                                   WHERE created_at IS NOT NULL
                                                     AND id IS NOT NULL
                                                   ORDER BY "created_at" ASC, "id" ASC
                                                   LIMIT 1) AS position_query,
                                                             LATERAL
                                                  (SELECT "record"."created_at",
                                                          "record"."id"
                                                   FROM (
                                                         VALUES (NULL,
                                                                 NULL)) AS nulls
                                                   LEFT JOIN
                                                     (SELECT "issues"."created_at",
                                                             "issues"."id"
                                                      FROM (
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
                                                                 AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
                                                                 AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NULL
                                                                 AND "issues"."created_at" IS NULL
                                                                 AND "issues"."id" > recursive_keyset_cte.issues_id_array[POSITION]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
                                                                 AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
                                                                 AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
                                                                 AND "issues"."created_at" IS NULL
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
                                                                 AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
                                                                 AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
                                                                 AND "issues"."created_at" > recursive_keyset_cte.issues_created_at_array[POSITION]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)
                                                            UNION ALL
                                                              (SELECT "issues"."created_at",
                                                                      "issues"."id"
                                                               FROM "issues"
                                                               WHERE "issues"."project_id" = recursive_keyset_cte.array_cte_id_array[POSITION]
                                                                 AND "issues"."issue_type" = recursive_keyset_cte.array_cte_value_array[POSITION]
                                                                 AND recursive_keyset_cte.issues_created_at_array[POSITION] IS NOT NULL
                                                                 AND "issues"."created_at" = recursive_keyset_cte.issues_created_at_array[POSITION]
                                                                 AND "issues"."id" > recursive_keyset_cte.issues_id_array[POSITION]
                                                               ORDER BY "issues"."created_at" ASC, "issues"."id" ASC)) issues
                                                      ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
                                                      LIMIT 1) record ON TRUE
                                                   LIMIT 1) AS next_cursor_values)) SELECT (records).*
   FROM "recursive_keyset_cte" AS "issues"
   WHERE (COUNT <> 0)) issues
LIMIT 20

계산된 ORDER BY 표현식 사용#

다음 예시는 에픽 레코드를 생성 시각과 종료 시각 사이의 기간으로 정렬합니다. 기간은 다음 공식으로 계산합니다.

SELECT EXTRACT('epoch' FROM epics.closed_at - epics.created_at) FROM epics

위 쿼리는 두 타임스탬프 칼럼 사이의 기간을 초 단위(double precision)로 반환합니다. 이 표현식으로 레코드를 정렬하려면 ORDER BY 절에서 이 표현식을 참조해야 합니다.

SELECT EXTRACT('epoch' FROM epics.closed_at - epics.created_at)
FROM epics
ORDER BY EXTRACT('epoch' FROM epics.closed_at - epics.created_at) DESC

그룹 수준에서 in-operator 최적화로 이 정렬을 효율적으로 수행하려면 사용자 지정 ORDER BY 구성을 사용합니다. 기간은 고유한 값이 아니므로(고유 인덱스가 없음) 타이브레이커 칼럼(id)을 추가해야 합니다.

최종 ORDER BY 절은 다음과 같습니다.

ORDER BY extract('epoch' FROM epics.closed_at - epics.created_at) DESC, epics.id DESC

계산된 기간 순으로 정렬된 레코드를 로드하는 스니펫은 다음과 같습니다.

arel_table =  Epic.arel_table
order = Gitlab::Pagination::Keyset::Order.build([
  Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
    attribute_name: 'duration_in_seconds',
    order_expression: Arel.sql('EXTRACT(EPOCH FROM epics.closed_at - epics.created_at)').desc,
    sql_type: 'double precision' # important for calculated SQL expressions
  ),
  Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
    attribute_name: 'id',
    order_expression: arel_table[:id].desc
  )
])

records = Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
  scope: Epic.where.not(closed_at: nil).reorder(order), # filter out NULL values
  array_scope: Group.find(9970).self_and_descendants.select(:id),
  array_mapping_scope: -> (id_expression) { Epic.where(Epic.arel_table[:group_id].eq(id_expression)) }
).execute.limit(20)

puts records.pluck(:duration_in_seconds, :id) # other columns are not available

쿼리를 만들려면 상당한 구성이 필요합니다. 정렬 구성에 대한 자세한 내용은 키셋 페이지네이션 데이터베이스 쿼리의 복잡한 정렬 구성 절을 참고합니다.

이 쿼리에는 특수한 데이터베이스 인덱스가 필요합니다.

CREATE INDEX index_epics_on_duration ON epics USING btree (group_id, EXTRACT(EPOCH FROM epics.closed_at - epics.created_at) DESC, id DESC) WHERE (closed_at IS NOT NULL);

finder_query 파라미터를 사용하지 않는다는 점에 유의합니다. 이 쿼리는 ORDER BY 칼럼인 duration_in_seconds(계산된 칼럼)와 id 칼럼만 반환합니다. 이는 이 기능의 제한 사항입니다. 계산된 ORDER BY 표현식과 함께 finder_query 를 정의하는 것은 지원되지 않습니다. 전체 데이터베이스 레코드가 필요하면 반환된 id 칼럼으로 추가 쿼리를 실행할 수 있습니다.

records_by_id = records.index_by(&:id)
complete_records = Epic.where(id: records_by_id.keys).index_by(&:id)

# Printing the complete records according to the `ORDER BY` clause
records_by_id.each do |id, _|
  puts complete_records[id].attributes
end

JOIN 칼럼으로 정렬#

하나 이상의 칼럼이 JOIN 테이블에서 오는 혼합 칼럼으로 레코드를 정렬하는 방식은 제한적으로 동작합니다. 공통 테이블 표현식(CTE)을 통한 추가 구성이 필요합니다. 핵심은 구체화되지 않은(non-materialized) CTE 를 필요한 모든 칼럼을 노출하는 "가짜" 테이블로 사용하는 것입니다.

예시: 그룹 계층 안에서 이슈를 projects.name, issues.id 순으로 정렬합니다.

첫 번째 단계는 필요한 모든 칼럼을 SELECT 절에 모으는 CTE 를 만드는 것입니다.

cte_query = Issue
  .select('issues.id AS id', 'issues.project_id AS project_id', 'projects.name AS projects_name')
  .joins(:project)

cte = Gitlab::SQL::CTE.new(:issue_with_projects, cte_query, materialized: false)

사용자 지정 정렬 객체 구성은 다음과 같습니다.

order = Gitlab::Pagination::Keyset::Order.build([
          Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
            attribute_name: 'projects_name',
            order_expression: Issue.arel_table[:projects_name].asc,
            sql_type: 'character varying',
            nullable: :nulls_last
          ),
          Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
            attribute_name: :id,
            order_expression: Issue.arel_table[:id].asc
          )
        ])

쿼리를 생성합니다.

scope = cte.apply_to(Issue.where({}).reorder(order))

opts = {
  scope: scope,
  array_scope: Project.where(namespace_id: top_level_group.self_and_descendants.select(:id)).select(:id),
  array_mapping_scope: -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
}

records = Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
  .new(**opts)
  .execute
  .limit(20)

배치 반복#

키셋 Iterator 클래스를 통해 레코드를 배치 단위로 반복할 수 있습니다.

scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }

opts = {
  in_operator_optimization_options: {
    array_scope: array_scope,
    array_mapping_scope: array_mapping_scope,
    finder_query: finder_query
  }
}

Gitlab::Pagination::Keyset::Iterator.new(scope: scope, **opts).each_batch(of: 100) do |records|
  puts records.select(:id).map { |r| [r.id] }
end

ORDER BY 칼럼만 로드하는 예시는 다음과 같습니다.

scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }

opts = {
  in_operator_optimization_options: {
    array_scope: array_scope,
    array_mapping_scope: array_mapping_scope
  }
}

Gitlab::Pagination::Keyset::Iterator.new(scope: scope, **opts).each_batch(of: 100) do |records|
  puts records.select(:id).map { |r| [r.id] } # only id and created_at are available
end

키셋 페이지네이션#

이 최적화는 GraphQL 및 keyset_paginate 헬퍼 메서드와 함께 별도 설정 없이 동작합니다. 자세한 내용은 키셋 페이지네이션을 참고합니다.

array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }

opts = {
  in_operator_optimization_options: {
    array_scope: array_scope,
    array_mapping_scope: array_mapping_scope,
    finder_query: finder_query
  }
}

issues = Issue
  .order(:created_at, :id)
  .keyset_paginate(per_page: 20, keyset_order_options: opts)
  .records

Kaminari 를 사용한 오프셋 페이지네이션#

InOperatorOptimization 클래스가 생성하는 ActiveRecord scope 는 오프셋 페이지네이션 쿼리에서 사용할 수 있습니다.

Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
  .new(...)
  .execute
  .page(1)
  .per(20)
  .without_count

일반화된 IN 최적화 기법#

일반화된 IN 최적화 기법을 사용하여 QueryBuilder 가 그룹 gitlab-org 에서 가장 오래 전에 생성된 이슈 20개를 가져오는 최적화된 쿼리를 어떻게 만드는지 자세히 살펴보겠습니다.

배열 CTE#

첫 번째 단계로 공통 테이블 표현식(CTE)을 사용해 projects.id 값을 수집합니다. 이는 전달받은 array_scope ActiveRecord relation 파라미터를 CTE 로 감싸서 수행합니다.

WITH array_cte AS MATERIALIZED (
  SELECT "projects"."id"
   FROM "projects"
   WHERE "projects"."namespace_id" IN
       (SELECT traversal_ids[array_length(traversal_ids, 1)] AS id
        FROM "namespaces"
        WHERE (traversal_ids @> ('{9970}')))
)

이 쿼리는 칼럼이 하나(projects.id)뿐인 다음 결과 집합을 생성합니다.

배열 매핑#

각 프로젝트(즉, array_cte 에서 프로젝트 ID 를 저장하는 각 레코드)에 대해, ORDER BY 절에 따른 첫 번째 이슈를 식별하는 커서 값을 가져옵니다.

예를 들어 array_cte 의 첫 번째 레코드 ID=9 를 선택합니다. 다음 쿼리는 ID=9 프로젝트에서 ORDER BY 절에 따른 첫 번째 이슈 레코드를 식별하는 커서 값 (created_at, id) 를 가져옵니다.

SELECT "issues"."created_at", "issues"."id"
FROM "issues"."project_id"=9
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1;

LATERAL JOIN 으로 array_cte 의 레코드를 순회하며 각 프로젝트의 커서 값을 찾습니다. 이 쿼리는 array_mapping_scope 람다 함수를 사용해 만듭니다.

SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
  ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
  ARRAY_AGG("issues"."id") AS issues_id_array
FROM (
  SELECT "array_cte"."id" FROM array_cte
) array_cte
LEFT JOIN LATERAL
(
  SELECT "issues"."created_at", "issues"."id"
  FROM "issues"
  WHERE "issues"."project_id" = "array_cte"."id"
  ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
  LIMIT 1
) issues ON TRUE

project_id, created_at, id 에 인덱스가 있으므로 인덱스 온리 스캔으로 모든 커서 값을 빠르게 찾을 수 있습니다.

이 쿼리를 Ruby 로 옮기면 다음과 같습니다.

created_at_values = []
id_values = []
project_ids.map do |project_id|
  created_at, id = Issue.select(:created_at, :id).where(project_id: project_id).order(:created_at, :id).limit(1).first # N+1 but it's fast
  created_at_values << created_at
  id_values << id
end

결과 집합은 다음과 같은 모습입니다.

표는 각 프로젝트에서 ORDER BY 절에 따른 첫 번째 레코드의 커서 값(created_at, id)을 보여 줍니다.

이 시점에서 초기 데이터가 준비되었습니다. 데이터베이스에서 실제 레코드를 수집하기 시작하기 위해 재귀 CTE 쿼리를 사용하며, 각 재귀는 행 하나를 찾습니다. 이는 LIMIT 에 도달하거나 더 이상 데이터를 찾을 수 없을 때까지 계속됩니다.

재귀 CTE 쿼리에서 수행하는 단계의 개요는 다음과 같습니다 (SQL 로 단계를 표현하는 것은 간단하지 않으며 다음에서 설명합니다).

1. 초기 resultset 을 ORDER BY 절에 따라 정렬합니다.

2. 맨 위 커서를 선택하여 레코드를 가져옵니다. 이것이 첫 번째 레코드입니다. 예시에서 이 커서는 project_id=9 의 (2020-01-05, 3) 입니다.

3. (2020-01-05, 3)을 사용해 ORDER BY 절과 project_id=9 필터에 따른 다음 이슈를 가져올 수 있습니다. 이렇게 하면 갱신된 resultset 이 생성됩니다.

   project_ids	created_at_values	id_values
   2	2020-01-10	5
   5	2020-01-05	4
   10	2020-01-15	7
   9	2020-01-06	6

4. 갱신된 resultset 으로 1~3단계를 N=20 개의 레코드를 가져올 때까지 반복합니다.

재귀 CTE 쿼리 초기화#

초기 재귀 쿼리에서는 정확히 한 행을 생성해야 합니다. 이를 초기화 쿼리(initializer_query)라고 합니다.

ARRAY_AGG 함수로 초기 결과 집합을 한 행으로 압축하고, 그 행을 재귀 CTE 쿼리의 초기값으로 사용합니다.

초기화 행 예시:

• records 칼럼에는 정렬된 데이터베이스 레코드가 담기며, 초기화 쿼리는 첫 번째 값을 NULL 로 설정하고 나중에 걸러 냅니다.
• count 칼럼은 찾은 레코드 수를 추적합니다. 이 칼럼으로 결과 집합에서 초기화 행을 걸러 냅니다.

CTE 쿼리의 재귀 부분#

결과 행은 다음 단계로 생성됩니다.

1. 키셋 배열을 정렬합니다.
2. 다음 커서를 찾습니다.
3. 새 행을 생성합니다.

키셋 배열 정렬#

UNNEST [] WITH ORDINALITY 테이블 함수를 사용해 원래의 ORDER BY 절에 따라 LIMIT 1 로 키셋 배열을 정렬합니다. 이 함수는 "가장 작은" 키셋 커서 값을 찾아 배열 위치를 알려 줍니다. 이 커서 값으로 레코드를 찾습니다.

첫 번째 행은 네 번째 행(position = 4)입니다. created_at 과 id 값이 가장 작기 때문입니다. UNNEST 함수는 추가 칼럼으로 위치도 노출합니다(참고: PostgreSQL 은 1부터 시작하는 인덱스를 사용합니다).

UNNEST [] WITH ORDINALITY 테이블 함수 시연:

SELECT position FROM unnest('{2020-01-10, 2020-01-05, 2020-01-15, 2020-01-05}'::timestamp[], '{5, 4, 7, 3}'::int[])
  WITH ORDINALITY AS t(created_at, id, position) ORDER BY created_at ASC, id ASC LIMIT 1;

결과:

position
----------
         4
(1 row)

다음 커서 찾기#

이제 id = 9 인 프로젝트의 다음 커서 값(next_cursor_values_query)을 찾습니다. 이를 위해 키셋 페이지네이션 SQL 쿼리를 만듭니다. created_at = 2020-01-05 및 id = 3 다음의 행을 찾습니다. 데이터베이스 칼럼 두 개로 정렬하므로 다음 두 경우가 있을 수 있습니다.

• created_at = 2020-01-05 이고 id > 3 인 행이 있습니다.
• created_at > 2020-01-05 인 행이 있습니다.

이 쿼리는 범용 키셋 페이지네이션 라이브러리가 생성합니다. 쿼리가 완료되면 다음 커서 값이 담긴 임시 테이블이 생깁니다.

새 행 생성#

마지막 단계로 초기화 행(data_collector_query 메서드)을 조작하여 새 행을 생성해야 합니다. 여기서 두 가지 일이 일어납니다.

• 데이터베이스에서 전체 행을 읽어 records 칼럼에 반환합니다. (result_collector_columns 메서드)
• 현재 위치의 커서 값을 키셋 쿼리 결과로 교체합니다.

데이터베이스에서 전체 행을 읽는 작업은 기본 키에 대한 인덱스 스캔 한 번뿐입니다. finder_query 로 전달된 ActiveRecord 쿼리를 사용합니다.

(SELECT "issues".* FROM issues WHERE id = id_values[position] LIMIT 1)

괄호를 추가하면 결과 행을 records 칼럼에 넣을 수 있습니다.

position 위치의 커서 값 교체는 표준 PostgreSQL 배열 연산자로 수행할 수 있습니다.

-- created_at_values column value
created_at_values[:position-1]||next_cursor_values.created_at||created_at_values[position+1:]

-- id_values column value
id_values[:position-1]||next_cursor_values.id||id_values[position+1:]

Ruby 로 표현하면 다음과 같습니다.

id_values[0..(position - 1)] + [next_cursor_values.id] + id_values[(position + 1)..-1]

이후 다음으로 가장 작은 커서 값을 찾는 것으로 재귀가 다시 시작됩니다.

쿼리 마무리#

최종 issues 행을 생성하기 위해 쿼리를 또 다른 SELECT 문으로 감쌉니다.

SELECT "issues".*
FROM (
  SELECT (records).* -- similar to ruby splat operator
  FROM recursive_keyset_cte
  WHERE recursive_keyset_cte.count <> 0 -- filter out the initializer row
) AS issues

성능 비교#

올바른 데이터베이스 인덱스가 있다고 가정하면, 쿼리가 접근하는 데이터베이스 행의 수를 보고 쿼리 성능을 비교할 수 있습니다.

• 그룹 수: 100
• 프로젝트 수: 500
• 이슈 수(그룹 계층 안): 50 000

표준 IN 쿼리:

최적화된 IN 쿼리:

그룹 쿼리와 프로젝트 쿼리는 정렬을 사용하지 않습니다. 필요한 칼럼은 데이터베이스 인덱스에서 읽습니다. 이 값들은 자주 접근되므로 대부분의 데이터가 PostgreSQL 버퍼 캐시에 있을 가능성이 매우 높습니다.

최적화된 IN 쿼리는 인덱스에서 최대 519개의 항목(커서 값)을 읽습니다.

• 각 프로젝트의 배열을 채우기 위한 인덱스 온리 스캔 500회. 첫 번째 레코드의 커서 값이 여기에 있습니다.
• 이어지는 레코드를 위한 추가 인덱스 온리 스캔 최대 19회.

최적화된 IN 쿼리는 배열(프로젝트별 커서 값 배열)을 20번 정렬하므로 20 x 500 개의 행을 정렬하는 셈입니다. 그러나 이는 10 000개의 행을 한 번에 정렬하는 것보다 메모리를 덜 쓰는 작업일 수 있습니다.

gitlab-org 그룹의 성능 비교: