데이터베이스 페이지네이션의 안정성: 중복과 누락을 방지하는 정렬의 원리

현대 웹 애플리케이션과 모바일 앱에서 대규모 데이터셋을 사용자에게 효율적으로 보여주는 기술인 페이지네이션(Pagination)은 필수적입니다. 게시판 목록, 상품 리스트, 검색 결과 등 수많은 데이터를 한 번에 로드하는 대신, 페이지 단위로 나누어 제공함으로써 초기 로딩 속도를 개선하고 사용자 경험을 향상시킬 수 있습니다. 가장 보편적인 페이지네이션 구현은 SQL의 LIMIT와 OFFSET을 사용하는 것입니다. 하지만 이 방식은 간단해 보이는 외관과 달리, 특정 조건에서 데이터가 중복되거나 누락되는 심각한 문제를 야기할 수 있습니다. 이 글에서는 이러한 문제가 왜 발생하는지 근본적인 원인을 파헤치고, 안정적인 페이지네이션을 구현하기 위한 결정적 정렬(Deterministic Sort)의 중요성과 더 나아가 성능까지 고려한 커서 기반 페이지네이션(Cursor-based Pagination)까지 심도 있게 탐구합니다.

페이지네이션의 함정: 데이터 중복 현상의 재현

문제 상황을 명확하게 이해하기 위해, 가상의 게시판 애플리케이션을 예로 들어보겠습니다. ARTICLE이라는 테이블이 있으며, 구조는 다음과 같습니다.

CREATE TABLE ARTICLE (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    title VARCHAR(255) NOT NULL,
    content TEXT,
    posted DATETIME NOT NULL
);

이 테이블에는 여러 게시물이 저장되어 있으며, 최신순으로 목록을 보여주고자 합니다. 한 페이지에 5개의 게시물을 보여주기로 결정하고, 두 번째 페이지의 데이터를 가져오기 위해 다음과 같은 쿼리를 작성했습니다.

-- 두 번째 페이지 데이터 조회 (페이지당 5개)
SELECT * FROM ARTICLE
ORDER BY posted DESC
LIMIT 5, 5; -- OFFSET 5, LIMIT 5

대부분의 경우 이 쿼리는 정상적으로 작동하는 것처럼 보입니다. 하지만 사용자가 몰리거나, 시스템이 자동으로 콘텐츠를 생성하여 'posted' 시간이 정확히 동일한 데이터가 다수 존재하는 순간, 문제는 수면 위로 드러납니다. 아래와 같은 데이터가 있다고 가정해 보겠습니다.

id	title	posted
15	게시물 O	2023-10-27 15:00:00
14	게시물 N	2023-10-27 14:00:00
13	게시물 M	2023-10-27 13:00:00
12	게시물 L	2023-10-27 12:00:00
11	게시물 K	2023-10-27 12:00:00
10	게시물 J	2023-10-27 12:00:00
9	게시물 I	2023-10-27 11:00:00
8	게시물 H	2023-10-27 10:00:00
7	게시물 G	2023-10-27 10:00:00
6	게시물 F	2023-10-27 09:00:00
5	게시물 E	2023-10-27 09:00:00
4	게시물 D	2023-10-27 08:00:00
3	게시물 C	2023-10-27 07:00:00
2	게시물 B	2023-10-27 06:00:00
1	게시물 A	2023-10-27 05:00:00

id 10, 11, 12번 게시물은 `posted` 시간이 `2023-10-27 12:00:00`으로 동일합니다. 이 상태에서 첫 번째 페이지를 조회해 보겠습니다.

-- 첫 번째 페이지 데이터 조회 (LIMIT 0, 5)
SELECT id, title, posted FROM ARTICLE
ORDER BY posted DESC
LIMIT 0, 5;

데이터베이스는 다음과 같은 결과를 반환할 수 있습니다.

[첫 번째 페이지 조회 결과]

• (15, '게시물 O', '2023-10-27 15:00:00')
• (14, '게시물 N', '2023-10-27 14:00:00')
• (13, '게시물 M', '2023-10-27 13:00:00')
• (12, '게시물 L', '2023-10-27 12:00:00')
• (11, '게시물 K', '2023-10-27 12:00:00')

이제 사용자가 '다음' 버튼을 눌러 두 번째 페이지를 요청합니다. 서버는 동일한 정렬 기준으로 OFFSET만 변경하여 쿼리를 실행합니다.

-- 두 번째 페이지 데이터 조회 (LIMIT 5, 5)
SELECT id, title, posted FROM ARTICLE
ORDER BY posted DESC
LIMIT 5, 5;

여기서 문제가 발생합니다. 데이터베이스는 `posted`가 동일한 (12, 11, 10)번 게시물들의 내부 순서를 보장하지 않기 때문에, 쿼리가 실행되는 시점의 내부 상태에 따라 다음과 같은 결과를 반환할 수 있습니다.

[두 번째 페이지 조회 결과 (문제 발생)]

• (11, '게시물 K', '2023-10-27 12:00:00') <-- 첫 페이지에서 봤던 데이터 중복!
• (10, '게시물 J', '2023-10-27 12:00:00')
• (9, '게시물 I', '2023-10-27 11:00:00')
• (8, '게시물 H', '2023-10-27 10:00:00')
• (7, '게시물 G', '2023-10-27 10:00:00')

결과적으로 사용자에게는 '게시물 K'(id: 11)가 중복으로 노출됩니다. 더 심각한 것은, 첫 페이지에서 `(12, 11)` 순서로 나왔던 데이터가 정렬 과정에서 `(11, 10)` 순서로 바뀌면서 '게시물 L'(id: 12)은 두 번째 페이지에서 누락되어 버렸습니다. 이처럼 데이터의 중복 및 누락은 애플리케이션의 신뢰도를 떨어뜨리는 치명적인 버그입니다.

문제의 근원: 비결정적 정렬(Non-deterministic Sort)

이 문제의 핵심 원인은 '비결정적 정렬'에 있습니다. SQL 표준은 ORDER BY 절에 명시된 컬럼들의 값이 동일할 경우, 그 로우(row)들의 상대적인 순서를 보장하지 않습니다. 이를 '불안정 정렬(Unstable Sort)'이라고도 부릅니다.

데이터베이스 관리 시스템(DBMS)의 쿼리 옵티마이저는 주어진 쿼리를 가장 효율적으로 실행할 수 있는 계획(Execution Plan)을 수립합니다. `ORDER BY posted DESC`라는 요청에 대해, 옵티마이저는 `posted` 컬럼을 기준으로 내림차순 정렬을 수행합니다. 하지만 `posted` 값이 같은 `2023-10-27 12:00:00`인 데이터 그룹(id: 12, 11, 10)을 만나면, 이 그룹 내에서의 순서는 어떻게 되든 상관없습니다. 왜냐하면 쿼리가 요구한 정렬 조건을 모두 만족하기 때문입니다.

따라서 DBMS는 성능상 가장 유리한 순서대로 데이터를 반환할 수 있습니다. 예를 들어, 첫 번째 페이지 요청 시에는 메모리 캐시에 있던 순서대로 (12, 11)을 반환하고, 두 번째 페이지 요청 시에는 다른 트랜잭션의 영향이나 내부 데이터 블록의 변경으로 인해 디스크에서 읽어온 다른 순서인 (11, 10)을 반환할 수 있는 것입니다. 이처럼 쿼리를 실행할 때마다 결과의 순서가 달라질 가능성이 있는 정렬을 '비결정적'이라고 하며, 이는 페이지네이션의 일관성을 깨뜨리는 주범입니다.

해결책 1: 결정적 정렬을 통한 안정성 확보

이 문제를 해결하는 방법은 간단하고 명확합니다. 정렬 순서가 항상 동일하게 유지되도록 '결정적 정렬(Deterministic Sort)'을 만드는 것입니다. 즉, ORDER BY 절에 명시된 컬럼들의 값 조합이 모든 로우에 대해 고유(Unique)하도록 만들어, 어떤 상황에서 쿼리를 실행하더라도 항상 동일한 순서의 결과를 반환하게 보장하는 것입니다.

가장 좋은 방법은 정렬 기준의 마지막에 고유한 값을 가진 컬럼, 예를 들어 **Primary Key(기본 키)**를 추가하는 것입니다. 우리의 `ARTICLE` 테이블에서는 `id` 컬럼이 그 역할을 할 수 있습니다. `id`는 `AUTO_INCREMENT` 속성을 가지므로 절대 중복되지 않습니다.

수정된 쿼리는 다음과 같습니다.

SELECT * FROM ARTICLE
ORDER BY posted DESC, id DESC;

이 쿼리는 데이터베이스에게 다음과 같이 지시합니다.

1. 1차 정렬: `posted` 컬럼을 기준으로 내림차순 정렬하라.
2. 2차 정렬 (Tie-breaker): 만약 `posted` 값이 같다면, 그 그룹 내에서는 `id` 컬럼을 기준으로 내림차순 정렬하라.

이제 `id`라는 고유한 '타이브레이커(tie-breaker)'가 생겼기 때문에, `posted`가 동일한 데이터 그룹도 `id` 값에 따라 항상 일관된 순서를 갖게 됩니다. 위 예시 데이터에서 `posted`가 `2023-10-27 12:00:00`으로 동일한 게시물들은 `id`의 내림차순인 (12, 11, 10) 순서로 항상 정렬될 것입니다.

이제 수정된 쿼리로 페이지네이션을 다시 실행해 보겠습니다.

[첫 번째 페이지 조회 - 수정된 쿼리]

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC, id DESC LIMIT 0, 5;

결과:

• (15, '게시물 O', '2023-10-27 15:00:00')
• (14, '게시물 N', '2023-10-27 14:00:00')
• (13, '게시물 M', '2023-10-27 13:00:00')
• (12, '게시물 L', '2023-10-27 12:00:00')
• (11, '게시물 K', '2023-10-27 12:00:00')

[두 번째 페이지 조회 - 수정된 쿼리]

SELECT id, title, posted FROM ARTICLE ORDER BY posted DESC, id DESC LIMIT 5, 5;

결과:

• (10, '게시물 J', '2023-10-27 12:00:00')
• (9, '게시물 I', '2023-10-27 11:00:00')
• (8, '게시물 H', '2023-10-27 10:00:00')
• (7, '게시물 G', '2023-10-27 10:00:00')
• (6, '게시물 F', '2023-10-27 09:00:00')

보시다시피, 이제 데이터의 중복이나 누락 없이 정확하게 다음 페이지의 내용이 조회됩니다. 이는 쿼리의 정렬 순서가 '결정적'이 되었기 때문입니다. SQLite와 같은 일부 데이터베이스에서는 테이블에 명시적인 Primary Key가 없어도 내부적으로 `ROWID`라는 고유한 식별자를 가집니다. 이 경우 `ORDER BY posted DESC, ROWID DESC`와 같이 `ROWID`를 타이브레이커로 사용할 수도 있습니다.

페이지네이션 구현 방식의 심층 분석

결정적 정렬로 데이터 무결성 문제를 해결했지만, 페이지네이션의 세계는 여기서 끝나지 않습니다. 우리가 사용한 `OFFSET` 기반 페이지네이션은 대용량 데이터 환경에서 또 다른 문제를 드러냅니다. 더 나은 대안인 커서 기반 페이지네이션과 비교하여 각 방식의 장단점을 살펴보겠습니다.

오프셋 기반 페이지네이션 (Offset-based Pagination)

LIMIT [count] OFFSET [offset] 구문은 "offset개의 로우를 건너뛰고, 그 다음부터 count개의 로우를 가져와라"는 의미입니다. 직관적이고 구현이 간단하여 널리 사용됩니다.

• 장점:
  • 구현이 매우 간단합니다. (페이지 번호 - 1) * 페이지 크기`로 `OFFSET`을 계산하면 됩니다.
  • 사용자가 특정 페이지(예: 50페이지)로 바로 이동하는 기능을 쉽게 구현할 수 있습니다.
• 단점:
  • 대규모 오프셋에서의 성능 저하: 가장 치명적인 단점입니다. `LIMIT 10 OFFSET 1000000` 쿼리를 실행하면, 데이터베이스는 1,000,010개의 로우를 정렬 순서에 따라 모두 읽은 다음, 앞의 1,000,000개를 버리고 마지막 10개만 반환합니다. `OFFSET`이 커질수록 버려야 하는 데이터가 많아져 쿼리 시간이 선형적으로 증가하며, 데이터베이스에 심각한 부하를 줍니다.
  • 실시간 데이터 변경에 취약: 페이지를 조회하는 사이에 새로운 데이터가 추가되거나 기존 데이터가 삭제되면 페이지 경계가 밀리는 현상이 발생합니다. 예를 들어, 1페이지를 본 후 새로운 게시물이 1페이지 맨 앞에 추가되면, 2페이지를 조회할 때 1페이지의 마지막 항목이 2페이지의 첫 항목으로 다시 나타나는 중복 문제가 발생할 수 있습니다. (결정적 정렬을 사용하더라도 이 문제는 발생합니다)

커서 기반 페이지네이션 (Keyset/Cursor-based Pagination)

커서 기반 페이지네이션은 '페이지 번호' 대신 '마지막으로 조회한 데이터의 특정 값'을 기준으로 다음 페이지를 조회하는 방식입니다. 주로 '더보기'나 '무한 스크롤' 기능에 사용됩니다.

핵심 아이디어는 `OFFSET`으로 건너뛰는 대신, `WHERE` 절을 사용하여 "마지막으로 본 항목보다 더 오래된(또는 새로운) 항목부터 N개를 가져와라"고 명시하는 것입니다. 이를 위해 결정적 정렬에 사용된 컬럼들을 `WHERE` 절에 활용합니다.

예를 들어, 첫 페이지에서 마지막으로 본 데이터가 `(posted: '2023-10-27 12:00:00', id: 11)`이었다면, 다음 페이지를 가져오는 쿼리는 다음과 같이 작성됩니다.

-- (posted, id)가 ('2023-10-27 12:00:00', 11) 보다 작은 다음 5개 데이터를 조회
-- MySQL, PostgreSQL 등 Row Value Constructor를 지원하는 경우
SELECT * FROM ARTICLE
WHERE (posted, id) < ('2023-10-27 12:00:00', 11)
ORDER BY posted DESC, id DESC
LIMIT 5;

-- 범용적으로 사용 가능한 쿼리
SELECT * FROM ARTICLE
WHERE posted < '2023-10-27 12:00:00' OR 
      (posted = '2023-10-27 12:00:00' AND id < 11)
ORDER BY posted DESC, id DESC
LIMIT 5;

• 장점:
  • 일관된 고성능: `OFFSET`과 달리 불필요한 데이터를 스캔하고 버리는 과정이 없습니다. 데이터베이스는 정렬 기준에 맞는 인덱스(예: `(posted, id)`)를 사용하여 `WHERE` 절의 시작점을 빠르게 찾고, 거기서부터 필요한 만큼의 데이터만 읽으면 됩니다. 따라서 페이지가 아무리 깊어져도 쿼리 성능이 거의 일정하게 유지됩니다.
  • 실시간 데이터 변경에 강함: 조회 기준이 상대적인 위치(offset)가 아닌 절대적인 데이터 값(cursor)에 고정되어 있으므로, 조회 중에 새로운 데이터가 추가되거나 삭제되어도 보고 있던 페이지의 내용이 밀리거나 중복되지 않습니다.
• 단점:
  • 구현이 오프셋 방식보다 복잡합니다. 클라이언트는 다음 페이지를 요청할 때 마지막 항목의 커서 값(여기서는 `posted`와 `id`)을 함께 보내야 합니다.
  • 특정 페이지 번호로 직접 이동하는 기능을 구현하기 어렵습니다. 전체 페이지 수를 계산하거나 특정 페이지의 시작 커서를 알아내기 어렵기 때문입니다. '다음', '이전' 방식의 탐색에 최적화되어 있습니다.

성능 최적화를 위한 인덱스의 역할

안정적인 페이지네이션을 논할 때 **인덱스(Index)**의 중요성을 빼놓을 수 없습니다. `ORDER BY`와 `WHERE` 절에 사용되는 컬럼에 적절한 인덱스가 없으면, 데이터베이스는 매 쿼리마다 테이블 전체를 스캔하고(Full Table Scan), 메모리나 디스크를 사용해 데이터를 정렬하는 비효율적인 '파일소트(Filesort)' 작업을 수행해야 합니다.

우리의 예시에서는 `ORDER BY posted DESC, id DESC`를 사용하므로, 다음과 같은 복합 인덱스(Composite Index)를 생성하는 것이 성능에 매우 중요합니다.

CREATE INDEX idx_article_posted_id ON ARTICLE (posted, id);

이 인덱스는 `posted`와 `id` 순서로 데이터의 위치 정보를 미리 정렬해 놓은 B-Tree 구조를 만듭니다. 이 인덱스가 있으면, 데이터베이스는 다음과 같은 이점을 얻습니다.

1. 정렬 비용 제거: ORDER BY posted DESC, id DESC 요청 시, 이미 정렬된 인덱스를 뒤에서부터 순차적으로 읽기만 하면 되므로 별도의 정렬 과정이 필요 없습니다.
2. 빠른 검색: 커서 기반 페이지네이션의 `WHERE (posted, id) < (?, ?)` 조건 역시 인덱스를 통해 특정 지점을 매우 빠르게 찾아낼 수 있습니다.

따라서 안정성과 성능을 모두 잡기 위해서는 결정적 정렬을 적용하고, 그 정렬 기준이 되는 컬럼들에 대해 반드시 복합 인덱스를 생성해야 합니다.

결론

단순해 보이는 데이터베이스 페이지네이션은 '비결정적 정렬'이라는 함정을 품고 있습니다. `ORDER BY` 절에 사용된 컬럼에 중복된 값이 존재할 경우, 데이터베이스는 정렬 순서를 보장하지 않으며 이는 페이지 간 데이터 중복 및 누락으로 이어질 수 있습니다. 이 문제의 해결책은 Primary Key와 같은 고유한 컬럼을 2차 정렬 기준으로 추가하여 '결정적 정렬'을 보장하는 것입니다.

나아가, 대규모 데이터를 다루는 현대적인 애플리케이션에서는 성능과 실시간 데이터 일관성을 고려하여 오프셋 기반 페이지네이션의 한계를 인지하고, 커서 기반 페이지네이션을 적극적으로 검토해야 합니다. 어떤 방식을 선택하든, 정렬과 검색 조건에 맞는 적절한 인덱스 설계는 빠른 응답 속도를 위한 필수 전제 조건입니다. 안정적인 정렬 원리를 이해하고 올바른 페이지네이션 전략을 선택하는 것은 확장 가능하고 신뢰성 높은 애플리케이션을 구축하는 핵심적인 첫걸음입니다.