Cursor pagination: vì sao OFFSET càng ngày càng chậm và cách fix — hoatq.dev

cat blog/.md

Cursor pagination: vì sao OFFSET càng ngày càng chậm và cách fix

date: tags: backend, postgresql, performance, api-design, database

Có một dạng bug rất oái oăm: trang đầu danh sách load nhanh, nhưng càng scroll xuống càng chậm. Khách hàng trong app mobile lướt đến trang 500 thì thấy loading mãi không ra, họ thoát app. Bạn nhìn query log: cùng một câu SELECT ... LIMIT 20 OFFSET 10000 nhưng EXPLAIN cho thấy nó đang scan cả bảng. Cache tầng nào cũng không cứu nổi.

Đây là câu chuyện về OFFSET — cái cú pháp quen thuộc đến mức hầu như dev nào cũng gõ trong câu đầu tiên, nhưng cũng là một trong những thủ phạm gây chậm API phổ biến nhất khi data lớn dần. Bài này mổ xẻ tại sao OFFSET tệ và cách chuyển sang cursor-based pagination cho đúng.

Vì sao OFFSET chậm

Nhìn vào câu query cơ bản:

SELECT id, title, created_at
FROM articles
ORDER BY created_at DESC
LIMIT 20 OFFSET 10000;

Trong đầu bạn có thể hình dung Postgres “nhảy” thẳng đến row thứ 10001 rồi lấy 20 row. Nhưng thực tế thì không có chuyện đó — kể cả khi bạn có index trên created_at.

Postgres (và MySQL, và hầu hết các RDBMS) phải:

  1. Duyệt index theo thứ tự created_at DESC.
  2. Đếm từng row: 1, 2, 3, …, 10000.
  3. Vứt đi 10000 row đầu.
  4. Trả về 20 row tiếp theo.

Tức là OFFSET 10000 đồng nghĩa với việc đọc và loại bỏ 10000 row trước khi lấy dữ liệu bạn cần. OFFSET càng lớn, công việc càng nhiều. Độ phức tạp là O(offset + limit), không phải O(limit).

Cái này còn tệ hơn nếu query có WHERE hoặc JOIN — mỗi row bị “vứt” vẫn phải filter và join đầy đủ, chỉ để rồi bị bỏ đi.

Chưa kể vấn đề thứ hai: consistency. Giữa lúc bạn đang lật trang, nếu có row mới được insert, dữ liệu trang sau bị lệch. User có thể thấy cùng một bài viết ở trang 3 rồi lại ở trang 4. Hoặc bị skip luôn vài bài.

Cursor-based pagination là gì

Thay vì nói “bỏ qua 10000 row”, ta nói “cho tôi 20 row tiếp theo sau row có created_at = X, id = Y”. Đó là cursor (con trỏ).

Cursor không phải một chỉ số vị trí, mà là giá trị của cột sort ở row cuối cùng của trang trước. Với cách này, Postgres dùng index để seek trực tiếp đến đúng chỗ, không cần đếm.

Câu query trở thành:

SELECT id, title, created_at
FROM articles
WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 20;

Với index:

CREATE INDEX idx_articles_created_at_id
  ON articles (created_at DESC, id DESC);

Query này luôn là O(limit) — không phụ thuộc bạn đang ở “trang” nào. Trang 1 và trang 1000 đều nhanh như nhau.

Tại sao phải kèm id vào cursor

Nhiều người viết cursor chỉ với một cột sort:

WHERE created_at < $1
ORDER BY created_at DESC
LIMIT 20;

Trông có vẻ ổn, nhưng sai khi created_at không unique. Nếu có 3 row cùng timestamp và trang trước kết thúc giữa chừng 3 row đó, trang sau sẽ bỏ sót 1-2 row.

Cách đúng là kết hợp cột sort chính với một cột unique (thường là id) để cursor luôn duy nhất:

WHERE (created_at, id) < ($1, $2)
ORDER BY created_at DESC, id DESC
LIMIT 20;

Cú pháp tuple comparison (a, b) < (x, y) của Postgres tương đương với: a < x OR (a = x AND b < y) — đúng logic keyset, và optimizer hiểu nó để dùng index đa cột hiệu quả.

Code thực tế với FastAPI + SQLAlchemy

Mình thường encode cursor dưới dạng base64 để vừa gọn, vừa chống user tự nghịch giá trị:

import base64
import json
from datetime import datetime
from fastapi import APIRouter, Query
from sqlalchemy import select

router = APIRouter()

def encode_cursor(created_at: datetime, id: int) -> str:
    payload = json.dumps({
        "c": created_at.isoformat(),
        "i": id,
    })
    return base64.urlsafe_b64encode(payload.encode()).decode()

def decode_cursor(cursor: str) -> tuple[datetime, int]:
    raw = base64.urlsafe_b64decode(cursor.encode()).decode()
    data = json.loads(raw)
    return datetime.fromisoformat(data["c"]), data["i"]


@router.get("/articles")
async def list_articles(
    cursor: str | None = Query(None),
    limit: int = Query(20, le=100),
    db=ReadDbDep,
):
    stmt = select(Article).order_by(
        Article.created_at.desc(),
        Article.id.desc(),
    ).limit(limit + 1)  # lấy dư 1 để biết có next_page không

    if cursor:
        ts, last_id = decode_cursor(cursor)
        stmt = stmt.where(
            tuple_(Article.created_at, Article.id) < (ts, last_id)
        )

    rows = (await db.execute(stmt)).scalars().all()

    has_next = len(rows) > limit
    items = rows[:limit]
    next_cursor = (
        encode_cursor(items[-1].created_at, items[-1].id)
        if has_next else None
    )

    return {
        "items": items,
        "next_cursor": next_cursor,
    }

Vài điểm cần chú ý:

  • Lấy limit + 1 row để biết còn trang sau hay không, rồi trim lại limit row trả về. Tránh phải đếm thêm bằng COUNT(*) (vốn cực đắt trên bảng lớn).
  • Không có total. Đây là trade-off: cursor pagination không biết tổng số page. Nếu UI bắt buộc hiện tổng, bạn phải dùng một count riêng, và chấp nhận nó chậm + stale.
  • Cursor opaque với client — nó chỉ biết “có hay không có next_cursor”. Format bên trong bạn đổi lúc nào cũng được.

Khi nào cursor không phù hợp

Cursor đẹp nhất với infinite scroll kiểu feed, chat, timeline — user chỉ đi tiếp, không nhảy cóc. Nhưng nó có giới hạn:

  • Không nhảy đến trang bất kỳ. Không có khái niệm “trang 50”. Nếu yêu cầu UI là jump page (kiểu Google search 1 2 3 4… 10), cursor không làm được — cần offset.
  • Không đi ngược tự nhiên. Để làm “previous page”, bạn cần lưu cursor của trang trước, hoặc dùng bidirectional cursor (cursor chứa cả hướng).
  • Sort phức tạp thì cursor dài ra. Nếu bạn sort theo (popularity, created_at, id) thì cursor phải chứa cả 3 giá trị, và index phải khớp chính xác 3 cột đó.

Quy tắc tôi hay dùng: dưới ~1000 row thì dùng offset cho đơn giản, trên đó chuyển cursor ngay. Đừng đợi nó chậm rồi mới refactor — API contract đã expose ?page=N thì khó bỏ.

Deep pagination và giới hạn cứng

Kể cả khi dùng offset, nhiều team chọn cách đơn giản hơn: chặn trang sâu. Ví dụ cap offset + limit ≤ 10000, vượt thì trả 400. Vì thực tế 99% user không bao giờ scroll quá trang 50 — và 1% còn lại thường là bot scrape. Chặn luôn vừa bảo vệ DB vừa tiết kiệm bandwidth.

Kết hợp tốt: hiện search + filter rõ ràng để user thu hẹp kết quả thay vì scroll, và dùng cursor cho phần feed chính. Đây là pattern của hầu hết app lớn — Twitter, Instagram, GitHub search đều vậy.

Kiểm tra xem bạn có đang bị OFFSET kéo chậm không

Đơn giản nhất là EXPLAIN ANALYZE với offset lớn:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM articles
ORDER BY created_at DESC
LIMIT 20 OFFSET 50000;

Nhìn dòng Buffers: shared hit=.... Nếu nó đọc hàng chục nghìn buffer cho một request trả 20 row, bạn đã có vấn đề. So với cursor query tương đương, số buffer gần như constant bất kể cursor ở đâu.

Một metric khác đáng watch ở production: p99 latency của endpoint list chia theo page parameter. Nếu thấy p99 tăng tuyến tính theo page, bạn biết mình đang cõng chi phí offset.

Tóm lại

OFFSET không xấu — nó đúng và dễ hiểu khi data nhỏ. Nhưng nó là O(n) ngụy trang thành O(1), và khi data lớn dần, chi phí đó rơi thẳng lên p99 của bạn.

Checklist khi design endpoint pagination mới:

  • Với data có thể grow vô hạn (feed, log, message), mặc định dùng cursor.
  • Index đa cột khớp với clause ORDER BY, luôn thêm id để tie-break.
  • Cursor opaque, encode base64, không expose raw values.
  • Lấy limit + 1 để detect next page, không dùng COUNT(*).
  • Có hard cap trang sâu cho trường hợp vẫn phải giữ offset.

Pagination nghe tưởng là feature đơn giản nhất của một API, nhưng nó là nơi nhiều hệ thống âm thầm “mục” nhất — data tăng dần, p99 tăng dần, và một ngày nào đó bạn sẽ tự hỏi sao list API lại chậm đến thế.

// reactions

lsrelated/

Tối ưu PostgreSQL: Index, Query Plan và những bài học từ production
postgresql, database, performance
Idempotency Key: thiết kế API không ngại retry
backend, api-design, postgresql
Database migration không downtime: expand-contract pattern và bài học từ production
database, postgresql, devops

cat comments.log

← cd ../blog EOF
hoatq@dev : ~/blog $