Phân trang OFFSET đắt

Gần như mọi ứng dụng đều phân trang: hiển thị 20 kết quả mỗi trang, có nút "trang sau". Cách quen thuộc nhất là LIMIT 20 OFFSET N, và nó trông hoàn hảo khi bạn thử. Nhưng nó ẩn một cái bẫy chỉ lộ ra ở các trang sâu — cái bẫy mà tôi suýt bỏ qua vì đo sai chỗ. Bài này đo phân trang OFFSET ở mọi độ sâu, và so với một cách khác nhanh đều.

OFFSET phải quét rồi vứt

LIMIT 20 OFFSET N nghe như "nhảy tới hàng thứ N rồi lấy 20 hàng". Nhưng cơ sở dữ liệu không có cách "nhảy" tới hàng thứ N — nó phải quét lần lượt N hàng đầu (theo thứ tự ORDER BY), vứt bỏ chúng, rồi mới giữ 20 hàng tiếp theo. Nghĩa là số hàng nó thật sự đọc là OFFSET + LIMIT, dù bạn chỉ nhận về LIMIT hàng.

Hệ quả: trang càng sâu, OFFSET càng lớn, cơ sở dữ liệu quét càng nhiều hàng chỉ để vứt đi. Trang 1 (OFFSET 0) không phải bỏ gì; nhưng trang 25.000 (OFFSET 500.000) phải đọc và bỏ nửa triệu hàng; trang cuối phải đọc gần như cả bảng. Chi phí tăng tuyến tính theo độ sâu trang — O(N). Đây là chỗ tôi đo hớ.

Đo: từ 0,02 ms tới 64 ms

Tôi tạo bảng một triệu hàng (khóa chính id), rồi phân trang ORDER BY id LIMIT 20 ở các độ sâu khác nhau, đọc EXPLAIN ANALYZE:

Con số kể câu chuyện rõ ràng. OFFSET 0 (trang 1) quét đúng 20 hàng, xong trong 0,02 ms — nhanh như chớp. Nhưng OFFSET 500.000 quét 500.020 hàng (đọc nửa triệu rồi vứt, giữ 20), mất 34 ms — chậm hơn một nghìn lần. Và trang cuối (OFFSET 999.980) quét toàn bộ một triệu hàng để trả về 20 hàng cuối, mất 64 ms. actual rows trong kế hoạch phơi bày sự thật: nó đúng bằng OFFSET + LIMIT ở mỗi trang — con số đó, chứ không phải 20 hàng trả về, mới là khối lượng công việc thật. Cùng một LIMIT 20, mà lượng việc chênh nhau năm mươi nghìn lần chỉ vì OFFSET.

Dòng cuối là lời giải: keyset pagination. Thay vì OFFSET, nó dùng WHERE id > <id_cuối_trang_trước> ORDER BY id LIMIT 20. Nhờ index trên id, cơ sở dữ liệu nhảy thẳng tới đúng chỗ và chỉ đọc 20 hàng — 0,03 ms, bất kể trang sâu tới đâu. Nhanh đều tuyệt đối. Lý do sâu xa là nó biến "đi tới trang thứ N" — một phép đếm tuyến tính — thành "tìm giá trị lớn hơn X" — một phép tra cứu index logarit, đúng cái B-tree làm giỏi nhất (như bài B-tree đã đo). OFFSET đếm; keyset tra cứu.

Một lần tôi đo hớ: chỉ thử trang đầu

Cái bẫy tôi bước vào rất tự nhiên. Tôi viết phân trang LIMIT 20 OFFSET N, và để kiểm tra hiệu năng, tôi chạy thử — với OFFSET 0, trang đầu tiên. EXPLAIN ANALYZE cho Index Scan quét đúng 20 hàng, 0,02 ms. Tôi hài lòng chốt: "phân trang OFFSET ổn mà, chỉ là một Index Scan nhỏ gọn, index lo hết".

Nhưng con số đẹp đó chỉ đúng cho trang đầu. Với OFFSET 0, cơ sở dữ liệu không phải bỏ hàng nào — nên tất nhiên nhanh. Tôi đã đo phân trang OFFSET ở đúng điều kiện tốt nhất của nó và ngoại suy cho mọi trang. Khi thử một trang sâu (OFFSET 500.000), câu chuyện lật hẳn: 34 ms, quét 500.020 hàng. Trang cuối còn tệ hơn — quét cả bảng. Chi phí của OFFSET không phải hằng số như tôi tưởng từ trang đầu; nó tăng tuyến tính theo độ sâu.

Cái tôi đo hớ là đo một thao tác ở điều kiện thuận lợi nhất rồi kết luận cho mọi điều kiện — đúng lỗi lặp lại của sê-ri: nested loop nhanh khi ngoài nhỏ, merge join rẻ khi đã sắp, và giờ OFFSET nhanh ở trang đầu. Một con số nhanh chỉ đúng cho điều kiện nó được đo. Với phân trang, điều kiện quyết định là độ sâu trang; đo ở trang 1 rồi yên tâm là bỏ sót đúng cái sẽ đau ở production (nơi người dùng lật tới trang 500). Bài học đo lường: khi đo một thứ mà chi phí phụ thuộc tham số (ở đây OFFSET), phải đo ở dải giá trị thật của tham số đó — đặc biệt là ở giá trị lớn — chứ không chỉ ở điểm dễ chịu nhất.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: OFFSET pagination chấp nhận được cho vài trang đầu, nhưng sập ở trang sâu. Nếu ứng dụng của bạn cho người dùng lật tới trang sâu — hoặc tệ hơn, có bot/crawler đi qua mọi trang — OFFSET biến mỗi lần lật trang sâu thành một lần quét gần cả bảng. Đây là nguyên nhân kinh điển của "trang 1 nhanh, trang 900 treo cả giây". Với danh sách lớn, đừng dùng OFFSET cho điều hướng sâu.

Hệ quả thứ hai: keyset pagination là lời giải cho danh sách lớn cuộn liên tục. Kiểu "cuộn vô tận" (infinite scroll) và feed hợp hoàn hảo với keyset: mỗi lần tải trang sau chỉ cần WHERE id > id_cuối ... LIMIT k, nhanh đều bất kể đã cuộn bao xa. Đánh đổi là keyset chỉ đi tiếp/lùi được (next/prev), không nhảy tới "trang 500" tùy ý như OFFSET — vì nó dựa vào giá trị mốc của trang liền trước, không có khái niệm "trang thứ N". Với phần lớn giao diện (feed, cuộn vô tận, nút "xem thêm"), đó là đánh đổi hoàn toàn chấp nhận được. Lưu ý: cột dùng keyset phải có index và có thứ tự ổn định (thường là khóa chính hoặc một cột duy nhất kết hợp). Nếu sắp theo cột có thể trùng (ví dụ ngày tạo), phải thêm một cột phá hòa (tie-breaker) như id để mốc là duy nhất, kẻo bỏ sót hoặc lặp bản ghi ở ranh giới trang.

Hệ quả thứ ba là bài học đo lường. Con số mang theo: LIMIT ... OFFSET N quét OFFSET+LIMIT hàng rồi vứt N hàng đầu — trang 1 chỉ 0,02ms nhưng OFFSET 500000 quét 500020 hàng (34ms) và trang cuối quét cả bảng (64ms), chậm tuyến tính theo độ sâu; keyset (WHERE id > last_id) nhảy thẳng qua index, 0,03ms mọi trang. Đừng đo phân trang ở trang đầu rồi kết luận nó nhanh — chi phí OFFSET nằm ở độ sâu, và đó là điều kiện phải đo.

Thử ba mươi giây

Trên một bảng lớn, chạy EXPLAIN (ANALYZE) SELECT * FROM bang ORDER BY id LIMIT 20 OFFSET 0 rồi lại với OFFSET 500000 (hoặc một số lớn tùy bảng bạn). So actual rows của node quét: OFFSET 0 quét ~20 hàng, còn OFFSET lớn quét tới OFFSET+20 hàng — và thời gian tăng theo. Rồi thử keyset: EXPLAIN (ANALYZE) SELECT * FROM bang WHERE id > 500000 ORDER BY id LIMIT 20 — bạn sẽ thấy nó chỉ quét 20 hàng và nhanh y như trang đầu. Đó chính là khác biệt "quét rồi vứt" so với "nhảy thẳng" mà bài này đo, và là lý do các feed lớn dùng keyset thay vì OFFSET.