Trang 1 nhanh 0,02ms, trang cuối treo 64ms: vì sao OFFSET giết phân trang ở trang sâu

Bạn muốn đọc trang 300 của một cuốn sách không đánh số trang. Cách duy nhất: mở trang đầu, lật từng tờ, đếm tới 300. Trang 5 thì nhanh; trang 300 thì mỏi tay; trang cuối của cuốn nghìn trang thì lật gần hết cả cuốn. Nhưng nếu cuốn sách có đánh số trang và một mục lục, bạn giở thẳng tới trang 300 trong một giây, bất kể nó nằm đâu. Phân trang trong cơ sở dữ liệu có đúng hai cách đó — OFFSET là lật-từng-tờ-đếm, còn keyset là giở-thẳng — và bài này là lần tôi thử cách lật-đếm ở trang 1, thấy nhanh, rồi quên mất nó sẽ ra sao ở trang 500.

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. Đúng cái lật từng tờ để đếm. 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ụt.

Đ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, đúng cuốn sách có đánh số trang giở thẳng tới nơ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.

Cái bẫy: 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 trật 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). 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ề đến code hằng ngày

Điều đầ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.

Điều 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.

Gói lại bằng số: 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à cái nguyên tắc "biến một phép đếm/quét tuyến tính thành một phép tra cứu có mốc" này bạn gặp lại ở khắp nơi ngoài SQL. Cuộn một danh sách khổng lồ trong Android/iOS dùng cursor (con trỏ mốc) chứ không dùng chỉ số tuyệt đối, đúng vì lý do keyset. Một API REST phân trang tốt trả về next_cursor (token trỏ tới vị trí kế) thay vì ?page=500 — chính là keyset đội lốt; GitHub, Stripe, Slack API đều làm vậy. Ngay cả duyệt một LinkedList bằng chỉ số get(i) trong vòng lặp là O(n²) vì mỗi get phải đếm lại từ đầu, trong khi một Iterator giữ mốc và đi thẳng — cùng một bài toán "đếm lại từ đầu" so với "nhớ chỗ đang đứng". Mẫu số chung đáng mang theo: khi cần "đi tới vị trí thứ N" trên một tập lớn, hỏi xem bạn đang bắt hệ thống đếm lại từ đầu mỗi lần hay nhớ mốc và nhảy thẳng; cái sau gần như luôn thắng ở quy mô lớn, và thường chỉ cần đổi từ chỉ số tuyệt đối sang một mốc có index.

Muốn tự thấy thì 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.