Edited at
LaravelDay 4

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

More than 1 year has passed since last update.


はじめに

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

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

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

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

スクリーンショット 2017-11-03 19.35.10.png

このように「ページ番号」,場合によっては「総ページ数」も伴うページネーションが主流でした。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

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

(↑の自分の記事にロジックの実装例があります)

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

じゃあ,無ければつくればいいじゃない!


Lampager

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

31754281-a36010cc-b4d1-11e7-8371-851f5faa3785.png

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(); // 結果を取得

スクリーンショット 2017-11-05 2.29.23.png

デフォルトでは, 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]);

スクリーンショット 2017-11-05 2.34.53.png

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

$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


ページを戻る

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

スクリーンショット 2017-11-05 2.45.52.png

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


生成されるSQLの確認

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

スクリーンショット 2017-11-05 2.49.27.png

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

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


インデックス作成に用いた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

typerangeなのでしっかりインデックス効いてますね。また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なるものもあるそうです。

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


  • Elasticsearch の from+size は MySQLの OFFSET+LIMIT と本質的にやっていることは同じですが,オンメモリストレージという特性を活かしてハードウェア性能で殴れるという違いがあります。

  • Elasticsearch の Scroll API は,全文検索をカーソルベースで実現しているものですが,これは初回クエリ実行でスナップショットを作成し,それを指定した時間だけ保持しておくことによって実現されています。「全文検索 + カーソルベース」という夢のような機能が実現されていますが,ステートフルになってしまう弱点があります。
    (参考) ElasticsearchのScroll APIをためしてみた - 平日インプット週末アウトプットぶろぐ


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

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

主要なフレームワークのリポジトリは作ってあります。

(ブランチを変えるだけでは共存が厳しいレベルで前方互換性の無い古いバージョンに対応させる必要がある場合,CakePHP2のようにリポジトリそのものを分けることも検討します)

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


Advent Calendar 初参戦の記事をお読み頂きありがとうございました。

明日は @mpyw さんです!