【SQL】ページ中盤の検索速度が遅い検索ページネータができやすい仕組み

　SQLでページネーションを作る時、中盤のページを表示しようとすると実行されるSQLが遅くなりやすい仕組みの解説記事です。
　検索機能が必要とされることがよくあります。また、その検索機能を見るためにページネーション（複数ページ分割）が必要となることもあります。次みたいなものを作る必要があるわけです。

　検索対象でよくある対象はリレーショナルデータベースであり、そういった時SQLによって表示するデータのページネーション検索を実現する必要があります。
　検索、と銘打ちましたが実際には並び替え機能も必須になることがほとんどです。SQLの並び替えの計算時間はインデックスという仕組みでほぼ 0 にすることができます。インデックスはその名の通り目次の役目を果たす機能です。大体次の様なイメージのモノをデータベースが持ちます。

// 元テーブル
ID  名前   作成日
1   さとう 2020/01/02
2   たなか 2018/05/20
3   やまだ 2019/11/12
...
100 すずき 2020/06/26

// 名前インデックス
// 実際に持つのはレコードそのものではなくレコードの参照
順番 ID 名前   作成日
1    24 あおき 2010/08/12
2    12 あかぎ 2012/03/06
3    75 あかせ 2009/04/13
...
100  45 わだ   1998/03/26

// 作成日インデックス
// ID順と作成日順が揃わないのは妙なデータですがそういうのもあるということで
順番 ID 名前   作成日
1    42 ななせ 1994/08/12
2    52 さとう 1994/08/12
3    35 さとう 1994/08/13
...
100  43 つだ   2220/06/26

　こういった並び替えインデックスを持つことによって並び替えが必要になった時は、そのインデックスを見に行くことで計算をせずに済みます。また順番も記録されているのでページネーションで何件目から何件目までと要求された際にもあっという間にデータを返せます。
　並び替えは高速でしたが実際には検索条件が必要になります。この検索条件が曲者で実行速度を微妙なものに変えてしまいます（検索条件にもインデックスをはれれば問題ないのですができない時、割に合わない時が少なくないです）。検索条件がある時、よく発行されるSQLは次の様なSQLです。

SELECT * # 実際の検索実装ではSELECT句も厳密に指定します。データ量の都合か速度が向上します
FROM `members`
WHERE `members`.`name` like '%佐藤%'
ORDER BY `members`.`name_kana` ASC
LIMIT 50 offset 300

　name_kana昇順で並んだnameに”佐藤”を含むレコードの301件目から350件目を取得する、というSQLです。デモ動画上でいえば、名前=佐藤で名前かな昇順で並べた表示件数50件の7ページ目です。並び替えが不要なのは先ほどのインデックスで記述した通りです。問題になるのは LIMIT 50 offset 300 です。この検索時には名前インデックスのみでいきなり301件目から350件目と取得することはできません。なぜならばインデックス中のどれが名前に佐藤を含むかわからないからです。インデックス中の301から350をいきなりとってきても名前に佐藤を含まないレコードが大量に紛れていますし、条件に合う301件目でもないわけです。ではどの様に動作するかというと、一つ一つ数え上げるのです。PHPで申し訳ありませんが次の様な動作です。

$offset = 300;
$limit = 50
$result = [];
foreach($名前インデックス昇順のレコード達 as $レコード){
    if($レコード がWHERE句に合致するならば true){
        if($offset > 0){
            $offset--;
        }else{
            $result[] = $レコード;// $resultに$レコードを追加
            $limit--;
            if($limit === 0){
                break;
            }
        }
    }
}

　OFFSET + LIMIT件数分のWHERE句に合致するレコードをインデックスの中から順に探す必要があるわけです。レコードの総数はデータベースにとって既知なので昇順インデックス、降順インデックスのどちらが少ない数え上げで済むのかも既知です。このため必要な数え上げ数が最大になるのは中盤ページであり、中盤のページのデータを得るためのSQLの実行速度は遅くなりやすいです。
　ちなみに対策としては件数（ページ番号）の指定によるOFFSETを諦めて、WHEREを使う方法があります（”もっと見る”ボタンでじゃんじゃか表示する系の機能はこれを使いやすいです）。次の様なSQLが発行されるようにします。

SELECT *
FROM `members`
WHERE `members`.`name` like '%佐藤%'
    AND `members`.`name_kana` > '前回の検索結果の末尾のレコードのname_kana'
ORDER BY `members`.`name_kana` ASC
LIMIT 50

　実際には並び替えの第二条件などでもっと複雑なSQLが発行されやすいですが”前回の検索結果の続き”をWHERE句で表現することには変わりません。この様にすると OFFSET 分の計算が浮きます。データベースのインデックスの実装次第ですが、最悪でも必要になるのは二分探索で検索の始点を探すぐらいの計算でしょう。こうすると次の様な動作で検索が走り、高速化されます。

$limit = 50
$result = [];
foreach($前回の検索の末尾のレコードのname_kanaより後の名前インデックス昇順のレコード達 as $レコード){
    if($レコード がWHERE句に合致するならば true){
        $result[] = $レコード;// $resultに$レコードを追加
        $limit--;
        if($limit === 0){
            break;
        }
    }
}