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

はじめに

Qiita芸人とか巷で言われますが Qiita の Advent Calendar は初参加です。お手柔らかにお願いします。

Laravel Advent Calendar 2017 4日目の記事になります。

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

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

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

総ページ数が不要な場合

SELECT * FROM articles
WHERE user_id = 1
ORDER BY updated_at DESC, id DESC
LIMIT 30
OFFSET 1000

総ページ数が必要な場合（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での範囲絞り込みを使う方法がよく採られてきました。

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は前の行を読み飛ばすのにはよくない方法
• YappoLogs: なぜ SQL_CALC_FOUND_ROWS や LIMIT OFFSET のページングが良く無いのか
• 2014年なんだからCOUNT(*)とかSQL_CALC_FOUND_ROWSとかLIMIT OFFSETのページングはやめようぜ - Togetterまとめ
• [Pagination(ページネーション)がずれる、抜ける問題を解決する - Qiita]
  (https://qiita.com/marnie_ms4/items/1dc51042844c85c30550)
• Web Api でずれないページネーションとSQL - Qiita
• OFFSETを使わない高速なページネーションの実現 - Qiita (自分の記事です，コメント欄でネタバレあり)

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

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

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

Lampager

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

• lampager/lampager: Rapid pagination for various PHP frameworks
• lampager/lampager-laravel: Rapid pagination for Laravel
• lampager/lampager-cakephp: Rapid pagination for CakePHP
• lampager/lampager-cakephp2: Rapid pagination for CakePHP 2
• lampager/lampager-idiorm: Rapid pagination for Idiorm and Paris

CakePHPはContributorの趣向によりなぜか3より前に2が対応されてしまいました（笑

Laravelでのサンプル

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

下準備

環境構築

プロジェクトの作成

laravel new example
cd example
php artisan key:generate

.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

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

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

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);
    }
}

シーダー定義

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件降順に取得してみます。今回は特に更新は行っていないので，作成日時＝更新日時になっています。

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

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

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

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

ページを進む

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

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

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

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

ページを戻る

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

$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]);

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

生成されるSQLの確認

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

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

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

インデックス作成に用いたSQL

ALTER TABLE `articles` ADD INDEX `articles_user_id_updated_at_created_at_index`(`user_id`, `updated_at`, `created_at`);

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

（参考） MySQL 5.6で追加されたICPを追ってみました。 - Qiita

Q & A

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

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

Sorting by nullable fields · Issue #22 · lampager/lampager

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

MySQLでLaravel標準のSoftDeletesを使った論理削除とユニーク制約を両立させる方法 - Qiita

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

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

• elasticquent/Elasticquent: Maps Laravel Eloquent models to Elasticsearch types
• Elasticquent を使って、LaravelからElasticSearchのデータを取得する - Qiita

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

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

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

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

• lampager/lampager-symfony ★★☆
• lampager/lampager-zendframework ★★☆
• lampager/lampager-codeigniter ★★☆
• lampager/lampager-yii ★☆☆
• lampager/lampager-phalcon ★☆☆
• lampager/lampager-fuel ☆☆☆ （最近淘汰され気味）

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

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

---

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