中間テーブルに外部キーを設定しない場合のLaravelにおける性能劣化を検証する

こんにちはみなさん

Lalavelではリレーションを簡単に表現できるため、そこに隠されてあまり意識されない中間テーブルに外部キー制約を貼り忘れると、かなり性能劣化するようです。
これは、LaravelのEloquent上でリレーション先のテーブルに検索を書ける場合に`whereHas`を使うのですが、そのとき、多対多のリレーションに対しては相関サブクエリが発生しており、外部キーが設定されていないとこれがもろに影響してくるみたいです。

まあ、インデックス貼り忘れると何がやばいのかって実感するのにはいいんじゃないかって思いました。

# 問題設定

 **１万人の生徒がいて、彼らが各々持ち物を1000種類ある中からいくつか持っているという状況。生徒と彼らが持つ持ち物のリストを作成する。1ページにまとめるのは大変なので、ページネーションすること。生徒の名前や特定の持ち物を持った生徒で検索したい。**
たいして難しい問題では無いですが、これを元に検証を進めてみましょう。

## モデルとマイグレーション

まずは生徒と持ち物のモデルを作っておきます。

### 生徒(Student)
モデルは以下のとおりです。検索用のスコープメソッドを作っておきます。

```app/Entities/Student.php
<?php

namespace App\Entities;

use Illuminate\Database\Eloquent\Model;

class Student extends Model
{
    public function items()
    {
        return $this->belongsToMany(Item::class);
    }

    public function scopeSearch($query, string $search)
    {
        $query->where('first_name', 'like', "%${search}%")
            ->orWhere('last_name', 'like', "%${search}%")
            ->orWhereHas('items', function($builder) use ($search) {
                $builder->where('name', 'like', "%${search}%");
            });
    }
}
```
同時にマイグレーションを作ると

```php

<?php

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

class CreateStudentsTable extends Migration
{
    /**
     * Run the migrations.
     *
     * @return void
     */
    public function up()
    {
        Schema::create('students', function (Blueprint $table) {
            $table->increments('id');
            $table->string('first_name');
            $table->string('last_name');
            $table->timestamps();

            $table->index(['first_name']);
            $table->index(['last_name']);
        });
    }

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

### 持ち物(Item)
モデルは空っぽです。

```app/Entities/Item.php
<?php

namespace App\Entities;

use Illuminate\Database\Eloquent\Model;

class Item extends Model
{
    //
}
```
マイグレーションには名前にインデックスを貼っておきます

```php
<?php

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

class CreateItemsTable extends Migration
{
    /**
     * Run the migrations.
     *
     * @return void
     */
    public function up()
    {
        Schema::create('items', function (Blueprint $table) {
            $table->increments('id');
            $table->string('name');
            $table->timestamps();

            $table->index(['name']);
        });
    }

    /**
     * Reverse the migrations.
     *
     * @return void
     */
    public function down()
    {
        Schema::dropIfExists('items');
    }
}
```
### 中間テーブル
中間テーブルのマイグレーションも作っておきます。

```php
<?php

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

class CreateItemStudent extends Migration
{
    /**
     * Run the migrations.
     *
     * @return void
     */
    public function up()
    {
        Schema::create('item_student', function (Blueprint $table) {
            $table->bigIncrements('id');
            $table->unsignedInteger('student_id');
            $table->unsignedInteger('item_id');
            $table->timestamps();

            $table->foreign('student_id')->references('id')->on('students');
            $table->foreign('item_id')->references('id')->on('items');
        });
    }

    /**
     * Reverse the migrations.
     *
     * @return void
     */
    public function down()
    {
        Schema::dropIfExists('item_student');
    }
}
```
この中間テーブルに外部キーをはるか否かを検証することになります。

## データの投入
適当なランダムデータを作って検証に使いましょう。

```database/seeds/StudentSeeder.php
<?php

use Illuminate\Database\Seeder;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Str;

class StudentSeeder extends Seeder
{
    /**
     * Run the database seeds.
     *
     * @return void
     */
    public function run()
    {
        $students = [];
        for ($num = 0; $num < 9999; $num++) {
            $students[] = [
                'first_name' => Str::random(6),
                'last_name' => Str::random(6)
            ];
        }
        $students[] = [
            'first_name' => 'John',
            'last_name' => 'Doe'
        ];
        DB::table('students')->insert($students);
    }
}
```
こんな感じで適当なデータを詰め込みます。
Item側も同様にした上で適当にお互いをひっつけます。

```database/seeds/StudentItemSeeder.php
<?php

use App\Entities\Item;
use App\Entities\Student;
use Illuminate\Database\Seeder;
use Illuminate\Support\Facades\DB;

class StudentItemSeeder extends Seeder
{
    /**
     * Run the database seeds.
     *
     * @return void
     */
    public function run()
    {
        $sids = Student::select('id')->get()->pluck('id')->all();
        $iids = Item::select('id')->get()->pluck('id');
        
        $data = [];
        foreach ($sids as $sid) {
            $random_ids = $iids->random(mt_rand(2, 4))->all();
            foreach ($random_ids as $iid) {
                $data[] = [
                    'student_id' => $sid,
                    'item_id' => $iid,
                ];
            }
        }

        DB::table('item_student')->insert($data);
    }
}
```

## データベースのログを出す
データベースのログを出すようにしておきましょう。

```app/Providers/AppServiceProvider.php
    public function boot()
    {
        \DB::listen(function ($query) {
            $sql = $query->sql;
            for ($i = 0; $i < count($query->bindings); $i++) {
                $sql = preg_replace("/\?/", "'" . $query->bindings[$i] . "'", $sql, 1);
            }

            \Log::debug("SQL", ["time" => sprintf("%f ms", $query->time), "sql" => $sql]);                                                               
        });
    }
```

# 検証
検証はGETアクセスで`search`フィールドがあったら検索をするようにします。

```app/Http/Controllers/IndexController.php
    public function index(Request $request)
    {
        $query = Student::with('items');
        if ($search = $request->input('search')) {
            $query->search($search);
        }
        $students = $query->paginate();
        return view('students/index', compact('students'));
    }
```
結果が帰ってくるのは当然として、どのようなクエリ結果が出るのか確認してみましょう。

## 外部キー制約が存在する
先程のマイグレーションでは外部キー制約を貼ってありましたが、この状態で`GET - /index?search=abc`のようなクエリを投げると以下のようなクエリが発生します。

```
{"time":"56.410000 ms","sql":"select count(*) as aggregate from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%'))"} 
{"time":"61.270000 ms","sql":"select * from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%')) limit 15 offset 0"} 
{"time":"0.590000 ms","sql":"select `items`.*, `item_student`.`student_id` as `pivot_student_id`, `item_student`.`item_id` as `pivot_item_id` from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `item_student`.`student_id` in (1857, 4144)"} 
```
ページネーションがあるため、カウントがはじめに走っています。
メインの検索クエリにかかる時間はだいたい60msec前後といったところでしょうか
クエリの中に`exists`が確認できますが、こいつが相関サブクエリを発生させています。

インデックスが聞くような検索でもないので、基本、ALL検索にはなっているはずですが、EXPLAINを覗いて見ましょう。

```
+----+--------------------+--------------+------------+--------+--------------------------------------------------------------+---------------------------------+---------+--------------------------------+-------+----------+-------------+
| id | select_type        | table        | partitions | type   | possible_keys                                                | key                             | key_len | ref                            | rows  | filtered | Extra       |
+----+--------------------+--------------+------------+--------+--------------------------------------------------------------+---------------------------------+---------+--------------------------------+-------+----------+-------------+
|  1 | PRIMARY            | students     | NULL       | ALL    | NULL                                                         | NULL                            | NULL    | NULL                           | 10266 |   100.00 | Using where |
|  2 | DEPENDENT SUBQUERY | item_student | NULL       | ref    | item_student_student_id_foreign,item_student_item_id_foreign | item_student_student_id_foreign | 4       | homestead.students.id          |     2 |   100.00 | NULL        |
|  2 | DEPENDENT SUBQUERY | items        | NULL       | eq_ref | PRIMARY                                                      | PRIMARY                         | 4       | homestead.item_student.item_id |     1 |    11.11 | Using where |
+----+--------------------+--------------+------------+--------+--------------------------------------------------------------+---------------------------------+---------+--------------------------------+-------+----------+-------------+
```
## 外部キーをとった場合
外部キー制約を外すとどうなるでしょうか。
いや、やばいことはわかっているのですが、どれだけやばいのかを検証してみます。

```php

        Schema::create('item_student', function (Blueprint $table) {
            $table->bigIncrements('id');
            $table->unsignedInteger('student_id');
            $table->unsignedInteger('item_id');
            $table->timestamps();

            // $table->foreign('student_id')->references('id')->on('students');
            // $table->foreign('item_id')->references('id')->on('items');
        });
```
こんな状態でデータを作り直してみましょう。

```sh
php artisan migrate:fresh --seed
```
この状態で先程のGETを走らせましょう。

```
{"time":"45321.270000 ms","sql":"select count(*) as aggregate from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%'))"} 
{"time":"45730.320000 ms","sql":"select * from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%')) limit 15 offset 0"} 
{"time":"5.120000 ms","sql":"select `items`.*, `item_student`.`student_id` as `pivot_student_id`, `item_student`.`item_id` as `pivot_item_id` from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `item_student`.`student_id` in (3843)"} 
```
45秒ずつかかっているので、合計で90秒。
普通にタイムアウトするレベルですね。
EXPLAINはどうなるでしょうか。

```
+----+--------------------+--------------+------------+--------+---------------+---------+---------+--------------------------------+-------+----------+-------------+
| id | select_type        | table        | partitions | type   | possible_keys | key     | key_len | ref                            | rows  | filtered | Extra       |
+----+--------------------+--------------+------------+--------+---------------+---------+---------+--------------------------------+-------+----------+-------------+
|  1 | PRIMARY            | students     | NULL       | ALL    | NULL          | NULL    | NULL    | NULL                           | 10266 |   100.00 | Using where |
|  2 | DEPENDENT SUBQUERY | item_student | NULL       | ALL    | NULL          | NULL    | NULL    | NULL                           | 29557 |    10.00 | Using where |
|  2 | DEPENDENT SUBQUERY | items        | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | homestead.item_student.item_id |     1 |    11.11 | Using where |
+----+--------------------+--------------+------------+--------+---------------+---------+---------+--------------------------------+-------+----------+-------------+
```
select_typeは前と同じですが、item_studentの検索で、type=ALLが出ています。
おそらくですが、rowsの掛け算になっていて大量の計算コストが発生しているのだと思います。

## ただのindexを貼った場合
何らかの事情で外部キーを設定できない場合、最低限インデックスをはろうと思うでしょう。
中間テーブルに外部キー制約ではなく、単純なindexを貼ったらどうなるでしょうか。

```php

            $table->index(['student_id']);
            $table->index(['item_id']);
```

この状態で再度検索を投げてみましょう。

```
{"time":"60.810000 ms","sql":"select count(*) as aggregate from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%'))"} 
{"time":"62.000000 ms","sql":"select * from `students` where (`first_name` like '%abc%' or `last_name` like '%abc%' or exists (select * from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `students`.`id` = `item_student`.`student_id` and `name` like '%abc%')) limit 15 offset 0"} 
{"time":"1.050000 ms","sql":"select `items`.*, `item_student`.`student_id` as `pivot_student_id`, `item_student`.`item_id` as `pivot_item_id` from `items` inner join `item_student` on `items`.`id` = `item_student`.`item_id` where `item_student`.`student_id` in (5744, 7759, 8877)"} 
```
外部キーを貼った状態と同じです。
念の為EXPLAINもみてみます。

```
+----+--------------------+--------------+------------+--------+---------------+---------+---------+--------------------------------+-------+----------+-------------+
| id | select_type        | table        | partitions | type   | possible_keys        | key     | key_len | ref                            | rows  | filtered | Extra       |
+----+--------------------+--------------+------------+--------+----------------------------------------------------------+-------------------------------+---------+--------------------------------+-------+----------+-------------+
|  1 | PRIMARY            | students     | NULL       | ALL    | NULL                                                     | NULL                          | NULL    | NULL                           | 10266 |   100.00 | Using where |
|  2 | DEPENDENT SUBQUERY | item_student | NULL       | ref    | item_student_student_id_index,item_student_item_id_index | item_student_student_id_index | 4       | homestead.students.id          |     2 |   100.00 | NULL        |
|  2 | DEPENDENT SUBQUERY | items        | NULL       | eq_ref | PRIMARY                                                  | PRIMARY                       | 4       | homestead.item_student.item_id |     1 |    11.11 | Using where |
+----+--------------------+--------------+------------+--------+----------------------------------------------------------+-------------------------------+---------+--------------------------------+-------+----------+-------------+
```
外部キー制約を貼っているときと、外見上ほとんど変化なしです。
rowsが同じなので、検索コストも同じみたいです。

## 一部だけ外部キーを貼った
一部だけ外部キーを貼るとどうなるでしょうか

```php
            $table->foreign('student_id')->references('id')->on('students');
            // $table->foreign('item_id')->references('id')->on('items');
```
もう時間だけ抜き出しますが、

```
"time":"62.080000 ms"
"time":"31.130000 ms"
```
十分な速度を出せました。

逆転させると少し性能が下がります。

```php
            // $table->foreign('student_id')->references('id')->on('students');
            $table->foreign('item_id')->references('id')->on('items');
```

```
"time":"2809.290000 ms"
"time":"1235.500000 ms"
```

# まとめ
アタリマエのことですが、中間テーブルにもインデックスなり外部キーなりを貼りましょうっていう話でした。
ユニットテストとかだとデータ量が少なすぎるので、気づかないことが多いのですが、実際のアプリだと、データ数が多くなると飛躍的に検索コストが上がってきます。

今回はこんなところです。