ORDER BY + pagination — vì sao OFFSET 100k chậm 200 lần

Dashboard TaskFlow hiển thị danh sách task theo thời gian tạo. Page 1 trả về trong 12ms. Page 100 (OFFSET 1000 LIMIT 10): 250ms. Page 5000 (OFFSET 50000): 4 giây. Schema không thay đổi, không có thêm query nào khác, chỉ số trang tăng dần — nhưng app ngày càng chậm khi người dùng cuộn thêm. Vì sao OFFSET càng cao càng chậm, và keyset pagination vẫn chỉ vài ms dù đang ở page 10000?

Bài này giải thích cơ chế OFFSET cost, NULL ordering trap, stable sort tiebreaker, và pattern keyset pagination cho production infinite scroll.

1. Analogy — OFFSET vs keyset

Hình dung thư viện có một cuốn sách dày 500.000 trang, được đánh số trang liên tục. Bạn muốn đọc 10 trang bắt đầu từ trang 100.001.

Cách A (OFFSET): Mở từ trang 1, đếm và lật qua 100.000 trang, rồi đọc 10 trang tiếp theo. Trang 200.001 thì lật qua 200.000 trang. Càng đọc sâu, càng mất công lật.

Cách B (keyset): Bạn đã đánh dấu trang 100.000 bằng bookmark. Mở thẳng bookmark đó, đọc 10 trang tiếp theo. Không cần lật bất kỳ trang nào trước đó — dù bookmark ở trang 1 hay trang 499.000, chi phí như nhau.

2. ORDER BY cú pháp + NULL ordering

Cú pháp đầy đủ và các pattern thường gặp:

-- Single column, ascending (default)
SELECT * FROM tasks
ORDER BY created_at;       -- ASC la default

-- Multi-column sort: priority truoc, sau do due_at, sau do tiebreaker id
SELECT * FROM tasks
ORDER BY status, due_at NULLS LAST, id;

-- Explicit NULL position (portable cross-engine)
SELECT * FROM tasks
ORDER BY due_at ASC NULLS LAST,     -- NULL xuat hien cuoi
         created_at DESC NULLS FIRST;  -- NULL xuat hien dau

NULL ordering mặc định theo hệ quản trị:

Default NULL ordering khác nhau giữa engine — để code portable và intent rõ ràng, luôn viết explicit NULLS FIRST / NULLS LAST. ASC NULLS LAST đặt "chưa có hạn" sau task có hạn; DESC NULLS FIRST đặt "chưa xác định" trước.

Stable sort và tiebreaker:

Khi nhiều row có cùng giá trị ở column sort, thứ tự trả về là nondeterministic — hệ quản trị không cam kết thứ tự giữa các row tied. Hai lần chạy cùng query có thể trả về thứ tự khác nhau. Fix: thêm column unique làm tiebreaker cuối cùng.

-- Khong stable: cac task cung status, due_at co the doi thu tu giua 2 query
SELECT * FROM tasks
ORDER BY status, due_at NULLS LAST;

-- Stable: id la primary key, unique, dam bao thu tu quyet dinh
SELECT * FROM tasks
ORDER BY status, due_at NULLS LAST, id;

3. OFFSET cơ chế — vì sao chậm

flowchart TD
  subgraph OFFSET["OFFSET pagination"]
    O1["Table 5M rows"] --> O2["Sort theo ORDER BY"]
    O2 --> O3["Scan va skip N rows\n(OFFSET cost: O(N))"]
    O3 --> O4["Fetch LIMIT rows"]
    O4 --> O5["Tra ket qua"]
  end
  subgraph KEYSET["Keyset / seek pagination"]
    K1["Table 5M rows"] --> K2["Index seek den cursor\n(created_at, id)"]
    K2 --> K3["Fetch LIMIT rows\ntừ vi tri cursor"]
    K3 --> K4["Tra ket qua"]
  end
  note1["Page cang sau: N cang lon\n=> OFFSET cang cham (tuyen tinh)"]
  note2["Moi page: cost nhu nhau\n=> O(log N) bat ke page nao"]
  OFFSET --- note1
  KEYSET --- note2
  style note1 fill:#fef3c7,color:#92400e
  style note2 fill:#d1fae5,color:#065f46

Hệ quản trị xử lý LIMIT 10 OFFSET 100000 theo ba bước:

1. Scan + sort rows theo ORDER BY clause.
2. Đếm và skip 100.000 rows đầu tiên.
3. Return 10 rows tiếp theo.

Bước 2 là vấn đề: database phải thực sự đọc và xử lý 100.000 rows đó, chỉ để bỏ đi. Cost tỷ lệ thuận với OFFSET + LIMIT. Gấp đôi offset = gấp đôi thời gian.

-- Bang tasks voi 5 trieu row
-- Execution plan cho thay: Limit -> Sort -> Seq Scan
SELECT * FROM tasks
ORDER BY created_at DESC
LIMIT 10 OFFSET 100000;
-- actual time: ~850ms (phai xu ly 100010 rows)

SELECT * FROM tasks
ORDER BY created_at DESC
LIMIT 10 OFFSET 1000000;
-- actual time: ~8500ms (10x worse -- 10x offset = 10x cost)

Nếu column sort có index: database dùng index scan thay vì seq scan + sort, nhưng vẫn phải traverse 100k index entries để đếm và skip — chậm tuyến tính với offset.

Module 6 — Storage & indexing sẽ đi sâu vào cách đọc execution plan và nhận biết bước nào gây chậm.

4. Keyset pagination — O(1) per page

Thay vì "skip N rows đầu tiên", keyset pagination dùng giá trị của row cuối cùng đã thấy làm cursor — chỉ lấy rows đứng sau cursor đó.

-- Page 1: khong co cursor
SELECT id, title, created_at
FROM tasks
ORDER BY created_at DESC, id DESC
LIMIT 10;
-- Tra ve 10 rows, row cuoi co: created_at = '2026-05-04 10:00:00', id = 9991

-- Page 2: dung (created_at, id) cua row cuoi lam cursor
SELECT id, title, created_at
FROM tasks
WHERE (created_at, id) < ('2026-05-04 10:00:00', 9991)
ORDER BY created_at DESC, id DESC
LIMIT 10;
-- Plan: Limit -> Index Scan Backward on (created_at DESC, id DESC)
-- actual time: ~4ms -- bat ke page nao

Với B-tree composite index trên (created_at DESC, id DESC), database thực hiện index seek trực tiếp đến cursor thay vì scan từ đầu. Cost là O(log N) cho seek + O(LIMIT) để fetch — bất kể page nào.

Tradeoff keyset vs OFFSET:

5. Tuple comparison — cú pháp (a, b) < (x, y)

ANSI SQL hỗ trợ tuple comparison (row value comparison) — so sánh nhiều column cùng lúc theo lexicographic order:

-- Tuong duong: created_at < '2026-05-04' OR (created_at = '2026-05-04' AND id < 9991)
WHERE (created_at, id) < ('2026-05-04 10:00:00', 9991)

Cú pháp này ngắn gọn hơn điều kiện AND/OR tương đương, và query planner của nhiều hệ quản trị nhận biết được để tối ưu với composite B-tree index.

6. Pitfall — pagination không có ORDER BY

-- SAI: page 1 va page 2 co the overlap hoac miss rows
SELECT id, title FROM tasks LIMIT 10 OFFSET 0;
SELECT id, title FROM tasks LIMIT 10 OFFSET 10;

-- Khong co ORDER BY: thu tu row phu thuoc vao execution plan (nondeterministic).
-- Planner co the chon seq scan, index scan, hoac plan khac
-- tuy thuoc vao statistics va cache -- thu tu row co the doi.

-- DUNG: luon co ORDER BY
SELECT id, title FROM tasks ORDER BY id LIMIT 10 OFFSET 0;
SELECT id, title FROM tasks ORDER BY id LIMIT 10 OFFSET 10;

7. Khi nào OFFSET vẫn ổn

OFFSET không phải luôn sai — context quyết định:

Pattern quyết định nhanh: nếu user có thể scroll/page sâu tùy ý, hoặc nếu data liên tục insert mới — chọn keyset. Nếu dataset nhỏ và UI có jump-to-page cố định — OFFSET ổn.

8. Applied — TaskFlow infinite scroll

Frontend hiển thị task feed 20 task/lần, scroll tự động load thêm. API design:

// Request 1 -- page dau tien
GET /api/tasks?limit=20

// Response
{
  "items": [...],
  "next_cursor": "eyJjcmVhdGVkX2F0IjoiMjAyNi0wNS0wNCAxMDowMDowMCIsImlkIjo5OTkxfQ=="
}

// Request 2 -- dung cursor tu response truoc
GET /api/tasks?limit=20&cursor=eyJjcmVhdGVkX2F0IjoiMjAyNi0wNS0wNCAxMDowMDowMCIsImlkIjo5OTkxfQ==

Backend node-postgres:

// Decode cursor tu base64 JSON
const cursor = req.query.cursor
  ? JSON.parse(Buffer.from(String(req.query.cursor), 'base64').toString())
  : null;

// Build query dua vao cursor
const { rows } = cursor
  ? await pool.query(
      `SELECT id, title, created_at FROM tasks
       WHERE (created_at, id) < ($1, $2)
       ORDER BY created_at DESC, id DESC
       LIMIT $3`,
      [cursor.created_at, cursor.id, limit]
    )
  : await pool.query(
      `SELECT id, title, created_at FROM tasks
       ORDER BY created_at DESC, id DESC
       LIMIT $1`,
      [limit]
    );

// Encode cursor tu row cuoi cung
const lastRow = rows[rows.length - 1];
const nextCursor = lastRow
  ? Buffer.from(JSON.stringify({ created_at: lastRow.created_at, id: lastRow.id })).toString('base64')
  : null;

Index cần thiết cho keyset query trên:

-- Composite index phai match thu tu ORDER BY
CREATE INDEX idx_tasks_created_at_id ON tasks (created_at DESC, id DESC);

9. Deep Dive — Pagination performance

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

• Bài 02 — WHERE + NULL three-valued logic: NULL ordering (NULLS FIRST/LAST) là hệ quả trực tiếp của three-valued logic — NULL không so sánh được nên cần vị trí tường minh.
• Bài 04 — DISTINCT vs GROUP BY: GROUP BY cũng cần tiebreaker khi nhiều row tied — cùng nguyên lý stable sort.
• Bài 07 — Mini-challenge dashboard: keyset pagination được áp dụng trực tiếp trong bài challenge — ôn tập toàn bộ phần này.
• Module 6 — Storage & indexing: composite B-tree index cho keyset query — tại sao index seek đến cursor O(log N) thay vì full scan.

11. Tóm tắt

• ORDER BY cần explicit NULL position (NULLS FIRST / NULLS LAST) để portable và intent rõ ràng — default NULL ordering khác nhau giữa engine.
• Stable sort cần tiebreaker — thêm column unique (, id) ở cuối ORDER BY để tránh nondeterministic order khi có tied rows.
• OFFSET cost = O(offset + limit) — database phải đọc và bỏ toàn bộ rows trước cursor. Tăng tuyến tính, không scale với deep page.
• Keyset pagination = O(log N) + O(LIMIT) — seek trực tiếp đến cursor qua B-tree index. Cost không đổi dù page 1 hay page 10000.
• Tuple comparison (a, b) < (x, y) là cú pháp keyset chuẩn — ngắn hơn AND/OR tương đương và planner tối ưu được với composite index.
• LIMIT/OFFSET không có ORDER BY = nondeterministic — page overlap hoặc miss rows, tùy execution plan.
• Keyset không hỗ trợ jump-to-page trực tiếp — dùng OFFSET khi cần tính năng đó và table đủ nhỏ.
• Forward links: Module 6 — Storage & indexing (composite B-tree index cho keyset, execution plan đọc OFFSET cost).

12. Tự kiểm tra

CREATE INDEX idx_tasks_created_at_id
ON tasks (created_at DESC, id DESC);

Bài tiếp theo: DISTINCT vs GROUP BY — khi nào dùng cái nào