동기
- IN 쿼리의 성능 문제
순서있는 IN 쿼리 최적화
- 요구 사항
InOperatorOptimization 모듈
- QueryBuilder의 기본 사용법
- IN 쿼리 최적화 사용
일반화된 IN 최적화 기법

효율적인 `IN` 연산자 쿼리

이 문서는 IN SQL 연산자를 사용하여 효율적으로 정렬된 데이터베이스 쿼리를 작성하는 기술과 해당 기술을 적용하는 데 도움을 주는 GitLab 유틸리티 모듈에 대해 설명합니다.

참고: 기술된 기법은 keyset pagination 을(를) 빈번히 사용합니다. 먼저 해당 주제에 익숙해지는 것이 좋습니다.

동기

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 열로 정렬하는 것만으로는 충분하지 않습니다. Tie-breaker 열을 추가해야 합니다.

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

데이터베이스는 모든 그룹 계층 구조의 모든 프로젝트를 찾기 위해 namespaces 및 projects 테이블에 액세스합니다.
데이터베이스는 각 프로젝트에 대해 issues 레코드를 검색하여 많은 디스크 I/O를 발생시킵니다. 이 프로세스를 최적화하기 위해 적절한 인덱스 구성이 이상적입니다.
데이터베이스는 메모리에서 created_at으로 issues 행을 정렬하고 LIMIT 20 행을 최종 사용자에게 반환합니다. 매우 큰 그룹의 경우 이 최종 단계는 큰 메모리 및 CPU 리소스가 모두 필요합니다.

이 데이터베이스 쿼리의 실행 계획:

 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 레코드보다 더 빠른 속도로 증가한다고 말할 수 있습니다.

이 문제는 그룹 수준의 특정 순서대로 레코드가 나열되는 대부분의 기능에 영향을 미칩니다. 매우 큰 그룹의 경우 데이터베이스 쿼리가 쉽게 타임아웃되어 HTTP 500 에러가 발생할 수 있습니다.

순서있는 `IN` 쿼리 최적화

여기의 발표에서 Maxim Boguk은 ordered IN 쿼리의 특별한 클래스를 최적화하는 기술을 시연했습니다. 이러한 쿼리는 우리가 사용하는 ordered group-level 쿼리와 같습니다.

전형적인 ordered IN 쿼리는 다음과 같이 보일 수 있습니다:

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

이 기술에서 사용된 주요 통찰력은 다음과 같습니다: 우리는 |value_set| + N 개의 레코드 조회 조작을 최대로 필요로 하며, t.fkey IN value_set 조건을 만족하는 모든 레코드를 검색하는 것이 아닙니다 (|value_set|은 value_set 내의 값 개수입니다).

우리는 이 기술을 GitLab에서 사용하기 위해 Gitlab::Pagination::Keyset::InOperatorOptimization 클래스에 효율적인 IN 쿼리를 구축하는 데 도움을 주는 유틸리티를 구현하여 채택하고 일반화시켰습니다.

요구 사항

이 기술은 기존의 IN 연산자를 사용하는 그룹-레벨 쿼리에 대한 완전한 대체가 아닙니다. 이 기술은 다음 요구 사항을 만족하는 IN 쿼리만 최적화할 수 있습니다:

일반적으로 페이징된 쿼리를 의미하는 LIMIT이 존재합니다 (오프셋 또는 키셋 페이징).
IN 쿼리와 ORDER BY 절에서 사용되는 열은 데이터베이스 인덱스로 커버됩니다. 인덱스의 열은 다음 순서로 있어야 합니다: IN 쿼리에 대한 열, order by column 1, order by column 2.
ORDER BY 절의 열은 고유합니다 (열의 조합이 테이블에서 특정 행을 고유하게 식별합니다).

경고: 이 기술은 COUNT(*) 쿼리의 성능을 향상시키지 않습니다.

`InOperatorOptimization` 모듈

GitLab 14.3에 추가되었습니다.

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

요구 사항을 충족하는 최적화된 ordered IN 쿼리를 작성하려면 모듈에서 제공하는 QueryBuilder 유틸리티 클래스를 사용하세요.

참고: 병합 요청 51481에서 소개된 일반 키셋 페이징 모듈은 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` 그룹 및 하위 그룹
  .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 객체를 나타냅니다. 관련은 키셋 페이징 라이브러리에서 지원되어야 하는 순서를 정의해야 합니다.
array_scope에는 IN (서브쿼리)를 나타내는 ActiveRecord::Relation 객체가 포함되어야 합니다. 선택된 값은 서브쿼리를 메인 쿼리에 “연결”하는 데 사용되는 열을 포함해야 합니다: 프로젝트 레코드의 id.
array_mapping_scope는 ActiveRecord::Relation 객체를 반환하는 람다를 정의합니다. 람다는 array_scope에서 단일 선택 값과 매치(=)합니다. 람다는 array_scope에서 정의된 선택값과 같은 수의 인수를 생성합니다. 이러한 인수는 Arel SQL 표현입니다.
finder_query는 데이터베이스에서 실제 레코드 행을 로드합니다. 이것도 람다여야 하며 여기서 order by column 표현을 이용해서 레코드를 찾을 수 있어야 합니다. 이 예시에서는 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 쿼리:

위 내용은 full translation에는 필요한 정보가 없기 때문에 생략합니다.

`IN` 쿼리 최적화 사용

더 많은 필터 추가

이 예에서는 ‘milestone_id’에 대한 추가 필터를 추가해 봅시다.

쿼리에 추가적인 필터를 추가할 때 주의하세요. 컬럼이 동일한 인덱스로 커버되지 않는 경우, 쿼리는 최적화되지 않은 쿼리보다 성능이 떨어질 수 있습니다. issues 테이블의 milestone_id 컬럼은 현재 다른 인덱스로 커버되어 있습니다:

"index_issues_on_milestone_id" btree (milestone_id)

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

예 (나쁨):

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? # 추가 매개변수가 없거나 ORDER BY 절과 동일한 인덱스로 커버되는 매개변수
  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` 그룹 및 해당 하위 그룹
  .where(issue_type: [:incident, :test_case]) # 1, 2
  .order(:created_at, :id)
  .limit(20)

배열 스코프를 구성하기 위해 project_id IN 및 issue_type IN 쿼리의 카티션 곱을 취해야 합니다. issue_type은 ActiveRecord 열거형이므로 다음 테이블을 구성해야 합니다:

`project_id`	`issue_type_value`
2	1
2	2
5	1
5	2
10	1
10	2
9	1
9	2

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 구성을 사용하십시오. 이 기간은 유일한 인덱스가 없으므로(distinct value가 아님) 추가적인 컬럼(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,
    distinct: false,
    sql_type: 'double precision' # 계산된 SQL 표현에 중요함
  ),
  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), # NULL 값 필터링
  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) # 다른 열은 사용 불가

쿼리를 작성하는 데 많은 구성이 필요합니다. 순서 구성에 대한 자세한 정보는 키셋 페이징 데이터베이스 쿼리의 복잡한 순서 구성 섹션에서 찾을 수 있습니다.

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

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)

# `ORDER BY` 절에 따라 완전한 레코드를 출력
records_by_id.each do |id, _|
  puts complete_records[id].attributes
end

`JOIN` 열 별로 정렬

여러 열을 JOIN 테이블에서 가져올 때 믹싱 열로 레코드를 정렬하는 경우에는 제한이 있습니다. 추가적인 Common Table Expression (CTE)을 통해 데이터베이스 쿼리를 수행합니다. “가짜” 테이블로 작용하는 비물질화 CTE를 사용하여 필요한 모든 열을 노출합니다.

참고: 쿼리 성능은 표준 IN 쿼리와 비교해 개선되지 않을 수 있습니다. 항상 쿼리 계획을 확인하십시오.

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

첫 번째 단계는 CTE를 생성하여 모든 필요한 열을 SELECT 절에 수집하는 것입니다.

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,
            distinct: false
          ),
          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

참고: 이 쿼리는 디스크에서 완전한 데이터베이스 레코드를 로드합니다. 이는 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] } # id 및 created_at 만 사용 가능
end

키셋 페이지네이션

최적화는 GraphQL 및 keyset_paginate 도우미 메서드와 함께 기본 구성에서 작동합니다. keyset pagination에 대해 자세히 알아보세요.

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 스코프는 offset-paginated 쿼리에서 사용할 수 있습니다.

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

일반화된 `IN` 최적화 기법

여기서 QueryBuilder가 일반화된 IN 최적화 기법을 사용하여 gitlab-org 그룹에서 최초로 생성된 이슈 20개를 가져오기 위한 최적화된 쿼리를 작성하는 방법을 살펴봅시다.

배열 CTE

첫 번째 단계로, Common Table Expression (CTE)을 사용하여 projects.id 값을 수집합니다. 이는 들어오는 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):

ID
9
2
5
10

배열 매핑

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

예를 들어, array_cte에서 첫 번째 레코드 ID=9를 선택하면, 다음 쿼리는 ID=9인 프로젝트에 대해 ORDER BY 절을 준수하는 최초의 이슈 레코드를 식별하는 커서 값을 가져올 것입니다:

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에 대한 인덱스만을 가진 인덱스만 스캔될 것입니다.(index-only scans)

이 쿼리는 루비로 어떻게 변환될 수 있을까요?

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

결과 세트는 다음과 같이 나타날 것입니다:

`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-05	3

이 테이블은 ORDER BY 절을 준수하는 각 프로젝트의 첫 번째 레코드의 커서 값(created_at, id)을 보여줍니다.

이 시점에서 초기 데이터가 준비되었습니다. 데이터베이스에서 실제 레코드 수집을 시작하려면 재귀 CTE 쿼리를 사용하여 각 재귀 단계에서 LIMIT에 도달하거나 더 이상 데이터를 찾을 수 없을 때까지 하나의 레코드를 찾습니다. ```

초기 재귀 CTE 쿼리 초기화

초기 재귀 쿼리를 위해 정확히 한 행을 생성해야 합니다. 이를 초기화 쿼리(initializer_query)라고 합니다. 초기 결과 세트를 단일 행으로 압축하기 위해 ARRAY_AGG 함수를 사용하고 이를 재귀 CTE 쿼리의 초기값으로 사용합니다.

예시 초기화 행:

`records`	`project_ids`	`created_at_values`	`id_values`	`Count`	`Position`
`NULL::issues`	`[9, 2, 5, 10]`	`[...]`	`[...]`	`0`	`NULL`

records 열에는 정렬된 데이터베이스 레코드가 포함되며, 초기화 쿼리는 첫 번째 값을 NULL로 설정하고 나중에 이를 필터링합니다.
count 열은 발견된 레코드 수를 추적합니다. 이 열을 사용하여 결과 세트에서 초기화 행을 필터링합니다.

CTE 쿼리의 재귀 부분

결과 행은 다음 단계를 통해 생성됩니다:

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

키셋 배열을 정렬

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

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

`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-05	3

첫 번째 행은 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) 찾아봅시다. 이를 위해 키셋 페이지네이션 SQL 쿼리를 작성합니다. created_at = 2020-01-05이고 id = 3인 레코드 다음에 있는 행을 찾습니다. 두 개의 데이터베이스 열별로 정렬하기 때문에 두 가지 경우가 발생할 수 있습니다:

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

이 쿼리를 생성하는 것은 제네릭 키셋 페이지네이션 라이브러리에 의해 수행됩니다. 쿼리가 끝나면 다음 커서 값을 가진 임시 테이블이 생성됩니다.

`created_at`	ID
2020-01-06	6

새로운 행 생성

마지막 단계로, 초기화된 행을 조작하여 새로운 행을 생성해야 합니다(data_collector_query 방법). 이 과정에서 두 가지가 발생합니다:

DB에서 전체 행을 읽어 records 열에 반환합니다(result_collector_columns 방법)
현재 위치의 커서 값을 키셋 쿼리 결과로 대체합니다.

데이터베이스에서 전체 행을 읽는 것은 기본 키에 의한 인덱스 스캔에 의해 단 한 번만 수행됩니다. finder_query로 전달된 ActiveRecord 쿼리를 사용합니다:

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

괄호를 추가함으로써 결과 행을 records 열에 넣을 수 있습니다.

position에서 커서 값을 다음과 같은 표준 PostgreSQL 배열 연산자를 사용하여 대체할 수 있습니다:

-- created_at_values 열 값
created_at_values[:position-1]||next_cursor_values.created_at||created_at_values[position+1:]

-- id_values 열 값
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).* -- 루비 splat 연산자와 유사함
  FROM recursive_keyset_cte
  WHERE recursive_keyset_cte.count <> 0 -- 초기화 행은 필터링합니다
) AS issues

성능 비교

올바른 데이터베이스 인덱스가 있는 경우, 쿼리 실행 성능을 비교할 수 있습니다. 쿼리에 의해 액세스된 데이터베이스 행의 수를 확인합니다.

그룹 수: 100
프로젝트 수: 500
이슈 수 (그룹 계층 구조 내): 50,000

표준 IN 쿼리:

쿼리	인덱스에서 읽은 항목	테이블에서 읽은 행	메모리 내에서 정렬된 행
그룹 계층 서브쿼리	100	0	0
프로젝트 조회 쿼리	500	0	0
이슈 조회 쿼리	50,000	20	50,000

최적화된 IN 쿼리:

쿼리	인덱스에서 읽은 항목	테이블에서 읽은 행	메모리 내에서 정렬된 행
그룹 계층 서브쿼리	100	0	0
프로젝트 조회 쿼리	500	0	0
이슈 조회 쿼리	519	20	10,000

그룹 및 프로젝트 쿼리는 정렬을 사용하지 않으며, 필요한 열은 데이터베이스 인덱스에서 읽습니다. 이러한 값들은 빈번하게 액세스되므로 PostgreSQL의 버퍼 캐시에 대부분의 데이터가 있을 가능성이 매우 높습니다.

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

각 프로젝트에 대한 배열을 채우기 위해 500개의 인덱스 기반 스캔. 첫 번째 레코드의 커서 값이 여기에 있습니다.
연이은 레코드에 대해 최대 19개의 추가적인 인덱스 기반 스캔.

최적화된 IN 쿼리는 배열을 20회(각 프로젝트 배열당 커서 값) 정렬하며, 이는 20 x 500 행을 정렬함을 의미합니다. 그러나 이는 한 번에 10,000개의 행을 정렬하는 것보다 메모리 부담이 적을 수 있습니다.

gitlab-org 그룹에 대한 성능 비교:

쿼리	참여한 8K 버퍼 수	캐시되지 않은 실행 시간	캐시된 실행 시간
`IN` 쿼리	240,833	1.2초	660밀리초
최적화된 `IN` 쿼리	9,783	450밀리초	22밀리초

참고: 측정을 수행하기 전에, 그룹 조회 쿼리는 별도로 실행되어 프로덕션 환경에서 쿼리 실행 중에 많은 공유 버퍼에 대한 쿼리를 수행하여 그룹 데이터를 버퍼 캐시에 사용할 수 있도록 했습니다. 빈번하게 호출되는 쿼리이므로 실행 전 많은 공유 버퍼에 대해 액세스합니다.

효율적인 `IN` 연산자 쿼리

동기

`IN` 쿼리의 성능 문제

순서있는 `IN` 쿼리 최적화

요구 사항

`InOperatorOptimization` 모듈

`QueryBuilder`의 기본 사용법

`IN` 쿼리 최적화 사용

더 많은 필터 추가

다중 `IN` 쿼리

계산된 `ORDER BY` 표현 사용

`JOIN` 열 별로 정렬

일괄 처리 반복

키셋 페이지네이션

Kaminari로 오프셋 페이지네이션

일반화된 `IN` 최적화 기법

배열 CTE

배열 매핑

초기 재귀 CTE 쿼리 초기화

CTE 쿼리의 재귀 부분

키셋 배열을 정렬

다음 커서를 찾기

새로운 행 생성

쿼리 완료

성능 비교

도움말

기능 사용 가능성과 제품 평가판

도움받기

효율적인 IN 연산자 쿼리

동기

IN 쿼리의 성능 문제

순서있는 IN 쿼리 최적화

요구 사항

InOperatorOptimization 모듈

QueryBuilder의 기본 사용법

IN 쿼리 최적화 사용

더 많은 필터 추가

다중 IN 쿼리

계산된 ORDER BY 표현 사용

JOIN 열 별로 정렬

일괄 처리 반복

키셋 페이지네이션

Kaminari로 오프셋 페이지네이션

일반화된 IN 최적화 기법

배열 CTE

배열 매핑

초기 재귀 CTE 쿼리 초기화

CTE 쿼리의 재귀 부분

키셋 배열을 정렬

다음 커서를 찾기

새로운 행 생성

쿼리 완료

성능 비교

도움말

기능 사용 가능성과 제품 평가판

도움받기

효율적인 `IN` 연산자 쿼리

`IN` 쿼리의 성능 문제

순서있는 `IN` 쿼리 최적화

`InOperatorOptimization` 모듈

`QueryBuilder`의 기본 사용법

`IN` 쿼리 최적화 사용

다중 `IN` 쿼리

계산된 `ORDER BY` 표현 사용

`JOIN` 열 별로 정렬

일반화된 `IN` 최적화 기법