OFFSETを使わない高速なページネーションの実現

概要

SQLでページネーションと言えばこんな処理が定番かと思われますが…

SELECT * FROM samples ORDER BY id LIMIT 5 OFFSET 30 
SELECT * FROM samples ORDER BY id LIMIT 30, 5

OFFSETを使ってしまうと，毎回OFFSET以降に加えて先頭からOFFSETまでの検索も行うため，奥に進むにつれてどんどん効率が悪くなってきます。そこで，以下のような解決策を提案します。

• OFFSETの代わりにPRIMARY KEY(インデックスの効いたキー)で範囲を絞り込む
• 常に1件手前と1件奥を余分に取得し，前のページおよび次のページがあるかどうか判定可能にする

idが連続

BETWEENを使って両端のidで挟み撃ちしてやればスパッと抜けます。

奥に進むとき

SELECT * FROM samples WHERE id BETWEEN 30-1 AND 30+5 ORDER BY id

前に戻るとき

SELECT * FROM samples WHERE id BETWEEN 30-5 AND 30+1 ORDER BY id

idが不連続

LIMIT制限下で両方向に探索した後，結果をUNION ALLでマージします。UNION対象の集合に直接ORDER BYを使うことは出来ないので，もう一重SELECTに被せてます。

奥に進むとき

SELECT * FROM (
    SELECT * FROM samples WHERE id < 30 ORDER BY id DESC LIMIT 1
) x
UNION ALL
SELECT * FROM (
    SELECT * FROM samples WHERE id >= 30 ORDER BY id ASC LIMIT 5+1
) x

前に戻るとき (逆順なのでarray_reverse適用必須)

SELECT * FROM (
    SELECT * FROM samples WHERE id > 30 ORDER BY id ASC LIMIT 1
) x
UNION ALL
SELECT * FROM (
    SELECT * FROM samples WHERE id <= 30 ORDER BY id DESC LIMIT 5+1
) x

サンプル

idの連続・不連続を問わず汎用的に使えます。

<?php

try {

    /* SQLite3のテンポラリデータベースに接続およびモード設定 */
    $pdo = new \PDO('sqlite::memory:');
    $pdo->setAttribute(\PDO::ATTR_ERRMODE, \PDO::ERRMODE_EXCEPTION);
    $pdo->setAttribute(\PDO::ATTR_DEFAULT_FETCH_MODE, \PDO::FETCH_ASSOC);
    $pdo->setAttribute(\PDO::ATTR_EMULATE_PREPARES, true);

    /*
        スキーマとレコードの生成
        idは絞り込み等で番号が飛んでいることを想定
    */
    $pdo->exec('CREATE TABLE samples(
        id INTEGER PRIMARY KEY NOT NULL,
        name TEXT NOT NULL
    )');
    array_map(
        [$pdo->prepare("INSERT INTO samples VALUES (?, ?)"), 'execute'],
        [
            [3, '安藤'], [6, '伊藤'], [7, '上田'], [10, '江口'], [32, '小野田'],
            [33, '柏木'], [43, '木村'], [73, '黒木'], [75, '慶野'], [89, '小林'],
            [91, '澤田'], [101, '城山'], [107, '鈴木'], [123, '瀬川'], [137, '薗部'],
            [155, '田中'], [199, '千代田'],
        ]
    );

    /*
        $_GET['left'], $_GET['right'], $_GET['count'] が1以上の整数かどうか検証する
        更に $_GET['count'] は 1〜10を強制し、該当しない場合は5とする
    */
    $left = filter_input(INPUT_GET, 'left', FILTER_VALIDATE_INT, [
        'options' => ['min_range' => 1],
    ]);
    $right = filter_input(INPUT_GET, 'right', FILTER_VALIDATE_INT, [
        'options' => ['min_range' => 1],
    ]);
    $count = filter_input(INPUT_GET, 'count', FILTER_VALIDATE_INT, [
        'options' => ['min_range' => 1, 'max_range' => 10],
    ]) ?: 5;

    /*
        レコード取得
        SQL文に変数直埋め込みやってますが整数バリデーション通してるので安全です
        ($_GETや$_POSTをそのままぶち込むのは厳禁！)
    */
    if (is_int($left)) {

        // 左端が指定されたとき
        $rows = $pdo->query("
            SELECT * FROM (
                SELECT * FROM samples WHERE id < $left ORDER BY id DESC LIMIT 1
            ) x
            UNION ALL
            SELECT * FROM (
                SELECT * FROM samples WHERE id >= $left ORDER BY id ASC LIMIT $count+1
            ) x
        ")->fetchAll();

        // 余分な先頭レコードを取り出す
        $prev_right = isset($rows[0]) && $rows[0]['id'] < $left ? $rows[0]['id'] : null;
        $rows = array_slice($rows, (int)($prev_right !== null));

        // 余分な末端レコードを取り出す
        $next_left = isset($rows[$count]) ? $rows[$count]['id'] : null;
        $rows = array_slice($rows, 0, $count);

    } elseif (is_int($right)) {

        // 右端が指定されたとき (逆順)
        $rows = $pdo->query("
            SELECT * FROM (
                SELECT * FROM samples WHERE id > $right ORDER BY id ASC LIMIT 1
            ) x
            UNION ALL
            SELECT * FROM (
                SELECT * FROM samples WHERE id <= $right ORDER BY id DESC LIMIT $count+1
            ) x
        ")->fetchAll();

        // 余分な末端レコードを取り出す
        $next_left = isset($rows[0]) && $rows[0]['id'] > $right ? $rows[0]['id'] : null;
        $rows = array_slice($rows, (int)($next_left !== null));

        // 余分な先頭レコードを取り出す
        $prev_right = isset($rows[$count]) ? $rows[$count]['id'] : null;
        $rows = array_slice($rows, 0, $count);

        // 逆順を元に戻す
        $rows = array_reverse($rows);

    } else {

        // 何も指定されなかった時
        $rows = $pdo->query("
            SELECT * FROM samples ORDER BY id ASC LIMIT $count+1
        ")->fetchAll();

        // 余分な先頭レコードは存在しない
        $prev_right = null;

        // 余分な末端レコードを取り出す
        $next_left = isset($rows[$count]) ? $rows[$count]['id'] : null;
        $rows = array_slice($rows, 0, $count);

    }

} catch (\PDOException $e) {

    /* 異常発生 */
    header('Content-Type: text/plain; charset=UTF-8', true, 500);
    exit($e->getMessage());

}

function h($str) {
    return htmlspecialchars($str, ENT_QUOTES, 'UTF-8');
}

header('Content-Type: text/html; charset=UTF-8');

?>
<!DOCTYPE html>
<title>OFFSETを使わない高速なページネーションの実現</title>
<?php if ($rows): ?>
<?php if ($prev_right !== null): ?>
<a href="<?=h("?right=$prev_right&count=$count")?>">前の<?=h($count)?>件</a>
<?php else: ?>
前の<?=h($count)?>件
<?php endif; ?>
<?php if ($next_left !== null): ?>
<a href="<?=h("?left=$next_left&count=$count")?>">次の<?=h($count)?>件</a>
<?php else: ?>
次の<?=h($count)?>件
<?php endif; ?>
<ul>
<?php foreach ($rows as $row): ?>
    <li><?=h("$row[id]: $row[name]")?></li>
<?php endforeach; ?>
</ul>
<?php endif; ?>

FAQ

主キー以外も含めてソートしたい場合は？

ソート方向が共通 であって その順序どおりの複合インデックス が貼られている場合，今回のテクニックを応用できます。以下に日付とIDの複合条件で検索する例を示します。更新日時の新しい順であることに注意してください。

想定するインデックス生成クエリ

CREATE INDEX index_updated_at_and_id ON posts(updated_at, id);

/* 
  ※ 2つ目のインデックスが主キーなので，以下のように書いても同じ効果が得られます。

    CREATE INDEX index_updated_at ON posts(updated_at);
*/

更新日時の新しい順に，奥に進む例

SELECT * FROM (
    SELECT * FROM posts
    WHERE updated_at = '2017-01-01 00:00:00' AND id > 30
       OR updated_at > '2017-01-01 00:00:00'
    ORDER BY updated_at ASC, id ASC
    LIMIT 1
) x
UNION ALL
SELECT * FROM (
    SELECT * FROM posts
    WHERE updated_at = '2017-01-01 00:00:00' AND id <= 30
       OR updated_at < '2017-01-01 00:00:00'
    ORDER BY updated_at DESC, id DESC
    LIMIT 5+1
) x

更新日時の新しい順に，前に戻る例 (逆順なのでarray_reverse適用必須)

SELECT * FROM (
    SELECT * FROM posts
    WHERE updated_at = '2017-01-01 00:00:00' AND id < 30
       OR updated_at < '2017-01-01 00:00:00'
    ORDER BY updated_at DESC, id DESC
    LIMIT 1
) x
UNION ALL
SELECT * FROM (
    SELECT * FROM posts
    WHERE updated_at = '2017-01-01 00:00:00' AND id >= 30
       OR updated_at > '2017-01-01 00:00:00'
    ORDER BY updated_at ASC, id ASC
    LIMIT 5+1
) x

GROUP BYしたい場合は？

これはもうどうしようもないです。この用途ではむしろOFFSETを使うほうがいいかもしれません。

全体件数および総ページ数を求めたい場合は？

idが連続

あらかじめ全体件数を格納するテーブルを作っておくべきでしょう。追加や削除があった場合にはこのテーブルも同時に更新することになります。追加や削除に時間をかけてもいいので検索をより高速にするのがセオリーです。

絞り込みが必要

分かりません。大手検索エンジンはどんなロジックを使っているんでしょうか…？詳しい人教えて下さい。