페이지네이션 성능 가이드라인

다음 문서는 페이지네이션(정렬) 성능을 개선하기 위한 몇 가지 아이디어를 제공합니다. 이는 오프셋 및 키셋 페이지네이션 모두에 적용됩니다.

타이브레이커 열

열을 정렬할 때는 유일한 열로만 정렬하는 것이 좋습니다. 다음 예제를 고려하세요:

`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 절에 있는 열과 일치해야 합니다.

점진적 정렬

PostgreSQL 13에서는 점진적 정렬이 추가되어 인덱스를 추가하거나 대체하지 않고 ORDER BY 절에 타이브레이커 열을 도입할 수 있게 해줍니다. 또한 점진적 정렬을 사용하면 새로운 키셋 페이지네이션 데이터베이스 쿼리를 새 인덱스가 구축되기 전에 발생할 수 있습니다(비동기 인덱스). 점진적 정렬은 기본적으로 활성화되어 있습니다.

다음 데이터베이스 쿼리를 고려하세요:

SELECT *
FROM merge_requests
WHERE author_id = 1
ORDER BY created_at ASC
LIMIT 20

쿼리는 다음 인덱스를 사용하여 20개의 행을 읽습니다:

"index_merge_requests_on_author_id_and_created_at" btree (author_id, created_at)

이 쿼리를 키셋 페이지네이션과 함께 사용하는 것은 created_at 열이 고유하지 않기 때문에 불가능합니다. 타이브레이커 열을 추가합시다:

SELECT *
FROM merge_requests
WHERE author_id = 1
ORDER BY created_at ASC, id ASC
LIMIT 20

실행 계획:

 Limit  (cost=1.99..30.97 rows=20 width=910) (actual time=1.217..1.220 rows=20 loops=1)
   Buffers: shared hit=33 read=2
   I/O Timings: read=0.983 write=0.000
   ->  Incremental Sort  (cost=1.99..919.33 rows=633 width=910) (actual time=1.215..1.216 rows=20 loops=1)
         Sort Key: merge_requests.created_at, merge_requests.id
         Buffers: shared hit=33 read=2
         I/O Timings: read=0.983 write=0.000
         ->  Index Scan using index_merge_requests_on_author_id_and_created_at on public.merge_requests  (cost=0.57..890.84 rows=633 width=910) (actual time=0.038..1.139 rows=22 loops=1)
               Index Cond: (merge_requests.author_id = 1)
               Buffers: shared hit=24 read=2
               I/O Timings: read=0.983 write=0.000

보시다시피 쿼리는 동일한 인덱스를 사용하여 22개의 행을 읽었습니다. 데이터베이스는 created_at 열의 20번째, 21번째 및 22번째 값을 비교하여 22번째 값이 다름을 판단하여 다음 레코드를 확인할 필요가 없다고 결정했습니다. 이 예제에서 20번째 및 21번째 열은 동일한 created_at 값을 가졌습니다.

점진적 정렬은 중복 값이 거의 없는 타임스탬프 열과 잘 작동하지만, 열이 고유한 값이 극히 적은 경우(enum과 같은) 점진적 정렬이 잘 수행되지 않거나 전혀 사용되지 않을 수 있습니다.

예를 들어 점진적 정렬이 비활성화된 경우, 데이터베이스는 작성자가 제출한 모든 병합 요청 레코드를 읽고 데이터를 메모리에서 정렬합니다.

set enable_incremental_sort=off;

 Limit  (cost=907.69..907.74 rows=20 width=910) (actual time=2.911..2.917 rows=20 loops=1)
   Buffers: shared hit=1004
   ->  Sort  (cost=907.69..909.27 rows=633 width=910) (actual time=2.908..2.911 rows=20 loops=1)
         Sort Key: created_at, id
         Sort Method: top-N heapsort  Memory: 52kB
         Buffers: shared hit=1004
         ->  Index Scan using index_merge_requests_on_author_id_and_created_at on merge_requests  (cost=0.57..890.84 rows=633 width=910) (actual time=0.042..1.974 rows=1111 loops=1)
               Index Cond: (author_id = 1)
               Buffers: shared hit=1111
 Planning Time: 0.386 ms
 Execution Time: 3.000 ms
(11 rows)

이 예제에서 데이터베이스는 1111개의 행을 읽고 메모리에서 행을 정렬했습니다.

조인된 테이블 열로 정렬하기

종종, 우리는 조인된 데이터베이스 테이블의 열로 데이터를 정렬하고 싶습니다. 다음 예제는 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에 대해 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).

필터링

프로젝트별

프로젝트별 필터링은 매우 일반적인 사용 사례입니다. 왜냐하면 우리는 프로젝트 수준에서 많은 기능을 갖고 있기 때문입니다. 예: 병합 요청, 이슈, 보드, 반복.

이러한 기능들은 기본 쿼리에 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)

그룹별

안타깝게도 그룹 수준에서 정렬 및 페이지 매김을 위한 효율적인 방법은 없습니다. 그룹의 레코드 수에 따라 데이터베이스 쿼리 실행 시간이 증가합니다.

그룹 수준이 실제로 그룹과 그 하위 그룹을 의미할 때 상황이 더 악화됩니다. 첫 페이지를 로드하기 위해 데이터베이스는 그룹 계층을 조회하고 모든 프로젝트를 찾은 다음 모든 이슈를 조회합니다.

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

예: 그룹 내 이슈 나열

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)보다 훨씬 더 많은 행(61)을 읽었다는 것을 보여줍니다. 행은 메모리에서 정렬됩니다:

 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 쿼리에 필터가 존재하는 이중 조인에서 발생할 수 있습니다. 예시: Issue -> LabelLink -> Label(name=bug).

이러한 문제를 해결할 수 있는 쉬운 방법은 없습니다. 데이터 비정규화가 크게 도움이 될 수 있지만, Data Duplication 및 데이터 업데이트 유지와 같은 부정적인 효과도 있습니다.

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 열이 달라지고 project_id 필터가 issues 테이블에서 사라졌다는 것입니다:

SELECT "issues".*
FROM "issues"
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에서는 이러한 종류의 데이터 비정규화를 수행하고 있지 않습니다.

페이지네이션 성능 가이드라인

타이브레이커 열

점진적 정렬

조인된 테이블 열로 정렬하기

필터링

프로젝트별

그룹별

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

특별한 경우: 기밀 플래그

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

도움말

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

도움받기