Pagination performance — OFFSET vs keyset, Slice bỏ COUNT

TL;DR: OFFSET N LIMIT 20 yêu cầu DB scan rồi bỏ đúng N row — thời gian tỉ lệ thuận với N, trang 1.000 chậm hơn trang 1 gấp 1.000 lần. Keyset (cursor) pagination dùng WHERE id sau lastId để nhảy thẳng qua B-tree index, tốc độ O(log N) hằng số bất kể depth. Slice<T> bỏ query COUNT(*) thứ hai, tiết kiệm ~50% cho table lớn nhưng không giải quyết OFFSET scan. Ba cơ chế phục vụ ba nhu cầu UX khác nhau: "trang X/Y" cần Page, infinite scroll cần Slice, realtime feed cần keyset.

Bài Pageable và Sort đã giới thiệu cách bind ?page=0&size=20 và API Page<T> / Slice<T>. Bài này đào sâu một câu hỏi: vì sao Page chậm ở deep page, Slice nhanh hơn nhưng vẫn không đủ cho 100M row, và keyset giải quyết thế nào bên dưới?

1. Scenario — deep page trong production

TaskFlow có 2 triệu activity row. Endpoint /api/activities?page=0&size=20 trả kết quả trong 5ms. Nhưng khi crawler của analytics team gửi ?page=50000&size=20, response mất 30 giây rồi timeout.

page=0,     OFFSET=0      → 5ms
page=100,   OFFSET=2000   → 50ms
page=1000,  OFFSET=20000  → 500ms
page=10000, OFFSET=200000 → 5000ms → timeout

Không phải lỗi code. Đây là hành vi xác định của OFFSET — cần hiểu cơ chế để chọn đúng chiến lược.

2. Cơ chế OFFSET — tại sao chậm tuyến tính

SQL LIMIT 20 OFFSET 20000 không có shortcut: PostgreSQL phải đọc tuần tự từ đầu index (hoặc heap), đếm và bỏ qua đúng 20.000 row, rồi mới trả 20 row tiếp theo. Không thể nhảy thẳng vì không biết row thứ 20.001 nằm ở địa chỉ nào cho đến khi đã đọc 20.000 row trước đó.

-- Moi lan deep page, Postgres lap lai toan bo cong viec nay:
SELECT * FROM activities
ORDER BY created_at DESC
LIMIT 20 OFFSET 20000;

-- Postgres thuc hien:
-- 1. Doc index created_at tu dau (hoac full heap scan)
-- 2. Dem va bo qua 20000 row dau
-- 3. Doc 20 row tiep theo
-- 4. Tra ve client
-- Chi phi: doc 20020 row, tra ve 20

Với index trên created_at, bước 1 là index scan thay sequential scan — nhanh hơn ~10 lần nhưng vẫn O(N). Index giúp tìm điểm bắt đầu của toàn bộ tập kết quả, không giúp nhảy đến vị trí OFFSET.

flowchart TB
  subgraph OFF["OFFSET pagination -- chi phi tang tuyen tinh"]
    direction TB
    O1["Index scan tu dau tap ket qua"]
    O2["Bo qua N row dau (OFFSET N)"]
    O3["Doc 20 row tiep theo (LIMIT 20)"]
    O4["Tra ve client -- nhung da doc N+20 row"]
    O1 --> O2 --> O3 --> O4
  end

  subgraph KS["Keyset pagination -- chi phi hang so"]
    direction TB
    K1["WHERE id sau lastId -- dieu kien index"]
    K2["B-tree lookup O(log N) toi vi tri"]
    K3["Doc 20 row tiep theo (LIMIT 20)"]
    K4["Tra ve client -- chi doc 20 row"]
    K1 --> K2 --> K3 --> K4
  end

Đây là lý do keyset nhanh hơn: điều kiện WHERE id sau lastId là một index seek — B-tree tìm ngay vị trí của lastId trong O(log N) rồi đọc 20 row tiếp theo. Không có bước "bỏ qua N row".

3. Keyset pagination — cơ chế seek thay scan

Keyset (cursor-based) pagination dùng giá trị của row cuối đã thấy làm điểm bắt đầu cho trang tiếp theo:

// Trang dau: khong co cursor
List<Activity> findFirst20ByOrderByCreatedAtDescIdDesc();

// Trang tiep theo: cursor = (createdAt, id) cua row cuoi trang truoc
@Query("""
    SELECT a FROM Activity a
    WHERE a.createdAt < :cursorCreatedAt
       OR (a.createdAt = :cursorCreatedAt AND a.id < :cursorId)
    ORDER BY a.createdAt DESC, a.id DESC
    """)
List<Activity> findNextPage(
    @Param("cursorCreatedAt") Instant cursorCreatedAt,
    @Param("cursorId") Long cursorId,
    Pageable limit
);

SQL tương ứng:

-- Trang dau
SELECT * FROM activities
ORDER BY created_at DESC, id DESC
LIMIT 20;
-- Postgres: index seek toi dau index, lay 20 row

-- Trang 2 (cursor = row cuoi trang 1: created_at='2026-05-01 10:00:00', id=5000)
SELECT * FROM activities
WHERE created_at < '2026-05-01 10:00:00'
   OR (created_at = '2026-05-01 10:00:00' AND id < 5000)
ORDER BY created_at DESC, id DESC
LIMIT 20;
-- Postgres: B-tree seek den (created_at, id) = cursor, lay 20 row ke tiep
-- Chi phi: O(log N) bat ke depth

Index cần tạo để hỗ trợ seek:

-- Index composite khop voi ORDER BY va WHERE
CREATE INDEX idx_activities_created_id
ON activities(created_at DESC, id DESC);

Tại sao cần composite cursor (createdAt, id)? Nếu chỉ dùng createdAt, nhiều row cùng timestamp sẽ bị bỏ sót hoặc lặp lại ở ranh giới trang. id là tiebreaker đảm bảo cursor duy nhất cho mỗi row.

Keyset với Spring Data Window API (Spring Data 3.1 trở lên)

Spring Data 3.1 giới thiệu Window<T> và ScrollPosition để chuẩn hoá keyset:

public interface ActivityRepository extends JpaRepository<Activity, Long> {
    Window<Activity> findFirst20ByOrderByCreatedAtDescIdDesc(ScrollPosition position);
}

// Service
public ScrollResult<ActivityDto> feed(ActivityCursor cursor, int size) {
    ScrollPosition position = cursor == null
        ? ScrollPosition.offset()
        : ScrollPosition.forward(Map.of(
            "createdAt", cursor.createdAt(),
            "id", cursor.id()
          ));

    Window<Activity> window = repo.findFirst20ByOrderByCreatedAtDescIdDesc(position);

    ActivityCursor nextCursor = window.hasNext()
        ? toCursor(window.getContent().get(window.size() - 1))
        : null;

    return new ScrollResult<>(
        window.getContent().stream().map(ActivityDto::from).toList(),
        nextCursor
    );
}

public record ActivityCursor(Instant createdAt, Long id) {}
public record ScrollResult<T>(List<T> items, ActivityCursor nextCursor) {}

ScrollPosition.forward(Map.of(...)) truyền cursor map xuống Spring Data, framework tự generate điều kiện WHERE keyset phù hợp.

4. Slice — bỏ COUNT query, không bỏ OFFSET scan

Slice<T> giải quyết vấn đề khác với keyset: nó bỏ query COUNT(*) thứ hai mà Page<T> luôn chạy.

// Page: chay 2 SQL
Page<Activity> findAll(Pageable pageable);
// SQL 1: SELECT * FROM activities ... LIMIT 20 OFFSET N
// SQL 2: SELECT COUNT(*) FROM activities ... (co the rat cham)

// Slice: chi 1 SQL
Slice<Activity> findAll(Pageable pageable);
// SQL: SELECT * FROM activities ... LIMIT 21 OFFSET N
// (fetch size+1, neu co row thu 21 thi hasNext=true)

Cơ chế hasNext của Slice: Hibernate fetch size + 1 row. Nếu tồn tại row thứ size + 1 thì hasNext = true và row đó không được trả về client. Không cần COUNT(*) — tiết kiệm ~50% thời gian cho table có COUNT chậm.

flowchart LR
  subgraph PG["Page -- 2 SQL"]
    direction TB
    P1["SQL 1: SELECT ... LIMIT 20 OFFSET N"]
    P2["SQL 2: SELECT COUNT(*) FROM ..."]
    P3["totalElements, totalPages"]
    P1 --> P3
    P2 --> P3
  end

  subgraph SL["Slice -- 1 SQL"]
    direction TB
    S1["SQL: SELECT ... LIMIT 21 OFFSET N"]
    S2["Row thu 21 ton tai?"]
    S3["hasNext = true -- row do khong tra ve"]
    S1 --> S2 --> S3
  end

Điều quan trọng: Slice vẫn dùng OFFSET. Nó chỉ giúp khi COUNT(*) là bottleneck (table có nhiều JOIN, WHERE phức tạp), không giúp khi OFFSET scan là bottleneck. Với table 100M row và OFFSET 2.000.000, Slice vẫn chậm như Page về data query.

5. So sánh ba chiến lược

Quy tắc chọn:

• Cần "Trang X / Y" và table dưới 100k row: Page<T>.
• Infinite scroll, không cần total, table dưới 1M row: Slice<T>.
• Table lớn hơn 100k row, data thay đổi thường xuyên, hoặc realtime feed: keyset.

6. Pitfall thường gặp

Pitfall 1 — OFFSET sâu làm timeout endpoint

// SAI: khong gioi han page, OFFSET tang khong kiem soat
@GetMapping("/activities")
public Page<ActivityDto> list(Pageable pageable) {
    return repo.findAll(pageable).map(ActivityDto::from);
}
// Request ?page=50000&size=20 -> timeout 30s

// DUNG: gioi han max page, buoc dung search/filter cho data sau
@GetMapping("/activities")
public Page<ActivityDto> list(
    @RequestParam(defaultValue = "0") @Min(0) @Max(500) int page,
    @RequestParam(defaultValue = "20") @Min(1) @Max(100) int size
) {
    return service.list(PageRequest.of(page, size)).map(ActivityDto::from);
}

Bổ sung cấu hình global trong application.yml:

spring:
  data:
    web:
      pageable:
        max-page-size: 100

Pitfall 2 — Sort không stable gây lặp/bỏ sót row ở ranh giới trang

-- SAI: ORDER BY status khong unique
SELECT * FROM activities ORDER BY status LIMIT 20 OFFSET 20;
-- Neu 2 execution co row moi insert giua 2 lan chay
-- -> row co the xuat hien 2 lan hoac mat hoan toan

-- DUNG: luon co tiebreaker unique
SELECT * FROM activities ORDER BY status, id LIMIT 20 OFFSET 20;

Trong Spring Data:

// DUNG: sort composite co id lam tiebreaker
Pageable pageable = PageRequest.of(page, size,
    Sort.by(Sort.Order.asc("status"), Sort.Order.asc("id")));

Pitfall 3 — Dùng Slice khi vẫn cần COUNT

Slice bỏ COUNT hoàn toàn. Nếu UI cần hiển thị "tìm thấy 1.234 kết quả", Slice không cung cấp thông tin đó. Cần Page hoặc query COUNT riêng với cache.

Pitfall 4 — Keyset cursor không unique

// SAI: cursor chi co createdAt, neu nhieu row cung timestamp
// -> co the bỏ sót hoac lap row
WHERE createdAt < :cursor ORDER BY createdAt DESC LIMIT 20

// DUNG: composite cursor (createdAt, id)
WHERE createdAt < :cursorCreatedAt
   OR (createdAt = :cursorCreatedAt AND id < :cursorId)
ORDER BY createdAt DESC, id DESC LIMIT 20

Liên hệ các bài khác

• Pageable và Sort: cách bind ?page=&size=&sort= qua PageableHandlerMethodArgumentResolver, cấu hình @PageableDefault, @SortDefault — nền tảng API trước khi chọn chiến lược performance.
• Cascade & N+1 query: N+1 query khi load relationship trong Page — paginate entity với JOIN FETCH cần countQuery custom để tránh COUNT sai do Cartesian product.
• Propagation & isolation: đánh dấu service method @Transactional(readOnly = true) khi chỉ đọc data — giảm overhead lock, tối ưu cùng keyset pagination.

Tóm tắt

• OFFSET N yêu cầu DB đọc và bỏ N row — chi phí O(N), tăng tuyến tính theo depth.
• Keyset dùng WHERE id sau lastId như điều kiện index seek — chi phí O(log N) hằng số bất kể trang bao nhiêu.
• Slice<T> bỏ query COUNT(*), tiết kiệm ~50% khi COUNT là bottleneck, nhưng vẫn dùng OFFSET cho data query.
• Ba chiến lược phục vụ ba UX khác nhau: Page cho "trang X/Y", Slice cho "Load more" trên table vừa, keyset cho table lớn và realtime feed.
• Luôn có tiebreaker unique (thường là id) trong sort và keyset cursor để tránh bỏ sót hoặc lặp row ở ranh giới trang.

Tự kiểm tra

Bài tiếp theo: Tổng kết module