おことわり

こちらは、プログラミング初学者である筆者が、ポートフォリオ作成の際に得た知識を記録するものです。
誤りや改善点については、お手柔らかにご教示いただけますと幸甚です。

概要

シーク法を用いたカーソル・ページネーションを実装します。
kaminariなどで使用されているオフセット・ページネーションと比べて、高速に動作することが特徴です。実際のコードの後に、簡単な説明を記載します。

動作環境

カテゴリー	技術
バックエンド	Ruby 3.2.2, Ruby on Rails 7.1.3.2
データベース	MySQL 8.3.0
インフラ	Docker

用語の整理

オフセット・ページネーション
カーソル・ページネーション
オフセット法
シーク法

これらの用語を、筆者は下表のように整理しました。

分類	名称1	名称2
ページネーション技術	オフセット・ページネーション	カーソル・ページネーション
データ取得方法	オフセット法	シーク法

「オフセット・ページネーション」で使われるデータ取得方法が「オフセット法」
「カーソル・ページネーション」で使われるデータ取得方法が「シーク法」

という理解で話を進めます。

実装

想定

ユーザー一覧画面に、ページネーションを実装する
- 1ページあたり最大表示ユーザー数は10とする
- 十分なレコード数があるとき、次のページに進むか、手前のページに戻ることができる

コード

Model

models/user.rb

# frozen_string_literal: true

class User < ApplicationRecord
  USERS_PER_PAGE = 10

  # (略)

  class << self
    def resolve_users_with_pagination(last_user_id: nil, first_user_id: nil)
      resolve_users_and_cursors(last_user_id:, first_user_id:)
    end

    private

    def resolve_users_and_cursors(last_user_id: nil, first_user_id: nil)
      users = resolve_users(last_user_id:, first_user_id:)
      # 遷移先のページに表示するレコードが存在しないとき、最初のレコードを返す
      users = all.limit(USERS_PER_PAGE) if users.empty?

      # カーソルを取得
      next_cursor = users.last&.id
      prev_cursor = users.first&.id

      [users, next_cursor, prev_cursor]
    end

    def resolve_users(last_user_id: nil, first_user_id: nil)
      if last_user_id
        # last_user_id が存在する場合、そのIDより大きいユーザーを取得（次のページ）
        where('id > ?', last_user_id).limit(USERS_PER_PAGE)
      elsif first_user_id
        # first_user_id が存在する場合、そのIDより小さいユーザーを取得（前のページ）
        users = where('id < ?', first_user_id).order(id: :desc).limit(USERS_PER_PAGE)
        users.reverse
      else
        # 最初のページの場合
        all.limit(USERS_PER_PAGE)
      end
    end
  end
end

Controller

controllers/users_controller.rb

# frozen_string_literal: true

class UsersController < ApplicationController

  # (略)

  # GET /users
  def index
    @last_user_id = params[:last_user_id]
    @first_user_id = params[:first_user_id]
    @users, @next_cursor, @prev_cursor = User.resolve_users_with_pagination(
      last_user_id: @last_user_id,
      first_user_id: @first_user_id
    )
  end

  # (略)

end

View

views/users/index.html.erb

<%# (略) %>

<%# ページングナビゲーション表示位置に、以下を追加する %>
  <nav class="pagination" role="navigation" aria-label="pagination">
    <ul class="pagination-list">
      <li style="margin: 0;">
        <%= link_to '< prev', users_path(first_user_id: @prev_cursor), class: 'pagination-previous' %>
      </li>

      <li style="margin: 0;">
        <%= link_to 'next >', users_path(last_user_id: @next_cursor), class: 'pagination-next' %>
      </li>
    </ul>
  </nav>

Schema

db/schema.rb

ActiveRecord::Schema[7.1].define(version: 0) do
  create_table "users", charset: "utf8mb4", collation: "utf8mb4_bin", comment: "ユーザー", force: :cascade do |t|
    t.string "email", null: false, comment: "メールアドレス"
    t.string "password_digest", null: false, comment: "パスワード"
    t.datetime "created_at", null: false
    t.datetime "updated_at", null: false
  end
end

簡単な解説

2種のページネーションをざっくり比較する

広く使用されているオフセット・ページネーションと、今回実装したカーソル・ページネーションの特徴は、それぞれ以下のとおりです。

項目	オフセット・ページネーション	カーソル・ページネーション
位置	先頭からの絶対位置で取得する	記録した基準からの相対位置で取得する
長所	実装が容易特定ページ番号にすぐアクセスできる	レコード数が多くなっても高速に動作する連続的なデータ取得が容易
短所	ページ数が後になるほど、動作が遅くなる	特定ページ番号にアクセスすることが難しい前後のページ移動のみになる
ページ指定	ページ番号を直接指定できる	直接指定できない
データ変更	データの変化で結果がズレることがある	データの変化によるズレがない
実装	多くのGemや記事が存在し、容易	カーソル管理が必要でやや複雑
適した場面	データがあまり動的でない場面ページ番号を指定したい場面レコード数が少ない場面	データの変化が激しい場面レコード数が多い場面無限スクロールを実装したい場面

Twitterクローンのように、レコード数が膨大でデータの変化が激しいサービスを想定するのであれば、カーソル・ページネーションが適していることがわかります。
以下に、それぞれの特徴をもう少し詳しく解説します。

オフセット・ページネーションの特徴

オフセット・ページネーションでは、例えば以下のようなSQL文が走ります。

offset_pagination

SELECT * FROM users
ORDER BY id ASC
LIMIT 10 OFFSET 10;

このSQL文の内容は、

users テーブルから取得しなさい
id 昇順で並べた
10個のレコードを
ただし、初めの10レコードは差し引きなさい

と読むことができます。
この OFFSET を使ってページネーションを実現するのが、オフセット・ページネーションというわけです。
「offset」という英単語は、「相殺する」「差引き勘定する」という意味を持ちます。
オフセット・ページネーションで後のページになるほどパフォーマンスが低下する理由が、この「相殺」の部分にあります。
次では、データベースからレコードを取得する過程を、辞書を引く作業に例えて考えてみます。

辞書で考えるオフセット・ページネーション

これからAさんは、命令に従って辞書を引きます。
ただし、Aさんは辞書を引いてもすぐに内容を忘れてしまいます。

早速最初の命令です。

国語辞典から
50音順で並べたとき
冒頭から10個の見出し語を引きなさい

あ, ア, ......, アーサ感度, アース ─『新明解国語辞典第七版（三省堂）』より

続いて、2つ目の命令です。
ここでAさんは「前回 "アース" まで引いたから……」というようなことは記憶していません。

国語辞典から
50音順で並べたとき
冒頭から10個の見出し語を引きなさい
ただし、最初の10個は読み飛ばしなさい

2つ目の命令では、辞書の冒頭から10個の見出し語を読み飛ばすようです。
読み飛ばす単語を数える分、少し面倒そうに見えます。
同様の命令を3つ目、4つ目、……と続けていくと、読み飛ばす見出し語の数も20個、30個、……と増加します。
すると、見出し語を数えるのにかかる時間も増えていくことが想像できるでしょう。
これが、オフセット・ページネーションが後のページになるほど動作が遅くなる理由です。

さらに、データの変化によって結果がズレることがあるという点も、辞書の例えで考えてみましょう。
2つ目の命令を終えたところで、辞書に改訂が入ったとします。
改訂前の17番目と18番目の見出し語の間に、2つの新しい見出し語が加わったとしましょう。
Aさんに3つ目の命令が下ります。

国語辞典から
50音順で並べたとき
冒頭から10個の見出し語を引きなさい
ただし、最初の20個は読み飛ばしなさい

Aさんは冒頭から20個の見出し語を読み飛ばし、21番目から30番目までの見出し語を引きます。
すると、改訂前に19番目と20番目にあった見出し語が改訂後に21番目と22番目になっているため、2つ目と3つ目の命令で引いた内容に重複が発生します。

順番	改訂前	改訂後
17	アートペーパー	アートペーパー
18	アーバン	アートポスター
19	アーベント	アートワーク
20	アーム	アーバン
21	アームチェア	アーベント
22	アームホール	アーム

新しい命令が下るたびに、辞書の冒頭を起点にして見出し語数を数えるため、このようなズレが発生しうるのです。
オフセット・ページネーションでは、ページ読み込みのたびにデータベースの先頭を基準として数え直すため、常に絶対的な位置でレコードを取得していると言えます。

カーソル・ページネーションの特徴

カーソル・ページネーションでは、例えば以下のようなSQL文が走ります。

cursor_pagination

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

このSQL文の内容は、

users テーブルから取得しなさい
id の値が30より大きいものについて
id 昇順で並べた
10個のレコードを

と読むことができます。
IDなど基準となる値を記録し、条件に合ったレコードを探すことでページネーションを実現するのが特徴です。
先ほどと同じように、辞書を引く作業に例えて考えてみます。

辞書で考えるカーソル・ページネーション

これからBさんは、命令に従って辞書を引きます。
ただし、Bさんは辞書を引いてもすぐに内容を忘れてしまいます。

早速最初の命令です。

国語辞典から
50音順で並べたとき
冒頭から10個の見出し語を引きなさい

あ, ア, ......, アーサ感度, アース ─『新明解国語辞典第七版（三省堂）』より

これは、さっきのAさんと同じです。
2つ目の命令が下ります。

国語辞典から
"アース" より後の見出し語を
50音順で並べたとき
冒頭から10個の見出し語を引きなさい

"アース" を探した後、次の10個を引くだけの簡単な作業です。
同様の命令がいくつ下されても、基準となる見出し語が示されるため、すぐに引くことができます。
辞書の改訂で見出し語が増減しても、重複することはありません。
示された基準となる見出し語が辞書になくても、辞書順の並び方が理解できていれば、基準点を見つけることが可能です。

基準とする値は、比較可能なデータ型でなくてはなりません。
加えて、唯一性があるほうが望ましいでしょう。
効率的な探索のため、インデックスも付与されているべきです。

このように、取得したレコードの最初と最後の値を記録しておき、前後のページに移動する際に基準点とするのがカーソル・ページネーションの考え方です。
基準点が次々と変化し、相対的な位置で次のレコードを取得していると言えます。

クエリ実行時間を比較する

ここまでで、オフセット・ページネーションとカーソル・ページネーションにはデータ探索の方法に違いがあることがわかりました。
次に、その違いで実行時間がどれほど変わるのかを確認します。
1000万件超のレコードを作成し、オフセット法とシーク法でデータ取得にかかる時間を比較します。
ここでは、Twitterクローンアプリのpostsテーブルを使って検証しています。

	Duration(sec)	Query
Offset	11.3933	SELECT * FROM posts ORDER BY id LIMIT 20 OFFSET 10000000
Seek	0.0074	SELECT * FROM posts WHERE id > 10000000 ORDER BY id LIMIT 20

実行時間の取得には performance_schema を使っています。

実行時間取得SQL

benchmark_pagination.sql

-- キャッシュのクリア
FLUSH TABLES;

-- クエリ1: オフセット法
SELECT * FROM posts ORDER BY id LIMIT 20 OFFSET 10000000;

-- キャッシュのクリア
FLUSH TABLES;

-- クエリ2: シーク法
SELECT * FROM posts WHERE id > 10000000 ORDER BY id LIMIT 20;

-- オフセット法の実行時間を取得する
SELECT
  EVENT_ID,
  TRUNCATE(TIMER_WAIT/1000000000000,6) AS Duration,
  SQL_TEXT
FROM
  performance_schema.events_statements_history_long
WHERE
  SQL_TEXT  = 'SELECT * FROM posts ORDER BY id LIMIT 20 OFFSET 10000000';

SELECT event_name AS Stage, TRUNCATE(TIMER_WAIT/1000000000000,6) AS Duration
FROM performance_schema.events_stages_history_long WHERE NESTING_EVENT_ID=9;

-- シーク法の実行時間を取得する
SELECT
  EVENT_ID,
  TRUNCATE(TIMER_WAIT/1000000000000,6) AS Duration,
  SQL_TEXT
FROM
  performance_schema.events_statements_history_long
WHERE
  SQL_TEXT  = 'SELECT * FROM posts WHERE id > 10000000 ORDER BY id LIMIT 20';

SELECT event_name AS Stage, TRUNCATE(TIMER_WAIT/1000000000000,6) AS Duration
FROM performance_schema.events_stages_history_long WHERE NESTING_EVENT_ID=36;

2つの方法で、1000万1番目から1000万20番目までのレコードを取得しています。
オフセット法では、10秒以上かかりました。
シーク法であれば、十分高速に動作することがわかります。

実行時間には、ばらつきがあります。
同じクエリを繰り返し実行すると、オフセット法で実行時間が4秒程度まで縮まることもありました。
バッファプールなどの要因が考えられますが、それを差し引いてもシーク法の速さは際立っています。

終わりに

ここでは、カーソル・ページネーションが高速で優れたページネーション技術であると述べてきました。
しかし、だからと言ってオフセット・ページネーションが劣った技術であると述べたいわけではありません。

データの更新が少ない
レコード数が多くない
レコードの総数や総ページ数を取得する必要がある

このような場面では、オフセット・ページネーションの採用が考えられます。
2つのページネーション技術の特徴を知り、要件や条件に合わせて使い分けましょう。

最後までご覧くださいまして、ありがとうございます。
当記事は、筆者の初投稿記事です。
いいねなど、リアクションをいただけると大変励みになります。