Từ bài viết trước
Cursor Pagination
Kĩ thuật: keyset pagination and seek method
Ở một số trang web, bạn sẽ thấy, bạn không thể đi đến thẳng trang cuối, hoặc nhảy đến 1 trang bất kì, mà thông thường sẽ có nút để sang trang kế và trang phía trước. Như vậy ta có thể assume rằng:
Người dùng sẽ chỉ mở trang 10 sau khi mở trang 9.Vậy, ta chỉ cần nhớ vị trí cuối cùng của bài viết ở trang 9 là ở id bao nhiêu, rồi dùng WHERE để truy vấn từ điểm đó, chứ không cần bỏ dần để đi đến điểm đó nữa
SELECT * FROM my_table WHERE id > 21 ORDER BY id LIMIT 5
Ví dụ: Sort theo thời gian
SELECT *
FROM my_table
WHERE (update_date = '2017-12-21' AND id > 21)
OR update_date > '2017-12-21'
ORDER BY update_date,id LIMIT 5Cơ bản là ta sẽ chỉ lấy các bài viết có cùng thời gian đăng như bài viết cuối và id > , hoặc thời gian lớn hơn bài viết cuối
Để hình dung rõ hơn, hãy thử nhìn vào bảng sau:
| ID | Name |
| 1 | An |
| 2 | Nam |
| 3 | Quan |
| 4 | Tien |
| 5 | Hoang |
| 6 | Nguyen |
| 7 | Duc |
| 8 | Thanh |
| 9 | Hai |
| 10 | Minh |
Ta mong muốn nhận được dữ liệu ở Page 1 như sau
| ID | Name |
| 1 | An |
| 2 | Nam |
| 3 | Quan |
| 4 | Tien |
| 5 | Hoang |
Ta sẽ có câu query để lấy page 2 dạng như sau
Lấy page 1: SELECT * FROM users ORDER BY ID LIMIT 5
SELECT * FROM users WHERE ID > '5' ORDER BY ID LIMIT 5Ta có thể thêm HAL bằng Spring HateOAS để response trả về ở dạng như sau, giúp ta lấy dữ liệu dễ dàng hơn
{
“cursor”: {
“previous_page”: null,
“next_page”: "next___5"
}
}
{
“cursor”: {
“previous_page”: "prev___5" ,
“next_page”: "next___10"
}
}- Cursor sẽ như một con trỏ chỉ tới một record nào đó trong dữ liệu, và khi ta truyền cursor đó vào, backend cần biết ta đang muốn lấy trang tiếp theo hay trang trước từ vị trí con trỏ đó
- Có nhiều cách để làm điều này, ví dụ thêm prefix dạng như prev___, hay next___ như ví dụ trên
- Hoặc đơn giản hơn, ta sẽ truyền thêm một biến chỉ ra là đó là next hay prev
Null Cursor
- Lúc này, từ phía backend, ta có thể sử dụng count hoặc tương tự để kiểm tra xem có trang ở trước đó hay ở sau đó không, rồi trả response ra là null để thể hiện rằng không còn trang nào khác để đi tới ở hướng đó.
Next Cursor
- Có thể bạn đã nắm được về cách để đi tới trang tiếp theo với cursor pagination.
- Ví dụ, ta có một danh sách id tăng dần, thì từ trang có id [1,2,3,4,5], ta sẽ where id > 5 để tới trang tiếp theo
SELECT * FROM entries WHERE (myCol > 5) ORDER BY myCol ASC LIMIT 2; -> 6,7
SELECT * FROM entries WHERE (myCol > 7) ORDER BY myCol ASC LIMIT 2; -> 8,9
- Với một danh sách id giảm dần, ví dụ trang là [10,9,8,7,6] thì ta sẽ where id < 6 để tới trang tiếp theo.
SELECT * FROM entries WHERE (myCol < 5) ORDER BY myCol DESC LIMIT 2; -> 4,3
SELECT * FROM entries WHERE (myCol < 3) ORDER BY myCol DESC LIMIT 2; -> 2,1
Previous Cursor
- Tuy nhiên, việc đi tới trang trước đó trở lên khó khăn hơn. Bởi vì dữ liệu sẽ được trả ra từ phía trái đầu
- Ví dụ, ta đang ở trang id [8,9] , và ta thực hiện truy vấn lấy trang trước đó, 2 phần tử
SELECT * FROM entries WHERE (myCol < 8) ORDER BY myCol ASC LIMIT 2;
- Kết quả sẽ trả về 0,1. Bởi vì nó đang đọc từ trái sang, và khi limit sẽ lấy từ đầu trái chứ không lấy 6,7
Cách giải quyết lấy previous cursor
- Cách để giải quyết vấn đề này, ta sẽ đảo ngược chiều order by, và sau đó khi limit để lấy đúng vùng dữ liệu xong, ta sẽ đảo một lần nữa về chiều đúng
SELECT pagination.* FROM(SELECT * FROM entries WHERE (myCol < 8) ORDER BY myCol DESC LIMIT 2) AS pagination ORDER BY myCol ASC;
- Các bước vừa xảy ra
- 1. Đầu tiên, select các row có id < 8 và order by desc. ta có 7,6,…,1,0
- Sau đó limit 2 để lấy 7,6
- Rồi order by asc lần nữa để lấy thành 6,7 . Là thứ tự ASC như ban đầu ta muốn
Time Complexity
- Next Page Travesal: O(log(N) + L) , ta mấy log(N) để tìm tới điểm bất kì vì nó thực hiện như binary search và ta đã index database. Và L là Limit là số ta phải lặp đến để lấy vùng đầu tiên đã chọn
- Previous Page Traversal: O(log(N) + 2L), sở dĩ là 2L vì ta đã phải đảo chiều 1 lần.
- Thông thường limit được đặt ở 5-20 cho 1 trang, vì vậy có thể coi L là constant và không đáng kể
Triển khai trong code
- Ta có một class thực hiện việc lấy cursor trước hoặc sau. Sử dụng để decode một giá trị cursor base64 hoặc encode 1 giá trị
- Ví dụ ta đang cursor pagination theo column 35, ta sẽ có hàm getEncodeCursor để tạo ra giá trị mã hoá cursor
- Hàm getDecodedCursor sẽ chuyển giá trị mã hoá đó thành số để dùng paging
- Đây là class thực hiện việc paging và nhảy trang. Có thể thấy logic sẽ kiểm tra xem ta đang lấy trang trước hay trang sau, sau đó sort cho phù hợp.
- Class xử lý việc trả về. Tại đây ta sẽ lấy ra element tại đầu list và cuối list của trang hiện tại, rồi tìm thử xem phía trước đó còn trang nào không, hay sau đó còn trang nào hay không
Tham khảo:
![[Java Memory 1] Escaping References trong Java, Call-by-value và sử dụng Defensive copying. Biến trong Java lưu thế nào](https://quochung.cyou/wp-content/uploads/2023/10/image-43.png "[Java Memory 1] Escaping References trong Java, Call-by-value và sử dụng Defensive copying. Biến trong Java lưu thế nào 20")
![[Web] CyouTodo](https://quochung.cyou/wp-content/uploads/2023/08/cyoutodo1.jpg "[Web] CyouTodo 35")
![[Android] P-Connect Social](https://quochung.cyou/wp-content/uploads/2023/04/1-1.jpg "[Android] P-Connect Social 41")
