페이지 네이션

크게 세가지 방법이 있음

• Offset
• 커서
• Keyset

Offset 페이지네이션

방식 : LIMIT와 OFFSET SQL 구문을 사용하여 특정 페이지 번호를 지정해 데이터를 가져옴.
특징 : 구현이 간단, 사용자가 특정 페이지로 직접 이동하는 UI에 적합함
단점 : 뒤로 갈수록 이전 행들을 모두 읽고 버려야하므로, 데이터가 많아질수록 성능이 떨어짐 (O(N))

작동 원리

• LIMIT : 한 페이지에 보여줄 데이터의 개수
• OFFSET : 건너뛸 데이터의 개수 ((페이지 번호 - 1 ) * 페이지당 개수)
• 프론트는 페이지 번호만 넘겨주면 됨
• 백엔드 역시 직접 계산하지 않고 Pageable객체에 페이지 번호만 넘겨주면 알아서 OFFSET쿼리를 생성해줌

  Ex. 5페이지를 조회 (페이지당 10개 조회)

SELECT * FROM posts
ORDER BY created_at DESC
LIMIT 10 OFFSET 40;

장점

• 임의 접근 가능 : 사용자가 1페이지에서 10페이지로 바로 이동하는 경우 쉬움
• 구현 단순성 : 백엔드와 프론트엔드 모두 추가적인 로직 없이 정수값만 주고받으면 됨
• 전체 페이지 수 계산 용이: count(*) 쿼리를 통해 전체 페이지가 총 몇 개인지 사용자에게 쉽게 보여줄 수 있음

단점

• 성능 저하
  : 뒤쪽 페이지로 갈수록 DB는 앞의 데이터를 읽고 버리는 작업을 반복해야함. 만약 OFFSET 1,000,000이라면 엔진은 100만개의 행을 메모리에 올리고 정렬한 뒤 버림. I/O 부하와 CPU 소모를 급격히 증가시킴
• 데이터 불일치
  : 사용자가 1페이지를 보는 동안 새로운 데이터가 삽입되면 2페이지로 넘어갔을 때 1페이지에서 봤던 마지막 데이터가 2페이지의 첫 번째 데이터로 중복 노출되는 현상 발생. 반대로 삭제가 일어나면 데이터를 건너띄게됨

질문

• Offset 방식에서 인덱스가 있는 컬럼(예: PK인 id)으로 정렬하더라도, 뒤쪽 페이지로 갈수록 성능이 느려지는 근본적인 이유는 무엇일까요? (힌트: 인덱스 엔트리만 읽는 것과 실제 데이터 블록에 접근하는 것의 차이)
  => DB엔진이 특정 행의 물리적 위치를 즉시 알 수 없어 앞선 데이터를 전부 읽고 숫자를 세며 지나가야 함

1. 배열과 다른 구조 : 메모리 상의 배열은 인덱스로 즉시 접근 가능하지만, DB의 데이터는 디스크 블록에 흩어져있음. 100만번째를 찾으려면 1번부터 100만번까지 순차적으로 스캔해야함
2. 불필요한 I/O 발생 : OFFSET 1,000,000인 경우, DB는 실제로 쓰지도 않을 100만개의 행을 디스크에서 읽어 메모리로 올림. 이 과정에서 엄청난 디스크 I/O와 CPU 자원이 낭비됨
3. 인덱스의 한계 : 인덱스가 정렬은 도와주지만, "몇 번째 데이터가 어디에 있는지"에 대한 지도는 없음. 따라서 인덱스 리프 노드를 하나하나 따라가며 개수를 세는 작업은 피할 수 없음.

• Offset 방식의 성능 문제를 해결하기 위해, 인덱스만으로 Offset을 처리하여 PK만 뽑아낸 뒤, 그 PK들로만 다시 본문을 조회하는 최적화 기법을 '커버링 인덱스(Covering Index)'를 활용한다고 합니다. 이 방식이 왜 성능을 개선할 수 있을까요? (힌트: 데이터 블록 접근 여부)
  : 불필요한 데이터 블록 접근을 차단하여 디스크 I/O를 획기적으로 줄이기 때문.

1. 일반 Offset 방식의 한계
   : 일반적인 SELECT * ... LIMIT 10 OFFSET 100000 쿼리는 아래와 같이 동작
   a. 인덱스 탐색 : 정렬 기준에 맞는 인덱스를 찾음

   어떤 인덱스를 말하는 것인가?
   PK 인덱스: 가장 흔하게 ORDER BY id DESC를 사용하는데, 이때는 기본 키(Primary Key)에 자동으로 생성된 인덱스를 사용합니다.
   보조 인덱스(Secondary Index): 만약 ORDER BY created_at처럼 생성일순으로 정렬한다면, 개발자가 성능을 위해 해당 컬럼에 직접 생성해둔 인덱스를 의미합니다.

   b. 데이터 블록 접근 : 인덱스에 없는 나머지 컬럼 데이터(제목, 내용 등)를 읽기 위해 매번 디스크의 실제 데이터 블록에 접근함
   c. 버림 : 100만개를 다 읽어온 뒤, 100만개를 버림 (가장 비효율)
   
   
2. 커버링 인덱스 최적화의 원리
   : 커버링 인덱스란 쿼리에 필요한 모든 컬럼이 인덱스에 이미 포함되어있는 상태

a. 인덱스만 스캔 : SELECT id와 같이 인덱스에 포함된 컬럼만 사용하여 100만개를 건너 띔. 이때 DB는 실제 데이터 블록에 가지 않고 가벼운 인덱스 파일만 읽음

여기서 질문!
그럼 정렬부터 시켜야하지 않나?
-> 1. 대부분 B-Tree 구조로 인덱스를 관리함. 따라서 정렬된 상태를 유지함. 데이터가 삽입/수정될 때마다 DB는 인덱스 트리 내에서 정렬 순서에 맞는 위치를 찾아 삽입함.
2. 리프 노드의 연결 : 인덱스의 가장 아래층은 데이터들이 정렬된 상태로 양방향 연결 시트르 형태로 연결되어있음.
3. 결과 : ORDER BY createdAt쿼리가 들어오면, DB는 정렬 알고리즘을 돌리는게 아니라 인덱스 리프 노드의 시작점부터 필요한 개수만큼 순서대로 따라가며 읽기만 함
즉, createdAt을 인덱싱하면 알아서 됨~

b. 최소한의 접근 : 결과로 확정된 10개의 PK(Id)에 대해서만 실제 데이터 블록에 접근하여 전체 컬럼을 가져옴

< 요약 >
일빈 방식은 1,000,010 번의 데이터 블록 접근 발생
최적화 방식은 1,000,000 번의 가벼운 인덱스 스캔 + 10번의 데이터 블록 접근
즉, 정렬 비용은 사라지지만 읽고 버리는 행위자체는 여전히 O(N)의 비용이 듬. 단지 불필요한 데이터 블록 접근(I/O)를 최소화 하는 것에 의의가 있음 (게시글,작성자,내용 등을 같이 불러오는 비효율을 말하는 것)

커서 기반

방식 : 마지막으로 조회한 데이터의 식별자를 커서로 삼아 그 다음 데이터를 조회함
특정 : 대용량 데이터에서도 인덱스를 활용해 일정한 성능 O(1) 또는 O(logN) 보장
한계 : 3페이지로 바로가기 같은 임의 접근이 불가능하며 무한 스크롤이나 더보기 버튼 형태에 주로 쓰임

작동 원리

: 사용자가 마지막으로 본 데이터의 고유한 값을 커서로 삼아, 그 다음 데이터를 조회함

SELECT * FROM posts 
WHERE id < [마지막_조회_ID] 
ORDER BY id DESC 
LIMIT 10;

ID 기준 내림차순으로 최대 10개까지 조회를 함. 무한 스크롤에 최적
커서는 값을 기준으로 점프함.
offset : 100번째 데이터를 줘 (20개씩 1페이지일 때 5페이지 누르면됨)
=> 앞에서부터 N개를 건너뛰고 다음걸 보여줌
cursur : 100번째 데이터를 주라고 못함. 대신 ID가 550번인 데이터 다음부터 10개 줘 라고 가능
=> 이 값보다 큰 것 중 가장 가까운걸 보여줘

왜 무한스크롤에 적합한가?

무한 스크롤은 사용자가 데이터를 순차적으로 소비함

1. 첫 10개를 본다. (마지막 데이터 ID를 기억함)
2. 다음 10개를 요청할 때 그 ID(커서)를 넘겨준다.
3. DB는 그 ID 위치로 점프해서 다음 10개를 가져온다.
   즉, 사용자는 직전의 좌표를 항상 가지고 있기에 "특정 조건"에 해당되어 관련된 데이터로 바로 점프할 수 있기 때문임

질문

1. "무한 스크롤 서비스에서 커서 방식을 사용 중인데, 사용자가 특정 게시물을 보고 '뒤로 가기'를 눌렀을 때 이전에 보던 스크롤 위치(데이터 리스트)를 그대로 유지하려면 기술적으로 어떤 처리가 필요할까요?"
   : 프론트에서 지금까지 불러온 데이터 리스트와 마지막 커서 위치를 캐싱해야함

2. 개념을 잘 이해하셨다면, 기술 면접 단골 질문을 드리겠습니다.
   "커서 기반 페이지네이션을 구현할 때, 정렬 기준이 되는 컬럼(예: 생성일시 created_at)에 인덱스가 걸려 있지 않다면 성능상 어떤 문제가 발생할까요? 이 경우에도 OFFSET 방식보다 빠를까요?"
   :
   a. FULL SCAN : WHERE createdAt > '' 으로 하나하나 다 찾음
   b. 정렬 부하 : 인덱스는 이미 정렬된 상태를 유지하지만, 인덱스가 없으면 DB는 매 요청마다 메모리나 디스크에서 데이터를 다시 정렬해야함. (문제에서 정렬 기준이 되는 컬럼에 인덱스만 없다는 조건이니까)

3. "커서 기반 페이지네이션을 사용 중인데, 사용자가 리스트 중간에 있는 게시물을 삭제하고 다시 리스트로 돌아왔을 때, 캐싱된 데이터와 서버 데이터 사이의 '데이터 정합성' 문제를 어떻게 해결하는 것이 가장 효율적일까요?"
   a. 로컬 캐시 업데이트
   -> 서버에서 삭제 성공 응답을 받는 즉시, 프론트 메모리에 저장된 데이터 리스트에서 해당 게시물의 ID를 찾아 삭제
   -> 장점 : 추가적인 API 호출 없이 UI를 즉시 갱신할 수 있어 사용자 경험UX가 가장 뛰어남

b. 쿼리 무효화
-> 사용자가 리스트로 돌아왔을 때 해당 리스트 API를 다시 호출하도록 설정
-> 장점 : 구현이 단순, 그 사이 다른 사용자에 의해 변경된 데이터까지 모두 반영된 최신 상태를 보장함
-> 커서 기반 페이지네이션에서 첫 페이지부터 다시 불러와야 하므로 데이터 소모와 서버 부하가 발생할 수 있음.

Keyset

커서 방식의 일종이지만, 정렬 조건이 복잡할 때(생성일순 등) 여러 컬럼을 조합한 키셋을 사용하여 다음 페이지를 결정하는 방식