ライブラリの実装からCursor-based paginationにおけるcursorのフォーマットのベストプラクティスを探る

この記事は [GraphQL Advent Calendar 2020](https://qiita.com/advent-calendar/2020/graphql) 13 日目の記事です。
前回の記事は @maaz118 さんの [GraphQL の @defer, @stream ディレクティブを試してみる](https://zenn.dev/adwd/articles/53c991e373f84d) でした。

# GraphQLにおける2つのPagination方式

## Offset-basedとCursor-based
GraphQLにおけるpaginationには、Offset-based paginationとCursor-based paginationの2つが主な方法としてあります。

GraphQLの公式ページには3つの例が載っています。
https://graphql.org/learn/pagination/#pagination-and-edges

> - We could do something like friends(first:2 offset:2) to ask for the next two in the list.
- We could do something like friends(first:2 after:$friendId), to ask for the next two after the last friend we fetched.
- We could do something like friends(first:2 after:$friendCursor), where we get a cursor from the last item and use that to paginate.

最初のケースである `friends(first:2 offset:2)` がOffset-based paginationです。
これはGraphQLに限らず、REST APIにおいても主流なページネーションの方法の1つですね。
SQLにおいて、`first` が`LIMIT`, `offset`がそのまま`OFFSET`に対応するので、SQLに触れたことのある方なら理解がしやすいと思います。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28883/75244857-c282-8233-f531-a8e0a7b1de37.png)

2つ目、3つ目の例の`friends(first:2 after:$friendId)`、`friends(first:2 after:$friendCursor)` がCursor-based paginationの例となります。

この2つはCursorのフォーマットが違います。一方の例では、IDをcursorとして使用していますが、もう一方は前回取得結果より、cursorを取り出して使用しています。

Cursor-based paginationにおいては、firstが`LIMIT`に対応するのはOffset-basedと同様ですが、`after`に指定された値以降を取得することになります。
この場合の実際のSQLは実装によって異なりますが、もっとも単純な例として、sequentionに大きくなる値の場合には `WHERE cursor > $1` のようになります。

* cursorがIdで3を指定した場合(`friends(first:2 after:3)`)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28883/51650217-0242-1ec2-3974-789dce4b948c.png)

## それぞれのページネーション方式に適するユースケース

この2つのページネーション方式は、それぞれ適するユースケースが違います。

Offset-basedは、リストの中の特定の範囲の集合を抜き出すのに向いています。
具体的にはGoogleの検索結果のページ遷移などです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/28883/35cad56b-0f57-f160-9a49-07390ccb114f.png)

ここでダイレクトに3ページ目に遷移したい時、1ページあたりの表示件数が20件であれば、`offset: 40, first: 20` と指定すれば良いことになります。

Cursor-basedでは、このような遷移には基本的には向いていません。afterに指定することになるcursorは前回の取得結果から取り出すことになるので、2ページ目を取得するまではafterに指定する値が分からないからです。
Cursor-basedが向いているのは、Twitterのタイムラインのような、前回の取得結果から最新の差分のみを取得したいケースです。
常に前回結果から取得した値の最後を次のクエリのafterに指定すれば良いことになるので、実装が簡易になります。

この2つにおいてはどちらが優れているということはなく、適材適所で使い分けるべきかなと思います。

## cursorのフォーマット

先ほどあげた3つ目の例(`friends(first:2 after:$friendCursor)`)としてIDを使わないことを示唆しているように、cursorのフォーマットに厳密な決まりはありません。

必要な情報は要件によって変わるため、上のGraphQLの公式ページにおいても、必要な情報を入れた上でbase64 encodingして文字列に変換した値を使用することが推奨されています。
base64 encodingをcursorに施した実装においては、Resolverがcursorの指定を受け取った時にdecodeして、paginationに必要な情報を取得することになります。

特に明確な決まりがないため、どのような実装にしようか自分でも悩むことが多いです。

前置きが長くなりましたが、この記事ではcursorの生成をサポートしているライブラリの実装を比べながら、ベストプラクティスを探っていきます。

# 対象のライブラリたち

この記事では以下のライブラリを対象にしています。
- [graphql-ruby](https://github.com/rmosolgo/graphql-ruby) v1.11.6
- [Prisma1](https://github.com/prisma/prisma1) v1.34.10
- [Hasura](https://github.com/hasura/graphql-engine/releases) v1.3.3

## graphql-ruby

実装はこちらにありました。
https://github.com/rmosolgo/graphql-ruby/blob/v1.11.6/lib/graphql/relay/relation_connection.rb#L9

```ruby

      def cursor_from_node(item)
        item_index = paged_nodes.index(item)
        if item_index.nil?
          raise("Can't generate cursor, item not found in connection: #{item}")
        else
          offset = item_index + 1 + ((paged_nodes_offset || 0) - (relation_offset(sliced_nodes) || 0))

          if after
            offset += offset_from_cursor(after)
          elsif before
            offset += offset_from_cursor(before) - 1 - sliced_nodes_count
          end

          encode(offset.to_s)
        end
      end
```

この実装においては、offsetを計算した上で、base64 encodingの元としています。
なので方法論的にはOffset-basedと同じ仕組みで動くことになります。
Cursorのフォーマットに指定がないゆえに、このようにOffset-basedにも寄せられるのはCursor-basedの利点とも言えそうですね。

## Prisma1

Prisma2もCursorには対応しているのですが、こちらはbase64 encodingなどの対応は入っておらず、uniqueなモデルのフィールドは、要件を満たす限りcursorとしても採用可能というだけの素朴な対応なので、今回はあえてPrisma1を参考にしていきます。(Prisma1はすでにmaintenance modeで、重大なバグを除いて機能追加はないので、新規採用はおすすめしません。)
Prisma2のドキュメントはこちら。 https://www.prisma.io/docs/concepts/components/prisma-client/pagination#cursor-based-pagination

ラフにコードベースを眺めたところ、ちょうどcursorから実際のSQL条件に変換するところ(生成側ではなく受け取り時)が見つかったので、そこを参考にします。

実装はこのあたり
https://github.com/prisma/prisma1/blob/1.34.10/server/connectors/api-connector-jdbc/src/main/scala/com/prisma/api/connector/jdbc/database/CursorConditionBuilder.scala#L26

```scala
    // First, we fetch the ordering for the query. If none is passed, we order by id, ascending.
    // We need that since before/after are dependent on the order.
    val (orderByField: jooq.Field[AnyRef], orderByWithAlias: jooq.Field[AnyRef], sortOrder: SortOrder) = orderBy match {
      case Some(order) => (modelColumn(order.field), aliasColumn(order.field.dbName), order.sortOrder)
      case None        => (idField, idWithAlias, SortOrder.Asc)
    }

    val value: IdGCValue = before match {
      case None     => after.get
      case Some(id) => id
    }

    val cursor = `val`(value.value.asInstanceOf[AnyRef])

    val selectQuery = sql
      .select(orderByField)
      .from(modelTable(model))
      .where(idField.equal(placeHolder))

    // Then, we select the comparison operation and construct the cursors. For instance, if we use ascending order, and we want
    // to get the items before, we use the "<" comparator on the column that defines the order.
    def cursorFor(cursorType: String): Condition = (cursorType, sortOrder) match {
      case ("before", SortOrder.Asc)  => or(and(orderByWithAlias.eq(selectQuery), idWithAlias.lessThan(cursor)), orderByWithAlias.lessThan(selectQuery))
      case ("before", SortOrder.Desc) => or(and(orderByWithAlias.eq(selectQuery), idWithAlias.lessThan(cursor)), orderByWithAlias.greaterThan(selectQuery))
      case ("after", SortOrder.Asc)   => or(and(orderByWithAlias.eq(selectQuery), idWithAlias.greaterThan(cursor)), orderByWithAlias.greaterThan(selectQuery))
      case ("after", SortOrder.Desc)  => or(and(orderByWithAlias.eq(selectQuery), idWithAlias.greaterThan(cursor)), orderByWithAlias.lessThan(selectQuery))
      case _                          => throw new IllegalArgumentException
    }
```

orderByで指定されたフィールドの値を、今回の`after/before`(Prisma1はafterだけでなくbeforeにも対応しています)で指定された値とみなして採用する実装になっています。
つまり`orderBy: createdAt`と指定されていれば、`WHERE createdAt > $1`のようになるわけですね。
当然ですが、前回結果取得時のorderBy条件が、今回も同様でなければ動きません。

## Hasura

コードを追ってみてもイマイチ生成箇所が掴めなかった(Haskell分からん..)ので、テストコードから値を探ってみます。

https://github.com/hasura/graphql-engine/blob/v1.3.4-beta.2/server/tests-py/queries/graphql_query/relay/author_pagination_articles_aggregate_orderby/forward/page_2.yaml

```yml
description: Fetch 2nd page of articles ordered by their article count
url: /v1beta1/relay
status: 200
query:
  query: |
    query {
      author_connection(
        first: 2
        order_by: {articles_aggregate: {count: asc}}
        after: "eyJhcnRpY2xlc19hZ2dyZWdhdGUiIDogeyJjb3VudCIgOiAxfSwgImlkIiA6IDN9"
      ){
        pageInfo{
          startCursor
          endCursor
          hasPreviousPage
          hasNextPage
        }
        edges{
          cursor
          node{
            name
            articles_aggregate{
              aggregate{
                count
              }
            }
          }
        }
      }
    }
response:
  data:
    author_connection:
      pageInfo:
        startCursor: eyJhcnRpY2xlc19hZ2dyZWdhdGUiIDogeyJjb3VudCIgOiAyfSwgImlkIiA6IDJ9
        endCursor: eyJhcnRpY2xlc19hZ2dyZWdhdGUiIDogeyJjb3VudCIgOiAzfSwgImlkIiA6IDF9
        hasPreviousPage: true
        hasNextPage: false
      edges:
      - cursor: eyJhcnRpY2xlc19hZ2dyZWdhdGUiIDogeyJjb3VudCIgOiAyfSwgImlkIiA6IDJ9
        node:
          name: Author 2
          articles_aggregate:
            aggregate:
              count: 2
      - cursor: eyJhcnRpY2xlc19hZ2dyZWdhdGUiIDogeyJjb3VudCIgOiAzfSwgImlkIiA6IDF9
        node:
          name: Author 1
          articles_aggregate:
            aggregate:
              count: 3
```

endCursorの値をdecodeしてみると`{"articles_aggregate" : {"count" : 3}, "id" : 1}`という値が算出されました。
これはorder_byに指定されている値 + 自身のIDになっていますね。
仕組み的にはPrisma1と同様、orderByで指定された値をCursorとしても使用することになるのだと思います。

# さてベストプラクティスは？

どの実装もCursorを実現する妥当な実装と言えるかなぁと思います。
graphql-rubyの実装が他の2つとは違いましたが、ユースケースによってはOffset-basedの利点を取り入れることもできるのでケースバイケースとも言えそうです。
個人的には、一般的なCursor-basedの要件としては、Prisma1やHasuraの実装のように、OrderByに指定しているフィールドがsequentionであることを前提に、その値を元にcursorを生成するのが無難なのかと思います。