GraphQL と N+1 SQL 問題と dataloader

この記事ではハイパフォーマンスな GraphQL サーバを実装するのに避けて通れない N+1 SQL 問題について解説します。

## TL;DR
- GraphQL は resolver を個別にかつ再帰的に実行していくため、 RDB のリレーションを効率的に先読みすることができません。そのため一般的に遅延読み込みを行います。
- Facebook 社は GraphQL で遅延読み込みするために dataloader という npm パッケージを公開しており、各種言語にその移植版のライブラリが存在しているので、それを使って N+1 SQL 問題を抑制しましょう。

## （復習）N+1 SQL 問題とは
N+1 問題は「1 つの SQL で N 件のレコードをフェッチしたあと、それぞれ対して関連するレコードを個別にフェッチするのに N つの SQL を発行している」状態を指す言葉です。言葉で書いてもよく分からないので擬似コードを示します:

```rb
# N 個の articles をフェッチする（SQL 1 つ）
articles = Article.all

users = articles.map do |article|
  # article ごとに user をフェッチする（SQL 1 つが N 回）
  article.user
end
```

このコードを実行すると以下のような SQL が実行されます:

```sql
-- N 個の articles をフェッチする（SQL 1 つ）
SELECT * FROM articles;
-- article ごとに user をフェッチする（SQL 1 つが N 回）
SELECT * FROM users WHERE id = 1;
SELECT * FROM users WHERE id = 2;
SELECT * FROM users WHERE id = 3;
SELECT * FROM users WHERE id = 4;
SELECT * FROM users WHERE id = 5;
```

（ログの順番からすると 1+N SQL と呼ぶほうが理解しやすい気がしますが）これが N+1 SQL 問題です。SQL を実行する際はさまざまなオーバーヘッドがあります:

- RDB サーバと通信するための時間
- RDBMS が SQL を解析する時間
- など

SQL を複数回繰り返すと時間がかかるだけでなく、 DB が動いているサーバの CPU を過剰に消費した結果他のセッションにも影響が及ぶ可能性があります。

N+1 SQL 問題を解決するには N 回繰り返している SQL を 1 つにまとめる必要があります。一般的にこのひとまとめにした SQL を実行するタイミングによって 2 通りのアプローチが存在します:

- **先読み込み（Eager Loading）**: 必要になる前に読み込む
- **遅延読み込み（Lazy Loading）**: 必要なデータが分かったあとで読み込む

### 先読み込み
Rails を含め多くの WAF で広くサポートされているのが先読み込みです:

```rb
# N 個の articles をフェッチして（SQL 1 つ）
# 同時に N 個の users もフェッチする（SQL 1 つ）
articles = Article.includes(:user).all

users = articles.map do |article|
  # ロード済みなので SQL は発行されない
  article.user
end
```

このとき以下のような SQL が実行されます:

```sql
-- N 個の articles をフェッチする（SQL 1 つ）
SELECT * FROM articles;
-- 同時に N 個の users もフェッチする（SQL 1 つ）
SELECT * FROM users WHERE id IN (1, 2, 3, 4, 5);
```

### 遅延読み込み
遅延読み込みするには、何かしらの方法で必要となるリソースを表明し、然る後に必要なデータをまとめて読み込みます。ここでは [dataloader](https://github.com/sheerun/dataloader) gem を使った実装を示します:

```rb
articles = Article.all

user_loader = Dataloader.new do |user_ids|
  result = {}
  # user_ids のデータをまとめてとってくる
  User.where(id: user_ids).each do |user|
    result[user.id] = user
  end
  user_ids.each do |user_id|
    # データが見つからなかったときは nil を使う
    result[user_id] ||= nil
  end
  result
end

promises = articles.map do |article|
  # 必要な user id を表明する。user_loader は promise を返し、SQL は実行しない
  user_loader.load(article.user_id)
end

# まとめた SQL が実行される
promises.first.sync #=> User

# すでに↑でロードされているので SQL は実行されない
promises.second.sync #=> User
```

このとき実行される SQL は以下の通りです:

```sql
-- N 個の articles をフェッチする（SQL 1 つ）
SELECT * FROM articles;
-- 同時に N 個の users もフェッチする（SQL 1 つ）
SELECT * FROM users WHERE id IN (1, 2, 3, 4, 5);
```

### 先読み込み vs 遅延読み込み
先読み込みと遅延読み込みを比較します:

- 先読み込み
  - 実装が簡単。データを使うときにはすでにデータがそこにあるので使うのも楽。
  - データを使う場所と、データを読み込む場所がコード上で離れる傾向があるため、開発をしていくうちに不要なデータを先読みし続けたり、逆に適切に先読みできておらず N+1 SQL が発生したりする。
- 遅延読み込み
  - 必要なリソースの情報をためる特別な機構が必要なので実装が複雑。
  - 実際に使うデータだけをロードすることが保証される。

一長一短です。 GraphQL ではどうなるのでしょうか。

## GraphQL におけるクエリの実行
以下のような schema を持った GraphQL サーバを考えてみましょう:

```graphql
type Query {
  articles: [Article]
}
type Article {
  id: ID
  user: User
}
type User {
  id: ID
  name: String
}
```

このサーバに対して以下の query を実行したとします:


```graphql
{
  articles {
    user {
      id
      name
    }
    id
  }
}
```

このとき GraphQL はクエリ文字列のパース処理などのもろもろの作業を行ったあと、結果を得るために内部で以下のようなことを行います:

<details><summary>動作（真剣に読まなくていい）</summary><div>

- Query type の articles field 用の resolver を実行する ... (1)
    - (1) の resolver の結果得られた Article の配列の個々の要素を入力として Article type の user field 用の resolver を実行する ... (2)
        - (2) の resolver の結果得られた User を入力として User type の name field 用の resolver を実行し、その結果を name として使う
        - (2) の resolver の結果得られた User を入力として User type の id field 用の resolver を実行し、その結果を id として使う
    - (1) の resolver の結果得られた Article の配列の個々の要素入力として Article type の id field 用の resolver を実行する

詳しくは [6. Execution](https://facebook.github.io/graphql/June2018/#sec-Execution) を参照してください

</div></details>

ここで重要なのは以下の点です:

- GraphQL のクエリは木構造になっているので、 GraphQL は実行時に再帰的に resolver を実行していく必要がある
- 配列に要素ごとに resolver を実行するので、 resolver の中で単純に SQL を実行すると N+1 SQL 問題が発生する
- resolver はいつどこで実行されるのか、実行結果に対してどういう resolver が呼ばれるのか知らないので、 先読みをすることができない[^1]

言い換えると **GraphQL では N+1 SQL 問題が発生しやすく、遅延読み込みを使わないとそれを回避することが難しい** です。

[^1]: 先読みしてもいいけど、使われない可能性がある。今回の例で言えば `[Article]` を resolve するときに `User` を 先読み込みしてもいいけど、クエリが `{ articles { id } }` だったら無駄になる

## GraphQL で遅延読み込み
このような背景から GraphQL の開発元である Facebook 社は [dataloader](https://github.com/facebook/dataloader) というライブラリを参考実装として公開しています。このライブラリを同じく Facebook が公開している [JavaScript のサンプル実装](https://github.com/graphql/graphql-js)で使うと簡単に遅延読み込みを行うことができます。やっていることは基本的に↑で言及した dataloader gem と全く同じです。[^2]

[^2]: 名前から明らかだけど JS 版の dataloader を Ruby に移植したのが dataloader gem

### 遅延評価をどう教えるか
ところで前述の通り遅延読み込みは先に必要なデータを一通り宣言したあとで、それらをまとめて一括で解決することで効率化します。GraphQL はある resolver の結果を次の resolver へと再帰的に渡していくのですが、遅延読み込みするためには、 GraphQL サーバは resolver から返された値をそのまま使っていいのか、それとも遅延評価する必要があるのか知る術を持たなければなりません。

JavaScript の場合、言語に組み込みの [Promise](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/Promise) が存在するため話は早いです。resolver が promise を返した場合、その promise が fullfilled になるまで GraphQL は後続の評価を待ちます。

JavaScript のような組み込み機能がない言語の場合、 GraphQL に明示的に教えて上げる必要があります。例えば graphql-ruby の場合、 `GraphQL::Schema.lazy_resolve` で指定します:

```rb
class MySchema < GraphQL::Schema
  lazy_resolve Promise, :sync
end
```

こうすると graphql-ruby は resolver が `Promise` クラスのインスタンスを返したらそれを後回しにして、他にやることがなくなったらそのインスタンスの `sync` メソッドを実行してその返り値を使ってクエリの実行を再開します。

Go 言語の [graph-gophers/dataloader](https://github.com/graph-gophers/dataloader) の場合、 GraphQL 実装に遅延評価の仕組みが無いため、 struct を作ったときに Promise を内部的に作ってしまい、 resolver の中で評価を行います。

## まとめ
GraphQL において単純に実装すると N+1 SQL 問題が頻出すること、遅延読み込みを用いて解決することを紹介しました。

そもそも遅延読み込みは実装が面倒な反面、最適化が容易という長所があります。GraphQL のレールの上で遅延読み込みを行うことで複雑さを低下させつつ、普通に実装するより柔軟でパフォーマンスがよい API を実装することができるはずです。