오프셋 페이지네이션 최적화

많은 REST API 엔드포인트에서, 결과를 페이지별로 나열하기 위해 page URL 매개변수를 사용하는 오프셋 기반 페이지네이션을 사용합니다. 오프셋 페이지네이션은 페이지 번호가 높아질수록 데이터베이스 쿼리가 더 느려진다는 점에서 선형적으로 확장됩니다. 이는 큰 페이지 번호에서 데이터베이스 쿼리가 타임아웃될 수 있다는 것을 의미합니다. 일반적으로 사용자가 고의적으로 높은 페이지 번호를 방문하는 일은 드뭅니다.

오프셋 페이지네이션과 관련된 확장성 문제를 다루는 이상적인 방법은 키셋 페이지네이션으로 전환하는 것인데, 이는 API 변경이 필요합니다. 임시 방편으로는 Gitlab::Pagination::Offset::PaginationWithIndexOnlyScan 클래스를 사용할 수 있습니다. 이 최적화는 높은 OFFSET 값이 있는 오프셋 페이지네이션 쿼리의 성능을 향상시킬 수 있습니다. 이 성능 향상은 쿼리 시간을 개선하여 쿼리가 선형적으로 확장되지만, 데이터베이스 타임아웃이 발생하더라도 훨씬 더 높은 page 번호에서 발생하게 됨을 의미합니다.

최적화 사용 요구사항

최적화는 ORDER BY, OFFSET, 및 LIMIT 절을 기반으로 레코드를 결정할 때 SELECT *을 호출하지 않고 인덱스 전용 스캔을 사용하려는 것으로, 키셋 페이지네이션에 필요한 요구사항과 동일하게 충족해야 합니다:

  • ORDER BY 절이 존재합니다.
  • ORDER BY 절이 하나의 데이터베이스 열을 고유하게 식별합니다.
    • 좋음, 기본 키 사용: ORDER BY id
    • 나쁨, created_at이 고유하지 않음: ORDER BY created_at
    • 좋음, 충돌 해결자가 존재함: ORDER BY created_at, id
  • 쿼리가 데이터베이스 인덱스로 완전히 커버됨.

최적화 클래스 사용 방법

최적화 클래스는 ActiveRecord::Relation 객체와 함께 사용할 수 있으며, 결과적으로 최적화된 kaminari-페이지네이션ActiveRecord::Relation 객체를 반환합니다. 최적화가 적용되지 않을 경우, 페이지네이션에는 원래의 ActiveRecord::Relation 객체가 사용됩니다.

기본 사용법: 

scope = Issue.where(project_id: 1).order(:id)
records = Gitlab::Pagination::Offset::PaginationWithIndexOnlyScan.new(scope: scope, page: 5, per_page: 100).paginate_with_kaminari
puts records.to_a

최적화는 항상 특성 플래그와 함께 롤아웃되어야 하며, 특정 조건이 충족될 때 최적화 사용을 대상으로 할 수도 있습니다. 

# - 큰 페이지 번호 조회에만 최적화 적용
# - label_names 필터 매개변수가 제공될 때는 최적화가 적용되지 않음 (복잡한 JOIN).
if params[:page] > 100 && params[:label_names].blank? && Feature.enabled?(:my_optimized_offet_query)
  Gitlab::Pagination::Offset::PaginationWithIndexOnlyScan.new(scope: scope, page: params[:page], per_page: params[:per_page]).paginate_with_kaminari
else
  scope.page(params[:page]).per(params[:per_page])
end

최적화 동작 방식

최적화는 전달된 ActiveRecord::Relation 객체를 가져와 CTE로 이동시킵니다. CTE 내에서 원본 쿼리가 변경되어 ORDER BY 열만을 선택하도록 합니다. 이로써 데이터베이스가 인덱스 전용 스캔을 사용할 수 있게 됩니다.

쿼리가 실행되면 CTE 내의 쿼리가 먼저 계산되며, CTE에는 선택된 열을 갖는 LIMIT 개수의 행이 포함됩니다. ORDER BY 값을 사용하여 LATERAL 쿼리가 한 번에 한 행씩 전체 행을 찾습니다. 여기서 LATERAL 쿼리는 중첩 루프를 강제하기 위해 사용됩니다: CTE의 각 행에 대해 테이블에서 전체 행을 찾아냅니다.

원본 쿼리:

  • 인덱스에서 OFFSET + LIMIT 개수의 항목을 읽음.
  • 테이블에서 OFFSET + LIMIT 개수의 행을 읽음.

최적화된 쿼리:

  • 인덱스에서 OFFSET + LIMIT 개수의 항목을 읽음.
  • 테이블에서 LIMIT 개수의 행을 읽음.

최적화가 도움이 되는지 확인

높은(100,000) OFFSET 값으로 데이터베이스 쿼리에 EXPLAIN (buffers, analyze)를 실행하여 최적화가 도움이 되는지 명확히 확인할 수 있습니다.

다음 사항을 찾아봅니다:

  • 최적화된 쿼리 계획은 인덱스 전용 스캔 노드를 가져야 합니다.
  • 캐시된 버퍼 수와 타이밍을 비교하여 더 낮아야 합니다.
    • 동일한 쿼리를 2번 또는 3번 실행하여 확인할 수 있습니다.

다음과 같은 쿼리를 고려해봅니다: 

SELECT issues.*
FROM issues
ORDER BY id
OFFSET 100000
LIMIT 100

인덱스 스캔을 사용하는 실행 계획을 생성합니다: 

 Limit  (cost=27800.96..27828.77 rows=100 width=1491) (actual time=138.305..138.470 rows=100 loops=1)
   Buffers: shared hit=73212
   I/O Timings: read=0.000 write=0.000
   ->  Index Scan using issues_pkey on public.issues  (cost=0.57..26077453.90 rows=93802448 width=1491) (actual time=0.063..133.688 rows=100100 loops=1)
         Buffers: shared hit=73212
         I/O Timings: read=0.000 write=0.000

 
Time: 143.779 ms
  - planning: 5.222 ms
  - execution: 138.557 ms
    - I/O read: 0.000 ms
    - I/O write: 0.000 ms

Shared buffers:
  - hits: 73212 (~572.00 MiB) from the buffer pool
  - reads: 0 from the OS file cache, including disk I/O
  - dirtied: 0
  - writes: 0

최적화된 쿼리: 

WITH index_only_scan_pagination_cte AS MATERIALIZED
  (SELECT id
   FROM issues
   ORDER BY id ASC
   LIMIT 100
   OFFSET 100000)
SELECT issues.*
FROM
  (SELECT id
   FROM index_only_scan_pagination_cte) index_only_scan_subquery,
     LATERAL
  (SELECT issues.*
   FROM issues
   WHERE issues.id = index_only_scan_subquery.id
   LIMIT 1) issues

실행 계획: 

 Nested Loop  (cost=2453.51..2815.44 rows=100 width=1491) (actual time=23.614..23.973 rows=100 loops=1)
   Buffers: shared hit=56167
   I/O Timings: read=0.000 write=0.000
   CTE index_only_scan_pagination_cte
     ->  Limit  (cost=2450.49..2452.94 rows=100 width=4) (actual time=23.590..23.621 rows=100 loops=1)
           Buffers: shared hit=55667
           I/O Timings: read=0.000 write=0.000
           ->  Index Only Scan using issues_pkey on public.issues issues_1  (cost=0.57..2298090.72 rows=93802448 width=4) (actual time=0.070..20.412 rows=100100 loops=1)
                 Heap Fetches: 1063
                 Buffers: shared hit=55667
                 I/O Timings: read=0.000 write=0.000
   ->  CTE Scan on index_only_scan_pagination_cte  (cost=0.00..2.00 rows=100 width=4) (actual time=23.593..23.641 rows=100 loops=1)
         Buffers: shared hit=55667
         I/O Timings: read=0.000 write=0.000
   ->  Limit  (cost=0.57..3.58 rows=1 width=1491) (actual time=0.003..0.003 rows=1 loops=100)
         Buffers: shared hit=500
         I/O Timings: read=0.000 write=0.000
         ->  Index Scan using issues_pkey on public.issues  (cost=0.57..3.58 rows=1 width=1491) (actual time=0.003..0.003 rows=1 loops=100)
               Index Cond: (issues.id = index_only_scan_pagination_cte.id)
               Buffers: shared hit=500
               I/O Timings: read=0.000 write=0.000


Time: 29.562 ms
  - planning: 5.506 ms
  - execution: 24.056 ms
    - I/O read: 0.000 ms
    - I/O write: 0.000 ms

Shared buffers:
  - hits: 56167 (~438.80 MiB) from the buffer pool
  - reads: 0 from the OS file cache, including disk I/O
  - dirtied: 0
  - writes: 0