• 타이브레이커 열
  • 점진적 정렬
• 조인된 테이블 열에 의한 정렬
• 필터링
  • 프로젝트별
  • 그룹별
  • 동일한 데이터베이스 테이블의 열
    • 특수한 경우: 기밀 플래그
    • 다른 데이터베이스 테이블의 열

페이지네이션 성능 지침

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

타이브레이커 열

열을 정렬할 때는 유일한 열로 정렬하는 것이 좋습니다. 다음 예를 고려해보십시오:

만약 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개의 행을 읽습니다. 데이터베이스는 20번째, 21번째 및 22번째 created_at 값을 비교하고 22번째 값이 다르다는 것을 확인하여 다음 레코드를 확인하지 않아도 되는 결론을 내립니다. 이 예시에서 20번째와 21번째 열은 동일한 created_at 값을 가졌습니다.

점진적 정렬은 중복된 값이 드물게 발생하는 타임스탬프 열과 잘 작동합니다. 따라서 열이 매우 적은 고유한 값을 가지고 있는 경우에는 점진적 정렬이 잘 작동하지 않거나 전혀 사용되지 않을 수 있습니다(예: 열거 형과 같은 경우).

예를 들어, 점진적 정렬이 비활성화된 경우, 데이터베이스는 작성자별로 모든 머지 요청 레코드를 모두 읽고 메모리 내에서 데이터를 정렬합니다.

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개의 레코드를 읽고 메모리 내에서 행을 정렬했습니다.

조인된 테이블 열에 의한 정렬

자주, 우리는 조인된 데이터베이스 테이블의 열로 데이터를 정렬하고 싶어합니다. 아래 예시는 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).

필터링

프로젝트별

프로젝트별 필터링은 프로젝트 수준의 많은 기능이 있기 때문에 매우 일반적입니다. 예: 병합 요청, 이슈, 보드, 이터레이션.

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

project = Project.find(5)

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

기본 쿼리를 효율적으로 만들기 위해, 대개 project_id 열을 포함하는 데이터베이스 인덱스가 있습니다. 이는 데이터베이스가 스캔해야 하는 행의 수를 현저하게 줄입니다. 인덱스가 없으면, 데이터베이스가 테이블 전체를 읽어야 합니다 (전체 테이블 스캔).

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 테이블에는 이슈를 기밀로 표시하는 부울 필드(confidential)가 있습니다. 이로 인해 비회원 사용자에게는 해당 이슈가 보이지 않습니다(필터링됨).

예제 SQL 쿼리:

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

프로젝트 수준 쿼리에 해당 인덱스를 추가하여 데이터베이스 쿼리를 개선하려는 유혹을 느낄 수 있지만, 이 경우 이것은 아마도 불필요할 것입니다. 테이블의 데이터 분포에 따라 기밀 이슈는 드물게 발견됩니다. 그들을 필터링하는 것은 데이터베이스 쿼리를 현저하게 느리게 만들지 않습니다. 데이터베이스는 몇 가지 추가 행을 읽을 수도 있지만, 성능 차이는 실제로 최종 사용자에게는 거의 보이지 않을 수 있습니다.

반면, 기밀 이슈만 표시하는 특별한 필터를 구현했다면, 해당 인덱스가 필요합니다. 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

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

1. 데이터베이스는 SQL 쿼리를 구문 분석하고 JOIN을 감지합니다.
2. 데이터베이스는 쿼리를 두 개의 서브쿼리로 분할합니다.
   • SELECT "issue_assignees".* FROM "issue_assignees" WHERE "issue_assignees"."user_id" = 10
   • SELECT "issues".* FROM "issues" WHERE "issues"."project_id" = 5
3. 데이터베이스는 행의 수와 이러한 쿼리를 실행하는 데 필요한 비용을 추정합니다.
4. 데이터베이스는 가장 저렴한 쿼리를 먼저 실행합니다.
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 레코드 수가 수백만 개인 경우를 가정해 봅시다. 이 조인 쿼리는 잘 작동하지 않고, 시간 초과될 가능성이 높습니다.

비슷한 문제는 2번째 JOIN 쿼리에 필터가 있는 경우입니다. 예: Issue -> 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 "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에서 이러한 형태의 비정규화를 수행하고 있지 않습니다.