페이지네이션 성능 지침

다음 문서는 페이지네이션(정렬) 성능을 향상시키기 위한 몇 가지 아이디어를 제시합니다. 이는 offset 및 keyset 페이지네이션에 적용됩니다.

타이브레이커 열

열을 정렬할 때는 구분된 열로만 정렬하는 것이 좋습니다. 다음 예를 고려해보세요:

`id`	`created_at`
`1`	`2021-01-04 14:13:43`
`2`	`2021-01-05 19:03:12`
`3`	`2021-01-05 19:03:12`

만일 created_at으로 정렬한다면 결과는 레코드가 디스크 상에서 어떻게 위치하느냐에 따라 다를 것입니다.

데이터가 잘 정의된 인터페이스를 통해 노출되고 API와 같은 자동화된 프로세스에 의해 사용된다면 타이브레이커 열을 사용하는 것이 좋습니다. 타이브레이커 열이 없을 경우 행의 순서가 변경될 수 있어(데이터가 다시 가져와짐) 디버깅하기 어려운 문제를 일으킬 수 있습니다.

행을 비교하여 변경 사항을 결정하는 통합이 중단됩니다.
E-tag 캐시 값이 변경되어 완전한 재다운로드가 필요합니다.

SELECT issues.* FROM issues ORDER BY created_at;

이를 해결하기 위해 ORDER BY에 두 번째 열을 추가하여 다음과 같이 수정할 수 있습니다:

SELECT issues.* FROM issues ORDER BY created_at, id;

이 변경으로 순서가 구분되어 “안정적인” 정렬을 할 수 있게 됩니다.

쿼리를 효율적으로 만들기 위해 두 열을 모두 커버하는 인덱스가 필요합니다: (created_at, id). 열의 순서는 ORDER BY 절의 열과 일치해야 합니다.

조인된 테이블 열을 기준으로 정렬

자주 발생하는 경우는 다른 데이터베이스 테이블의 열을 기준으로 데이터를 정렬하고자 하는 것입니다. 다음 예에서는 issue_metrics 테이블의 first_mentioned_in_commit_at 메트릭 열을 기준으로 issues 레코드를 정렬합니다:

SELECT issues.* FROM issues
INNER JOIN issue_metrics on issue_metrics.issue_id=issues.id
WHERE issues.project_id = 2
ORDER BY issue_metrics.first_mentioned_in_commit_at DESC, issues.id DESC
LIMIT 20
OFFSET 0

PostgreSQL 11에서 플래너는 먼저 project_id 필터와 일치하는 모든 문제를 찾고 그 다음 모든 issue_metrics 행을 결합합니다. 행의 정렬은 메모리에서 이루어집니다. 결합된 관계가 항상 존재하는 경우(1:1 관계), 데이터베이스는 project_id 필터와 일치하는 행의 수(N) * 2만큼의 행을 읽습니다.

성능상의 이유로 ORDER BY 절에서 다른 테이블의 열을 섞는 것을 피해야 합니다.

특별한 경우에는 쿼리를 개선할 수 있는 간단한 방법(예: 인덱스 생성)이 없습니다. ‘issues.id’ 열을 ‘issue_metrics.issue_id’로 변경하면 쿼리의 성능이 저하될 수 있습니다. 왜냐하면 데이터베이스가 ‘issue_metrics’ 테이블의 모든 행을 처리하게 할 수 있기 때문입니다.

이 문제를 해결하기 위한 한 가지 아이디어는 정규화입니다. issue_metrics 테이블에 project_id 열을 추가하면 필터링과 정렬을 효율적으로 수행할 수 있습니다:

SELECT issues.* FROM issues
INNER JOIN issue_metrics on issue_metrics.issue_id=issues.id
WHERE issue_metrics.project_id = 2
ORDER BY issue_metrics.first_mentioned_in_commit_at DESC, issue_metrics.issue_id DESC
LIMIT 20
OFFSET 0

issue_metrics 테이블에 다음과 같은 열 구성을 가진 인덱스가 필요합니다: (project_id, first_mentioned_in_commit_at DESC, issue_id DESC).

필터링

프로젝트별

프로젝트별로 필터링하는 것은 프로젝트 수준에서 많은 기능이 있기 때문에 매우 흔한 사용 사례입니다. Merge Request, 이슈, 보드, 이터레이션 등의 예시가 있습니다.

이러한 기능은 기본 쿼리에서 project_id에 대한 필터를 가지고 있습니다. 프로젝트의 이슈를 불러오기:

project = Project.find(5)

# 내부 ID로 정렬
issues = project.issues.order(:iid).page(1).per(20)

기본 쿼리를 효율적으로 만들기 위해 보통 project_id 열을 커버하는 데이터베이스 인덱스가 있습니다. 이는 데이터베이스가 스캔해야 하는 행의 수를 크게 줄여줍니다. 인덱스가 없다면 데이터베이스가 issues 테이블 전체를 스캔해야 합니다(전체 테이블 스캔).

project_id가 외래 키이므로 아마 다음과 같은 인덱스가 있는 것일 수 있습니다:

"index_issues_on_project_id" btree (project_id)

GitLab 13.11에는 issues 테이블에 다음과 같은 인덱스 정의가 있습니다:

"index_issues_on_project_id_and_iid" UNIQUE, btree (project_id, iid)

이 인덱스는 데이터베이스 쿼리와 페이지네이션을 완전히 커버합니다.

그룹별

그룹 수준에서 정렬하고 페이지네이션하는 효율적인 방법은 아쉽게도 없습니다. 데이터베이스 쿼리 실행 시간이 그룹 내 레코드 수에 따라 증가합니다.

그룹 수준이 그룹과 해당 하위 그룹을 의미할 때 상황은 더 나빠집니다. 첫 번째 페이지를 불러오기 위해서 데이터베이스는 그룹 계층 구조를 조회하고 모든 프로젝트를 찾은 다음 모든 이슈를 조회합니다.

그룹 수준에서 효율적이지 못한 쿼리의 주된 이유는 데이터베이스 스키마가 설계된 방식 때문입니다. 핵심 도메인 모델은 프로젝트와 연결되어 있고, 프로젝트는 그룹과 연결되어 있습니다. 이것은 데이터베이스 구조가 나쁘다는 것을 의미하는 것이 아니라, 효율적인 그룹 수준 쿼리를 위해 최적화되지 않은 잘 정규화된 형태에 있다는 것입니다. 장기적으로 정규화를 살펴봐야 할 수도 있습니다.

예시: 그룹 내의 이슈 나열

group = Group.find(9970)

Issue.where(project_id: group.projects).order(:iid).page(1).per(20)

생성된 SQL 쿼리:

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" IN
    (SELECT "projects"."id"
     FROM "projects"
     WHERE "projects"."namespace_id" = 5)
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

실행 계획에 따르면 요청된 행(20개)보다 훨씬 많은 행이 읽히고 행은 메모리에서 정렬됩니다:

 Limit  (cost=10716.87..10716.92 rows=20 width=1300) (actual time=1472.305..1472.308 rows=20 loops=1)
   ->  Sort  (cost=10716.87..10717.03 rows=61 width=1300) (actual time=1472.303..1472.305 rows=20 loops=1)
         Sort Key: issues.iid
         Sort Method: top-N heapsort  Memory: 41kB
         ->  Nested Loop  (cost=1.00..10715.25 rows=61 width=1300) (actual time=0.215..1331.647 rows=177267 loops=1)
               ->  Index Only Scan using index_projects_on_namespace_id_and_id on projects  (cost=0.44..3.77 rows=19 width=4) (actual time=0.077..1.057 rows=270 loops=1)
                     Index Cond: (namespace_id = 9970)
                     Heap Fetches: 25
               ->  Index Scan using index_issues_on_project_id_and_iid on issues  (cost=0.56..559.28 rows=448 width=1300) (actual time=0.101..4.781 rows=657 loops=270)
                     Index Cond: (project_id = projects.id)
 Planning Time: 12.281 ms
 Execution Time: 1472.391 ms
(12 rows)

동일한 데이터베이스 테이블의 열

동일한 데이터베이스 테이블에 있는 열로 필터링하는 경우에는 인덱스를 추가하여 성능을 향상시킬 수 있습니다. 이 경우 state_id 열로 필터링을 지원하려면 다음과 같은 인덱스를 추가할 수 있습니다:

"index_issues_on_project_id_and_state_id_and_iid" UNIQUE, btree (project_id, state_id, iid)

Rails에서의 예제 쿼리:

project = Project.find(5)

# 내부 ID 기준으로 정렬
issues = project.issues.opened.order(:iid).page(1).per(20)

SQL 쿼리:

SELECT "issues".*
FROM "issues"
WHERE
  "issues"."project_id" = 5
  AND ("issues"."state_id" IN (1))
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

위의 인덱스는 다음의 프로젝트 레벨 쿼리를 지원하지 않습니다:

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" = 5
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

특수 케이스: 기밀 플래그

issues 테이블에서 이슈를 기밀로 표시하는 부울 필드(confidential)가 있습니다. 이로써 기밀 이슈는 비회원 사용자에게는 보이지 않게 됩니다.

예제 SQL 쿼리:

SELECT "issues".*
FROM "issues"
WHERE "issues"."project_id" = 5
AND "issues"."confidential" = FALSE
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

project_id, confidential, iid에 대한 인덱스를 추가하여 데이터베이스 쿼리를 개선할 수 있을 것으로 유혹될 수 있습니다. 그러나 이 경우에는 그런 필요가 없을 가능성이 높습니다. 테이블 내 데이터 분포를 기반으로, 기밀 이슈가 드물다는 것을 감안하면, 해당 이슈를 걸러내는 것이 데이터베이스 쿼리의 성능에 큰 영향을 미치지 않을 것입니다. 데이터베이스는 몇 개의 추가 행을 읽을 수도 있지만, 성능 차이는 최종 사용자에게 심각한 영향을 미칠 정도는 아닐 것입니다.

반면에, 기밀 이슈만 표시하는 특수 필터를 구현한다면, 해당 인덱스가 필요합니다. 20개의 기밀 이슈를 찾는 것은 수백 개의 행이나, 최악의 경우에는 프로젝트 내 모든 이슈를 스캔해야 할 수도 있습니다.

새로운 데이터베이스 인덱스를 도입할 때 데이터 분포와 테이블 액세스 패턴(기능 작동 방식)에 대해 신중히 고려해야 합니다. 올바른 결정을 내리기 위해 프로덕션 데이터를 샘플링하는 것이 필요할 수 있습니다.

다른 데이터베이스 테이블의 열

예시: 담당자에 따라 프로젝트의 이슈 필터링하기

project = Project.find(5)

project
  .issues
  .joins(:issue_assignees)
  .where(issue_assignees: { user_id: 10 })
  .order(:iid)
  .page(1)
  .per(20)

SELECT "issues".*
FROM "issues"
INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
WHERE "issues"."project_id" = 5
  AND "issue_assignees"."user_id" = 10
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

예제 데이터베이스(과도하게 단순화한) 실행 계획:

데이터베이스는 SQL 쿼리를 구문 분석하고 JOIN을 감지합니다.
데이터베이스는 쿼리를 두 개의 하위 쿼리로 분할합니다.
- SELECT "issue_assignees".* FROM "issue_assignees" WHERE "issue_assignees"."user_id" = 10
- SELECT "issues".* FROM "issues" WHERE "issues"."project_id" = 5
데이터베이스는 실행할 쿼리의 행 수 및 비용을 추정합니다.
데이터베이스는 가장 저렴한 쿼리를 먼저 실행합니다.
쿼리 결과를 사용하여 다른 테이블에서 (다른 쿼리에서) 행을 로드하고, JOIN 열을 사용하여 행을 더 필터링합니다.

이 특별한 예제에서 issue_assignees 쿼리가 먼저 실행될 가능성이 높습니다.

GitLab 프로젝트에서 이 쿼리를 실행하는 경우 다음 실행 계획이 생성됩니다:

 Limit  (cost=411.20..411.21 rows=1 width=1300) (actual time=24.071..24.077 rows=20 loops=1)
   ->  Sort  (cost=411.20..411.21 rows=1 width=1300) (actual time=24.070..24.073 rows=20 loops=1)
         Sort Key: issues.iid
         Sort Method: top-N heapsort  Memory: 91kB
         ->  Nested Loop  (cost=1.00..411.19 rows=1 width=1300) (actual time=0.826..23.705 rows=190 loops=1)
               ->  Index Scan using index_issue_assignees_on_user_id on issue_assignees  (cost=0.44..81.37 rows=92 width=4) (actual time=0.741..13.202 rows=215 loops=1)
                     Index Cond: (user_id = 4156052)
               ->  Index Scan using issues_pkey on issues  (cost=0.56..3.58 rows=1 width=1300) (actual time=0.048..0.048 rows=1 loops=215)
                     Index Cond: (id = issue_assignees.issue_id)
                     Filter: (project_id = 278964)
                     Rows Removed by Filter: 0
 Planning Time: 1.141 ms
 Execution Time: 24.170 ms
(13 rows)

쿼리는 먼저 assignees를 조회하고, user_id (user_id = 4156052)로 필터링한 215개의 행을 찾습니다. 이 215개의 행을 사용하여 데이터베이스는 기본 키로 연결된 215개의 이슈 행을 찾습니다. project_id 열에 대한 필터가 인덱스로 지원되지 않았다는 점에 주목하세요.

대부분의 경우에는 다행히도 조인된 관계가 너무 많은 행을 반환하지 않아서, 상대적으로 효율적인 데이터베이스 쿼리를 실행하게 됩니다. 그러나 데이터베이스가 커질수록 이러한 쿼리는 다르게 작동할 수 있습니다. 특정 사용자의 issue_assignees 레코드 수가 수백만 개인 경우를 생각해보겠습니다. 이 조인 쿼리는 성능이 좋지 않아 타임아웃될 가능성이 높습니다.

비슷한 문제로는 2개의 JOIN 쿼리에서 필터가 존재하는 이중 조인 문제가 있을 수 있습니다. 예시: 이슈 -> LabelLink -> Label(name=bug).

이러한 문제를 해결하는 것은 쉽지 않습니다. 데이터의 비정규화는 크게 도움이 될 수 있지만, 부정적인 영향(데이터 중복 및 데이터 업데이트 유지)도 가지고 있습니다.

issue_assignees 필터를 개선하기 위한 아이디어:

issue_assignees 테이블에 project_id 열을 추가하여 JOIN 수행 시 추가 project_id 필터로 행을 더 필터하는 방법. 정렬은 메모리에서 이루어질 것으로 예상됩니다:

SELECT "issues".*
FROM "issues"
INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
WHERE "issues"."project_id" = 5
  AND "issue_assignees"."user_id" = 10
  AND "issue_assignees"."project_id" = 5
ORDER BY "issues"."iid" ASC
LIMIT 20
OFFSET 0

issue_assignees 테이블에 iid 열을 추가하는 방법. ORDER BY 열이 다르며, issues 테이블에서 project_id 필터가 제거되었음에 주목하세요:

SELECT "issues".*
FROM "project_id"
INNER JOIN "issue_assignees" ON "issue_assignees"."issue_id" = "issues"."id"
WHERE "issue_assignees"."user_id" = 10
  AND "issue_assignees"."project_id" = 5
ORDER BY "issue_assignees"."iid" ASC
LIMIT 20
OFFSET 0

이제 쿼리는 무수히 많은 issue_assignees 레코드에 대해 잘 작동하지만, 그에 대가를 치뤄야 합니다:

두 열이 중복되어 데이터베이스 크기가 증가합니다.
두 열을 동기화 유지해야 합니다.
쿼리를 지원하기 위해 issue_assignees 테이블에 더 많은 인덱스가 필요합니다.
새로운 데이터베이스 쿼리는 담당자 검색에 매우 특정화되어 있으며, 이를 작성하기 위한 복잡한 백엔드 코드가 필요합니다.
- 담당자가 사용자에 의해 필터링되고, 다른 열을 기준으로 정렬하거나, project_id 필터를 제거하는 등의 경우.

현재로서 GitLab에서는 이러한 종류의 비정규화를 수행하지 않고 있습니다.

페이지네이션 성능 지침

타이브레이커 열

조인된 테이블 열을 기준으로 정렬

필터링

프로젝트별

그룹별

동일한 데이터베이스 테이블의 열

특수 케이스: 기밀 플래그

다른 데이터베이스 테이블의 열

도움말

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

도움받기