47

コンテンツのランキングがすぐに変わる可能性がある場合、ページネーションは難しく、ランキングがユーザーごとに異なる場合はさらに難しくなります。(無限スクロールは、リンクが見えないページネーションの一種として扱いましょう。) 2 つの難しい問題があります。新しく追加されたコンテンツが上部に表示されることと、コンテンツが再ランク付けされることです。

新しく追加されたコンテンツのことは忘れて、それを表示するにはページ 1 を更新する必要があることを受け入れましょう。また、 pure を行っているふりをしましょうORDER BY position。他のもので注文している場合は、ウィンドウ関数を使用する必要がある場合があります。私たちのページには、1 ページあたり 4 行の動物があります。彼らは始めます：

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  1 |        1 | Alpacas   |
|  2 |        2 | Bats      |
|  3 |        3 | Cows      |
|  4 |        4 | Dogs      |
|  5 |        5 | Elephants |
|  6 |        6 | Foxes     |
|  7 |        7 | Giraffes  |
|  8 |        8 | Horses    |
+----+----------+-----------+

ページ 1 をフェッチした後、ページ 2 をフェッチする前に、多くのアイテムが移動します。DBは次のとおりです。

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  4 |        1 | Dogs      |
|  2 |        2 | Bats      |
|  1 |        3 | Alpacas   |
|  5 |        4 | Elephants |
|  6 |        5 | Foxes     |
|  7 |        6 | Giraffes  |
|  3 |        7 | Cows      |
|  8 |        8 | Horses    |
+----+----------+-----------+

次の 3 つの一般的なアプローチがあります。

オフセット/リミットアプローチ

これは典型的な素朴なアプローチです。Railsでは、will_paginateとKaminariがどのように機能するかです. ページ 2 をフェッチする場合は、

SELECT * FROM animals
ORDER BY animals.position
OFFSET ((:page_num - 1) * :page_size) 
LIMIT :page_size;

行5〜8を取得します。私は象を見ることはないだろうし、牛は二度見るだろう.

最終確認 ID アプローチ

Reddit は別のアプローチを採用しています。ページ サイズに基づいて最初の行を計算する代わりに、クライアントは、ブックマークのように、最後に表示したアイテムの ID を追跡します。「次へ」を押すと、そのブックマークから探し始めます。

SELECT * FROM animals
WHERE position > (
  SELECT position FROM animals 
  WHERE id = :last_seen_id
) 
ORDER BY position
LIMIT :page_size;

場合によっては、これはページ/オフセットよりもうまく機能します。しかし、私たちの場合、最後に表示された投稿である Dogs がすぐに 1 位になりました。したがって、クライアントは を送信し?last_seen_id=4、私のページ 2 はコウモリ、アルパカ、ゾウ、キツネです。見逃した動物はいませんが、コウモリとアルパカは 2 回見ました。

サーバー側の状態

HackerNews (および現在の私たちのサイト) は、サーバー側の継続によってこれを解決します。それらは結果セット全体を (または少なくとも数ページ前に)保存し、"More" リンクはその続きを参照します。ページ 2 をフェッチするときは、「元のクエリのページ 2」を要求します。同じオフセット/制限計算を使用していますが、元のクエリに反しているため、物事が移動したことは気にしません。ゾウ、キツネ、キリン、ウマが見えます。重複も見逃されたアイテムもありません。

欠点は、サーバーに多くの状態を保存する必要があることです。HN では、それは RAM に保存されます。実際には、これらの継続は、[詳細] ボタンを押す前に期限切れになることが多く、有効なリンクを見つけるためにページ 1 に戻る必要があります。ほとんどのアプリケーションでは、それを memcached に格納することも、データベース自体に格納することもできます (独自のテーブルを使用するか、保持可能なカーソルを使用して Oracle または PostgreSQL に格納します)。アプリケーションによっては、パフォーマンスが低下する場合があります。少なくとも PostgreSQL では、適切なデータベース接続を再度ヒットする方法を見つける必要があります。これには、多くのスティッキー状態または巧妙なバックエンド ルーティングが必要です。

考えられるアプローチはこれら 3 つだけですか? そうでない場合、これについて読むための Google ジュースを提供してくれるコンピューター サイエンスの概念はありますか? 結果セット全体を保存せずに継続アプローチを近似する方法はありますか? 長期的には、複雑なイベント ストリーミング/ポイント イン タイム システムがあり、「ページ 1 を取得した時点での結果セット」は永久に導出可能です。それどころか…？

4

5 に答える 5

8

オラクルはこれをうまく処理します。カーソルが開いている限り、必要な回数だけフェッチでき、結果には常にカーソルが開かれた時点が反映されます。元に戻すログのデータを使用して、カーソルが開かれた後にコミットされた変更を仮想的にロールバックします。

必要なロールバック データがまだ利用可能である限り、機能します。最終的にログはリサイクルされ、ロールバック データは使用できなくなるため、ログ スペースやシステム アクティビティなどに応じて、ある程度の制限があります。

残念ながら (IMO)、このように機能する他の DB は知りません。私が扱ってきた他のデータベースでは、ロックを使用して読み取りの一貫性を確保していますが、これは、非常に短期間以上の読み取りの一貫性が必要な場合に問題になります。

于 2012-03-16T23:56:39.973 に答える
4

当面はサーバー側の状態アプローチを使用し、最初のクエリで結果全体をキャッシュして、常に一貫性のあるリストを返します。これは、クエリがすでにすべての行を返している限り機能します。最終的には最近傍アプローチを使用する必要があり、それは機能しません。

しかし、次の条件が満たされている限り、非常にうまくスケーリングできる第 4 の可能性があると思います。

  1. 重複がないという保証は必要ありませんが、可能性が高いだけです
  2. 重複を避ける限り、スクロール中に一部のコンテンツが欠落しても問題ありません

解決策は、「最後に見た ID」解決策の変形です。クライアントに 1 つではなく、5 つ、10 つ、または 20 個のブックマークを保持してもらいます。これは、効率的に保存できるように十分な数です。クエリは次のようになります。 

SELECT * FROM posts
WHERE id > :bookmark_1
AND id > :bookmark_2
...
ORDER BY id

ブックマークの数が増えるにつれて、(a) n 個のブックマークすべてを過ぎた時点から開始しているが、(b) いずれにせよ重複したコンテンツがすべて再ランク付けされているために表示される可能性は急速に低下します。

穴がある場合、または将来的により良い回答がある場合は、喜んでこの回答を受け入れません。

于 2012-04-01T22:17:09.533 に答える
1

パーティーに非常に遅れましたが、ここで私たちが実験したことがあります. ユーザーが行ったり来たりするページではなく、継続的な読み込みを使用しています。

クライアントは、表示したすべての ID のリストを作成するため、最初のセットの後は次のようになります: 4,7,19,2,1,72,3

さらにコンテンツをロードすると、同じソートで同じクエリを実行しますが、これを追加します: WHERE id NOT IN (4,7,19,2,1,72,3)

NOT IN リストは急速に大きくなる可能性があります。通常、内部ツールには大量の結果がないため、これは問題ではありません。

別のアイデアを追加したい。おそらく、サーバー側の追加がこれに適用される可能性があります。ユーザーが検索すると、取得したすべての ID が、検索へのリンクを含むテーブルに追加されます。クライアントがさらに必要な場合は、検索 ID を提供する (またはサーバー側の状態を使用する) だけでよく、クエリは検索データに参加できます。

于 2015-04-11T19:08:42.403 に答える