←Quay lại Blog
✦

Cursor Pagination — phân trang triệu dòng không chậm

•Phong Hy
engineeringbackendoptimize

Mình từng nhận một ticket nghe rất vô lý: "API danh sách đơn hàng nhanh ở trang 1 mà trang 2.000 load 4 giây". Cùng một endpoint, cùng một query, cùng một index. Vấn đề không nằm ở index — nó nằm ở chữ OFFSET.

OFFSET không nhảy, nó bò

Khi bạn viết:

SELECT id, code, total, created_at
FROM orders
WHERE tenant_id = 42
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 40000;

Postgres không nhảy thẳng tới dòng thứ 40.000. Nó đi qua index theo đúng thứ tự ORDER BY, đọc từng dòng, bỏ đi 40.000 dòng đầu, rồi trả 20 dòng cuối. Chi phí là O(offset + limit) — offset càng sâu càng chậm, tuyến tính. EXPLAIN ANALYZE sẽ cho thấy đúng thủ phạm:

Limit  (cost=... rows=20)
  ->  Index Scan Backward using idx_orders_tenant_created on orders
        Index Cond: (tenant_id = 42)
        Rows Removed by Filter: 0
Execution Time: 3812 ms

"Rows Removed" không cao, nhưng số dòng index phải đọc là 40.020. Nặng hơn nữa khi có join: mỗi dòng bị bỏ vẫn phải fetch heap.

Cursor (keyset) pagination

Ý tưởng: đừng hỏi "bỏ qua bao nhiêu dòng", hỏi "dòng cuối tôi đã thấy là gì". Lấy mốc đó làm điều kiện, DB chỉ cần một lần seek trên index.

SELECT id, code, total, created_at
FROM orders
WHERE tenant_id = 42
  AND (created_at, id) < ($1, $2)   -- cursor: mốc của bản ghi cuối trang trước
ORDER BY created_at DESC, id DESC
LIMIT 20;

So sánh tuple (created_at, id) chạy thẳng trên B-tree composite index, độ phức tạp gần như hằng số dù bạn ở trang 2 hay trang 20.000.

Index bắt buộc phải khớp đúng thứ tự sort — sai một cột là Postgres quay lại sort toàn bộ:

CREATE INDEX idx_orders_tenant_created_id
  ON orders (tenant_id, created_at DESC, id DESC);

Code Go thực tế

Cursor nên là opaque — client không được tự chế. Mình encode base64 để đổi định dạng sau này mà không phá API:

type cursor struct {
    CreatedAt time.Time `json:"t"`
    ID        int64     `json:"i"`
}

func encodeCursor(c cursor) string {
    b, _ := json.Marshal(c)
    return base64.RawURLEncoding.EncodeToString(b)
}

func decodeCursor(s string) (cursor, error) {
    var c cursor
    b, err := base64.RawURLEncoding.DecodeString(s)
    if err != nil {
        return c, ErrBadCursor
    }
    return c, json.Unmarshal(b, &c)
}

func (r *OrderRepo) List(ctx context.Context, tenantID int64, cur *cursor, limit int) ([]Order, *cursor, error) {
    if limit <= 0 || limit > 100 {
        limit = 20 // chặn client xin limit=100000
    }

    var (
        rows []Order
        next *cursor
    )

    if cur == nil {
        q := `SELECT id, code, total, created_at FROM orders
              WHERE tenant_id = $1
              ORDER BY created_at DESC, id DESC LIMIT $2`
        // ... query bình thường, không cần mốc
    } else {
        q := `SELECT id, code, total, created_at FROM orders
              WHERE tenant_id = $1 AND (created_at, id) < ($2, $3)
              ORDER BY created_at DESC, id DESC LIMIT $4`
        // ... bind tenantID, cur.CreatedAt, cur.ID, limit+1
    }
    _ = rows
    _ = next
    return rows, next, nil
}

Mẹo nhỏ mà rất đáng: luôn query limit + 1 rồi cắt dòng cuối. Có dòng dư nghĩa là còn trang sau, next_cursor mới đáng tin; hết dòng dư thì trả null — khỏi tốn thêm một câu COUNT(*).

Ba cái bẫy mình đã dính

1. id không phải là tie-breaker thừa. Nếu chỉ sort theo created_at, hai đơn tạo cùng một millisecond sẽ bị index trả theo thứ tự tuỳ tiện — mỗi lần query một khác, user thấy record lặp hoặc mất hẳn. Tuple (created_at, id) là bắt buộc, kể cả khi bạn chắc chắn timestamp là duy nhất (bạn không chắc đâu).

2. Cursor gắn chặt với thứ tự sort. Đổi filter (thêm status = 'PAID') mà không đổi index thì tuple compare vẫn chạy nhưng index không dùng được nữa. Cursor phải mang theo cả "thứ tự" (ví dụ prefix v2:paid) để client cũ gửi cursor lệch sort thì trả 400 thay vì trả dữ liệu sai.

3. Mất khả năng nhảy trang. Cursor không cho ?page=57, không có "tổng 12.480 kết quả". Với infinite scroll và mobile app thì đó là điểm cộng (không cần biết tổng). Với dashboard admin thì là điểm trừ thật. Mình xử lý bằng pg_class.reltuples làm con số ước lượng hiển thị mờ ("~12k kết quả") thay vì chạy COUNT(*) trên bảng 40 triệu dòng.

Kết quả và lời khuyên

Endpoint /orders sau khi đổi sang cursor: p99 từ 3.2s xuống 41ms, CPU đọc của Postgres giảm hơn một nửa vì không còn quét index vô ích. Nhưng mình không đổi hết: màn hình admin nội bộ, bảng vài chục nghìn dòng, có ô "đi tới trang" — để OFFSET cho tiện. Kỹ thuật đúng là kỹ thuật phù hợp với bài toán, không phải cái nào cũng nâng cấp lên cho oai.

Quy tắc mình chốt: dữ liệu tăng không ngừng + cuộn vô hạn → cursor. Dataset nhỏ, có phân trang thật → offset vẫn ổn.

←Xem các bài viết khác
✦