GraphQL で N+1 問題を解決する 4 つのアプローチ

概要

この記事では TypeScript + Apollo Server + TypeORM を前提として話を進めます。

• GraphQL のサーバ実装では 1:N 構造において N+1 問題が発生しがち
• 技術選定がこれからの場合や、ORM が置き換えられる場合は N+1 を考慮した ORM を検討するのが良い
• それ以外の場合は DataLoader を実装するのが良さそう。ライブラリを使えばそんなに大変ではない
• JOIN での解決も可能だが、 GraphQL の道を踏み外している(ように感じる)

GraphQL における N+1 問題

GraphQL サーバで 1:N のデータ構造を実装しクエリすると、すぐに N+1 問題に行き当たります。User と Post が 1:N の関係となる、以下の例を見てみましょう。

type User {
  id: Int!
  name: String!
  posts: [Post!]!
}

type Post {
  id: Int!
  title: String!
  user: User!
}

type Query {
  users: [User!]!
}

Apollo Server と TypeORM を使って素朴に Resolver を実装すると、以下のようになります。

export const resolvers: Resolvers = {
  User: {
    posts: async (parent: User) => await postsOfUser(parent),
  },

  Query: {
    users: async () => await users(),
  },
}

const postsOfUser = async (user: User): Promise<Post[]> => {
  const postRepository = getConnection().getRepository(Post)
  return await postRepository.find({ where: { user } })
}

const users = async (): Promise<User[]> => {
  const userRepository = getConnection().getRepository(User)
  return await userRepository.find()
}

この実装に対し、以下のようなクエリを実行することを考えます。

query ExampleQuery {
  users {
    id
    name
    posts {
       id
       title
    }
  }
}

すると、Resolver はまず users() を実行して User を全件取得します。その後、それぞれの user に対して postsOfUser(user) を実行します。その結果、データベースへのアクセスは以下のようになります。

query: SELECT `User`.`id` AS `User_id`, `User`.`name` AS `User_name` FROM `user` `User`
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` = ? -- PARAMETERS: [1]
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` = ? -- PARAMETERS: [2]
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` = ? -- PARAMETERS: [3]
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` = ? -- PARAMETERS: [4]
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` = ? -- PARAMETERS: [5]

本例では User が 5 件登録されていましたが、ユーザーを全件取得するために 1 回、それぞれの User に対して posts を取得するために各 1 回、合計 6 回の SELECT が発生しました。これが N+1 問題です^[1]。

データ量が少ないうちは問題に気付きにくいですが、データ量が増えた場合や、1:N が多重階層となった場合 (例えば上記に加え Post:Comment = 1:N となる Comment を考える場合) などでは、パフォーマンスに与える影響が爆発的に大きくなります。

幸い、この N+1 問題を回避する方法はいくつかあります。上記の例を ベースケース として、それぞれの解決方法を紹介します。

方法1: DataLoader

Facebook により提供されている DataLoader というライブラリを使う方法です。DataLoader には Batching と呼ばれる機能があり、同一テーブルに対する複数の SELECT を 1 本にまとめてくれます。これを使うと、 Resolver の実装は以下のようになります。

export const resolvers: Resolvers = {
  User: {
    posts: async (parent: User) => await postsLoader.load(parent.id),
  },

  Query: {
    users: async () => await users(),
  },
}

const users = async (): Promise<User[]> => {
  const userRepository = getConnection().getRepository(User)
  return await userRepository.find()
}

const postsLoader = new DataLoader(async (keys): Promise<Post[][]> => {
  const postRepository = getConnection().getRepository(Post)
  const posts = await postRepository.find({ user: { id: In(keys as number[]) } })
  return keys.map((userId) => posts.filter((post) => post.userId! === userId))
})

ベースケースでは postsOfUser を使い User に紐づく Post を取得していましたが、 DataLoader を用いる場合は postsLoader という DataLoader のインスタンスを利用します。この Resolver に対して上記と同じクエリを実行しても、 SELECT は User と Post それぞれに対して 1 回ずつしか発行されません。

query: SELECT `User`.`id` AS `User_id`, `User`.`name` AS `User_name` FROM `user` `User`
query: SELECT `Post`.`id` AS `Post_id`, `Post`.`title` AS `Post_title`, `Post`.`userId` AS `Post_userId` FROM `post` `Post` WHERE `Post`.`userId` IN (?, ?, ?, ?, ?) -- PARAMETERS: [1,2,3,4,5]

DataLoader はリレーションの数だけ実装する必要があるので手間が増えますが、ライブラリの支援を受けることもできます。例えば TypeGraphQL-DataLoader を使うと、デコレータによるシンプルな DataLoader の実装が可能です。このあたりは以下の記事が参考になります。

https://zenn.dev/tatta/books/5096cb23126e64/viewer/e1ddb1

実際には Batching に加えて Caching の恩恵も受けるために、 DataLoader は Context の一部として実装することが多いようです。

方法2: テーブル結合

SQL に慣れた方は、ここまで読んで「テーブルを結合すれば 1 本の SELECT に纏められるのでは」と思うでしょう。その通りです。TypeORM の場合は relations を使って LEFT JOIN 句を使ったクエリを発行することができます。

export const resolvers: Resolvers = {
  Query: {
    users: async () => await users(),
  },
}

const users = async (): Promise<User[]> => {
  const userRepository = getConnection().getRepository(User)
  return await userRepository.find({ relations: ['posts'] })
}

Resolver がシンプルになりますし、 SELECT も LEFT JOIN を使って 1 本にまとまります。

SELECT `User`.`id` AS `User_id`, `User`.`name` AS `User_name`, `User__posts`.`id` AS `User__posts_id`, `User__posts`.`title` AS `User__posts_title`, `User__posts`.`userId` AS `User__posts_userId` FROM `user` `User` LEFT JOIN `post` `User__posts` ON `User__posts`.`userId`=`User`.`id`

一見メリットが多く、筆者も GraphQL に慣れない頃にこの方法で実装を進めた経験があります。しかし、この方法には 不要な場合も JOIN してしまう という欠点があります。例えば以下のようなクエリを実行したとしても、

query ExampleQuery {
  users {
    id
    name
  }
}

発行される SQL は上記と変わらず、不要な Post を取得してしまいます。クエリが重くなる可能性がありますし、何より「必要なデータのみ取得して返す」GraphQL の基本的な考え方にも背いているように見えます^[2]。

方法3: 条件付きテーブル結合

方法2: テーブル結合の欠点のうち、不要な JOIN を解決するアプローチもあります。Resolver の第 4 引数である info を活用して、必要な場合のみ結合を行う、というものです。

export const resolvers: Resolvers = {
  Query: {
    users: async (_, __, ___, info) => await users(info),
  },
}

const users = async (info: GraphQLResolveInfo): Promise<User[]> => {
  const shouldJoinPostTable = doesPathExist(info.fieldNodes, ['users', 'posts'])
  const userRepository = getConnection().getRepository(User)

  return shouldJoinPostTable
    ? await userRepository.find({ relations: ['posts'] })
    : await userRepository.find()
}

const doesPathExist = (nodes: readonly FieldNode[], path: string[]): boolean => {
  const node = nodes.find((n) => n.name.value === path[0])
  if (!node) return false
  if (path.length === 1) return true

  return doesPathExist(node.selectionSet!.selections as FieldNode[], path.slice(1))
}

かなり曲芸的ですが、この例では doesPathExist という関数^[3] を定義して、 info に含まれる GraphQL のクエリ情報をもとに { users { posts { ... } } } のような構造がクエリに含まれるかを判定します。 users => posts 構造が GraphQL クエリに含まれる場合のみ JOIN が必要になるので、 doesPathExist の結果に応じて DB リクエストを構築すれば良い、ということになります。

必要な場合のみ JOIN を使うことができるため、 方法2 のデメリットの一部は解消します。パッと思いつきませんが、 DataLoader によりテーブルの数だけ SELECT を発行する場合よりも、何らかの事情で JOIN を使った 1 本のクエリを使うほうがパフォーマンスが出る場合など、検討の余地が残るかもしれません。

しかし、 Resolver Map にリレーションを記述していないなど、依然として GraphQL の王道から外れいている感はあります。

方法4: N+1 を考慮した ORM を検討する

Apollo Server + TypeORM というスタックにこだわる理由がない場合、N+1 を内部で防ぐ機構を持つライブラリを検討するのも手です。

一例として、 Prisma では独自のアプローチにより N+1 問題を解決しています。ドキュメントによると、 Prisma で提供される findUnique には N+1 を防ぐための機構が組み込まれているようです。

The Prisma Client dataloader automatically batches findUnique queries that ✔ occur in the same tick and ✔ have the same where and include parameters.

Solving n+1 in GraphQL with findUnique and Prisma's dataloader

dataloader という単語が登場するので、方法1 にある DataLoader をラップしているのかと言うとそうではなく、独自実装で DataLoader の Batching 相当のことを行っているようです。専用の説明動画も用意されており、Prisma チームは力を入れてこの機能を実装しているようです。

https://www.youtube.com/watch?v=7oMfBGEdwsc

Rails をよく使っていた筆者としては、 ActiveRecord における includes のように ORM レイヤーで N+1 問題を解決してくれるのは便利な印象があります。npm trends を見ると TypeORM に軍配が上がっているように見えますが、実験的な PJ では Prisma を試す価値がありそうです。

(追記) 他にも、 Fastify 向けの GraphQL 実装である mercurius (かつては fastify-gql という名称でした) にはデフォルトで 1+N を避けるための機構が備わっているようです。graphql-jit も組み込まれており、パフォーマンス面でも期待できそうです。

まとめ

N+1 問題を解決するアプローチを 4 つ紹介しました。特徴を整理すると以下のようになります。

方法	アプローチ	課題
1. DataLoader	Batching による N+1 の解決	- 依存ライブラリが増える - 実装が手間ではある(ライブラリの利用で楽はできる)
2. テーブル結合	JOIN によるシンプルな N+1 の解決	- GraphQL の流儀に背いている(感じがする)
3. 条件付きテーブル結合	必要な場合のみ JOIN することによる N+1 の解決	- 実装が複雑になる - GraphQL の流儀に依然背いていそう
4. N+1 を考慮した ORM を検討する	ORM レイヤーでの N+1 の解決	- 技術選定レベルでの意思決定が必要

結論としては、TLDR に書いた以下のような落とし所になると思います。

• Prisma が検討できる場合: Prisma の findUnique を使う
• それ以外の場合: DataLoader を実装する。ライブラリを使えばそんなに大変ではない

他のアプローチを採用されている事例や、本文に関する指摘があればぜひお寄せください！

脚注

1. 個人的には 1+N 問題と呼ぶほうがしっくりきます

2. 他にも Resolver Map にリレーションが記述されていないことによる弊害があるかもしれません

3. 実装は https://github.com/benawad/graphql-n-plus-one-example を参考にしました