효율적인 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 열로 id 열을 추가해야 합니다.
이 쿼리의 실행은 크게 세 단계로 나뉘어질 수 있습니다:
-
데이터베이스는 그룹 계층 내의 모든 그룹에서 모든 프로젝트를 찾기 위해
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 쿼리 최적화
“코끼리를 록앤롤로 춤추게 하는 방법”라는 발표에서
Maxim Boguk은 우리의 정렬된 그룹 수준 쿼리와 같은 특별한 유형의 정렬된 IN 쿼리를 최적화하는 기술을
시연했습니다.
일반적인 정렬된 IN 쿼리는 다음과 같이 생겼습니다:
SELECT t.* FROM t
WHERE t.fkey IN (value_set)
ORDER BY t.pkey
LIMIT N;
이 기술에 사용된 주요 통찰력은 다음과 같습니다: t.fkey IN value_set 조건을 만족하는 모든 레코드를 조회하는 대신
최대 |value_set| + N 번의 레코드 조회가 필요하다는 것입니다.
value_set은 value_set의 값의 수입니다.
우리는 GitLab에서 효율적인 IN 쿼리를 구축하기 위해 Gitlab::Pagination::Keyset::InOperatorOptimization 클래스에 유틸리티를 구현하여
이 기술을 채택하고 일반화했습니다.
요구 사항
이 기술은 IN 연산자를 사용하는 기존 그룹 수준 쿼리를 대체할 수 없습니다.
이 기술은 다음 요구 사항을 충족하는 IN 쿼리만 최적화할 수 있습니다:
-
LIMIT가 존재해야 하며, 이는 일반적으로 쿼리가 페이지 매김(오프셋 또는 키셋 페이지 매김)된다는 의미입니다. -
IN쿼리에 사용되는 열과ORDER BY절의 열은 데이터베이스 인덱스에 의해 커버되어야 합니다. 인덱스의 열은 다음 순서여야 합니다:column_for_the_in_query,order by column 1,order by column 2. -
ORDER BY절의 열은 고유해야 하며 (열의 조합이 테이블의 특정 행을 고유하게 식별해야 합니다).
경고:
이 기술은 COUNT(*) 쿼리의 성능을 향상시키지 않습니다.
InOperatorOptimization 모듈
Gitlab::Pagination::Keyset::InOperatorOptimization 모듈은 이전 섹션에서 설명한 효율적인 IN 쿼리 기술의 일반화된 버전을 적용하기 위한 유틸리티를 구현합니다.
요구 사항을 충족하는 최적화된 정렬된 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는 데이터베이스에서 실제 레코드 행을 로드합니다. 이것도 람다여야 하며, 레코드를 찾기 위해 사용 가능한 순서 열 표현이 필요합니다. 이 예에서는, 전달된 값이created_at과idSQL 표현입니다. 레코드를 찾는 것은 기본 키를 통해 매우 빠르기 때문에,created_at값을 사용하지 않습니다.finder_query람다를 제공하는 것은 선택 사항입니다. 제공되지 않을 경우,IN연산자 최적화는 사용자가ORDER BY열만 사용할 수 있도록 하며 전체 데이터베이스 행은 사용할 수 없습니다.
다음 데이터베이스 인덱스는 쿼리가 효율적으로 실행되도록 하기 위해 필수입니다:
"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로 추가 필터를 추가해 보겠습니다.
쿼리에 추가 필터를 추가할 때 주의해야 합니다. 열이 동일한 인덱스로 커버되지 않으면 쿼리 성능이 최적화되지 않은 쿼리보다 더 나쁠 수 있습니다. 현재 issues 테이블의 milestone_id 열은 다른 인덱스로 커버되고 있습니다:
"index_issues_on_milestone_id" btree (milestone_id)
scope 인수 또는 최적화된 범위에 milestone_id = X 필터를 추가하면 성능에 나쁜 영향을 미칠 수 있습니다.
예시(나쁨):
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder.new(
scope: scope,
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
).execute
.where(milestone_id: 5)
.limit(20)
이 문제를 해결하기 위해 다른 인덱스를 정의할 수 있습니다:
"idx_issues_on_project_id_and_milestone_id_and_created_at_and_id" btree (project_id, milestone_id, created_at, id)
issues 테이블에 더 많은 인덱스를 추가하면 UPDATE 쿼리 성능에 심각한 영향을 미칠 수 있습니다. 이 경우 원래 쿼리를 사용하는 것이 좋습니다. 즉, 필터링되지 않은 페이지에 대해 최적화를 사용하려면 애플리케이션 코드에 추가 로직을 더해야 합니다:
if optimization_possible? # 추가 매개변수 없거나 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 표현식 사용
다음 예제는 에픽 기록을 생성 시간과 종료 시간 사이의 지속 시간에 따라 정렬합니다. 이는 다음 공식을 사용하여 계산됩니다:
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' # 계산된 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 매개변수가 사용되지 않음을 주목하세요. 이 쿼리는 duration_in_seconds(계산된 열) 및 id 열인 ORDER BY 열만 반환합니다. 이는 기능의 제한으로, 계산된 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로 문제를 정렬하기
첫 번째 단계는 모든 필요한 열을 SELECT 절에 수집하는 CTE를 생성하는 것입니다.
cte_query = Issue
.select('issues.id AS id', 'issues.project_id AS project_id', 'projects.name AS projects_name')
.joins(:project)
cte = Gitlab::SQL::CTE.new(:issue_with_projects, cte_query, materialized: false)
사용자 정의 정렬 객체 구성:
order = Gitlab::Pagination::Keyset::Order.build([
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: 'projects_name',
order_expression: Issue.arel_table[:projects_name].asc,
sql_type: 'character varying',
nullable: :nulls_last
),
Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
attribute_name: :id,
order_expression: Issue.arel_table[:id].asc
)
])
쿼리 생성:
scope = cte.apply_to(Issue.where({}).reorder(order))
opts = {
scope: scope,
array_scope: Project.where(namespace_id: top_level_group.self_and_descendants.select(:id)).select(:id),
array_mapping_scope: -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
}
records = Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
.new(**opts)
.execute
.limit(20)
배치 반복
레코드에 대한 배치 반복은 키셋 Iterator 클래스 덕분에 가능합니다.
scope = Issue.order(:created_at, :id)
array_scope = Group.find(9970).all_projects.select(:id)
array_mapping_scope = -> (id_expression) { Issue.where(Issue.arel_table[:project_id].eq(id_expression)) }
finder_query = -> (created_at_expression, id_expression) { Issue.where(Issue.arel_table[:id].eq(id_expression)) }
opts = {
in_operator_optimization_options: {
array_scope: array_scope,
array_mapping_scope: array_mapping_scope,
finder_query: finder_query
}
}
Gitlab::Pagination::Keyset::Iterator.new(scope: scope, **opts).each_batch(of: 100) do |records|
puts records.select(:id).map { |r| [r.id] }
end
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
카미나리와 함께하는 오프셋 페이지네이션
InOperatorOptimization 클래스에서 생성된 ActiveRecord 스코프는
offset-paginated 쿼리에서 사용할 수 있습니다.
Gitlab::Pagination::Keyset::InOperatorOptimization::QueryBuilder
.new(...)
.execute
.page(1)
.per(20)
.without_count
일반화된 IN 최적화 기술
QueryBuilder가 어떻게 최적화된 쿼리를 구축하여 gitlab-org 그룹에서 생성된 가장 오래된 20개의 문제를 가져오는지 살펴봅시다.
배열 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 절을 준수하는 최초의 문제 레코드를 식별하는 커서 값 (created_at, id)를 가져와야 합니다:
SELECT "issues"."created_at", "issues"."id"
FROM "issues"."project_id"=9
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1;
우리는 LATERAL JOIN을 사용하여 array_cte의 레코드를 반복하고
각 프로젝트에 대한 커서 값을 찾습니다. 쿼리는 array_mapping_scope 람다 함수를 사용하여 구축됩니다.
SELECT ARRAY_AGG("array_cte"."id") AS array_cte_id_array,
ARRAY_AGG("issues"."created_at") AS issues_created_at_array,
ARRAY_AGG("issues"."id") AS issues_id_array
FROM (
SELECT "array_cte"."id" FROM array_cte
) array_cte
LEFT JOIN LATERAL
(
SELECT "issues"."created_at", "issues"."id"
FROM "issues"
WHERE "issues"."project_id" = "array_cte"."id"
ORDER BY "issues"."created_at" ASC, "issues"."id" ASC
LIMIT 1
) issues ON TRUE
우리는 project_id, created_at, 및 id에 대한 인덱스가 있으므로,
인덱스 전용 스캔은 모든 커서 값을 빠르게 찾을 수 있어야 합니다.
이 쿼리를 Ruby로 변환하면 다음과 같습니다:
created_at_values = []
id_values = []
project_ids.map do |project_id|
created_at, id = Issue.select(:created_at, :id).where(project_id: project_id).order(:created_at, :id).limit(1).first # N+1이지만 빠릅니다.
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)이 됩니다. -
(
2020-01-05,3)을 사용하여ORDER BY절을 준수하는 다음 문제를 가져올 수 있습니다. 이는 업데이트된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 - 20개의 레코드를 가져올 때까지 업데이트된
resultset에 대해 1에서 3단계를 반복합니다.
재귀 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 절에 따라 LIMIT 1과 함께 정렬합니다. UNNEST [] WITH ORDINALITY 테이블 함수를 사용합니다. 이 함수는 “최소” 키 세트 커서 값들을 찾고 배열 위치를 제공합니다. 이러한 커서 값들은 레코드를 찾는 데 사용됩니다.
참고: 이 시점에서는 데이터베이스 테이블에서 아무것도 읽지 않았습니다. 왜냐하면 빠른 인덱스 전용 스캔에 의존했기 때문입니다.
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:]
루비에서의 동등한 표현은 다음과 같습니다:
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초 | 660ms |
최적화된 IN 쿼리 |
9,783 | 450ms | 22ms |
노트:
측정을 하기 전에 그룹 조회 쿼리를 별도로 실행하여 그룹 데이터가 버퍼 캐시에 사용 가능하도록 했습니다. 자주 호출되는 쿼리이기 때문에 생산 환경에서 쿼리 실행 중에 많은 공유 버퍼에 히트합니다.
도움말