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 của PostgreSQL:

PG default thường là điều bạn muốn — 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. Nhưng để code portable sang MySQL/SQLite và intent rõ ràng hơn, nên viết explicit NULLS FIRST / NULLS LAST.

Stable sort và tiebreaker:

Khi nhiều row có cùng giá trị ở column sort, thứ tự trả về là nondeterministic — PostgreSQL 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

PostgreSQL executor chạy 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
EXPLAIN ANALYZE
SELECT * FROM tasks
ORDER BY created_at DESC
LIMIT 10 OFFSET 100000;
-- Plan: Limit -> Sort -> Seq Scan
-- actual time: ~850ms (phai xu ly 100010 rows)

EXPLAIN ANALYZE
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 hơn linear với offset.

Module 7 của khoá này sẽ đi sâu vào cách đọc EXPLAIN plan và nhận biết node 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)

PostgreSQL (và ANSI SQL) hỗ trợ tuple 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à PostgreSQL query planner 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;

-- PostgreSQL khong cam ket thu tu khi khong co ORDER BY.
-- Planner co the chon seq scan, index scan, hoac bitmap scan
-- tuy thuoc vao statistics va plan 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

Liên kết khoá học khác

• Khoá Spring — bài 4.7 Pagination & Sorting — Pageable, Page<T>, Slice<T> trong Spring Data JPA build trên top SQL pagination.

10. Tóm tắt

• ORDER BY cần explicit NULL position (NULLS FIRST / NULLS LAST) để portable và intent rõ ràng — PG default khác MySQL/SQLite.
• 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 5 của khoá này (composite B-tree index cho keyset) + Module 7 (EXPLAIN ANALYZE đọc OFFSET cost).

11. 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