효율적인 IN 연산자 쿼리
이 문서는 IN SQL 연산자를 사용하여 효율적으로 정렬된 데이터베이스 쿼리를 작성하는 기술과 해당 기술을 적용하는 데 도움이 되는 GitLab 유틸리티 모듈에 대해 설명합니다.
동기
GitLab에서 Issue와 같은 많은 도메인 객체는 프로젝트 및 그룹의 중첩된 계층 구조 내에 존재합니다.
그룹 수준에서 도메인 객체의 중첩된 데이터베이스 레코드를 검색하려면 IN SQL 연산자를 사용하여 쿼리를 수행합니다.
우리는 주로 레코드를 일부 속성에 따라 정렬하고, ORDER BY 및 LIMIT 절을 사용하여 레코드 수를 제한합니다.
페이징을 사용하여 후속 레코드를 가져올 수 있습니다.
그룹 수준부터 중첩된 도메인 객체를 쿼리하는 예시 작업:
-
gitlab-org그룹에서 생성 날짜 또는 마감 날짜별로 처음 20개Issue표시 -
gitlab-com그룹에서 Merge된 날짜별로 처음 20개 Merge Request 표시
아쉽게도, 정렬된 그룹 수준 쿼리는 일반적으로 실행에 많은 문제가 발생하며, 이러한 실행은 많은 I/O, 메모리 및 연산을 필요로 합니다. 이러한 쿼리의 실행에 대해 심층적으로 검토해 보겠습니다.
IN 쿼리의 성능 문제
다음 쿼리를 사용하여 gitlab-org 그룹에서 생성된 날짜순으로 가장 오래된 20개 Issue를 가져오는 작업을 고려해보십시오.
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
이 쿼리의 실행은 주로 세 가지 단계로 분할될 수 있습니다.
- 데이터베이스는
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개 미만 Issue 수: 100,000개 미만
이 디렉터리에서 볼 때, issues 레코드 수가 가장 많은 영향을 미친다는 것이 명백합니다.
일반적인 사용에 따르면, namespaces 및 projects 레코드 수보다 issues 레코드 수가 더 빠른 속도로 증가한다고 말할 수 있습니다.
이 문제는 우리의 그룹 수준 기능의 대부분에 영향을 미치며, 여기에는 그룹 수준 Issue, Merge Request 페이지 및 API와 같이 특정 순서로 레코드가 나열되는 기능이 포함됩니다. 매우 큰 그룹의 경우 데이터베이스 쿼리가 쉽게 시간 초과될 수 있어 HTTP 500 오류가 발생할 수 있습니다.
정렬된 IN 쿼리의 최적화
“How to teach an elephant to dance rock and roll”
라는 강연에서 Maxim Boguk은 우리의 정렬된 그룹 수준 쿼리와 같은 특별한 종류에 대한 IN 쿼리를 최적화하기 위한 기술을 시연했습니다.
전형적인 정렬된 IN 쿼리는 다음과 같은 모습일 수 있습니다:
SELECT t.* FROM t
WHERE t.fkey IN (value_set)
ORDER BY t.pkey
LIMIT N;
다음은 이 기술에서 사용되는 주요 통찰력입니다: |value_set| + N 레코드 조회만 필요하며, 모든 조건을 충족하는 레코드를 모두 검색할 필요가 없습니다(|value_set|는 value_set에서의 값 수입니다).
우리는 이 기술을 채택하고 일반화하여 GitLab에서 효율적인 IN 쿼리를 작성하는 데 도움이 되는 Gitlab::Pagination::Keyset::InOperatorOptimization 클래스의 유틸리티를 구현했습니다.
요구 사항
기법은 기존의 IN 연산자를 사용하는 그룹 레벨 쿼리에 대한 완전한 대체가 아닙니다.
기법은 다음 요구 사항을 충족하는 IN 쿼리만 최적화할 수 있습니다.
- 일반적으로 쿼리가 페이지네이션(오프셋 또는 키셋 페이지네이션)된 것을 의미하는
LIMIT가 존재합니다. -
IN쿼리에서 사용되는 열과ORDER BY절의 열이 데이터베이스 인덱스로 처리됩니다. 인덱스의 열은 다음 순서대로여야 합니다:IN 쿼리를 위한 열,order by 열 1, 그리고order by 열 2. -
ORDER BY절의 열은 서로 구분되어야 합니다 (열의 조합이 테이블에서 특정 행을 고유하게 식별해야 함).
COUNT(*) 쿼리의 성능을 향상시키지 않습니다.The InOperatorOptimization module
Gitlab::Pagination::Keyset::InOperatorOptimization 모듈은 이전 섹션에서 설명한 효율적인 IN 쿼리 기술의 일반화된 버전을 적용하기 위한 유틸리티를 구현합니다.
요구 사항을 충족하는 최적화된, 순서가 지정된 IN 쿼리를 작성하려면 모듈에서 제공하는 유틸리티 클래스 QueryBuilder를 사용하세요.
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 (subquery)를 나타내는ActiveRecord::Relation객체입니다. 선택한 값은 서브쿼리가 주 쿼리에 “연결”되는 열로 포함해야 합니다. 즉, 프로젝트 레코드의id입니다. -
array_mapping_scope은ActiveRecord::Relation객체를 반환하는 람다를 정의합니다. 람다는array_scope의 단일 선택 값을=와 일치시킵니다. 람다는array_scope에서 정의한 선택 값과 같은 수의 인수를 생성합니다. 인수는 Arel SQL 표현식입니다. -
finder_query는 실제 레코드 행을 데이터베이스에서 로드합니다. 이 역시 람다여야 하며, 레코드를 찾기 위해ORDER BY열 표현식이 사용 가능해야 합니다. 이 예에서는 생성된 값이created_at및idSQL 표현식입니다. 레코드를 기본 키를 통해 매우 빠르게 찾을 수 있으므로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를 추가로 필터로 추가해보겠습니다.
쿼리에 추가 필터를 추가할 때 주의하세요. milestone_id 열이 같은 인덱스로 처리되지 않는 경우,
최적화되지 않은 쿼리보다 쿼리의 성능이 떨어질 수 있습니다. issues 테이블의 milestone_id 열이 현재 다른 인덱스에 의해 처리 중입니다:
"index_issues_on_milestone_id" btree (milestone_id)
scope 인수나 최적화된 scope에 milestone_id = X 필터를 추가하면 성능이 저하될 수 있습니다.
예시 (좋지 않은 방법):
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: scope,
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
).execute
.where(milestone_id: 5)
.limit(20)
이 우려에 대처하기 위해, 다른 인덱스를 정의할 수 있습니다:
"idx_issues_on_project_id_and_milestone_id_and_created_at_and_id" btree (project_id, milestone_id, created_at, id)
issues 테이블에 더 많은 인덱스를 추가하면 UPDATE 쿼리의 성능에 중대한 영향을 줄 수 있습니다. 이 경우 원래 쿼리에 의존하는 것이 더 좋습니다. 즉, 필터되지 않는 페이지에 최적화를 사용하려면 응용 프로그램 코드에 추가 논리를 추가해야 합니다:
if optimization_possible? # 추가 매개변수가 없거나 매개변수가 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 enum이므로 다음 표를 구성해야 합니다:
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
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 표현 사용
다음 예시는 이픽 레코드를 생성 시간과 종료 시간 사이의 기간으로 정렬합니다. 다음 공식으로 계산됩니다.
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가 없음) tie-breaker 열 (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) # 다른 열들은 사용 불가
쿼리를 작성하는 데 상당한 구성이 필요합니다. finder_query를 정의하는 방법에 대한 자세한 내용은 복합 ORDER BY 구성 섹션에서 찾을 수 있습니다.
특정 데이터베이스 인덱스가 필요합니다:
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)을 통해 추가 구성이 필요합니다. “가짜” 테이블로 작용하는 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 객체 구성:
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
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
Keyset 페이지네이션
이 최적화는 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 스케프(scope)는
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 절을 준수하는 각 프로젝트의 첫 번째 레코드의 커서 값(created_at, id)을 보여줍니다.
여기까지 초기 데이터가 있습니다. 데이터베이스에서 실제 레코드를 수집하기 시작하려면,
재귀 CTE 쿼리를 사용하여 각 재귀가 LIMIT에 도달하거나 더 이상 데이터를 찾을 수 없을 때까지 한 행씩 찾습니다.
재귀 CTE 쿼리에서 취하는 단계를 요약하면 다음과 같습니다 (SQL로 표현하는 것은 비직관적이지만 아래에서 설명합니다):
- 초기
resultset을ORDER BY절에 따라 정렬합니다. - 다음 커서를 찾아 이것이 첫 번째 레코드가 됩니다. 예를 들어,
project_id=9에 대해 (2020-01-05,3)의 커서가 되겠죠. -
project_id=9필터를 준수하는 다음 이슈를 가져오기 위해 (2020-01-05,3)을 사용합니다. 이렇게 하면 업데이트된resultset을 얻습니다.project_idscreated_at_valuesid_values2 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 쿼리의 반복 부분
결과 행은 다음 단계로 생성됩니다:
키셋 배열을 정렬합니다
원래 ORDER BY 절에 따라 키셋 배열을 정렬하고 UNNEST [] WITH ORDINALITY 테이블 함수를 사용하여
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를 찾아봅시다.
이를 위해 keyset pagination SQL 쿼리를 작성합니다. created_at = 2020-01-05 및 id = 3 이후의 다음 행을 찾습니다. 두 개의 데이터베이스 열을 기준으로 정렬하므로 다음과 같은 두 가지 경우가 있을 수 있습니다.
-
created_at = 2020-01-05및id > 3인 행이 있을 수 있습니다. -
created_at > 2020-01-05인 행이 있을 수 있습니다.
이 쿼리는 일반적인 keyset pagination 라이브러리에 의해 생성됩니다. 쿼리가 끝나면, 다음과 같은 임시 테이블에 다음 커서 값이 저장됩니다.
created_at
| ID |
|---|---|
| 2020-01-06 | 6 |
새로운 행 생성
마지막 단계로, 초기화자 행(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 열 값
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).* -- 루비 스플랫 연산자와 유사함
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밀리초 |
도움말