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

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

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

참고: 기술에는 키셋 페이지네이션이 많이 사용됩니다. 우선 해당 주제에 익숙해지는 것이 좋습니다.

동기

GitLab에서는 이슈와 같은 많은 도메인 객체가 프로젝트와 그룹의 중첩 구조 내에 존재합니다. 그룹 수준에서 도메인 객체의 중첩된 데이터베이스 레코드를 검색하려면, 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 열로 정렬하는 것만으로는 충분하지 않습니다. 타이브레이커 열을 추가해야 합니다.

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

데이터베이스는 namespaces와 projects 테이블 둘 다를 접근하여 그룹 계층 구조 내 모든 프로젝트를 찾습니다.
데이터베이스는 각 프로젝트에 대해 issues 레코드를 검색하여 많은 디스크 I/O를 야기합니다. 이 과정을 최적화하기 위해 적절한 인덱스 구성이 이상적입니다.
데이터베이스는 메모리에서 created_at에 따라 issues 행을 정렬하고 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 쿼리를 최적화하는 기술을 시연했습니다. 이러한 쿼리는 주로 우리의 순서대로 그룹 레벨 쿼리와 유사할 수 있습니다.

일반적인 순서대로 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::Pagination::Keyset::InOperatorOptimization 클래스에 관련된 유틸리티를 구현하여 GitLab에서 이 기술을 사용할 수 있도록 채택하고 일반화했습니다.

요구 사항

이 기술은 기존의 IN 연산자를 사용한 그룹 레벨 쿼리에 바로 적용할 수 없습니다. 이 기술은 다음 요구 사항을 충족하는 IN 쿼리만 최적화할 수 있습니다:

일반적으로 쿼리가 페이지별로 되어 있음을 나타내는 LIMIT이 존재합니다.
IN 쿼리와 ORDER BY 절에서 사용되는 열이 데이터베이스 인덱스로 지원됩니다. 인덱스의 열은 다음과 같은 순서로 있어야 합니다: IN 쿼리에 사용되는 열, ORDER BY 열 1, ORDER BY 열 2.
ORDER BY 절의 열은 서로 고유합니다 (열의 조합이 테이블에서 특정 행을 고유하게 식별합니다).

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

`InOperatorOptimization` 모듈

Gitlab::Pagination::Keyset::InOperatorOptimization 모듈은 이전 섹션에서 설명한 효율적인 IN 쿼리 기술의 일반화된 버전을 적용하기 위한 유틸리티를 구현합니다. 이 모듈은 QueryBuilder라는 유틸리티 클래스를 사용하여 최적화된 순서대로 IN 쿼리를 작성하도록 도와줍니다.

요구 사항을 충족하는 최적화된 순서대로 IN 쿼리를 작성하려면 해당 모듈에서 제공하는 QueryBuilder 클래스를 사용하세요.

참고: 병합 요청 51481에서 도입된 일반 키셋 페이지네이션 모듈은 Gitlab::Pagination::Keyset::InOperatorOptimization에서 이 기술의 일반화된 구현에 중요한 역할을 합니다.

`QueryBuilder`의 기본적인 사용법

기본적인 사용법을 설명하기 위해, gitlab-org 그룹에서 가장 오래된 created_at를 가진 20개의 이슈를 가져오는 쿼리를 작성해보겠습니다. 이를 위해 Issue 모델을 사용하여 다음과 같이 표현할 수 있을 것입니다:

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 객체를 나타냅니다. 관련된 순서는 반드시 키셋 페이지네이션 라이브러리에서 지원되어야 합니다.
array_scope는 IN (subquery)를 나타내는 ActiveRecord::Relation 객체를 포함합니다. 선택된 값은 하위 쿼리를 주 쿼리에 “연결”하는 데 사용되는 열을 포함해야 합니다. 즉, 프로젝트 레코드의 id입니다.
array_mapping_scope는 ActiveRecord::Relation 객체를 반환하는 람다를 정의합니다. 이 람다는 array_scope에서 단일 선택 값을 유사하게(=) 매칭시킵니다. 람다는 array_scope에서 정의된 선택 값만큼의 인수를 생성합니다. 이러한 인수는 Arel SQL 표현식입니다.
finder_query는 실제 레코드를 데이터베이스에서 로드합니다. 이 역시 람다여야 하며 여기서 created_at 열 표현식이 레코드를 찾기 위해 사용 가능해야 합니다. 이 예에서 제공된 레코드를 찾는 쿼리는 굉장히 빠르며 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 (  -- 초기화된 행 시작
                                               (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)
                                                -- 초기화된 행 완료
                                             UNION ALL
                                               (SELECT
                                                  -- 결과 행 시작
                                                  (SELECT issues -- 레코드 찾기 쿼리가 첫 번째 열
                                                   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
                                                -- 결과 행 완료
                                                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,
                                                  -- 다음 커서 값 찾기 (next_cursor_values_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 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))
                                                  -- 다음 커서 값 찾기 (next_cursor_values_query) 끝
SELECT (records).*
   FROM "recursive_keyset_cte" AS "issues"
   WHERE (COUNT <> 0)) issues -- 초기화된 행 필터링
LIMIT 20

`IN` 쿼리 최적화 사용

추가 필터 추가

이 예에서는 milestone_id로 추가 필터를 추가해봅시다.

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

"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? # 추가 매개변수가 없거나 매개변수가 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)

배열 scope를 구성하려면 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 쿼리:

위와 동일합니다.

참고: 쿼리를 효율적으로 만들기 위해 다음 열은 인덱스로 커버해야 합니다: 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

이러한 순서를 그룹 수준에서 효율적으로 만들기 위해 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' # 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), # 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 테이블에서 나온 혼합 열에 따라 레코드를 정렬하는 것은 제한사항이 있습니다. 이를 위해 공통 테이블 표현(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
          ),
          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가 최적화된 쿼리를 작성하는 방법에 대해 자세히 살펴보겠습니다. 이를 통해 그룹 gitlab-org에서 만들어진 가장 오래된 이슈 20개를 가져오기 위한 일반화된 IN 최적화 기술을 사용합니다.

배열 CTE

첫 번째 단계로 projects.id 값을 수집하기 위해 공통 테이블 표현식(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)로 이루어진 다음 결과 집합을 생성합니다:

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에 인덱스가 있기 때문에 인덱스만을 이용한 스캔을 통해 모든 커서 값을 빠르게 찾을 수 있어야 합니다.

다음은 이 쿼리가 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

이것이 결과 집합의 모습입니다:

`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 절을 고려하여 각 프로젝트의 첫 번째 레코드의 커서 값을 보여줍니다.

이 시점에서 우리는 초기 데이터를 갖게 되었습니다. 실제 레코드를 수집하기 위해 재귀 CTE 쿼리를 사용하여 각 재귀마다 한 행을 찾을 때까지 또는 더 이상 데이터를 찾을 수 없을 때까지 진행합니다.

다음은 재귀 CTE 쿼리에서 수행하는 단계의 개요입니다 (SQL로 단계를 표현하는 것은 비직관적이지만 다음에 설명하겠습니다):

resultset을 ORDER BY 절에 따라 초기 정렬합니다.
최상위 커서를 선택하여 레코드를 가져오고, 이것이 첫 번째 레코드입니다. 예를 들어, 예제에서 project_id=9에 대한 이 커서는 (2020-01-05, 3)일 것입니다.
(2020-01-05, 3)을 사용하여 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
갱신된 resultset으로 1부터 3까지 반복하여 N=20의 레코드를 가져올 때까지 진행합니다.

재귀 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 행 조회)

다음 커서를 찾습니다

이제 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` 쿼리	240833	1.2초	660ms
최적화된 `IN` 쿼리	9783	450ms	22ms

참고: 측정하기 전에 그룹 조회 쿼리가 별도로 실행되어 프로덕션 환경에서 쿼리 실행 중 공유 버퍼를 많이 찔렀습니다. 빈번히 호출되는 쿼리이므로 쿼리 실행 중에 많은 공유 버퍼에 접근하게 됩니다.

효율적인 `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` 최적화 기술