Triển khai Cursor Pagination trong Java Spring JPA/Hibernate

Triển khai Cursor Pagination trong Java Spring JPA/Hibernate

Từ bài viết trước

http://213.35.113.17:9002/toi-uu-truy-van-pagination-phan-trang-su-dung-spring-boot-java

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
image 17 - quochung.cyou PTIT
Tối ưu truy vấn Pagination (phân trang) sử dụng Spring Boot (Java) 38

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 5

Cơ 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

image 18 - quochung.cyou PTIT

Để hình dung rõ hơn, hãy thử nhìn vào bảng sau:

IDName
1An
2Nam
3Quan
4Tien
5Hoang
6Nguyen
7Duc
8Thanh
9Hai
10Minh

Ta mong muốn nhận được dữ liệu ở Page 1 như sau

IDName
1An
2Nam
3Quan
4Tien
5Hoang

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 5

Ta 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
image 9 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 22
image 10 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 23
  • 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
image 11 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 24
image 12 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 25

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;
image 13 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 26
  • 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;
image 14 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 27
  • 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

image 15 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 28
  • 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
image 16 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 29
  • Đâ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.
image 17 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 30
image 18 - quochung.cyou PTIT
Triển khai Cursor Pagination trong Java Spring JPA/Hibernate 31
  • 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:

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply