Hiểu về Offset và Cursor Pagination - Phần 1

Khi xây dựng các hệ thống web hoặc API, việc phân trang dữ liệu là một vấn đề quan trọng. Có nhiều cách để thực hiện phân trang, nhưng hai phương pháp phổ biến nhất là Offset Pagination và Cursor Pagination. Trong bài viết này, chúng ta sẽ tìm hiểu về Cursor Pagination (ưu và nhược điểm), lý do tại sao nó lại nhanh hơn Offset Pagination, và khi nào bạn nên sử dụng nó.

I. Các phương pháp phân trang phổ biến

1. Offset Pagination

Offset Pagination là phương pháp phổ biến nhất, đặc biệt khi sử dụng SQL với cú pháp:

SELECT * FROM users ORDER BY id DESC LIMIT 10 OFFSET 20;

Câu lệnh trên sẽ lấy 10 bản ghi bắt đầu từ bản ghi thứ 21. Mặc dù đơn giản, nhưng nó có một nhược điểm lớn:

• Hiệu suất giảm dần: Khi số lượng bản ghi tăng lên (ví dụ: OFFSET 10000), cơ sở dữ liệu vẫn phải quét qua tất cả các bản ghi trước đó để đến được vị trí mong muốn, dù chúng không được trả về. Điều này làm giảm tài nguyên và giảm tốc độ xử lý.
• Không ổn định: Nếu dữ liệu thay đổi (thêm hoặc xóa bản ghi) giữa các lần truy vấn, kết quả có thể bị trùng lặp hoặc bỏ sót.

2. Cursor Pagination

Cursor Pagination (phân trang dựa trên con trỏ) sử dụng một "con trỏ" (cursor) – thường là giá trị duy nhất của một cột (như id hoặc timestamp) – để xác định vị trí bắt đầu của trang tiếp theo. Thay vì đếm số bản ghi cần bỏ qua, bạn chỉ cần nói với cơ sở dữ liệu: "Lấy dữ liệu từ điểm này trở đi."

SELECT * FROM users WHERE id > 100 ORDER BY id LIMIT 10;

Ở đây, id > 100 đóng vai trò là con trỏ, và cơ sở dữ liệu chỉ cần tìm các bản ghi lớn hơn giá trị đó. Hãy cùng xem tại sao nó lại hiệu quả hơn.

II. Vì sao Cursor Pagination nhanh hơn?

• Tối Ưu Hiệu Suất Với Index: Khi cột làm con trỏ (như id) được đánh chỉ mục (index), cơ sở dữ liệu có thể nhảy trực tiếp đến vị trí cần thiết mà không phải quét toàn bộ bảng. Điều này đặc biệt hữu ích với các bảng lớn có hàng triệu bản ghi.
• Không Phụ Thuộc Vào Offset: Không cần đếm và bỏ qua các bản ghi trước đó, Cursor Pagination giảm đáng kể tài nguyên tính toán. Thời gian truy vấn gần như không tăng khi dữ liệu tăng lên, miễn là index được tối ưu.
• Ổn định hơn khi dữ liệu thay đổi: Nếu dữ liệu bị chèn hoặc xóa giữa các lần truy vấn, Offset Pagination có thể trả về dữ liệu bị trùng hoặc bỏ sót. Cursor Pagination dựa trên giá trị cụ thể (như id hoặc timestamp), kết quả không bị ảnh hưởng bởi sự thay đổi dữ liệu giữa các lần truy vấn. Điều này rất quan trọng trong các ứng dụng thời gian thực.

III. Phân Tích Kế Hoạch Thực Thi SQL?

Để hiểu rõ hơn sự khác biệt về hiệu suất giữa Offset Pagination và Cursor Pagination, mình đã sử dụng lệnh EXPLAIN ANALYZE trong PostgreSQL để phân tích kế hoạch thực thi của các truy vấn, với bảng user_notes có 1 triệu bản ghi.

CREATE TABLE user_notes (
    id uuid NOT NULL,
    user_id uuid NOT NULL,
    note character varying(500),
    date date NOT NULL,
    CONSTRAINT pk_user_notes PRIMARY KEY (id)
);

INSERT INTO user_notes (id, user_id, note, date)
SELECT 
    gen_random_uuid(), 
    gen_random_uuid(), 
    md5((random() * 1000000)::text), 
    (CURRENT_DATE - (random() * 365)::int)
FROM generate_series(1, 1000000) AS x;

1. Offset Pagination

Đây là truy vấn sử dụng Offset Pagination:

SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
ORDER BY u.date DESC, u.id DESC
LIMIT 1000 OFFSET 900000;

Ở đây, mình cố tình bỏ qua 900,000 bản ghi để thấy rõ được ảnh hưởng đến hiệu suất, sau đó lấy 1,000 bản ghi tiếp theo. Kế hoạch thực thi như sau:

EXPLAIN ANALYZE SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
ORDER BY u.date DESC, u.id DESC
LIMIT 1000 OFFSET 900000;

---
Limit  (cost=165541.59..165541.71 rows=1 width=52) (actual time=695.026..701.406 rows=1000 loops=1)
  ->  Gather Merge  (cost=68312.50..165541.59 rows=833334 width=52) (actual time=342.475..684.567 rows=901000 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=67312.48..68354.15 rows=416667 width=52) (actual time=327.846..450.295 rows=300841 loops=3)
              Sort Key: date DESC, id DESC
              Sort Method: external merge  Disk: 20440kB
              Worker 0:  Sort Method: external merge  Disk: 18832kB
              Worker 1:  Sort Method: external merge  Disk: 18912kB
              ->  Parallel Seq Scan on user_notes u  (cost=0.00..14174.67 rows=416667 width=52) (actual time=1.035..22.876 rows=333333 loops=3)
Planning Time: 0.050 ms
JIT:
  Functions: 8
  Options: Inlining false, Optimization false, Expressions true, Deforming true
  Timing: Generation 0.243 ms (Deform 0.111 ms), Inlining 0.000 ms, Optimization 0.270 ms, Emission 4.085 ms, Total 4.598 ms
Execution Time: 704.217 ms

Thời gian thực thi: 704.217 ms (0.7 giây).

2. Cursor Pagination

Đây là truy vấn sử dụng Cursor Pagination:

SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
WHERE u.date < @date OR (u.date = @date AND u.id <= @lastId)
ORDER BY u.date DESC, u.id DESC
LIMIT 1000;

Ở đây, @date và @lastId là giá trị của bản ghi cuối cùng trên trang trước. Kết quả:

EXPLAIN ANALYZE SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
WHERE u.date < @date OR (u.date = @date AND u.id <= @lastId)
ORDER BY u.date DESC, u.id DESC
LIMIT 1000;

---
Limit  (cost=20605.63..20722.31 rows=1000 width=52) (actual time=37.993..40.958 rows=1000 loops=1)
  ->  Gather Merge  (cost=20605.63..30419.62 rows=84114 width=52) (actual time=37.992..40.921 rows=1000 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=19605.61..19710.75 rows=42057 width=52) (actual time=24.611..24.630 rows=811 loops=3)
              Sort Key: date DESC, id DESC
              Sort Method: top-N heapsort  Memory: 240kB
              Worker 0:  Sort Method: top-N heapsort  Memory: 239kB
              Worker 1:  Sort Method: top-N heapsort  Memory: 238kB
              ->  Parallel Seq Scan on user_notes u  (cost=0.00..17299.67 rows=42057 width=52) (actual time=0.009..21.462 rows=33333 loops=3)
                    Filter: ((date < @date::date) OR ((date = @date::date) AND (id <= @lastId::uuid)))
                    Rows Removed by Filter: 300000
Planning Time: 0.063 ms
Execution Time: 40.993 ms

Thời gian thực thi: 40.993 ms (0.04 giây) – nhanh hơn gần 17 lần so với Offset Pagination.

3. Tối Ưu Cursor Pagination

Để kiểm tra được hiệu suất tối ưu của Cursor Pagination, bạn cần đảm bảo rằng cột làm con trỏ (ở đây là date và id) được đánh chỉ mục. Ví dụ:

CREATE INDEX idx_user_notes_date_id ON user_notes (date DESC, id DESC); -- composite index on date and id

Kết quả:

EXPLAIN ANALYZE SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
WHERE u.date < @date OR (u.date = @date AND u.id <= @lastId)
ORDER BY u.date DESC, u.id DESC
LIMIT 1000;

---
Limit  (cost=0.42..816.55 rows=1000 width=52) (actual time=298.534..298.924 rows=1000 loops=1)
  ->  Index Scan using idx_user_notes_date_id on user_notes u  (cost=0.42..82376.42 rows=100936 width=52) (actual time=298.532..298.888 rows=1000 loops=1)
        Filter: ((date < @date::date) OR ((date = @date::date) AND (id <= @lastId::uuid)))
        Rows Removed by Filter: 900000
Planning Time: 0.068 ms
Execution Time: 298.955 ms

Trong câu truy vấn trên, chúng ta có một index scan sử dụng chỉ mục tổng hợp (idx_user_notes_date_id). Tuy nhiên, thời gian thực hiện là 298.955 ms, cao hơn so với trước đó. Nhưng bình tĩnh, sẽ như thế nào nếu chúng ta sử dụng phép so sánh tuple trong SQL

EXPLAIN ANALYZE SELECT u.id, u.date, u.note, u.user_id
FROM user_notes AS u
WHERE (u.date, u.id) <= (@date, @lastId)
ORDER BY u.date DESC, u.id DESC
LIMIT 1000;

---
Limit  (cost=0.42..432.81 rows=1000 width=52) (actual time=0.020..0.641 rows=1000 loops=1)
  ->  Index Scan using idx_user_notes_date_id on user_notes u  (cost=0.42..43817.85 rows=101339 width=52) (actual time=0.019..0.606 rows=1000 loops=1)
        Index Cond: (ROW(date, id) <= ROW(@date::date, @lastId::uuid))
Planning Time: 0.060 ms
Execution Time: 0.668 ms

Cuối cùng, chỉ mục đã hoạt động. Thời gian thực thi giảm xuống còn 0.668 ms (0.0007 giây), nhanh hơn đáng kể so với các truy vấn trước đó.

IV. Khi nào nên dùng Cursor Pagination?

V. Kết Luận

Cursor Pagination là một công cụ mạnh mẽ giúp tối ưu hóa hiệu suất phân trang, đặc biệt phù hợp với các ứng dụng yêu cầu tốc độ cao và khả năng mở rộng tốt. Không chỉ cải thiện tốc độ truy vấn, nó còn đảm bảo tính ổn định khi xử lý lượng dữ liệu lớn. Tuy nhiên, để triển khai hiệu quả, bạn cần cân nhắc kỹ các yếu tố liên quan. Trong bài viết tiếp theo, mình sẽ hướng dẫn chi tiết cách áp dụng Cursor Pagination trong ASP.NET, giúp bạn tự xây dựng hệ thống phân trang hiệu quả.

Tham khảo

1. Pagination — Offset vs Cursor in MySQL
2. Understanding the Offset and Cursor Pagination
3. Offset and Cursor Pagination explained