Offset / Cursor Paginationについて

Paginationに関するイントロダクションデッキです！具体的にページめくりはどのように行われているのかをまとめています。

Transcript

1. 0 Offset / Cursor Paginationについて 2024-04-12 第86回NearMe技術勉強会 Kaito Asahi
2. 1 Cursor Paginationについて • ページングを実行する方法の1つ • 他の方法として主なものは、Offset Pagination ◦ 詳しくは後ほど紹介 ◦ これと比較しながら見てみる
3. 2 あれ、そもそもPaginationって何？ • 食べログ：ページ番号をしてページング https://tabelog.com/
4. 3 あれ、そもそもPaginationって何？ • Google検索：無限スクロールライク
5. 4 あれ、そもそもPaginationって何？ • X（旧Twitter）：無限スクロールタイムライン https://twitter.com/
6. 5 Why Pagination!? • クエリにとって重要なこと
7. 6 Why Pagination!? • クエリにとって重要なこと 必要なものだけとろう
8. 7 Why Pagination!? • 検索の取得量が大きくなることは、システム停止などの重大なインシデントを 引き起こす！！（これはフィルタの重要性とも言えるが...） TBS NEWS DIG：https://newsdig.tbs.co.jp/articles/-/924207?display=1
10. 9 Paginationのそれぞれの特徴 • Offset Pagination ◦ 重要な要素 ▪ Offset：位置ずらし（skipするデータを考慮してずらす） ◦ 特徴 ▪ Offsetを用いて、検索済みのものをスキップして再度検索 ▪ 次のページがあるかどうかはlimit+1件取得で判定可能 Ex ) 3件ずつ取得するとき（1回目の取得） 1 2 3 4 5 6 取得（次ではskipされる）
11. 10 Paginationのそれぞれの特徴 • Offset Pagination ◦ 重要な要素 ▪ Offset：位置ずらし（skipするデータを考慮してずらす） ◦ 特徴 ▪ Offsetを用いて、検索済みのものをスキップして再度検索 ▪ 次のページがあるかどうかはlimit+1件取得で判定可能 Ex ) 3件ずつ取得するとき（2回目の取得） 1 2 3 4 5 6 取得（次ではskipされる） skip = 3 Offset
12. 11 Paginationのそれぞれの特徴 • Cursor Pagination ◦ 重要な要素 ▪ Cursor : データのある点を指す（Cursor部分はスキップする） ◦ 特徴 ▪ オフセットではなく、ある基準（Cursor）のみをポイント ▪ 次のページがあるかどうかはlimit+1件取得で判定可能 Ex ) 3件ずつ取得するとき（検索したら、Cursorを定める） 1 2 3 4 5 6 Cursor 取得
13. 12 Paginationのそれぞれの特徴 • Cursor Pagination ◦ 重要な要素 ▪ Cursor : データのある点を指す（Cursor部分はスキップする） ◦ 特徴 ▪ オフセットではなく、ある基準（Cursor）のみをポイント ▪ 次のページがあるかどうかはlimit+1件取得で判定可能 Ex ) 3件ずつ取得するとき（Cursorより右の3件を取得！） 1 2 3 4 5 6 Cursor 取得
14. 13 Paginationの⽐較 • Offset Pagination ◦ Pros ▪ 実装は簡単 ▪ あるアイテムの場所の特定がしやすい（何ページ目にいるのか） ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない • OffsetやLimitが固定であるので、タイミングによっては取得したい情報が参照で きない時がある ◦ このようにならないために、limitが重要 ▪ Offset考慮のため、件数が多くなるとパフォーマンスが低下する • 位置依存性が比較的高いので
15. 14 Paginationの⽐較 • Offset Pagination ◦ Pros ▪ 実装は簡単 → 累積カウント数を次のoffsetとして利用してクエリすれば良い 40件検索した！！ n回目の検索 n+1回目の検索 40件を飛ばして、 次の limit 件を とる！！ カウントを引き継いで offsetとして利用
16. 15 Paginationの⽐較 • Offset Pagination ◦ Pros ▪ あるアイテムの場所の特定がしやすい（何ページ目にいるのか） 　　　　→ Offsetは3で、次の検索でヒットしているから、2ページ目にいる！！ 1 2 3 4 5 6 5
17. 16 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない Ex) Offset=3でLimit=3の検索の場合 　　　　　　　　　　　　　　　　　 次に検索される予定のもの 1 2 3 4 5 6
18. 17 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない Ex) Offset=3でLimit=3の検索の場合 （検索中に2#という新しいデータを挿入） 1 2 3 4 5 6 2#
19. 18 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない Ex) Offset=3でLimit=3の検索の場合 1 2 3 4 5 6 2#
20. 19 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない Ex) Offset=3でLimit=3の検索の場合 1 2 3 4 5 6 2# 実際に検索されたもの
21. 20 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない → 重複カウントを引き起こす Ex) Offset=3でLimit=3の検索の場合 また数えられてて草
 1 2 3 4 5 6 2# 実際に検索されたもの
22. 21 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ Offset考慮のため、件数が多くなるとパフォーマンスが低下する Ex) Don’t OFFSET Your SQL Query’s Performance (by Taras Drapalyuk in HACKERNOON) • SELECT * FROM tasks ORDER BY id LIMIT 10 OFFSET 10; ◦ Limit (cost=1.34..2.11 rows=10 width=628)… • SELECT * FROM tasks ORDER BY id LIMIT 10 OFFSET 1000000; ◦ Limit (cost=77270.24..77271.02 rows=10 width=628) https://hackernoon.com/dont-offset-your-sql-querys-performance
23. 22 Paginationの⽐較 • Offset Pagination ◦ Cons ▪ Offset考慮のため、件数が多くなるとパフォーマンスが低下する Ex) Don’t OFFSET Your SQL Query’s Performance (by Taras Drapalyuk in HACKERNOON) • SELECT * FROM tasks ORDER BY id LIMIT 10 OFFSET 10; ◦ Limit (cost=1.34..2.11 rows=10 width=628)… • SELECT * FROM tasks ORDER BY id LIMIT 10 OFFSET 1000000; ◦ Limit (cost=77270.24..77271.02 rows=10 width=628) https://hackernoon.com/dont-offset-your-sql-querys-performance 同じ10件でもコストが大きく異なる！！
24. 23 Paginationの⽐較 • Cursor Pagination ◦ Pros ▪ 件数が増えたときのパフォーマンスの低下が比較的緩い • 無限スクロールなどに有利 ◦ Ex ) X（旧Twitter）タイムライン ▪ 新しいデータが入ってきても、柔軟に対応できる ◦ Cons ▪ Offsetを考慮しなくて良いがために、自分の位置の特定は難しい（ど のページのどこにいるのかなど） • データは何かしらの順序性を持つことは必要 ◦ カーソルはあくまでもその位置より前後しか情報を持たないので
25. 24 Paginationの⽐較 • Cursor Pagination ◦ Pros ▪ 件数が増えたときのパフォーマンスの低下が比較的緩い → オフセットなどを考慮せず、特定のカーソル（ex. ID）から取り出すことができ る！！（まあ、indexを張っていればのはなし...）
26. 25 Paginationの⽐較 • Cursor Pagination ◦ Pros ▪ 新しいデータが入ってきても、柔軟に対応できる → カーソルに指定するカラムは、基本的に順序性を担保している (ULIDなど) → 最新のデータなどは基本的に後方に配置され、重複表示などは防げ　 　 る！！
27. 26 Paginationの⽐較 • Cursor Pagination ◦ Cons ▪ Offsetを考慮しなくて良いがために、自分の位置の特定は難しい（ど のページのどこにいるのかなど） → 1回の検索にて、次の検索時にはカーソルのみを保存する → あるコンテンツがどのページにいるのかは特定しにくい → ページ番号表示には不向き...（どこにいるのか分かりにくい...）
28. 27 Paginationの使い分け • Offset Pagination ◦ Pros ▪ 実装は簡単 ▪ あるアイテムの場所の特定がしやすい（何ページ目にいるのか） ◦ Cons ▪ リアルタイムで増減するデータにすぐ対応できない • OffsetやLimitが固定であるので、タイミングによっては取得したい情報が参照で きない時がある ◦ このようにならないために、limitが重要 ▪ Offset考慮のため、件数が多くなるとパフォーマンスが低下する • 位置依存性が比較的高いので
29. 28 Paginationの使い分け • Offset Pagination ◦ あるアイテムの場所の特定がしやすい（何ページ目にいるのか） → ページ番号付きのPaginationにぴったり！（前後が分かりやすい） 1 2 3 4 5 6
30. 29 Paginationの使い分け • Cursor Pagination ◦ Pros ▪ 件数が増えたときのパフォーマンスの低下が比較的緩い • 無限スクロールなどに有利 ◦ Ex ) X（旧Twitter）タイムライン ▪ 新しいデータが入ってきても、柔軟に対応できる ◦ Cons ▪ Offsetを考慮しなくて良いがために、自分の位置の特定は難しい（ど のページのどこにいるのかなど） • データは何かしらの順序性を持つことは必要 ◦ カーソルはあくまでもその位置より前後しか情報を持たないので
31. 30 Paginationの使い分け • Cursor Pagination ◦ 件数が増えたときのパフォーマンスの低下が比較的緩い ◦ 新しいデータが入ってきても、柔軟に対応できる → 無限スクロールなどの検索件数の多いPaginationにぴったり！ 1こめ 1こめ逃した... 面白かった！！
32. 31 PaginationのSQLによる簡単な実装 • Offset Pagination ◦ SELECT * FROM users ORDER BY id DESC LIMIT 20 OFFSET 20; ◦ OFFSET句を利用 ◦ 逐次的なページングの際には ▪ 検索後に累積カウント数を保存して、次の検索時にoffsetとして引き継ぐ • Cursor Pagination ◦ SELECT * FROM users WHERE id > 20 ORDER BY id DESC limit 20; ◦ WHERE句を利用（Cursorは id=20 にあるという感じ） ◦ Cursor対象になる列にはインデックスを張り、順序性を担保することが重要 ◦ 逐次的なページングの際には ▪ 検索後にCursorを保存して、次のページングの際に引き継ぐ
33. 32 参考⽂献 • Cursor Pagination ◦ https://planetscale.com/learn/courses/mysql-for-developers/examples/cursor-pagination • 図解ページネーション~オフセット・カーソル~ ◦ https://note.com/note_fumi/n/nd5ee70a912d2 • カーソルページネーションを実装した話 ◦ https://lab.mo-t.com/blog/cursor-pagination-implementation • GraphQL Cursor Connections Specification ◦ https://relay.dev/graphql/connections.htm# • Google Cloud - リストのページ分割 - ◦ https://cloud.google.com/apis/design/design_patterns?hl=ja#list_pagination • Don’t OFFSET Your SQL Query’s Performance ◦ https://hackernoon.com/dont-offset-your-sql-querys-performance
34. 33 イラスト利⽤ • 指差しアイコン ◦ https://illustcenter.com/2022/08/19/sdesign_00051/
35. 34 Thank you