raahii.meのブログのロゴ画像

ウェブログ
2024-02-10

SQLのページネーションでOFFSETを使うとレコードが重複する

#SQL#MySQL#データベース#ページング

最初にまとめ

OFFSETとLIMITを組み合わせたクエリでページネーションを実現するとき、ORDER BYに指定したカラムの値がユニークになっていないと 同じレコードが複数のページで現れることがある。

ページネーションするときは、必ず検索結果のレコード順序が確定的（ユニーク）になるようにしよう。

再現環境

  • MySQL 8

事象

Web APIでページネーションを実装するとき、OFFSETとLIMITを使って次のようなSQLを書くことがある。 下記はMySQLのEmployees Sample Databaseの employees データベースを使った例で、社員を first_name カラムの順で10人ずつ取り出す。

SELECT * FROM employees
ORDER BY first_name
LIMIT 10 OFFSET 0

一見何の問題もないSQLに見えるが、1ページ目と2ページ目の結果を引くと emp_no=22279 が重複して現れていることがわかる。

  • 1ページ目

    +--------+------------+------------+-------------+--------+------------+
| emp_no | birth_date | first_name | last_name   | gender | hire_date  |
+--------+------------+------------+-------------+--------+------------+
|  11935 | 1963-03-23 | Aamer      | Jayawardene | M      | 1996-10-26 |
|  13011 | 1955-02-25 | Aamer      | Glowinski   | F      | 1989-10-08 |
|  22279 | 1959-01-30 | Aamer      | Kornyak     | M      | 1985-02-25 |
| *20678 | 1963-12-25 | Aamer      | Parveen     | F      | 1987-03-25 |
|  23269 | 1952-02-15 | Aamer      | Szmurlo     | M      | 1988-05-25 |
|  12160 | 1954-12-11 | Aamer      | Garrabrants | M      | 1989-09-19 |
|  24404 | 1960-04-21 | Aamer      | Tsukuda     | M      | 1998-12-25 |
|  11800 | 1958-12-09 | Aamer      | Fraisse     | M      | 1990-08-08 |
|  28043 | 1957-07-13 | Aamer      | Kroll       | F      | 1986-05-17 |
|  15332 | 1961-12-29 | Aamer      | Slutz       | F      | 1989-05-19 |
+--------+------------+------------+-------------+--------+------------+

  • 2ページ目

    +--------+------------+------------+-----------+--------+------------+
| emp_no | birth_date | first_name | last_name | gender | hire_date  |
+--------+------------+------------+-----------+--------+------------+
|  29981 | 1957-07-14 | Aamer      | Gyorkos   | F      | 1985-12-01 |
| *20678 | 1963-12-25 | Aamer      | Parveen   | F      | 1987-03-25 |
|  30404 | 1957-10-08 | Aamer      | Basawa    | M      | 1985-07-17 |
|  22279 | 1959-01-30 | Aamer      | Kornyak   | M      | 1985-02-25 |
|  32854 | 1959-08-03 | Aamer      | Unni      | M      | 1989-08-06 |
|  28162 | 1960-04-06 | Aamer      | Parhami   | F      | 1996-02-15 |
|  33326 | 1956-05-06 | Aamer      | Cheshire  | M      | 1986-04-16 |
|  23269 | 1952-02-15 | Aamer      | Szmurlo   | M      | 1988-05-25 |
|  15332 | 1961-12-29 | Aamer      | Slutz     | F      | 1989-05-19 |
|  36146 | 1957-10-04 | Aamer      | Heusch    | F      | 1986-04-30 |
+--------+------------+------------+-----------+--------+------------+

原因は、ORDER BY first_name で同値 "Aamer" を持つ行が大量にあり、それらの順序が一意に定まらないためである。この場合、結果セットの順序は不定となり、今回のような事象が発生する。

解決策

解決策は、並び順が確定的となるようにORDER BYを構成することである。簡単な方法として、ORDER BY の最後に主キーを含めるのが良いだろう。

...
ORDER BY first_name, emp_no
...

もちろん単一のユニークなカラムでなくとも、カラムを組み合わせた結果ユニークになればよい。

雑感

この挙動、個人的にはけっこう面白いなと思った。

というのも、順序が不定になるとは言うものの、例えば1ページ目のSQLを何度か実行すると必ず同じ結果が返ってくる。そのためどことなく、順序は出鱈目だが、実装に依存して何かしらの順番になることは確定しているように思える。

しかし実際には、入力のSQLが変われば結果も変わり得るし、新しいレコードが挿入されるなどしてDBの状態が変わっても変わるだろう。不定とはまさに予測不能であり、一貫性もないという学びがあった。

オフセット法とシーク法

またこれは余談だが、そもそもSQLを使ったページネーションには2種類あり、今回紹介した方法がオフセット法である。 もう一つはシーク法と呼ばれるもので、ページの始まりに当たる特定のカラム値を受け取る方法で、多くの場合主キーを使う。

SELECT * FROM employees
WHERE emp_no > 18453 -- 前ページの最後のレコードのemp_no
ORDER BY emp_no
LIMIT 10

シーク法の強みはWHERE条件にインデックスを持つキーを指定することで高速に検索できることだ。 オフセット法は後ろのページに行くほど検索が遅くなる問題がある（OFFSETは前の行を読み飛ばすのにはよくない方法）。

ただしシーク法にも注意点が2つある。

1つは、ページ番号を指定してジャンプする要件があるケースでは採用できないことだ。ページの始点となるレコードの情報が必要なので、任意のページにジャンプするのが難しい。

2つ目に、シーク法は実装が複雑になりやすい。特に、ORDER BYの条件が複数になると途端に難しくなる。

例えばこうだ。最初に紹介した例と同じで first_name カラムの順に並べたいとする。そのままでは順序が確定的とならないので emp_no もORDER BYに含める必要がある。これはシーク法でも変わらない。するとORDER BYの条件が複数になる。

SELECT * FROM employees
ORDER BY first_name, emp_no
LIMIT 10

このとき、2ページ目を引くためにはどうすれば良いかと言うと、前ページの最後のレコードが first_name = 'Aamer' かつ emp_no = 18453 だったとすると、

SELECT * FROM employees
WHERE (first_name = 'Aamer' AND emp_no > 18453) -- 前ページと first_name が同値なものの続き
OR first_name > 'Aamer' -- first_nameが異なる場合は emp_no に関係なく結果に含める必要アリ
ORDER BY first_name, emp_no
LIMIT 10

とする必要がある。このようにORDER BYの条件が増えるごとにWHERE句条件が増え、境界位置の判定が複雑になることがわかるだろう。

別の方法として、

SELECT * FROM employees
WHERE CONCAT(first_name, ':', emp_no) > 'Aamer:18453'
ORDER BY first_name, emp_no
LIMIT 10

のようにORDER BY条件をCONCATで文字列として結合し、一発で判定する方法もある。こうすると一発で判定できるのだが、代わりに既存のインデックスが使えないというデメリットがある。

と、いうわけで、これはこれで結構ややこしい問題を抱えている。

実際のケースとして、主キー単体で ORDER BY して並べればOKということはほぼなく、必然的に複数キーでソートすることになる。 しかもシーク法ではページジャンプができないこともあって、パフォーマンスが相当に重要なケース以外では使われない気もしている。

現状の自分の理解では次のような感じで選ぶのが良さそうかな。

  1. オフセット法

    • 実装とインターフェースがシンプルで直感的
    • ただし後ろのページに行くほど検索が遅くなる
    • ページネーション対象の結果セットが小さいならこれで良い
    • 基本こちらを採用し、パフォーマンスが必要ならまずページング対象の結果セットを小さくすることを考え、無理ならならシーク法を使う

  2. シーク法

    • 高速に検索できる（論理設計次第ではある）
    • ただし、特定ページを指定した検索はできない、実装も複雑化しやすい
    • ページネーション対象の結果セットが大きく、速さが必要なら使う