FirestoreにおけるN+1問題と向きあう（後編）

社内LT用資料

https://zenn.dev/shuji_koike/articles/c79d37a959766e

前編のおさらい

firestoreのqueryに対してページングしながら全件取得するAsync Generatorの実装例としてpaginateを紹介しました。

export async function* paginate<T>(
  query: Query<T>,
  limit: number = 1000,
): AsyncGenerator<QueryDocumentSnapshot<T>, undefined, undefined> {
  const { docs, size } = await query.limit(limit).get()
  yield* docs
  if (size === limit) yield* $paginate(query.startAfter(docs.at(-1)))
}

paginateを使う側はfor awaitでイテレートする

for await (const doc of paginate(users)) {
  console.log(doc.id)
}

---

型が合わなくてyield*を使えない問題があったが、 @ruiewo さんのおかげで解決できた！

戻り値となるAsyncGeneratorの型パラメータのNextを指定せずデフォルトのunknownになっていたのが問題だった。
for (const doc of docs) yield doc.data()をyield* docsに書き換えることができた。

firestoreでJOINを実現する

JOIN対象をwhere inで取得する

• firestoreのwhere inは一度に取得できるデータの件数が30件までの制約がある
  • N+1をN/30+1に削減するのが限界
• 疎（まばら）なJOIN対象と相性が悪い
  • right側(JOINされる側)のデータが存在しない率が高いと無駄なクエリが増える
• 実装がちょっと厄介
  • left側(JOINする側)のデータも30件ずつ取得するか、30件に分割する実装が必要
  • その上でclient side join

paginateを応用してJOINを実現する！

documentIdで1対1対応しているcollection同士をinnerJoinする実装

• left側とright側それぞれdocumentId順でイテレートしていく
• left側とright側で対応するペアを見つけたらyeildする

export async function* $innerJoin<L, R>(
  left: Query<L>,
  right: Query<R>,
): AsyncGenerator<[QueryDocumentSnapshot<L>, QueryDocumentSnapshot<R>], undefined, undefined> {
  // right側のpaginateはfor awaitでイテレートせず、イテレータープロトコルで扱う
  const itr = $paginate(right.orderBy(FieldPath.documentId()))
  // right側のイテレートが先行した場合にデータを保持しておく入れ物
  const map: Map<string, QueryDocumentSnapshot<R>> = new Map()
  // left側をイテレートする(念のためにorderByを指定)
  for await (const leftDoc of $paginate(left.orderBy(FieldPath.documentId()))) {
    // マッチするペアが見つかるまでループ
    while (true) {
      // next()でright側の次のdocを取得
      const { done, value: rightDoc } = await itr.next()
      // innerJoinなのでright側がdoneならbreak
      if (done) break
      else {
        // マッチするペアが見つかったらyieldしてbreak
        if (leftDoc.id === rightDoc.id) {
          yield [leftDoc, rightDoc]
          break
        // mapからマッチするペアを探す
        } else if (map.has(leftDoc.id)) {
          const rightDoc = map.get(leftDoc.id)
          map.delete(leftDoc.id)
          yield [leftDoc, rightDoc!]
          break
        // マッチしない場合はrightDocをmapに保持
        } else {
          map.set(rightDoc.id, rightDoc)
          // rightの方がイテレートが進んでいたらbreak
          if (leftDoc.id < rightDoc.id) break
        }
      }
    }
  }
}

innerJoinを使う側の実装例

for await (const [left, right] of innerJoin(
  collection("left"),
  collection("right"),
)) {
  console.log(left, right)
}

• かなり限定的な場面でしか使えない
  • LEFT,RIGHT,FULL OUTER JOINも書けるはずだが手が回ってない
  • documentId以外のキーでJOINするのも理屈的には可能だが、ユニーク制約がない点どうケアするかなど課題が多い
• innerJoinの実装はかなり煩雑で泥臭いけど、使う側のコードはすごくエレガントじゃない？
• まだ実験的な試みなので広めるには早い