InfoGrab DocsInfoGrab Docs

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

요약

다음 문서는 페이지네이션(정렬) 성능을 개선하기 위한 몇 가지 아이디어를 제공합니다. 칼럼을 정렬할 때는 고유한 칼럼만으로 정렬하는 것이 좋습니다. created_at으로 정렬하면, 결과는 레코드가 디스크에 저장된 위치에 따라 달라질 수 있습니다.

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

타이브레이커 칼럼#

칼럼을 정렬할 때는 고유한 칼럼만으로 정렬하는 것이 좋습니다. 다음 예제를 살펴보세요:

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에서 증분 정렬(incremental sorting)이 추가되었으며, 이를 통해 인덱스를 추가하거나 교체하지 않고도 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 테이블의 모든 행을 처리하도록 강제할 수 있어 쿼리 성능이 더 나빠질 수 있습니다.

이 문제를 해결하는 한 가지 아이디어는 비정규화(denormalization)입니다. 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)

# order by internal 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)

# order by internal 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)

쿼리는 먼저 user_id(user_id = 4156052)로 필터링된 assignees를 조회하여 215개의 행을 찾습니다. 이 215개의 행을 사용하여 데이터베이스는 기본 키를 통해 215개의 연관된 이슈 행을 조회합니다. project_id 칼럼의 필터는 인덱스로 지원되지 않음을 유의하세요.

대부분의 경우 조인된 관계는 너무 많은 행을 반환하지 않으며, 적은 수의 행에 액세스하는 상대적으로 효율적인 데이터베이스 쿼리로 끝납니다. 데이터베이스가 커질수록 이 쿼리들은 다르게 동작할 수 있습니다. 예를 들어, issue_assignees 레코드 수가 매우 많은 사용자의 경우 이 조인 쿼리가 성능이 저하되고 타임아웃이 발생할 수 있습니다.

비슷한 문제로 2번째 JOIN 쿼리에 필터가 있는 이중 조인이 있을 수 있습니다. 예시: Issue -> LabelLink -> Label(name=bug).

이러한 문제를 해결하는 쉬운 방법은 없습니다. 데이터 비정규화가 상당한 도움이 될 수 있지만, 부정적인 효과(데이터 중복 및 데이터 최신 상태 유지)도 있습니다.

issue_assignees 필터 개선을 위한 아이디어:

JOIN을 수행할 때 추가 project_id 필터로 행을 추가로 필터링할 수 있도록 issue_assignees 테이블에 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에서는 이런 종류의 비정규화를 수행하지 않고 있습니다.

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

GitLab v19.1
원문 보기
요약

다음 문서는 페이지네이션(정렬) 성능을 개선하기 위한 몇 가지 아이디어를 제공합니다. 칼럼을 정렬할 때는 고유한 칼럼만으로 정렬하는 것이 좋습니다. created_at으로 정렬하면, 결과는 레코드가 디스크에 저장된 위치에 따라 달라질 수 있습니다.

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

타이브레이커 칼럼#

칼럼을 정렬할 때는 고유한 칼럼만으로 정렬하는 것이 좋습니다. 다음 예제를 살펴보세요:

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에서 증분 정렬(incremental sorting)이 추가되었으며, 이를 통해 인덱스를 추가하거나 교체하지 않고도 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 테이블의 모든 행을 처리하도록 강제할 수 있어 쿼리 성능이 더 나빠질 수 있습니다.

이 문제를 해결하는 한 가지 아이디어는 비정규화(denormalization)입니다. 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)

# order by internal 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)

# order by internal 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)

쿼리는 먼저 user_id(user_id = 4156052)로 필터링된 assignees를 조회하여 215개의 행을 찾습니다. 이 215개의 행을 사용하여 데이터베이스는 기본 키를 통해 215개의 연관된 이슈 행을 조회합니다. project_id 칼럼의 필터는 인덱스로 지원되지 않음을 유의하세요.

대부분의 경우 조인된 관계는 너무 많은 행을 반환하지 않으며, 적은 수의 행에 액세스하는 상대적으로 효율적인 데이터베이스 쿼리로 끝납니다. 데이터베이스가 커질수록 이 쿼리들은 다르게 동작할 수 있습니다. 예를 들어, issue_assignees 레코드 수가 매우 많은 사용자의 경우 이 조인 쿼리가 성능이 저하되고 타임아웃이 발생할 수 있습니다.

비슷한 문제로 2번째 JOIN 쿼리에 필터가 있는 이중 조인이 있을 수 있습니다. 예시: Issue -> LabelLink -> Label(name=bug).

이러한 문제를 해결하는 쉬운 방법은 없습니다. 데이터 비정규화가 상당한 도움이 될 수 있지만, 부정적인 효과(데이터 중복 및 데이터 최신 상태 유지)도 있습니다.

issue_assignees 필터 개선을 위한 아이디어:

JOIN을 수행할 때 추가 project_id 필터로 행을 추가로 필터링할 수 있도록 issue_assignees 테이블에 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에서는 이런 종류의 비정규화를 수행하지 않고 있습니다.