OFFSETを使わない高速ページネーションを任意のPHPフレームワークで超簡単に実現する

# はじめに

<font color="silver"><del>Qiita芸人とか巷で言われますが</del></font> Qiita の Advent Calendar は初参加です。お手柔らかにお願いします。

[Laravel Advent Calendar 2017](https://qiita.com/advent-calendar/2017/laravel) 4日目の記事になります。

3日目の記事は， @namaozi さんの [Laravel5.5でお手軽にフィルタ&検索付きメモアプリを作るチュートリアル](https://qiita.com/namaozi/items/11b65ccb6b7ecaefc23e) でした。クエリスコープを使ってコントローラをシンプルに保てるのはLaravelのいいところですね！このチュートリアルには登場しませんでしたが，今回の私のエントリはページネーションのお話になります。パフォーマンスチューニングされた複雑なページネーションを書こうとするとコントローラが煩雑になりがちですが，この記事で紹介する手法を使えばとてもシンプルに記述することができます。

ページネーションといえば，Webアプリケーションに頻繁に実装が求められる機能ですね。5年〜10年ほど前であれば

![スクリーンショット 2017-11-03 19.35.10.png](https://qiita-image-store.s3.amazonaws.com/0/25060/901680b3-aeee-1384-2656-7da401b58f55.png)

このように「ページ番号」，場合によっては「総ページ数」も伴うページネーションが主流でした。Elasticsearchなど検索に特化したエンジンを使う場合はこの限りではありませんが，標準的なリレーショナルデータベースであるMySQLでこれを実現しようとすると，以下のような非効率なクエリを発行する必要がありました。

```sql:総ページ数が不要な場合
SELECT * FROM articles
WHERE user_id = 1
ORDER BY updated_at DESC, id DESC
LIMIT 30
OFFSET 1000
```

```sql:総ページ数が必要な場合（2クエリ必要）
SELECT SQL_CALC_FOUND_ROWS * FROM articles
WHERE user_id = 1
ORDER BY updated_at DESC, id DESC
LIMIT 30
OFFSET 1000;

SELECT FOUND_ROWS();
```

後者は常に全件調べる必要があるので問題外として，前者にも以下のような問題点があります。

- オフセット値が中央に近づくにつれて遅くなる
- リアルタイムで更新される場合にページがズレる

解決策としては，MySQLに固執する場合はページ番号による取得を諦め，OFFSETの代わりにWHEREでの範囲絞り込みを使う方法がよく採られてきました。

```sql:OFFSETの代わりにWHEREで範囲を絞り込む場合
SELECT * FROM articles
WHERE user_id = 1 AND (
    updated_at = '2017-12-25' AND id <= 50
    OR updated_at < '2017-12-25'
)
ORDER BY updated_at DESC, id DESC
LIMIT 30
```

- [OFFSETは前の行を読み飛ばすのにはよくない方法](http://use-the-index-luke.com/ja/sql/partial-results/fetch-next-page)
- [YappoLogs: なぜ SQL_CALC_FOUND_ROWS や LIMIT OFFSET のページングが良く無いのか](http://blog.yappo.jp/yappo/archives/000835.html)
- [2014年なんだからCOUNT(*)とかSQL_CALC_FOUND_ROWSとかLIMIT OFFSETのページングはやめようぜ - Togetterまとめ](https://togetter.com/li/640847)
- [Pagination(ページネーション)がずれる、抜ける問題を解決する - Qiita]
 (https://qiita.com/marnie_ms4/items/1dc51042844c85c30550)
- [Web Api でずれないページネーションとSQL - Qiita](https://qiita.com/chikara_funabashi/items/72dde4fae55c9519610d)
- [OFFSETを使わない高速なページネーションの実現 - Qiita](https://qiita.com/mpyw/items/07c03600c2e38e91415e) <small><font color="silver">(自分の記事です，コメント欄でネタバレあり)</font></small>

但し，この方法を使う場合，WHERE条件の生成手順が非常に複雑になります。また，「次の結果があるか」と同時に「前の結果があるか」も取得する場合，UNION ALL を使ってある地点から双方向に検索する必要もあり，複雑さに拍車がかかります。逆順に探索した場合は，結果の並び順を反転する必要があったりもします。
（↑の自分の記事にロジックの実装例があります）

「フレームワークを使えば吸収してくれるのでは？」と思っていた時期もあったんですが，**最新鋭のPHPフレームワークLaravelでさえも，LIMIT+OFFSETの方法にしか対応しておりませんでした**。サードパーティのライブラリも探しましたが，求めているものが見つからず…

じゃあ，無ければつくればいいじゃない！

# Lampager

というわけで作ってみました。任意のフレームワークに対応できる構成にしており，とりあえず自分が好きなLaravelには真っ先に対応させました。実際に業務で必要に迫られて作った経緯があります…

<img width="290" alt="31754281-a36010cc-b4d1-11e7-8371-851f5faa3785.png" src="https://qiita-image-store.s3.amazonaws.com/0/25060/9ebc4f2e-9723-85d4-1d4b-f6f99f162f07.png">

- [lampager/lampager: Rapid pagination for various PHP frameworks](https://github.com/lampager/lampager)
- [lampager/lampager-laravel: Rapid pagination for Laravel](https://github.com/lampager/lampager-laravel)
- [lampager/lampager-cakephp: Rapid pagination for CakePHP](https://github.com/lampager/lampager-cakephp)
- [lampager/lampager-cakephp2: Rapid pagination for CakePHP 2](https://github.com/lampager/lampager-cakephp2)
- [lampager/lampager-idiorm: Rapid pagination for Idiorm and Paris](https://github.com/lampager/lampager-idiorm)

<font color="silver">CakePHPは<del>Contributorの趣向により</del>なぜか3より前に2が対応されてしまいました（笑</font>

# Laravelでのサンプル

リンクを貼って終わるだけではつまらないので，Laravelでサンプルを書いてみましょう。`laravel`コマンドがインストールされている前提で進めます。今回は Tinker で動作確認するところまでをやります。

## 下準備

### 環境構築

```:プロジェクトの作成
laravel new example
cd example
php artisan key:generate
```

```ini:.env
# データベース接続先を必要に応じて編集
DB_CONNECTION=mysql
DB_HOST=127.0.0.1
DB_PORT=3306
DB_DATABASE=homestead
DB_USERNAME=homestead
DB_PASSWORD=secret
```

### Lampagerの導入

```:Lampagerのインストール
composer require lampager/lampager-laravel:^0.2.5
```

```php:config/app.php
<?php

return [

    /* ... */

    'providers' => [

        /* ... */

        /*
         * Package Service Providers...
         */
        Lampager\Laravel\MacroServiceProvider::class,

        /* ... */

    ],

];
```

これで `Eloquent\Builder` `Query\Builder` `Relation` に `->lampager()` マクロが生えます！


### データベース定義

```:Articleのマイグレーションファイル生成
php artisan make:migration create_articles_table
```

```php:database/migrations/XXXX_XX_XX_XXXXXX_create_articles_table.php
<?php

use Illuminate\Support\Facades\Schema;
use Illuminate\Database\Schema\Blueprint;
use Illuminate\Database\Migrations\Migration;

class CreateArticlesTable extends Migration
{
    /**
     * Run the migrations.
     *
     * @return void
     */
    public function up()
    {
        Schema::create('articles', function (Blueprint $table) {
            $table->increments('id');
            $table->unsignedInteger('user_id');
            $table->string('text');
            $table->timestamps();
            $table->foreign('user_id')->references('id')->on('users');
            $table->index(['user_id', 'updated_at']);
        });
    }

    /**
     * Reverse the migrations.
     *
     * @return void
     */
    public function down()
    {
        Schema::dropIfExists('articles');
    }
}
```

```:マイグレーションの実行
php artisan migrate
```

`user_id` を指定しつつ， `updated_at` `id` 軸で効率的にソートができるようにインデックスを張っています。
「更新された順」 → 「作成された順」 の優先度でソートすることを想定しています。

**※ MySQLではクラスタインデックスの仕組みにより，主キーの `id` は自動的に最後に含められます。**

### モデル定義

```:Articleのモデルファイル生成
php artisan make:model Article
```

```php:app\Article.php
<?php

namespace App;

use Illuminate\Database\Eloquent\Model;

class Article extends Model
{
    protected $fillable = ['text'];

    public function user()
    {
        return $this->belongsTo(User::class);
    }
}

```

### シーダー定義

```php:database/seeds/DatabaseSeeder.php
<?php

use Illuminate\Database\Seeder;

class DatabaseSeeder extends Seeder
{
    /**
     * Run the database seeds.
     *
     * @return void
     */
    public function run()
    {
        for ($i = 0; $i < 10; ++$i) {
            $user = factory(App\User::class)->create();
            for ($j = 0; $j < 200; ++$j) {
                App\Article::make(['text' => "article[$i][$j]"])->user()->associate($user)->save();
            }
        }
    }
}
```

```:シーダーの実行
php artisan db:seed
```

Laravel 5.5からはシーダーファイルを分割することができますが，今回はルートシーダーにべた書きで済ませます。

## Tinker から確認してみる

### ページの開始

ユーザIDが`5`のユーザの記事を3件降順に取得してみます。今回は特に更新は行っていないので，作成日時＝更新日時になっています。

```php
$articles = Article::whereUserId(5) // まずEloqunetビルダまたはクエリビルダを生成し，絞り込み条件を書く
    ->lampager()                    // lampager() を呼んでページネータを生成
    ->orderByDesc('updated_at')     // ソート順序を定義する
    ->orderByDesc('id')             // (必ず最後は主キーで終わる)
    ->limit(3)                      // 1ページあたり3件に制限
    ->paginate();                   // 結果を取得
```

![スクリーンショット 2017-11-05 2.29.23.png](https://qiita-image-store.s3.amazonaws.com/0/25060/0f2b3563-6788-d55e-1b05-b4cd599a301c.png)

デフォルトでは， `Lampager\Laravel\PaginationResult` クラスのインスタンスが返されます。レコードは `records` に入り，次のカーソル情報を保持したメタデータは `nextCursor` に入ります。なお，このオブジェクトはLaravelの慣習に倣い，以下のような機能を備えています。

- `JsonSerializable` を実装しており， `json_encode` される際にキャメルケースのプロパティをスネークケースに変換します。
- `IteratorAggregate` を実装しており， foreach にかけると直接 `records` に対してイテレーションが実行できます。

（もちろん，このフォーマット・挙動はすべてカスタム可能です）

### ページを進む

`->paginate()` の引数に次ページへのカーソル情報を渡すと，続きから結果を取得することができます。

```php
$articles = Article::whereUserId(5)
    ->lampager()
    ->orderByDesc('updated_at')
    ->orderByDesc('id')
    ->limit(3)
    ->paginate(['updated_at' => '2017-11-03 15:04:28', 'id' => 997]);
```

![スクリーンショット 2017-11-05 2.34.53.png](https://qiita-image-store.s3.amazonaws.com/0/25060/ea4786d3-2d12-a094-0860-e91e4678fcc7.png)

この際 `->seekable()` オプションを指定すると，前ページへ戻るためのカーソルの取得も試みます。この情報は `previousCursor` に格納されます。もし前ページが存在しない場合は`previousCursor`は`null`になり，`hasPrevious`は`false`になります。**（そもそも探索を行っていない場合は`hasPrevious`も`null`になります）**

```php
$articles = Article::whereUserId(5)
    ->lampager()
    ->orderByDesc('updated_at')
    ->orderByDesc('id')
    ->limit(3)
    ->seekable()
    ->paginate(['updated_at' => '2017-11-03 15:04:28', 'id' => 997]);
```

![スクリーンショット 2017-11-05 2.41.59.png](https://qiita-image-store.s3.amazonaws.com/0/25060/faa8c07e-6e32-ac8c-8519-cca9d371925d.png)

### ページを戻る

`->backward()` オプションを指定すると， `->paginate()` に渡すカーソルを起点にして逆方向に戻ります。2ページ目から1ページ目へ戻ってみましょう。

```php
$articles = Article::whereUserId(5)
    ->lampager()
    ->orderByDesc('updated_at')
    ->orderByDesc('id')
    ->limit(3)
    ->seekable()
    ->backward()
    ->paginate(['updated_at' => '2017-11-03 15:04:28', 'id' => 997]);
```

![スクリーンショット 2017-11-05 2.45.52.png](https://qiita-image-store.s3.amazonaws.com/0/25060/bd764574-46bd-5e5d-ee92-b027b34a2a47.png)

戻ってこれましたね。探索したにも関わらず更なる前ページが見つからなかったので，`hasPrevious`の値は`false`になっています。

### 生成されるSQLの確認

`->paginate()` の代わりに `->build()` を使うと `Eloquent\Builder` または `Query\Builder` のインスタンスが取得できます。

![スクリーンショット 2017-11-05 2.49.27.png](https://qiita-image-store.s3.amazonaws.com/0/25060/3f9a4157-a6df-773a-b968-43c87d5bea56.png)


**※ 但し，これを実行してもそのままでは `->paginate()` と同じ結果は得られません。結果セットを加工する必要があります。**

インデックスが効いているかどうかを確認します。ここではさらに，`created_at` も交えてインデックスを作成している，より複雑な例を見てみましょう。

```sql:インデックス作成に用いたSQL
ALTER TABLE `articles` ADD INDEX `articles_user_id_updated_at_created_at_index`(`user_id`, `updated_at`, `created_at`);
```

![スクリーンショット 2017-11-05 2.57.02.png](https://qiita-image-store.s3.amazonaws.com/0/25060/ed659202-a1cc-7891-654a-d351c2b8842c.png)

`type`が`range`なのでしっかりインデックス効いてますね。また`Using index condition`なので Index Condition Pushdown 最適化も効いてます。バッチリ！

（参考） [MySQL 5.6で追加されたICPを追ってみました。 - Qiita](https://qiita.com/hrokmim/items/7843fcd362e348e9a857)

# Q & A

## ソート軸にNULLが入っても大丈夫ですか？

未対応です。もしこれを考慮するとなると考えたくもないぐらいロジックが複雑になりますね…

[Sorting by nullable fields · Issue #22 · lampager/lampager](https://github.com/lampager/lampager/issues/22)

応急処置的な対応としては，MySQLならバージョン5.7から使える生成カラムを使い，**任意の式を整数値としてあらかじめ格納しておく**という方法が考えられます。以下の記事ではそれに関連したテクニックを使っています。

[MySQLでLaravel標準のSoftDeletesを使った論理削除とユニーク制約を両立させる方法 - Qiita](https://qiita.com/mpyw/items/d3e25860ecaaeb8340ab)

## 全文検索したいんだけど？

Elasticsearch使ってください。Laravel向けにElasticquentなるものもあるそうです。

- [elasticquent/Elasticquent: Maps Laravel Eloquent models to Elasticsearch types](https://github.com/elasticquent/Elasticquent)
- [Elasticquent を使って、LaravelからElasticSearchのデータを取得する - Qiita](https://qiita.com/nonoichi123/items/c6a00b49b9eabfe6960e)

なおMySQL・Elasticsearchともに，全文検索インデックスはツリーに対する直接の絞り込みができないため，事実上**オフセット指定は必須**です。

- Elasticsearch の `from`+`size` は MySQLの `OFFSET`+`LIMIT` と本質的にやっていることは同じですが，オンメモリストレージという特性を活かしてハードウェア性能で殴れるという違いがあります。
- Elasticsearch の Scroll API は，全文検索をカーソルベースで実現しているものですが，これは初回クエリ実行でスナップショットを作成し，それを指定した時間だけ保持しておくことによって実現されています。「全文検索 + カーソルベース」という夢のような機能が実現されていますが，ステートフルになってしまう弱点があります。<br>（参考） [ElasticsearchのScroll APIをためしてみた - 平日インプット週末アウトプットぶろぐ](http://blog.soushi.me/entry/2016/12/23/162825)

## 俺が愛用してるフレームワークがねえじゃん！

Contributor大募集。是非プロジェクトに参加していただければ幸いです。参考程度に個人的な優先度の★をつけておきます。

- [lampager/lampager-symfony](https://github.com/lampager/lampager-symfony) ★★☆
- [lampager/lampager-zendframework](https://github.com/lampager/lampager-zendframework) ★★☆
- [lampager/lampager-codeigniter](https://github.com/lampager/lampager-codeigniter) ★★☆
- [lampager/lampager-yii](https://github.com/lampager/lampager-yii) ★☆☆
- [lampager/lampager-phalcon](https://github.com/lampager/lampager-phalcon) ★☆☆
- [lampager/lampager-fuel](https://github.com/lampager/lampager-fuel) ☆☆☆ <font color="silver"> （最近淘汰され気味）</font>

主要なフレームワークのリポジトリは作ってあります。
（ブランチを変えるだけでは共存が厳しいレベルで前方互換性の無い古いバージョンに対応させる必要がある場合，CakePHP 2のようにリポジトリそのものを分けることも検討します）

**注意: PHPバージョン5.5以前は切り捨てています。古いアプリケーションを対象にして古いバージョンに対応するにしても，PHPの環境は5.6までアップデートされていることが前提です。**

-----

Advent Calendar 初参戦の記事をお読み頂きありがとうございました。
明日は @mpyw さんです！