LoginSignup
80
71

More than 3 years have passed since last update.

@madilloar(madi lloar)

offsetでページネーションは遅い。これからはシーク法だ！

Last updated at Posted at 2020-06-07

動機

ページネーションは​​ページングと呼ぶこともありますが、
ページネーションでググるとoffsetを使った例(便宜上オフセット法と呼びます)がよくでてきます。

でも、これ遅いです。どれだけ遅いかはデータベース毎に調べたたのでこちらを参照(で、オフセット法に比べてシーク法のページネーションはどれだけ早いの？RDB毎に。)。

で、これを解決する方法にシーク法(後述)がありまして、かなり高速なのでお薦めです。

が、シーク法のsqlはちょっと複雑なので(特にorder by句に3項目以上の項目があり、
且つascやdescが組み合わさった場合)、後で見返すために覚書として。

シーク法の参考URL

Faster SQL Pagination with Keysets, Continued Posted on November 18, 2013

USE THE INDEX,LUKE! 次ページの取得

ページネーションとは

レコードを要件に従ってソートし、要件で指定された件数で分割し、画面に表示したり、印刷したりすることです。
ページネーションやページングでググるとoffsetの実装例や、高速にするためにoffsetを使わない実装例がヒットします。
offsetを使う方法を便宜上オフセット法と呼ぶことにします。
もう一つのoffsetを使わない方法を便宜上シーク法と呼ぶことにします。

オフセット法の特徴:

  1. 必要なページにたどり着くまでに、最初からそこまでの全ての行を数える必要があるため、後のページになればなるほど応答が悪くなります。
  2. 順序付けはクエリが呼び出される度にやり直されるため、新しいデータが挿入されるとページがズレます(シーク法はズレません)。
  3. シーク法と比べてわかりやすいsql。

シーク法の特徴:

  1. 前ページの最終行をキーにして、次ページの問い合わせを行います。そのため、後のページ行っても応答は悪くなりません。色々面倒な点はありますが、オフセット法より高速なので捨てがたいです。
  2. 任意のページを表示するのが面倒。ページ境界のキーを調べてからでないとページジャンプできないです(オフセット法はoffsetの行を指定すればよいので単純)。
  3. 前ページの最終行をキーにして次ページを決めるため、sqlが複雑になります(order by のascとdescを意識したwhere句を組み立てる必要があるため)。
  4. 表示順序を動的に変えるのが難しいです。order byのascとdescを意識したwhere句を組み立てる必要があるためです。
  5. order by句にはユニークキー(もしくはプライマリキー)を含める必要があります。これは後述するページ境界を判定するためにレコードがユニークになっている必要があるためです。

以下に、次のようなシナリオのもとで、オフセット法とシーク法のsqlの見た目の違いと、ページがズレる挙動を記します。
最後にシーク法に従ったsqlの考え方を記します。

前提、要件

  1. 注文明細テーブルを画面に表示。
  2. 10件ごとに改ページ。
  3. 画面のソート順は、注文日付の降順(新着順)、製品IDの昇順、注文明細番号PKの昇順。
  4. MySQLを利用して試します。

シナリオ

  1. 利用者Aはシステムに対して、注文一覧画面の初期表示を指示します。
  2. システムは、 最初の10件を取得するsqlによる問い合わせを行い、画面初期表示をします。
  3. 利用者Bはシステムに対して、注文10件の登録を指示します。
  4. システムは、注文10件を登録します。
  5. 利用者Aは、次の10件の表示を指示します。
  6. システムは、オフセット法 or シーク法 sqlによる問い合わせを行い、次の10件の画面表示をします。 (オフセット法だと、ページのズレが生じ、シーク法ではズレは生じませんがsqlの複雑さが増しています)

データの初期状態

次の黒三角をクリックするとテーブルイメージが表示されます。

注文明細テーブルの初期状態
order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
64 1 918 2427.928 BACLSLKBRT 2019-05-10
66 1 625 8224.982 KPBNTPQD2E 2019-05-10
58 4 473 369.075 IEQZLEWNOC 2019-05-08
4 2 406 4572.851 6AMV10X7I5 2019-05-02
97 3 669 8618.407 ESWY8F9XH8 2019-05-02
65 3 581 1406.956 FZERLSHOXO 2019-04-29
88 4 413 6083.994 N9TB8F5BKB 2019-04-29
79 5 261 1272.129 4SPMKMQFID 2019-04-27
18 1 605 4918.893 HWS18G3A87 2019-04-23
53 5 544 4189.116 1S0NGUAE56 2019-04-23 <- 1ページ目最終行
20 4 775 4036.631 ZR09YLOVNN 2019-04-20 <- 2ページ目先頭行
1 5 51 2296.772 BOHCRR0ABL 2019-04-16
87 1 584 9607.475 HAM7M68VAA 2019-04-14
36 2 610 6904.623 8FRX3J4OY3 2019-04-12
56 4 236 1647.53 OUGZ7YF9PE 2019-04-12
57 5 754 8712.255 6ZZ5T7ZN5E 2019-04-11
35 2 214 920.519 V3QJO0J1TA 2019-03-27
92 5 249 7932.025 SXHQ5EU4TS 2019-03-26
62 5 338 324.37 R9LAFDPISG 2019-03-23
3 1 50 2182.719 V1IFR3D0TO 2019-03-21 <- 2ページ目最終行

オフセット法

  1. 利用者Aはシステムに対して、注文一覧画面の初期表示を指示します。

  2. システムは、 最初の10件を取得するsqlによる問い合わせを行い、画面初期表示をします。

最初の10件
select
 *
from
 t_order_item
order by
 t_order_item.order_date desc,
 t_order_item.product_id,
 t_order_item.order_item_id
limit 10
;

次のように画面表示。

order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
64 1 918 2427.928 BACLSLKBRT 2019-05-10
66 1 625 8224.982 KPBNTPQD2E 2019-05-10
58 4 473 369.075 IEQZLEWNOC 2019-05-08
4 2 406 4572.851 6AMV10X7I5 2019-05-02
97 3 669 8618.407 ESWY8F9XH8 2019-05-02
65 3 581 1406.956 FZERLSHOXO 2019-04-29
88 4 413 6083.994 N9TB8F5BKB 2019-04-29
79 5 261 1272.129 4SPMKMQFID 2019-04-27
18 1 605 4918.893 HWS18G3A87 2019-04-23
53 5 544 4189.116 1S0NGUAE56 2019-04-23 <- 1ページ目最終行
  1. 利用者Bはシステムに対して、注文10件の登録を指示します。
  2. システムは、注文10件を登録します。
insert into t_order_item values( 37,3,257,5405.614,'SOP3FTE8YS','2019-05-28');
insert into t_order_item values( 25,3,121,7172.409,'DQJG9RQ47F','2019-05-27');
insert into t_order_item values( 31,4,489,5541.722,'BGDVAYSV3D','2019-05-27');
insert into t_order_item values( 95,4,407,6780.502,'SLJB751N7K','2019-05-27');
insert into t_order_item values( 27,1,804,1130.459,'5VYG7979A6','2019-05-25');
insert into t_order_item values( 69,5,623,3133.797,'XJFIE5WICC','2019-05-25');
insert into t_order_item values( 61,2,416,8150.302,'9SJRRSY8FY','2019-05-23');
insert into t_order_item values( 63,3,625,7854.713,'D96UN661BI','2019-05-19');
insert into t_order_item values( 89,1,598,8097.351,'2G5FKLWMOS','2019-05-14');
insert into t_order_item values( 48,3,140,6981.951,'4OGETATNL6','2019-05-14');
  1. 利用者Aは、次の10件の表示を指示します。
  2. システムは、オフセット法 sqlによる問い合わせを行い、
オフセット法で次の10件
select
 *
from
 t_order_item
order by
 t_order_item.order_date desc,
 t_order_item.product_id,
 t_order_item.order_item_id
limit 10 offset 10
;

次の10件の画面表示をします。

何と、初期表示と同じ結果になってしまいました。
利用者からすると何が起きたのかわからないです。
次の10件を表示する指示をし忘れたのか？と思ってしまいます。

order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
64 1 918 2427.928 BACLSLKBRT 2019-05-10
66 1 625 8224.982 KPBNTPQD2E 2019-05-10
58 4 473 369.075 IEQZLEWNOC 2019-05-08
4 2 406 4572.851 6AMV10X7I5 2019-05-02
97 3 669 8618.407 ESWY8F9XH8 2019-05-02
65 3 581 1406.956 FZERLSHOXO 2019-04-29
88 4 413 6083.994 N9TB8F5BKB 2019-04-29
79 5 261 1272.129 4SPMKMQFID 2019-04-27
18 1 605 4918.893 HWS18G3A87 2019-04-23
53 5 544 4189.116 1S0NGUAE56 2019-04-23 <- 1ページ目最終行

これは、order byで指定された順序付けはselectされるたびにやり直されるためです。
新しいデータが挿入されるとページがずれます。
この例では、ちょうど10件追加されたため、初期表示と全く同じデータが表示されました。

シーク法

  1. 利用者Aはシステムに対して、注文一覧画面の初期表示を指示します。

  2. システムは、 最初の10件を取得するsqlによる問い合わせを行い、画面初期表示をします。

最初の10件
select
 *
from
 t_order_item
order by
 t_order_item.order_date desc,
 t_order_item.product_id,
 t_order_item.order_item_id
limit 10
;

次のように画面表示。

order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
64 1 918 2427.928 BACLSLKBRT 2019-05-10
66 1 625 8224.982 KPBNTPQD2E 2019-05-10
58 4 473 369.075 IEQZLEWNOC 2019-05-08
4 2 406 4572.851 6AMV10X7I5 2019-05-02
97 3 669 8618.407 ESWY8F9XH8 2019-05-02
65 3 581 1406.956 FZERLSHOXO 2019-04-29
88 4 413 6083.994 N9TB8F5BKB 2019-04-29
79 5 261 1272.129 4SPMKMQFID 2019-04-27
18 1 605 4918.893 HWS18G3A87 2019-04-23
53 5 544 4189.116 1S0NGUAE56 2019-04-23 <- 1ページ目最終行
  1. 利用者Bはシステムに対して、注文10件の登録を指示します。
  2. システムは、注文10件を登録します。
insert into t_order_item values( 37,3,257,5405.614,'SOP3FTE8YS','2019-05-28');
insert into t_order_item values( 25,3,121,7172.409,'DQJG9RQ47F','2019-05-27');
insert into t_order_item values( 31,4,489,5541.722,'BGDVAYSV3D','2019-05-27');
insert into t_order_item values( 95,4,407,6780.502,'SLJB751N7K','2019-05-27');
insert into t_order_item values( 27,1,804,1130.459,'5VYG7979A6','2019-05-25');
insert into t_order_item values( 69,5,623,3133.797,'XJFIE5WICC','2019-05-25');
insert into t_order_item values( 61,2,416,8150.302,'9SJRRSY8FY','2019-05-23');
insert into t_order_item values( 63,3,625,7854.713,'D96UN661BI','2019-05-19');
insert into t_order_item values( 89,1,598,8097.351,'2G5FKLWMOS','2019-05-14');
insert into t_order_item values( 48,3,140,6981.951,'4OGETATNL6','2019-05-14');
  1. 利用者Aは、次の10件の表示を指示します。
  2. システムは、シーク法 sqlによる問い合わせを行います。

シーク法 は、前ページの最終行をキーにします。この例では次がキーになります。

order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
53 5 544 4189.116 1S0NGUAE56 2019-04-23 <- 1ページ目最終行
シーク法で次の10件
select
 *
from
 t_order_item
where
-- 前ページのorder_dateより小さい日付(descなので)なら残す。
( date('2019-04-23') > order_date )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも大きい(ascなので)なら残す。
( date('2019-04-23') = order_date and 5 < product_id )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも同じなら、前ページのorder_item_idより大きい(ascなので)なら残す。
( date('2019-04-23') = order_date and 5 = product_id and 53 < order_item_id)
order by
 order_date desc,
 product_id,
 order_item_id
limit 10
;

次の10件の画面表示をします。
意図した通り、2ページ目の10行が表示されました。

order_item_id product_id order_qty unit_prc shipping_address_desc order_date ページ境界
20 4 775 4036.631 ZR09YLOVNN 2019-04-20
1 5 51 2296.772 BOHCRR0ABL 2019-04-16
87 1 584 9607.475 HAM7M68VAA 2019-04-14
36 2 610 6904.623 8FRX3J4OY3 2019-04-12
56 4 236 1647.53 OUGZ7YF9PE 2019-04-12
57 5 754 8712.255 6ZZ5T7ZN5E 2019-04-11
35 2 214 920.519 V3QJO0J1TA 2019-03-27
92 5 249 7932.025 SXHQ5EU4TS 2019-03-26
62 5 338 324.37 R9LAFDPISG 2019-03-23
3 1 50 2182.719 V1IFR3D0TO 2019-03-21 <- 2ページ目最終行

シーク法の考え方

order by句に並べたカラムを数字の位取りのつもりで考えます。

例えば、order by句に並べたカラムが3つとしたら、3桁の数字と考え、100の位、10の位、1の位と考えます。
次に上位の桁、この例なら100の位からwhere句を組み立てていきます。
この時ascとdescを意識しながら、”<” か ”>”を決めていきます。
(前ページキー [ ”<” か ”>” ] item)の”<” か ”>”の向きはどちらにすべきかは、次のように考えます。
ascの場合:次のページとして抽出したい値は、前のページ < 次ページとなるようにする。
descの場合:次のページとして抽出したい値は、前のページ > 次ページとなるようにする。

order by句の項目数 where句の組み立て方
1つだけの場合 (前ページキー [ ”<” か ”>” ] item1)
2つだけの場合 (前ページキー [ ”<” か ”>” ] item1)
or (前ページキー [ ”=” ] item1) and (前ページキー [ ”<” か ”>” ] item2)
3つだけの場合 (前ページキー [ ”<” か ”>” ] item1)
or (前ページキー [ ”=” ] item1) and (前ページキー [ ”<” か ”>” ] item2)
or (前ページキー [ ”=” ] item1) and (前ページキー [ ”=” ] item2) and (前ページキー [ ”<” か ”>” ] item3)

要件では、「画面のソート順は、注文日付の降順(新着順)、製品IDの昇順、注文明細番号PKの昇順」となっていますので、

これに従って、where句を組み立てると次のようになります。

where
-- 前ページのorder_dateより小さい日付(descなので)なら残す。
( date('前ページ末尾のorder_date') > order_date )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも大きい(ascなので)なら残す。
( date('前ページ末尾のorder_date') = order_date and '前ページ末尾のproduct_id' < product_id )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも同じなら、前ページのorder_item_idより大きい(ascなので)なら残す。
( date('前ページ末尾のorder_date') = order_date and '前ページ末尾のproduct_id' = product_id and '前ページ末尾のorder_item_id' < order_item_id )
order by
 order_date desc,
 product_id,
 order_item_id

ちなみに、注文日付を昇順にした場合は、次のようになります。

where
-- 前ページのorder_dateより大きい日付(ascなので)なら残す。
( date('前ページ末尾のorder_date') < order_date )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも大きい(ascなので)なら残す。
( date('前ページ末尾のorder_date') = order_date and '前ページ末尾のproduct_id' < product_id )
or
-- 前ページのorder_dateと同じ日付で、前ページのproduct_idも同じなら、前ページのorder_item_idより大きい(ascなので)なら残す。
( date('前ページ末尾のorder_date') = order_date and '前ページ末尾のproduct_id' = product_id and '前ページ末尾のorder_item_id' < order_item_id)
order by
 order_date,
 product_id,
 order_item_id

おまけ：シーク法の為の全ページ境界を調べるsql

このsqlは、各ページの最終行のキーを調べるsqlです。
Googleとかで検索したときに下段に表示される、

<1 2 3 4 5 6 7 8 9 10 次へ>

これをやるために、各ページの最終行を求めるsqlです。

全ページ境界を調べるsql
select
 x.*,
 row_number() over(
   order by
     order_date desc, product_id, order_item_id
 ) + 1 page_number
from
 ( select
     case (row_number() over(
       order by
         order_date desc, product_id, order_item_id
     ) % 10)  -- 10行でページング
       when 0
       then 1
       else 0
     end page_boundary,
     t.*
   from
    t_order_item t
   order by
     order_date desc,
     product_id,
     order_item_id
 ) x
where
 x.page_boundary = 1
;
page_boundary order_item_id product_id order_qty unit_prc shipping_address_desc order_date page_number
1 48 3 140 6981.951 4OGETATNL6 2019-05-14 2
1 53 5 544 4189.116 1S0NGUAE56 2019-04-23 3
1 3 1 50 2182.719 V1IFR3D0TO 2019-03-21 4

おまけ２

100万件にデータを増やし、order by句 に使っている項目でindexを作り、オフセット法と
シーク法で最後のページを検索するsqlの実行計画を比較してみます。
下記の通り、オフセット法はtype=ALLのフルスキャンです。シーク法はtype=rangeのインデックスを使った範囲検索です。

index作成
create index idx1_t_order_item on t_order_item (order_date, product_id, order_item_id);
オフセット法(index有り)
  explain
  select
    *
  from
    t_order_item
  order by
    t_order_item.order_date desc,
    t_order_item.product_id,
    t_order_item.order_item_id
    limit 10 offset 999990
  ;
オフセット法(index有り)
+----+-------------+--------------+------------+------+---------------+------+---------+------+--------+----------+----------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows   | filtered | Extra          |
+----+-------------+--------------+------------+------+---------------+------+---------+------+--------+----------+----------------+
|  1 | SIMPLE      | t_order_item | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 856180 |   100.00 | Using filesort |
+----+-------------+--------------+------------+------+---------------+------+---------+------+--------+----------+----------------+
シーク法(index有り)
  explain
  select
    *
  from
    t_order_item
  where
    -- 前ページのorder_dateより小さい日付(descなので)なら残す。
    ( cast('2019-01-01' as date) > order_date )
    or
    -- 前ページのorder_dateと同じ日付で、前ページのproduct_idも大きい(ascなので)なら残す。
    ( cast('2019-01-01' as date) = order_date and 5 < product_id )
    or
    -- 前ページのorder_dateと同じ日付で、前ページのproduct_idも同じなら、前ページのorder_item_idより大きい(ascなので)なら残す。
    ( cast('2019-01-01' as date) = order_date and 5 = product_id and 990154 < order_item_id )
  order by
    order_date desc,
    product_id,
    order_item_id
  ;
シーク法(index有り)
+----+-------------+--------------+------------+-------+---------------------------+-------------------+---------+------+------+----------+---------------------------------------+
| id | select_type | table        | partitions | type  | possible_keys             | key               | key_len | ref  | rows | filtered | Extra                                 |
+----+-------------+--------------+------------+-------+---------------------------+-------------------+---------+------+------+----------+---------------------------------------+
|  1 | SIMPLE      | t_order_item | NULL       | range | PRIMARY,idx1_t_order_item | idx1_t_order_item | 13      | NULL |   12 |   100.00 | Using index condition; Using filesort |
+----+-------------+--------------+------------+-------+---------------------------+-------------------+---------+------+------+----------+---------------------------------------+

おまけ３

indexを削除し、オフセット法とシーク法で実行計画を比較してみます。
下記の通り、オフセット法はtype=ALLのフルスキャンです。シーク法はtype=ALLのフルスキャンなのですが、where句で主キーを使っているので状況が良いです。

index削除
drop index idx1_t_order_item on t_order_item;
オフセット法(index無し)
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra          |
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
|  1 | SIMPLE      | t_order_item | NULL       | ALL  | NULL          | NULL | NULL    | NULL | 1002885 |   100.00 | Using filesort |
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+----------------+
シーク法(index無し)
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+-----------------------------+
| id | select_type | table        | partitions | type | possible_keys | key  | key_len | ref  | rows    | filtered | Extra                       |
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+-----------------------------+
|  1 | SIMPLE      | t_order_item | NULL       | ALL  | PRIMARY       | NULL | NULL    | NULL | 1002885 |    35.77 | Using where; Using filesort |
+----+-------------+--------------+------------+------+---------------+------+---------+------+---------+----------+-----------------------------+
80
71
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
80
71