이 문서는 페이지네이션(정렬) 성능을 개선하는 몇 가지 방법을 소개합니다. 여기 나오는 내용은 오프셋 페이지네이션과 키셋 페이지네이션에 모두 적용됩니다.

타이브레이커 칼럼#

칼럼을 기준으로 정렬할 때는 값이 서로 다른 칼럼만 사용하기를 권장합니다. 다음 예시를 살펴봅니다.

created_at으로 정렬하면 결과는 레코드가 디스크에 어떻게 배치되어 있는지에 따라 달라질 가능성이 큽니다.

데이터가 잘 정의된 인터페이스로 노출되고 API처럼 자동화된 프로세스가 그 데이터를 소비한다면 타이브레이커 칼럼 사용을 권장합니다. 타이브레이커 칼럼이 없으면 행의 순서가 바뀔 수 있고(데이터 재임포트), 그 결과 디버깅하기 어려운 다음과 같은 문제가 생길 수 있습니다.

• 행을 비교해 변경 사항을 판단하는 통합이 동작하지 않습니다.
• E-tag 캐시 값이 바뀌어 전체를 다시 내려받아야 합니다.

SELECT issues.* FROM issues ORDER BY created_at;

ORDER BY에 두 번째 칼럼을 추가하면 이 문제를 해결할 수 있습니다.

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

이렇게 바꾸면 순서가 유일해지므로 "안정적인" 정렬이 됩니다.

증분 정렬#

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

조인된 테이블 칼럼으로 정렬#

조인한 데이터베이스 테이블의 칼럼으로 데이터를 정렬해야 할 때가 많습니다. 다음 예시는 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 필터에 맞는 모든 이슈를 찾은 다음 모든 issue_metrics 행을 조인합니다. 행 정렬은 메모리에서 이루어집니다. 조인 대상 관계가 항상 존재하면(1:1 관계) 데이터베이스는 N * 2 개 행을 읽으며, 여기서 N은 project_id 필터에 맞는 행 수입니다.

성능을 위해 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

필터링#

프로젝트별#

프로젝트 수준 기능이 많기 때문에 프로젝트로 필터링하는 것은 매우 흔한 사례입니다. 머지 리퀘스트, 이슈, 보드, 이터레이션이 그 예입니다.

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

그룹별#

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

그룹 수준이 사실상 그룹과 그 하위 그룹을 뜻하면 상황은 더 나빠집니다. 첫 페이지를 불러오려면 데이터베이스가 그룹 계층을 조회하고, 모든 프로젝트를 찾은 다음, 모든 이슈를 조회합니다.

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

예시: 그룹의 이슈 목록 조회

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

데이터베이스 실행 계획 예시(단순화)는 다음과 같습니다.

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. 그 쿼리 결과를 사용해 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 레코드가 매우 많은 사용자 때문에 이 조인 쿼리의 성능이 나빠지고 타임아웃이 날 수 있습니다.

두 번째 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 필터를 제거하는 식입니다.