TiDBにおけるページング処理 - LIMIT OFFSET と Keyset pagination の使い分け

この記事について

Webサービスなどでは、データベースにある情報をランキング形式や任意の順序に並べて、その結果を一定の件数ごとに表示することがよくあります。これはいわゆるページング処理と呼ばれるものです。このページング処理をUI/UXでいうと、例えば以下のように実装されています。

• ドキュメントサイトでの検索結果の表示
• ECサイトでの商品の売上順の表示
• SNSでの投稿順の表示

このうち、最初の２つは１画面で10件ごとに表示し、次の10件を表示したい場合は次のページ番号が付与されたリンクをクリックして遷移します。３つ目の場合、画面のスクロールに応じて次の10件の投稿が表示されるというような実装になることが多いでしょう。

本記事では、Web APIでの利用を前提として、上記のようなページング処理をデータベースの観点でどのように実装すべきかをSQLを用いて説明します。また、タイトルにもあるように、TiDBでのページング処理を題材とすることで、TiDBにおける分散データベースの特性についても触れていきます。

ページング処理はレポート作成のためのバッチ処理で実装する機会もあるかと思いますが、記事の内容をシンプルにするためにバッチ処理でのページング処理にはあまり踏み込みません。あらかじめご了承ください。

ページング処理の実装パターン

ページング処理をSQLで実装する場合、以下の３パターンが考えられます。

1. Offset pagination
   1. LIMIT OFFSETを使った、おそらく最も一般的なやり方
2. Keyset pagination
   1. あるカラム、またはカラムの組み合わせをカーソルのように扱うやり方
3. 事前にページ番号を計算しておくやり方

以降ではそれぞれの実装について簡単に見ていきます。

Offset pagination

Offset paginationの実装はLIMIT OFFSETを使ったものです。例えば、レコードが登録された順にPrimary Key（PK、ここではid列とします）が採番されるとした場合、商品が登録された順にレコードを取得するSQLは以下のようになります。

SELECT * FROM books
ORDER BY id
LIMIT 10 OFFSET 100
;

このSQLは、idを昇順に並べて、先頭の100件をスキップして次の10件を、つまり101番目から110番目までのレコードを取得せよ、という命令になります。これはよくある実装で、ORMなどが自動的にこのようなSQLを生成することもあるでしょう。

Keyset pagination

Keyset paginationの実装は、ある一意のキー（Primary KeyやUnique Key、 以後PK/UKとする）や、一意となる列の組み合わせをカーソルのように使って指定された件数を取得する方法です。Offset paginationと同じ例（商品が登録された順）をKeyset paginationで実装してみます。

SELECT *
FROM books
WHERE id > ${previous_id}
ORDER BY id
LIMIT 10;

もし並べる条件が売上順のようなレコードが一意にはならない場合、idなど複数の列を組み合わせてSQLを組み立てます。例えば以下のようになるでしょう。

SELECT *
FROM books
WHERE (sales, id) < (${previous_sales}, ${previous_id})
ORDER BY sales DESC, id DESC
LIMIT 10;

事前にページ番号を計算しておく

このやり方は実はTiDBの公式ドキュメントで紹介されています。ここでは以下のドキュメントに基づいて説明します。

https://docs.pingcap.com/tidbcloud/dev-guide-paginate-results/#paginate-results

ページ番号を計算するためにrow_numberというWindow関数を使います。そして、検索した結果セットに列番号を付与し、その列番号に基づいてページ番号を割り当てます。パーティションを仮想的に都度計算して作成しているような感じです。

https://docs.pingcap.com/tidb/stable/window-functions/#row_number

このやり方の場合、以下のようなSQLになるでしょう。

-- １ページあたりに1000件のレコードが含まれる
SELECT
    floor((t.row_num - 1) / 1000) + 1 AS page_num,
    min(t.id) AS start_key,
    max(t.id) AS end_key,
    count(*) AS page_size
FROM (
    SELECT id, row_number() OVER (ORDER BY id) AS row_num
    FROM books
) t
GROUP BY page_num
ORDER BY page_num;

このSQLの結果は例えば以下のようになります。

+----------+------------+------------+-----------+
| page_num | start_key  | end_key    | page_size |
+----------+------------+------------+-----------+
|        1 |     268996 |  213168525 |      1000 |
|        2 |  213210359 |  430012226 |      1000 |
|        3 |  430137681 |  647846033 |      1000 |
|        4 |  647998334 |  848878952 |      1000 |
|        5 |  848899254 | 1040978080 |      1000 |
...
|       20 | 4077418867 | 4294004213 |      1000 |
+----------+------------+------------+-----------+

この結果を用いると、１ページ目のレコードを取得する場合、以下のSQLになります。

SELECT *
FROM books
WHERE id BETWEEN 268996 AND 213168525
ORDER BY id;

このやり方は多少泥臭いですが、直観的で性能にも優れています。しかし、Web APIよりもバッチ処理のような時間のかかるプロセスのほうが適しているため、今回の記事ではここまでの説明に留めておきます。

ページング処理実装の性能比較

ここまで各パターンの実装をSQLを通じて見てきました。ここからOffset paginationとKeyset paginationの２つの性能比較をします。この性能比較を通じてそれぞれの実装パターンの動作を確認し、TiDBでの利用において、各パターンの使い所を見極めてみたいと思います。

検証環境

今回は以下の環境で検証を行いました。

• 実行環境: TiDB Cloud AWS Tokyo (ap-northeast-1) region
• Version: v8.5.4
• Topology: TiDB 4vCPU16GB x 1, TiKV 4vCPU16GB x 3
• Storage type: Standard

今回の検証では上記環境と以降に示すテストデータやテーブルに基づいた、それぞれのページング処理の傾向を示すものであり、実際のデータ量や分布、インデックスの設計など、様々な要因でここで示す結果とは異なる場合があります。あらかじめご了承ください。

テストデータ

検証で利用したDDLとテストデータ生成のスクリプトは以下をご参照ください。

CREATE TABLE

CREATE TABLE products (
  id BIGINT PRIMARY KEY AUTO_INCREMENT COMMENT '商品ID',
  name VARCHAR(255) NOT NULL COMMENT '商品名',
  price INT NOT NULL COMMENT '販売価格（円）',
  sales BIGINT NOT NULL COMMENT '累計売上数',
  stock INT NOT NULL COMMENT '在庫数（0の場合は売り切れ）',
  sold_at DATETIME NOT NULL COMMENT '発売日時（NOW() より未来の場合は未発売）',
  created_at DATETIME NOT NULL COMMENT '商品作成日時',
  KEY idx_sales_id (sales, id) COMMENT '売上順ページネーション用（Keyset pagination）'
)
COMMENT='ECサイトの商品マスタ';

テストデータ生成

SET cte_max_recursion_depth = 10000;

INSERT INTO products (
  id,
  name,
  price,
  sales,
  stock,
  sold_at,
  created_at
)
(
  WITH RECURSIVE seq AS (
    -- 開始行
    SELECT 0 AS n
    UNION ALL
    -- 0〜9999 まで生成（1万件）
    SELECT n + 1
    FROM seq
    WHERE n < 9999
  )
  SELECT
    n + 1 AS id,
    CONCAT('product-', n + 1) AS name,

    -- 価格: 500〜50000
    500 + (n % 50000) AS price,

    -- 売上: 偏りを持たせる（売れている商品が一部に集中）
    CASE
      WHEN n % 100 < 5  THEN 10000 + (n % 500)
      WHEN n % 100 < 20 THEN 1000 + (n % 300)
      ELSE n % 200
    END AS sales,

    -- 在庫: 売上が多いほど在庫が少ない想定
    CASE
      WHEN n % 100 < 10 THEN 0          -- 売り切れ
      WHEN n % 100 < 40 THEN n % 5      -- 在庫僅少
      ELSE 10 + (n % 50)                -- 在庫あり
    END AS stock,

    -- 発売日: 一部は未来（未発売）
    CASE
      WHEN n % 100 < 10 THEN DATE_ADD(NOW(), INTERVAL (n % 30) DAY)
      ELSE DATE_SUB(NOW(), INTERVAL (n % 90) DAY)
    END AS sold_at,

    -- 作成日: 過去180日以内
    DATE_SUB(NOW(), INTERVAL (n % 180) DAY) AS created_at
  FROM seq
);

ANALYZE TABLE products ALL COLUMNS;

テストシナリオ

今回の性能検証は以下の各２つの条件をOffset paginationおよびKeyset paginationのそれぞれにおいて、１ケースにつき10回クエリを実行して結果を評価することとします。

1. PK/UKのみでソートする
   • 在庫あり商品（stock > 0）のうち、発売中の商品（sold_at < NOW()）を新しく登録された順（ORDER BY id DESC）に並べる
2. Non PK/UKでソートする
   • 在庫あり商品（stock > 0）のうち、発売中の商品（sold_at < NOW()）を売上順に、同額の場合は新しく登録された順（ORDER BY sales DESC, id DESC）に並べる

Offset paginationの場合はOFFSETが100, 1000, 5000の場合を実行し、OFFSETの深さに応じた読み取り件数の違いによる性能の変化を見ます。Keyset paginationも比較のために近しい条件設定を行いますが、テストデータをランダムに生成しているためOffset paginationのスキャンの場合と対になるわけではなく、必ずしも同等の条件であるとは言えません。また、本来であればKeyset paginationは前ページの末尾に基づいて次のページングを行いますが、今回は検証を簡単にするために条件値を固定しています。

テストクエリ

テストシナリオに基づき、以下のテストクエリを実行します。クエリの実行計画を把握するためにEXPLAIN ANALYZE format = 'verbose'をクエリの先頭に付与しています。

Offset pagination x PK/UKのみでソートする

EXPLAIN ANALYZE format = 'verbose'
SELECT *
FROM products
WHERE stock > 0
  AND sold_at < NOW()
ORDER BY id DESC
LIMIT 10 OFFSET ?;

Offset pagination x Non PK/UKでソートする

EXPLAIN ANALYZE format = 'verbose'
SELECT *
FROM products
WHERE stock > 0
  AND sold_at < NOW()
ORDER BY sales DESC, id DESC
LIMIT 10 OFFSET ?;

Keyset pagination x PK/UKでソートする

EXPLAIN ANALYZE format = 'verbose'
SELECT *
FROM products
WHERE stock > 0
  AND sold_at < NOW()
  AND id < ?
ORDER BY id DESC
LIMIT 10;

Keyset pagination x Non PK/UKでソートする

EXPLAIN ANALYZE format = 'verbose'
SELECT *
FROM products
WHERE stock > 0
  AND sold_at < NOW()
  AND (sales, id) < (?, ?)
ORDER BY sales DESC, id DESC
LIMIT 10;

結果の評価

今回の性能比較では得られた実行計画から以下の指標を取り出して評価します。

• 実行計画の構造
• 実行時間 (execution info > １行目のtime)
• RU消費 (execution info > RU)
• 処理キーの数 (execution info > tikv_task > scan_detail > total_process_keys)
• RPCの数 (execution info > cop_task > rpc_info > Cop > num_rpc)

"実行計画の構造"では以下の点に注目して評価します。

• Indexが使われているか、使われている場合、どのようにIndexをスキャンしているか
  • IndexFullScanかIndexRangeScanか
• Indexが使われていなければ、どのようにTableをスキャンしているか
  • TableRangeScanかTableFullScanか
• keep order:true が付いているか（ソート処理の有無の確認）

以降４点（実行時間、RU消費、処理キーの数、RPCの数）は定量的な指標として評価します。見慣れない用語かもしれませんので、簡単にそれぞれの指標について説明します。

実行時間とは、実際にクエリの実行にかかった時間であり、TiDBクラスタ内で最終的な結果セットを取得するのにかかった時間といえます。この記事においては実行計画の一番上の行の値を採用しています。クライアントへの結果セットの返却にかかった時間は含まれません。この値が大きければ、TiDB内部でのクエリ処理に時間がかかったことを意味します。

RUはRequest Unitの略です。Request Unitとは、TiDBへの単一リクエストによって生じるCPU使用時間、Disk IOPSやIO帯域といったメトリクスを総合的に示したリソース消費の単位のことです。この値が大きいと、TiDBクラスタのマシンリソースが多く消費されていることを意味します。詳細は以下をご覧ください。

https://docs.pingcap.com/tidbcloud/tidb-resource-control-ru-groups/#what-is-request-unit-ru

処理キー（total_process_keys）とは、対応するOperator（Limit、SelectionあるいはIndexFullScanなど）において、TiDBからTiKVへのCoprocessorによって読み込まれた有効なキー数（削除されたキーやMVCCで管理されている古いバージョンのキーは含まない）の合計値です。TiDB内部の処理で読み込まれたキーの数を示しており、必ずしも返した行数を意味するとは限りません。本記事では、この指標を読み取りのコスト値として相対的な比較のために用いています。

RPCの数（num_rpc）は対応するOperatorにおけるTiDBとTiKV間で行われたRPCの回数の合計値です。この値が多いほどTiDBからTiKVへの操作が多いことを示しており、クエリ処理全体におけるネットワークオーバーヘッドを推測する指標となります。

ここに挙げている指標はあくまでTiDBクラスタ内部におけるクエリ実行の性能（結果セットの取得にかかった時間、リソース消費の程度など）を比較検討するためのものです。End-to-Endでのレイテンシーを評価するものではありません。また、掲載している値は本検証で観測されたものであり、他の環境では異なる場合があります。

それぞれのケースの実行結果は以下のリンク先にあるgistでご確認ください。この記事内では実行結果から上記の指標をまとめたものを記載します^[1]。

• Offset pagination x PK/UK
• Offset pagination x Non PK/UK
• Keyset pagination x PK/UK
• Keyset pagination x Non PK/UK

計測結果

ここではシナリオごとの計測結果を、各回の値を横に並べて比較します。

Offset x PK/UK

Offsetが増えると各指標が増えていることが明らかとなっています。timeは低い水準を維持していますが、RUは如実に増えています。先ほど説明したように、Offset paginationでは不要な行を読み取っているため、RUが増えていることはコストまたはリソース管理の観点において重要な意味を持ちます。

OFFSET	time (min-max, ms)	RU	total_process_keys	num_rpc
100	4.98-5.23	1.77-1.81	224	1
1000	15.9-16.4	6.88-6.95	1696	3
5000	30.0-33.8	17.45-17.56	6752	5

枝番に多少の違いはありますが、OFFSETの深さによらず、クエリは以下のように実行されています。

+------------------------------+
| Limit_12                     |
| └─TableReader_33             |
|   └─Limit_32                 |
|     └─Selection_31           |
|       └─TableFullScan_30     |
+------------------------------+

LIMITが２回出現しています。これはactRows列をみればわかりますが、条件を満たす110件をTiKVノードからroot（TiDBノード）へ返して（Limit_32）、返ってきた110件から先頭100件をrootが捨てて目的の10件を取得する（Limit_12）という動作をしていることを示しています。

operator info列を見ると、keep order:true, descとなっています。これは今回のORDER BY id DESCではソート処理を行わなかったことを意味しています。TiDBではClustered Indexの場合、（設定されたリージョンの容量に収まる限り）レコードが同一リージョンに配置されることでPKを降順にスキャンでき、追加のソート処理が不要となっているからです。

Offset x Non PK/UK

こちらも全体の傾向としては上述のとおりですが、OFFSETが1,000になってからはTableFullScanになっています。そのため、RUはOffsetが1,000でも5,000でもほぼ変わりありません。TableFullScanは必ずしもテーブルの中にあるレコードを全件スキャンしているわけではありませんが、Offsetがあるしきい値を超えてTableFullScanになってしまうとコストやリソース消費が上振れ、あるいは頭打ちになってしまうということを意味しています。

OFFSET	time (min-max, ms)	RU	total_process_keys	num_rpc
100	18.4-18.9	9.97-10.15	2,584	7
1000	27.81-28.7	20.68-20.82	10,000	4
5000	36.0-41.1	21.49-21.61	10,000	6

実行計画を見てみましょう。OFFSET 100の場合は以下のようになっています。

+---------------------------------+
| Limit_13                        |
| └─IndexLookUp_33                |
|   ├─IndexFullScan_30(Build)     |
|   └─Selection_32(Probe)         |
|     └─TableRowIDScan_31         |
+---------------------------------+

しかし、OFFSET 1000およびOFFSET 5000の場合は以下のようになっています。

+------------------------------+
| TopN_8                       |
| └─TableReader_17             |
|   └─TopN_16                  |
|     └─Selection_15           |
|       └─TableFullScan_14     |
+------------------------------+

このことから、OFFSETが深くなると、コスト計算によって、実行計画が変わる場合があるということがわかります。

ところで、実行計画の中にLimitではなくTopNが出現しています。この両者の違いはLimitの場合はソート処理を伴っていないこと、TopNの場合はソート処理を伴っていることです。例えると、Limitは"切り出し"で、TopNは"並べ替え+切り出し"といえるでしょう。この実行計画の場合、operator info列を見ると、Limitの場合はoffset:?, count:?のみですが、TopNの場合はtest.products.sales:desc, test.products.id:desc, offset:?, count:?となっており、TopNの場合はソート処理が行われていることがわかります。詳細は以下のリンク先をご参照ください。

https://docs.pingcap.com/tidb/stable/topn-limit-push-down/#topn-and-limit-operator-push-down

Keyset x PK/UK

Keyset paginationの場合、Offset paginationとは対照的に、Keyset条件に変更があっても、total_process_keysが一定であることから不要な読み取りが増えることはなく、RUがほぼ一定です。

keyset条件（id < X）	time (min-max, ms)	RU	total_process_keys	num_rpc
100	4.70-4.98	1.43-1.46	32	1
1000	4.40-4.72	1.35-1.38	32	1
5000	3.23-3.65	1.00-1.03	32	1

実行計画を見てみましょう。

+-------------------------------+
| Limit_11                      |
| └─TableReader_20              |
|   └─Limit_19                  |
|     └─Selection_18            |
|       └─TableRangeScan_17     |
+-------------------------------+

Offset pagination+PK/UKのケースと似ていますが、Keyset paginationの場合はTableFullScanではなくTableRangeScanとなっています。この違いが処理量の違いとなっており、性能差となっています。

Keyset x Non PK/UK

こちらも同様にKeyset条件に変更がなくてもほとんど指標に変化が無いか、誤差の範囲に収まっていることがわかります。

keyset 条件 (sales, id)	time (min-max, ms)	RU	total_process_keys	num_rpc
(1000, 100)	6.80–7.49	3.52–3.79	224	2
(3000, 1000)	7.17–7.91	3.65–4.30	224	2
(6000, 5000)	7.21–7.64	3.65–3.94	224	2

実行計画を確認します。

+----------------------------------+
| Limit_12                         |
| └─IndexLookUp_25                 |
|   ├─IndexRangeScan_22(Build)     |
|   └─Selection_24(Probe)          |
|     └─TableRowIDScan_23          |
+----------------------------------+

keysetの条件によらず、上記の通りになっています。これは、該当のソート順に合うインデックスがある場合、Keyset paginationが安定した性能を出すことが期待できることを意味しています。また、Offset paginationのときとの違いとして、IndexFullScanだったのがIndexRangeScanとなっています。これはより効率的なレコード検索ができていることを示しています。

計測結果まとめ

ここまで見てきた計測結果をまとめると以下のことが言えます。

• Offset paginationはページが進むにつれて負荷が高くなり、実行計画の変化によって、最悪の場合、性能が劣化しやすくなる
• Keyset paginationはkeyset条件によらず、該当のソート順に合うインデックスがある場合は負荷と性能は安定する

この結果を踏まえて、次に各ページング処理の使いどころについて考えてみたいと思います。

ページング処理の使い分け

Offset paginationの使いどころ

今回の検証では、Offset paginationはKeyset paginationよりも良くない性能になることがわかりました。このことはOffset paginationが使えないということを意味しているのでしょうか。確かに性能にシビアな状況ではそうかもしれません。しかし、Offset paginationはページ番号に応じたレコード検索が可能であるという特長があります。例えば１ページ目の結果から３ページ目にジャンプしたい場合、OFFSETの値をページ番号に応じて調整すればよいため、前回クエリの結果に依存せずにクエリを発行することができます。これは、ランキング形式のデータを表示するうえでは大変便利です。

一方で、大量のレコードを一定の順序で並べるような場合、特にNon PK/UKでソートする場合は注意が必要です。OFFSETが深くになるつれて無駄なIOが多くなってしまうため、絞り込みやインデックスを慎重に考えておく必要があります。必要ならばパーティションの導入、あるいは検索条件やソート条件の見直し、カバリングインデックスなども検討すべきでしょう。

すこしネガティブな表現が多くなってしまいましたが、Offset paginationは実装が簡単で、任意のページに飛べるという強みがあり、使い所は普通にあります。一方で、OFFSETが深くなるほど内部的な読み取り（読み捨て）が増えやすいという構造的性質があるため、「深くならない」前提が置ける場面では有力と言えるでしょう。ただし、RUなどのリソース消費はOFFSETの深さに応じて上振れしていくことは忘れずにいましょう。

よって、Offset paginationの使いどころは以下のようになると思います。

• 任意のページ番号へ直接アクセスできるようにしたい
• 検索対象のデータがそれほど大規模ではない

Keyset paginationの使いどころ

Keyset paginationはOffset paginationよりも良い結果となりました。これはクエリを見ればわかるように、読み出し位置をフィルタ条件で指定しており、無駄なIOが極力発生しないようになっているためです。このような動作は検索対象のデータ量に依存しにくいため、大規模なデータあるいはデータ量が増えやすい場合に有効です。

では、Keyset paginationは常にOffset paginationよりも優れているのでしょうか。残念ながらそうではありません。Keyset paginationでOffset paginationと同様のページ番号を実装するのは難しいです。また、Keyset paginationでは情報の鮮度を維持しづらく、"常に最新の上位"が求められるようでは多少の工夫が必要です^[2]。Offset paginationであれば、１ページ目に戻ればアクセス時点での最新の上位を見ることができますが、Keyset paginationでは画面のスクロールを上に戻しても最新が表示されるということはありません^[3]。このあたりは要件次第であるため、必ずしもクエリとしての短所というわけではありませんが、採用する際には留意すべき点であるでしょう。

今回の測定結果をよく見ればお気づきになると思いますが、Keyset paginationが性能的に優れた結果となっているのはソート条件と（前方）一致するインデックスがあるからです。逆に言うと、そのようなインデックスがなければ処理性能が大きく劣化する場合があります。もちろん、それはOffset paginationでも同様なのですが、Keyset paginationの特性を活かすにはソート条件と（前方）一致するインデックスが重要であることを念頭に置いてください。

よって、Keyset paginationの使いどころは以下のようになると思います。

• ページ番号を利用したページアクセスの要件が無い、いわゆる無限スクロールを実装したい
• クエリしたデータをページに分割する必要が無い
• 検索対象のデータが増えてもクエリのコストを一定の範囲内に抑えたい
• ソート条件に対応したインデックスを効かせることができる

冒頭でお伝えしたように、Keyset paginationではSNSのようにページをスクロールするたびにコンテンツを表示させていくようなUI/UXで利用に向いています。特に、SNSコンテンツは膨大になりやすいため、無駄なIOを減らし、読み込みのコストが予測しやすいのは非常に便利です。

まとめ

この記事ではSQLを使ったページング処理について、主に性能面から違いを議論しました。Offset paginationは実装しやすいですが、データの成長に伴い性能やコストが悪化しやすい傾向にあります。Keyset paginationは対照的に性能やコストは安定しやすいですが、従来のページング処理の実装には向かないため、必ずしもOffset paginationを置き換えるものではありません。ユーザーに提供したいUI/UXに基づき、適切なクエリを実装しましょう。

脚注

1. 若干余談ですが、実行計画の中で rpc_errors:{context canceled:1}} が含まれています。これはアプリケーションの実行失敗を意味するエラーではなく、rpcの中断を意味しています。TiDBがTiKVの対象リージョンの中にある探索範囲をすべてスキャンし終えたなどの理由により処理が打ち切られただけで、問題になるものではありません。

2. 実際のところ、ページング処理において常に最新の情報を表示する必要性はあまりないかもしれません。更新頻度が多いテーブルの場合、クエリするたびに結果が変わる可能性が高いため、一貫した結果を表示するほうがより重要かもしれません。その場合、TiDBではAS OF TIMESTAMP句を利用してある時点のデータをスナップショットとして利用することができます。詳細は https://docs.pingcap.com/tidb/stable/as-of-timestamp/ を参照してください。

3. そのように実装することも可能でしょうが、通常は画面のリフレッシュをさせるのが一般的であり、それではKeyset paginationに期待しているUI/UXとはならないでしょう