이 문서는 IN SQL 연산자를 사용하여 효율적인 정렬 데이터베이스 쿼리를 구축하는 기법과, 해당 기법을 적용하는 데 도움이 되는 GitLab 유틸리티 모듈 사용 방법을 설명합니다.

설명된 기법은 keyset 페이지네이션을 많이 활용합니다. 먼저 해당 주제에 익숙해지는 것을 권장합니다.

동기#

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

페이지네이션을 위해 created_at 칼럼으로 정렬하는 것만으로는 충분하지 않으며, 타이 브레이커로 id 칼럼을 추가해야 합니다.

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

• 데이터베이스는 namespaces와 projects 테이블 모두에 접근하여 그룹 계층 구조의 모든 그룹에서 모든 프로젝트를 찾습니다.

• 데이터베이스는 각 프로젝트의 issues 레코드를 검색하여 무거운 디스크 I/O를 발생시킵니다. 이상적으로는 적절한 인덱스 구성이 이 프로세스를 최적화해야 합니다.

• 데이터베이스는 메모리에서 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 쿼리 최적화#

"코끼리에게 록앤롤 춤을 가르치는 방법" 발표에서 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|은 value_set의 값 개수), 최대 |value_set| + N번의 레코드 조회만 필요합니다.

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

요구 사항#

이 기법은 IN 연산자를 사용하는 기존 그룹 레벨 쿼리의 드롭인 대체가 아닙니다. 이 기법은 다음 요구 사항을 충족하는 IN 쿼리만 최적화할 수 있습니다:

• LIMIT이 있어야 하며, 이는 일반적으로 쿼리가 페이지네이션됨을 의미합니다 (오프셋 또는 keyset 페이지네이션).

• IN 쿼리에 사용된 칼럼과 ORDER BY 절의 칼럼이 데이터베이스 인덱스로 커버되어야 합니다. 인덱스의 칼럼 순서는 다음과 같아야 합니다: column_for_the_in_query, order by column 1, order by column 2.

• ORDER BY 절의 칼럼이 고유해야 합니다 (칼럼 조합이 테이블에서 특정 행을 고유하게 식별해야 함).

이 기법은 COUNT(*) 쿼리의 성능을 개선하지 않습니다.

InOperatorOptimization 모듈#

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

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

머지 리퀘스트 51481에서 도입된 일반 keyset 페이지네이션 모듈은 Gitlab::Pagination::Keyset::InOperatorOptimization에서 기법의 일반화된 구현에 근본적인 역할을 합니다.

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 객체를 나타냅니다. 관계는 keyset 페이지네이션 라이브러리에서 지원해야 하는 순서를 정의해야 합니다.

• array_scope에는 원본 IN (subquery)를 나타내는 ActiveRecord::Relation 객체가 포함됩니다. 선택 값에는 서브쿼리가 메인 쿼리와 "연결"되는 칼럼(프로젝트 레코드의 id)이 포함되어야 합니다.

• array_mapping_scope는 ActiveRecord::Relation 객체를 반환하는 람다를 정의합니다. 람다는 array_scope의 단일 선택 값과 매칭(=)합니다. 람다는 array_scope에 정의된 선택 값만큼 많은 인수를 제공합니다. 인수는 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 인수 또는 최적화된 스코프에 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 쿼리#

인시던트(incident)와 테스트 케이스(test case) 이슈 유형만 포함하도록 그룹 레벨 쿼리를 확장하고 싶다고 가정해 봅시다.

원래 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)

배열 스코프를 구성하려면 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

쿼리를 효율적으로 만들려면 project_id, issue_type, created_at, id 칼럼이 인덱스로 커버되어야 합니다.

계산된 ORDER BY 표현식 사용#

다음 예는 에픽(epic) 레코드를 생성 시간과 종료 시간 사이의 기간으로 정렬합니다. 이것은 다음 수식으로 계산됩니다:

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

쿼리를 구축하려면 상당한 양의 구성이 필요합니다. 순서 구성에 대한 자세한 정보는 keyset 페이지네이션 데이터베이스 쿼리의 복잡한 순서 구성 섹션에서 확인할 수 있습니다.

쿼리에는 특수화된 데이터베이스 인덱스가 필요합니다:

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 테이블에서 오는 혼합 칼럼으로 레코드를 정렬하는 것은 제한 사항과 함께 작동합니다. 이것은 Common Table Expression(CTE)을 통한 추가 구성이 필요합니다. 트릭은 비구체화 CTE(non-materialized CTE)를 사용하여 필요한 모든 칼럼을 노출하는 "가짜" 테이블처럼 동작하게 하는 것입니다.

쿼리 성능이 표준 IN 쿼리에 비해 개선되지 않을 수 있습니다. 항상 쿼리 계획을 확인하세요.

예시: 그룹 계층 구조 내에서 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)

배치 반복#

레코드에 대한 배치 반복은 keyset 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

쿼리는 디스크에서 완전한 데이터베이스 행을 로드합니다. 이로 인해 I/O가 증가하고 데이터베이스 쿼리가 느려질 수 있습니다. 사용 사례에 따라 기본 키는 UPDATE 또는 DELETE와 같은 추가 구문을 실행하기 위한 배치 쿼리에만 필요한 경우가 많습니다. id 칼럼은 ORDER BY 칼럼(created_at과 id)에 포함되어 이미 로드되어 있습니다. 이 경우 finder_query 파라미터를 생략할 수 있습니다.

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

Keyset 페이지네이션#

최적화는 GraphQL과 keyset_paginate 헬퍼 메서드와 함께 바로 작동합니다. keyset 페이지네이션에 대해 자세히 알아보세요.

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 스코프는 오프셋 페이지네이션 쿼리에서 사용할 수 있습니다.

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

일반화된 IN 최적화 기법#

일반화된 IN 최적화 기법을 사용하여 QueryBuilder가 gitlab-org 그룹에서 가장 오래된 이슈 20개를 가져오는 최적화된 쿼리를 어떻게 구축하는지 자세히 살펴봅시다.

Array CTE#

첫 번째 단계로 projects.id 값을 수집하기 위해 Common Table Expression(CTE)을 사용합니다. 이는 들어오는 array_scope ActiveRecord 관계 파라미터를 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)을 보여줍니다.

이 시점에서 초기 데이터가 있습니다. 데이터베이스에서 실제 레코드를 수집하기 위해 LIMIT에 도달하거나 더 이상 데이터를 찾을 수 없을 때까지 각 재귀에서 한 행씩 찾는 재귀 CTE 쿼리를 사용합니다.

재귀 CTE 쿼리에서 수행하는 단계의 개요입니다 (SQL로 단계를 표현하는 것은 간단하지 않지만 다음에 설명합니다):

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

레코드를 가져올 상위 커서를 선택합니다. 이것이 첫 번째 레코드입니다. 예시에서 이 커서는 project_id=9에 대해 (2020-01-05, 3)이 됩니다.

(2020-01-05, 3)을 사용하여 project_id=9 필터로 ORDER BY 절을 준수하는 다음 이슈를 가져올 수 있습니다. 이것은 업데이트된 resultset을 생성합니다.

N=20개의 레코드를 가져올 때까지 업데이트된 resultset으로 1에서 3을 반복합니다.

재귀 CTE 쿼리 초기화#

초기 재귀 쿼리를 위해 정확히 하나의 행을 생성해야 하며, 이를 초기화 쿼리(initializer_query)라고 합니다.

ARRAY_AGG 함수를 사용하여 초기 결과 세트를 단일 행으로 압축하고 이 행을 재귀 CTE 쿼리의 초기값으로 사용하세요:

초기화 행 예시:

• records 칼럼에는 정렬된 데이터베이스 레코드가 포함되며, 초기화 쿼리는 첫 번째 값을 NULL로 설정하고 이후에 필터링됩니다.

• count 칼럼은 찾은 레코드 수를 추적합니다. 이 칼럼을 사용하여 결과 세트에서 초기화 행을 필터링합니다.

CTE 쿼리의 재귀 부분#

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

• keyset 배열 정렬.

• 다음 커서 찾기.

• 새 행 생성.

keyset 배열 정렬#

UNNEST [] WITH ORDINALITY 테이블 함수를 사용하여 LIMIT 1로 원래 ORDER BY 절에 따라 keyset 배열을 정렬합니다. 이 함수는 "가장 낮은" keyset 커서 값을 찾고 배열 위치를 제공합니다. 이 커서 값은 레코드를 찾는 데 사용됩니다.

이 시점에서 빠른 인덱스 전용 스캔에 의존했기 때문에 데이터베이스 테이블에서 아무것도 읽지 않았습니다.

첫 번째 행은 4번째 행(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)을 찾아봅시다. 이를 위해 keyset 페이지네이션 SQL 쿼리를 구축합니다. created_at = 2020-01-05와 id = 3 이후의 다음 행을 찾습니다. 두 데이터베이스 칼럼으로 정렬하기 때문에 두 가지 경우가 있을 수 있습니다:

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

• created_at > 2020-01-05인 행이 있습니다.

이 쿼리 생성은 일반 keyset 페이지네이션 라이브러리에 의해 수행됩니다. 쿼리가 완료되면 다음 커서 값이 있는 임시 테이블이 생성됩니다:

새 행 생성#

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

• DB에서 전체 행을 읽고 records 칼럼에 반환합니다. (result_collector_columns 메서드)

• 현재 위치의 커서 값을 keyset 쿼리의 결과로 교체합니다.

데이터베이스에서 전체 행을 읽는 것은 기본 키에 의한 인덱스 스캔 하나만 수행합니다. 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 그룹의 성능 비교:

측정 전에 그룹 조회 쿼리가 별도로 실행되어 그룹 데이터를 버퍼 캐시에서 사용할 수 있게 했습니다. 자주 호출되는 쿼리이므로 프로덕션 환경의 쿼리 실행 중에 많은 공유 버퍼에 접근합니다.