페이지네이션 성능 지침

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

Tie-breaker column

열을 정렬할 때에는 고유한 열에 의해서만 정렬하는 것이 좋습니다. 다음 예시를 고려해보세요:

`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와 같은 자동화된 프로세스에서 사용될 때는 tie-breaker 열을 사용하는 것이 좋습니다. tie-breaker 열이 없을 경우에는 행의 순서가 변경될 수 있으며(데이터가 다시 가져와질 때), 변경 사항을 확인하는 통합이 실패할 수 있고, 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 절의 열과 일치해야 합니다.

결합된 테이블 열을 통한 정렬

대부분의 경우, 우리는 결합된 데이터베이스 테이블의 열을 기준으로 데이터를 정렬하고 싶어합니다. 다음 예시는 issues 레코드를 first_mentioned_in_commit_at 메트릭 열로 정렬하는 것을 보여줍니다:

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 필터와 일치하는 모든 issues 레코드를 찾은 뒤 모든 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)

그룹별

유감스럽게도 그룹 수준에서의 정렬 및 페이지네이션에 효율적인 방법은 존재하지 않습니다. 데이터베이스 질의 실행 시간이 그룹 내 레코드 수에 따라 증가합니다.

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

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

예시: 그룹 내의 이슈 디렉터리

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 테이블에서 이슈를 기밀로 표시하는 boolean 필드(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
데이터베이스는 행 수 및 이러한 쿼리를 실행하는 데 드는 비용을 추정합니다.
데이터베이스는 먼저 가장 저렴한 쿼리를 실행합니다.
쿼리 결과를 사용하여 다른 테이블에서 행을로드하고, 행을 더 필터링합니다.

이 특별한 예에서는 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 레코드 수가 수백만 개인 경우, 이 조인 쿼리는 잘 작동하지 않으며, 아마도 타임아웃될 것입니다.

문제 해결에 대한 쉬운 방법이 없습니다. 데이터의 비정규화는 크게 도움이 될 수 있지만, 부정적인 영향도 있습니다(데이터 중복 및 데이터 업데이트 유지).

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 "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에서 이러한 종류의 비정규화를 수행하지 않습니다.

페이지네이션 성능 지침

Tie-breaker column

결합된 테이블 열을 통한 정렬

필터링

프로젝트별

그룹별

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

특별한 경우: 기밀 플래그

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

도움말

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

도움받기