24. 유일하지 않은 정렬 키의 키셋 페이지네이션: 경계 행 누락

난이도 상

내 리뷰 · C#

내 리뷰 · C++

해설 · C#

해설 — 유일하지 않은 정렬 키의 키셋 페이지네이션: 경계 행 누락

난이도: 상

요약

정렬·seek 키가 level(비유일) 하나뿐이라, 같은 레벨의 행들이 페이지 경계에 걸치면 다음 페이지가 level < @lvl (A) 로 경계 레벨을 통째로 건너뛴다. 커서를 rows[last].Level (B) 로만 잡기 때문에 경계 레벨의 남은 행들이 영구히 누락된다.

문제점

[정합성] 경계에서 동일 키 행 누락: pageSize=3, 레벨이 [50, 50, 50, 50, 40, ...] 라 하자.
- 1페이지: 앞의 50 세 개를 반환, 커서 next=50.
- 2페이지: WHERE level < 50 → 남은 네 번째 50 이 조건에서 제외되어 영영 안 나온다. 40 부터 시작. → 같은 레벨이 페이지 크기 경계에 걸친 만큼의 행이 통째로 사라진다.
[대안 오류로도 실패] <= 로 바꾸면 중복: 누락을 피하려 level <= 50 으로 바꾸면 1페이지의 50 세 개가 2페이지에 다시 나온다(무한 재조회 위험). 즉 유일 키 없이 </<= 어느 쪽도 정답이 아니다 — 근본 원인은 타이브레이커 부재다.
[근본 원인] 전순서(total order) 부재: 키셋 페이지네이션은 정렬 키가 행마다 유일해야 경계가 명확히 잘린다. level 만으로는 동률 행의 순서가 정의되지 않아 경계가 모호해진다.
재현 조건: 동일 레벨(또는 동일 점수/시각) 행이 pageSize 배수 경계에 걸칠 때. 대규모 길드·랭킹에서 흔함.

수정안

유일한 타이브레이커(예: member_id)를 정렬과 seek 조건에 함께 넣어 전순서를 만든다. 커서도 (레벨, member_id) 복합으로 들고 다닌다.

-- 첫 페이지
SELECT member_id, level FROM guild_members
WHERE guild_id = @g
ORDER BY level DESC, member_id ASC
LIMIT @n;

-- 다음 페이지: (level, member_id) 복합 seek
SELECT member_id, level FROM guild_members
WHERE guild_id = @g
  AND ( level < @lastLevel
        OR (level = @lastLevel AND member_id > @lastMemberId) )
ORDER BY level DESC, member_id ASC
LIMIT @n;

// 커서를 (Level, MemberId) 로 확장
public readonly struct Cursor { public readonly int Level; public readonly long MemberId; /* ... */ }

int? nextLevel; long? nextId;
if (rows.Count == pageSize)
{
    var last = rows[rows.Count - 1];
    nextLevel = last.Level; nextId = last.MemberId;   // 복합 커서
}

(level, member_id) 복합 인덱스가 있어야 이 seek 가 인덱스만으로 효율적으로 처리된다.

더 나은 설계

정렬 키에 항상 유일 타이브레이커 포함: 마지막 컬럼으로 PK 를 붙여 전순서를 보장한다(랭킹·목록 공통 규칙).
복합 인덱스 정렬 방향 일치: ORDER BY level DESC, member_id ASC 와 seek 조건이 인덱스 순서와 맞아야 인덱스 스캔으로 끝난다.
OFFSET 회피 이유 재확인: OFFSET 은 동시 삽입/삭제 시 스큐로 누락·중복이 나고 뒤 페이지가 느리다. 키셋은 이를 피하지만 "유일 키" 전제를 반드시 지켜야 한다.
트레이드오프: 복합 커서는 조건이 복잡해지지만 정확성·성능을 모두 얻는다. 튜플 비교 (level, member_id) < (@l, @id) 를 지원하는 DB 면 더 간결하게 쓸 수 있다.

면접 포인트

키셋 페이지네이션이 "정렬 키 유일성" 을 요구하는 이유와, 비유일 키에서 </<= 가 각각 누락·중복이 되는 원리.
타이브레이커(PK) 추가와 복합 인덱스 설계.
OFFSET vs 키셋의 스큐·성능 트레이드오프.

해설 · C++

해설 — 유일하지 않은 정렬 키의 키셋 페이지네이션: 경계 행 중복·무한 재조회

난이도: 상

요약

정렬·seek 키가 score(비유일) 하나뿐인데 (A) 가 score <= ? 를 쓰고 커서를 rows.back().score (B) 로만 잡는다. 같은 점수 행이 경계에 걸치면 다음 페이지가 경계 점수 행을 다시 반환하고, 한 페이지가 전부 같은 점수면 커서가 진전하지 않아 같은 페이지를 영원히 반복한다.

문제점

[정합성] 경계 동점 행 중복: pageSize=3, 점수가 [100,100,100,100,90,...] 라 하자.
- 1페이지: [100,100,100], 커서 cursorScore=100.
- 2페이지: WHERE score <= 100 → 다시 100 들부터 나온다 → 1페이지의 100 세 개가 중복 재조회.
[치명] 무한 루프: 한 페이지 전체가 동점(예: 점수 100 인 플레이어가 pageSize 보다 많음)이면 매 페이지가 [100,100,100] 이고 커서는 계속 100 → score <= 100 로 영원히 같은 결과를 돌려 페이지 순회가 끝나지 않는다(무한 스캔·중복 지급/표시).
[대안 오류로도 실패] < 로 바꾸면 누락: score < 100 으로 바꾸면 경계에 걸친 남은 100 들이 통째로 사라진다. 즉 유일 키 없이 </<= 어느 쪽도 정답이 아니다 — 근본 원인은 타이브레이커 부재.
[근본 원인] 전순서(total order) 부재: 키셋 seek 는 정렬 키가 행마다 유일해야 경계가 명확히 잘린다.
재현 조건: 동점 플레이어가 pageSize 경계에 걸치거나 한 페이지를 채울 만큼 많을 때. 랭킹에서 매우 흔함.

수정안

유일 타이브레이커(player_id)를 정렬·seek 조건에 함께 넣어 전순서를 만들고, 커서를 (score, player_id) 복합으로 이어간다.

-- 첫 페이지
SELECT player_id, score FROM ranking
WHERE board_id = ?
ORDER BY score DESC, player_id ASC
LIMIT ?;

-- 다음 페이지: (score, player_id) 복합 seek (엄격한 부등호로 경계 제외)
SELECT player_id, score FROM ranking
WHERE board_id = ?
  AND ( score < ?
        OR (score = ? AND player_id > ?) )
ORDER BY score DESC, player_id ASC
LIMIT ?;

struct Cursor { bool has=false; int64_t score=0; int64_t playerId=0; };
if ((int)rows.size() == pageSize) {
    cur.has = true;
    cur.score = rows.back().score;
    cur.playerId = rows.back().playerId;   // 복합 커서로 진전 보장
}

(score DESC, player_id ASC) 복합 인덱스를 두면 이 seek 가 인덱스 스캔만으로 처리된다.

더 나은 설계

정렬 마지막 컬럼에 PK 를 붙여 전순서 보장 — 랭킹·목록 공통 규칙. 커서 진전이 항상 보장돼 무한 루프가 원천 차단된다.
정렬 방향과 부등호 방향 일치: DESC 정렬엔 score < cur.score OR (= AND player_id > cur.id) 처럼 방향을 맞춰야 인덱스와 정합한다.
동점 표시 규칙 분리: 화면에 보이는 "공동 순위" 와 페이지 커서용 전순서는 별개 — 커서는 항상 유일 키로 자른다.
트레이드오프: 복합 커서는 조건이 길어지지만 정확성·성능·종료성을 모두 얻는다. 튜플 비교를 지원하는 DB 면 (score, player_id) < (?, ?) 로 간결하게 쓸 수 있다.

면접 포인트

키셋 페이지네이션의 "정렬 키 유일성" 전제와, 비유일 키에서 <=/< 가 각각 중복·누락(그리고 무한 루프)이 되는 원리.
커서 진전(progress) 보장의 중요성과 타이브레이커.
OFFSET vs 키셋의 스큐·성능 트레이드오프와 복합 인덱스 정렬 방향.

← 문제로 돌아가기