Offset hay cursor pagination: vì sao trang 4.000 chậm rì và keyset query cứu ra sao

Team mobile mở ticket: "feed càng kéo xuống càng chậm". Trang 1 API trả về trong 15 ms. Ông user nào kéo lâu lâu tới trang 4.000 thì ngồi chờ 2,8 giây. Cùng lúc đó, job export ban đêm chạy ?page=1..N qua 3 triệu đơn hàng đã từ 4 phút lên 40 phút, còn team support thì báo có đơn bị export hai lần, có đơn lại mất tiêu.

Ba triệu chứng này chung một nguyên nhân: LIMIT ... OFFSET .... Offset pagination là mặc định ở framework nào cũng có vì dễ hiểu, nhưng nó tốn công tỉ lệ thuận với độ sâu của trang, và nó mô tả một vị trí ("dòng thứ 80.000") chứ không phải một chỗ trong dữ liệu ("sau đúng dòng này"). Keyset pagination, hay còn gọi là cursor pagination, giải quyết cả hai chuyện đó.

Vì sao OFFSET càng sâu càng chậm

Database không nhảy thẳng tới dòng 200.000 được. Nó không biết dòng 200.000 nằm đâu cho tới khi đã sinh ra đủ 199.999 dòng trước đó theo đúng thứ tự. Kể cả có index chuẩn trên cột sort, engine vẫn phải đi từ đầu index, đếm rồi bỏ đi OFFSET entry, sau đó mới trả về LIMIT dòng.

-- Page 1: fast
SELECT id, title, created_at FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 0;

-- Page 10,000: the server reads 200,020 index entries and throws 200,000 away
SELECT id, title, created_at FROM posts
ORDER BY created_at DESC, id DESC
LIMIT 20 OFFSET 200000;

Nếu query không được index cover thì còn tệ hơn: MySQL có thể phải đọc nguyên dòng cho từng entry bị bỏ qua, hoặc bỏ luôn index mà filesort toàn bộ tập dữ liệu đã lọc. Chạy EXPLAIN ANALYZE cho một trang sâu là thấy số "rows examined" tăng tuyến tính theo offset, trong khi kết quả vẫn chỉ 20 dòng. Trang 1 và trang 10.000 trả về cùng lượng dữ liệu, nhưng trang sau tốn gấp mười ngàn lần công sức.

Còn một vấn đề về tính đúng nữa. Offset là tương đối so với trạng thái hiện tại của bảng:

• Có post mới chèn lên đầu trong lúc user đang ở trang 3. Mọi thứ dời xuống một dòng, dòng đầu tiên của trang 4 chính là dòng cuối user đã thấy ở trang 3. Bị trùng.
• Một post ở trang 2 bị xóa. Mọi thứ dời lên một dòng, dòng lẽ ra đứng đầu trang 4 giờ thành dòng cuối trang 3, mà trang 3 thì user load rồi. Bị sót.

Với người lướt bảng admin thì cái này chỉ hơi khó chịu. Với job export, job sync hay infinite feed thì đó là bug thiệt sự.

Keyset pagination chạy ra sao

Thay vì nói với database "bỏ qua N dòng", mình nói "đưa mình các dòng nằm sau dòng này". Client gửi lại giá trị sort của dòng cuối cùng nó nhận được, query kế tiếp biến giá trị đó thành điều kiện WHERE:

-- First page
SELECT id, title FROM posts
ORDER BY id DESC
LIMIT 20;

-- Next page: the client sends back the last id it saw, e.g. 981234
SELECT id, title FROM posts
WHERE id < 981234
ORDER BY id DESC
LIMIT 20;

Có index trên id, engine seek thẳng tới 981234 rồi đọc 20 entry. Chi phí ở trang 1 hay trang 1.000.000 đều như nhau, cỡ O(log n + limit).

Nó cũng ổn định. Chèn post mới hơn không làm thay đổi tập dòng cũ hơn 981234, xóa một dòng ở trang trước cũng không xê dịch gì. Dòng nào cũng được trả về đúng một lần, đúng thứ tự, miễn là bản thân sort key không đổi.

Đây là nguyên vòng request, kèm chiêu "lấy dư một dòng" để biết còn trang sau hay không mà khỏi chạy COUNT(*):

Cursor ghép cho cột sort không unique

Sort chỉ theo id thì hiếm lắm. Feed sort theo created_at, shop sort theo price, bảng xếp hạng sort theo score. Mấy cột này đều không unique: một lần import hàng loạt có thể tạo 500 dòng cùng một giây created_at. Nếu cursor chỉ là created_at < '2026-10-20 08:15:00' thì mọi dòng trùng timestamp đó mà chưa kịp nằm trong trang trước sẽ bị bỏ qua âm thầm. Còn xài <= thì chúng bị lặp hoài.

Cách sửa là thêm tiebreaker: cho một cột unique (thường là khóa chính) làm sort key cuối cùng, và cursor là một tuple gồm tất cả các cột sort.

CREATE INDEX posts_created_at_id_index ON posts (created_at, id);

-- Row constructor form (MySQL 8 and PostgreSQL can use the index for this range)
SELECT id, title, created_at FROM posts
WHERE (created_at, id) < ('2026-10-20 08:15:00', 981234)
ORDER BY created_at DESC, id DESC
LIMIT 21;

-- Expanded form: same meaning, works everywhere, and also handles mixed directions
SELECT id, title, created_at FROM posts
WHERE created_at < '2026-10-20 08:15:00'
   OR (created_at = '2026-10-20 08:15:00' AND id < 981234)
ORDER BY created_at DESC, id DESC
LIMIT 21;

Ba quy tắc để cái này chạy đúng:

1. ORDER BY phải hoàn toàn xác định: danh sách cột kết thúc bằng một cột unique.
2. Phép so sánh trong WHERE dùng đúng các cột đó, cùng thứ tự, cùng chiều với ORDER BY.
3. Có index mà các cột khớp với thứ tự đó, để database seek chứ không scan. Trong InnoDB, secondary index (created_at) vốn đã mang theo khóa chính, nhưng khai báo rõ (created_at, id) thì ý đồ rõ ràng hơn và query plan dễ đoán hơn.

Dạng row constructor (a, b) < (x, y) gọn, MySQL 8 lẫn PostgreSQL đều tối ưu nó thành range. Dạng OR khai triển thì nghĩa y chang, và là dạng bắt buộc khi các cột sort ngược chiều nhau, như ORDER BY price ASC, id DESC: đổi toán tử theo từng cột (price > ? OR (price = ? AND id < ?)) và tạo index khớp (price ASC, id DESC).

MySQL 8.0 có descending index thiệt sự, nên (price ASC, id DESC) được scan một lượt. Ở bản cũ hơn, sort ngược chiều thường đồng nghĩa với filesort.

cursorPaginate trong Laravel

Laravel có sẵn keyset pagination. Đổi paginate() thành cursorPaginate() và nhớ cho thứ tự sort kết thúc bằng một cột unique:

namespace App\Http\Controllers\Api;

use App\Http\Resources\PostResource;
use App\Models\Post;
use Illuminate\Http\Request;
use Illuminate\Http\Resources\Json\AnonymousResourceCollection;

final class PostFeedController
{
    public function __invoke(Request $request): AnonymousResourceCollection
    {
        $perPage = min((int) $request->integer('per_page', 20), 100);

        $posts = Post::query()
            ->select(['id', 'title', 'excerpt', 'created_at'])
            ->where('status', 'published')
            ->orderByDesc('created_at')
            ->orderByDesc('id')
            ->cursorPaginate($perPage)
            ->withQueryString();

        return PostResource::collection($posts);
    }
}

Bên dưới, paginator lấy perPage + 1 dòng, đọc các cột order từ query rồi dựng điều kiện khai triển where ... or (... and ...) từ cursor đã decode. Bản thân cursor là JSON gồm giá trị các cột sort cộng thêm một cờ cho biết nó trỏ tới hay trỏ lui, được base64 encode và gửi qua query string cursor. Trả qua API resource thì khối meta có path, per_page, next_cursor, prev_cursor, còn links.next là URL gọi được liền.

Để ý cái gì không có: không total, không last_page, không current_page. Paginator không bao giờ chạy COUNT(*), mà trên bảng lớn có filter thì COUNT(*) hay là query chậm nhất của cả request. prev_cursor cũng xài được, nên đi lui vẫn ổn.

Những gì framework trông chờ ở mình:

• Cột nào trong orderBy cũng phải được select và không được chứa NULL. Giá trị cursor được so bằng < và >, mà so sánh SQL với NULL thì không bao giờ đúng.
• Order theo expression chỉ chạy khi expression đó có alias và nằm trong select. Expression có binding tham số thì không hỗ trợ.
• Cursor chỉ được encode, không mã hóa cũng không ký. Client decode được, sửa giá trị rồi gửi lại. Với feed public thì vô hại vì query vẫn áp các filter where của mình, nhưng đừng để thông tin bí mật trong cột sort.

Tự viết cursor

Có lúc mình muốn kiểm soát format: cursor có chữ ký để khỏi bị sửa, chuỗi ngắn cho app mobile, hoặc xài cùng logic phân trang cho query builder thuần hay kết quả Elasticsearch. Pattern này đủ nhỏ để tự viết. Trước tiên là một value object encode và ký tuple:

namespace App\Support\Pagination;

use InvalidArgumentException;

final class FeedCursor
{
    public function __construct(
        public readonly string $createdAt,
        public readonly int $id,
    ) {}

    public static function fromRow(object $row): self
    {
        return new self((string) $row->created_at, (int) $row->id);
    }

    public function encode(string $key): string
    {
        $payload = json_encode([$this->createdAt, $this->id], JSON_THROW_ON_ERROR);
        $body = rtrim(strtr(base64_encode($payload), '+/', '-_'), '=');
        $sig = substr(hash_hmac('sha256', $body, $key), 0, 16);

        return $body . '.' . $sig;
    }

    public static function decode(string $cursor, string $key): self
    {
        [$body, $sig] = array_pad(explode('.', $cursor, 2), 2, '');

        if (! hash_equals(substr(hash_hmac('sha256', $body, $key), 0, 16), $sig)) {
            throw new InvalidArgumentException('Invalid cursor.');
        }

        $json = base64_decode(strtr($body, '-_', '+/'), true);
        $data = $json === false ? null : json_decode($json, true);

        if (! is_array($data) || count($data) !== 2 || ! is_int($data[1])) {
            throw new InvalidArgumentException('Malformed cursor.');
        }

        return new self((string) $data[0], $data[1]);
    }
}

Trong query, decode cursor nhận được, áp đúng điều kiện khai triển created_at < ? OR (created_at = ? AND id < ?) ở trên, lấy limit + 1 dòng, và chỉ encode FeedCursor::fromRow() của dòng cuối khi dòng dư thật sự có trả về.

Cắt chữ ký còn 16 ký tự hex là đánh đổi có chủ đích: cursor ngắn mà vẫn đủ khó giả mạo cho một token phân trang. Khi rotate key thì mọi cursor đang lưu hành đều hết hiệu lực, nên client cần xử lý 400 Invalid cursor bằng cách load lại từ trang đầu.

Thiết kế API với cursor

Keyset pagination thay đổi hợp đồng API, nên thiết kế API xoay quanh nó chứ đừng gắn tạm cursor vô một API kiểu số trang:

• Cursor phải opaque. Ghi tài liệu là "chuỗi bạn gửi lại nguyên xi". Client nào tự parse cursor sẽ gãy vào ngày mình thêm cột vô sort.
• Trả next_cursor và has_more, hoặc null khi hết. Infinite scroll hay job sync chỉ cần nhiêu đó.
• Gắn cursor với query. Client đổi sort hay filter thì cursor cũ vô nghĩa. Hoặc từ chối nó (lưu hash của filter trong cursor), hoặc ghi rõ filter phải giữ nguyên giữa các trang.
• Giới hạn limit. min($perPage, 100) chặn client xin 50.000 dòng trong một request.
• Tổng số dòng thì cung cấp riêng, nếu thật sự cần. UI cần hiện "1.234 kết quả" thì trả số ước lượng từ cache, đừng COUNT(*) ở mỗi trang.
• Xài cursor cho endpoint sync. "Đưa mình mọi thứ thay đổi từ X tới giờ" chính là keyset trên (updated_at, id), là xương sống của job export incremental.

Kiểm thử keyset pagination

Bug nằm ở mấy chỗ biên: timestamp trùng, trang cuối, và dữ liệu thay đổi giữa hai request. Test tốt là đi hết các trang bằng cách follow links.next tới khi nó null, rồi kiểm tra dòng nào cũng thấy đúng một lần. Seed một cục dòng có cùng created_at chính là cách bắt lỗi thiếu tiebreaker.

use App\Models\Post;
use Illuminate\Support\Carbon;

it('walks every post exactly once even when timestamps collide', function () {
    $sameMoment = Carbon::parse('2026-10-20 08:00:00');

    Post::factory()->count(30)->create(['status' => 'published', 'created_at' => $sameMoment]);
    Post::factory()->count(25)->create(['status' => 'published']);

    $seen = [];
    $url = '/api/posts?per_page=7';

    while ($url !== null) {
        $response = $this->getJson($url)->assertOk();
        $seen = [...$seen, ...array_column($response->json('data'), 'id')];
        $url = $response->json('links.next');
    }

    expect($seen)->toHaveCount(55)
        ->and(array_unique($seen))->toHaveCount(55)
        ->and($seen)->toEqualCanonicalizing(Post::pluck('id')->all());
});

Nên có thêm test thứ hai: load trang 1, chèn thêm post mới hơn, load trang 2 rồi assert hai trang không có id nào trùng. Chọn per_page lẻ lẻ như 7 để ranh giới trang rơi đúng giữa nhóm timestamp trùng. Sau này ai lỡ xóa orderByDesc('id') là test đầu tiên fail liền.

Những lỗi hay gặp

• Không có tiebreaker unique. Lỗi phổ biến nhất. Dòng biến mất âm thầm ở ranh giới trang mỗi khi cột sort có giá trị trùng.
• Index không khớp thứ tự sort. Keyset chỉ nhanh khi database seek được. Coi EXPLAIN: mình muốn thấy access kiểu range trên composite index, không phải filesort.
• Cột sort nullable. NULL phá phép so sánh. Dùng COALESCE về một giá trị mặc định rồi index expression đó, hoặc loại dòng NULL, hoặc sort theo cột không null.
• Sort key thay đổi được. Sort theo updated_at mà một dòng được update trong lúc có người đang phân trang thì nó có thể nhảy lên trước cursor và bị thấy hai lần, hoặc nhảy ra sau và bị sót. Với job sync thì đó thường là điều mình muốn; với feed thì nên sort theo cột bất biến.
• Muốn "nhảy tới trang 57". Keyset chỉ biết trang trước và trang sau. Sản phẩm cần số trang thì màn hình đó cứ giữ offset.
• Lọc sau khi fetch. Bỏ bớt dòng trong PHP sau khi query (check quyền, rule hiển thị) thì trang sẽ bị thiếu dòng. Đẩy mấy điều kiện đó vô SQL.

Khi nào xài offset, khi nào xài keyset

Xài offset (paginate() hoặc simplePaginate()) khi:

• dữ liệu nhỏ hoặc user không bao giờ đi quá vài trang, kiểu bảng admin có filter;
• UI cần số trang, tổng số, hoặc "nhảy tới trang N";
• thứ tự sort do user tự chọn trên nhiều cột và mình không thể index hết mọi tổ hợp.

Xài keyset (cursorPaginate() hoặc cursor tự viết) khi:

• bảng lớn và người hay job đi sâu: infinite scroll, activity feed, notification, lịch sử chat;
• export, sync hay backfill nguyên bảng theo batch. Với job chạy một lần trong Laravel thì lazyById() và chunkById() vốn đã dùng keyset bên trong;
• có dòng được chèn hoặc xóa trong lúc client phân trang và không chấp nhận trùng hay sót;
• API public và mình muốn latency ổn định bất kể client đi sâu cỡ nào.

Cách dung hòa hay gặp: màn hình admin giữ offset có số trang, còn API public và mọi job nền thì xài cursor. Query từng tốn 2,8 giây ở trang 4.000 giờ cũng chỉ là một lần seek 15 ms như trang 1, và job export hết làm rớt đơn.