GraphQLページネーション

ページネーションの種類

GitLabは主に2種類のページ分割を使います:オフセットと キーセット（カーソルベースと呼ばれることもあります）ページ分割です。GraphQL API では主にキーセットのページ分割を使用し、必要に応じてオフセットのページ分割にフォールバックします。

パフォーマンスに関する考慮事項

詳細については、一般的なページネーションのガイドラインのセクションを参照してください。

オフセット

最も一般的で、GitLabの多くで使われている伝統的なページ分割です。ページの一番下にページ番号のリストが表示され、それを選択するとそのページが表示されます。

たとえば、Page 100 を選択すると、100 をバックエンドに送信します。例えば、各ページに20のアイテムがある場合、バックエンドは20 * 100 = 2000を計算し、最初の2000レコードをオフセット（スキップ）して次の20レコードをプルすることでデータベースにクエリします。

page number * page size = where to find my records

これにはいくつかの問題があります：

  • パフォーマンス。100ページをクエリする場合（オフセットが2000になります）、データベースはその特定のオフセットまでテーブルをスキャンし、次の20レコードをピックアップしなければなりません。オフセットが大きくなるにつれて、パフォーマンスは急速に低下します。詳細はThe SQL I Love <3.100Mレコードを持つテーブルの効率的なページネーション。

  • データの安定性100ページ目（オフセット2000）の20項目を取得すると、GitLabはその20項目を表示します。誰かが99ページ以前のレコードを削除したり追加したりすると、オフセット2000のアイテムは別のアイテムになります。ページ分割をするときに、リストが変化し続けるので項目を読み飛ばしてしまうという事態も起こりえます。詳しくはページ分割をご覧ください：おそらく）間違っています。

キーセットのページ分割

特定のレコードがあった場合、そのレコードの後に何が来るかを計算する方法を知っていれば、それらの特定のレコードをデータベースにクエリできます。

例えば、作成日順にソートされたイシューのリストがあるとします。あるページの最初の項目が特定の日付（たとえば1月1日）であることがわかっていれば、その日付以降に作成されたすべてのレコードを問い合わせ、最初の20件を取り出すことができます。削除されたり追加されたりしても、その日付以降に作成されたものを求めるので、正しい項目を取得することができます。

残念ながら、1月1日に作成されたイシューが20ページにあるのか100ページにあるのかを簡単に知る方法はありません。

キーセットのページネーションの利点とトレードオフには、以下のようなものがあります。

  • パフォーマンスが向上します。

  • 削除や挿入によってリストからレコードが欠落することがないため、エンドユーザーにとってデータの安定性が向上します。

  • 無限スクロールには最適な方法です。

  • プログラミングとメンテナーはより難しい。updated_at やsort_order では簡単ですが、複雑なソートシナリオでは複雑（または不可能）です。

実施

クエリでページ分割がサポートされている場合、GitLab はデフォルトでキーセットのページ分割を使用します。この設定はpagination/connections.rbで確認できます。 クエリがActiveRecord::Relationを返した場合は、自動的にキーセットのページ分割が使われます。

これは、パフォーマンスとデータの安定性をサポートするための意識的な決定です。

しかし、イシューのラベルの優先順位でソートする場合など、ソートが複雑になるため、オフセット・ページネーション接続（OffsetActiveRecordRelationConnection ）を使用しなければならないケースもあります。

リゾルバから、(例えばソート順のために)キーセットのページネーションに適さないリレーションを返す場合、BaseResolver#offset_pagination メソッドを使用して、正しい接続タイプでリレーションをラップすることができます。例えば

def resolve(**args)
  result = Finder.new(object, current_user, args).execute
  result = offset_pagination(result) if needs_offset?(args[:sort])

  result
end

キーセットのページ分割

キーセットのページネーションの実装はgraphql gem の一部であるGraphQL::Pagination::ActiveRecordRelationConnection のサブクラスです。これはすべてのActiveRecord::Relationのデフォルトとしてインストールされています。しかし、オフセットに基づくカーソル（これがデフォルトです）ではなく、GitLabはより特殊なカーソルを使います。

カーソルは、関連する順序フィールドを含むJSONオブジェクトをエンコードすることで作成されます。例えば

ordering = {"id"=>"72410125", "created_at"=>"2020-10-08 18:05:21.953398000 UTC"}
json = ordering.to_json
cursor = Base64Bp.urlsafe_encode64(json, padding: false)

"eyJpZCI6IjcyNDEwMTI1IiwiY3JlYXRlZF9hdCI6IjIwMjAtMTAtMDggMTg6MDU6MjEuOTUzMzk4MDAwIFVUQyJ9"

json = Base64Bp.urlsafe_decode64(cursor)
Gitlab::Json.parse(json)

{"id"=>"72410125", "created_at"=>"2020-10-08 18:05:21.953398000 UTC"}

順序属性値をカーソルに格納する利点：

  • もしオブジェクトのIDだけが格納されていれば、オブジェクトとその属性をクエリすることができます。その場合、追加のクエリが必要となり、オブジェクトが存在しない場合、必要な属性は利用できません。
  • 属性がNULL, である場合、SQLクエリを1つ使用することが NULLできます。でNULLない NULL場合は、別のSQLクエリを使用することができます。

ソートされる主属性フィールドがNULL カーソル内に NULLあるかどうかに基づいてNULL 、適切なクエリ条件が構築さ NULLれます。NULL 最後の順序付けフィールドは一意である（プライマリキーである）とみなさ NULLれます。

クエリの複雑さの限界

私たちは2つの順序フィールドしかサポートしておらず、そのうちの1つは主キーである必要があります。

クエリの擬似コードの例を2つ示します：

  • X 、カーソルからの値を表します。 C 、昇順にソートされたデータベース内のカラムを表します。:after カーソルを使用し、NULL 値が最後にソートされます。

     X1 IS NOT NULL
   AND
     (C1 > X1)
       OR
     (C1 IS NULL)
       OR
     (C1 = X1
       AND
      C2 > X2)
   
 X1 IS NULL
   AND
     (C1 IS NULL
       AND
      C2 > X2)

    以下は、relative_position: 1500, id: 500 の後カーソルを持つリレーションIssue.order(relative_position: :asc).order(id: :asc) に基づく例です：

     when cursor[relative_position] is not NULL
   
     ("issues"."relative_position" > 1500)
     OR (
       "issues"."relative_position" = 1500
       AND
       "issues"."id" > 500
     )
     OR ("issues"."relative_position" IS NULL)
   
 when cursor[relative_position] is NULL
   
     "issues"."relative_position" IS NULL
     AND
     "issues"."id" > 500

  • 3条件クエリ。 X はカーソルからの値を表します。C はデータベース内の列を表し、昇順にソートされ、:after カーソルを使用し、NULL の値は最後にソートされます。

     X1 IS NOT NULL
   AND
     (C1 > X1)
       OR
     (C1 IS NULL)
       OR
     (C1 = X1 AND C2 > X2)
       OR
     (C1 = X1
       AND
         X2 IS NOT NULL
           AND
             ((C2 > X2)
                OR
              (C2 IS NULL)
                OR
              (C2 = X2 AND C3 > X3)
       OR
         X2 IS NULL.....

Gitlab::Graphql::Pagination::Keyset::QueryBuilder を使用することで、必要なSQL条件を構築し、Active Recordリレーションに適用することができます。

複雑なクエリは使いにくかったり、使えなかったりします。たとえば、issuable.rb で、order_due_date_and_labels_priority メソッドは非常に複雑なクエリを作成します。

このようなタイプのクエリはサポートされていません。このようなインスタンスンスでは、オフセット・ページ分割を使用できます。

注意点

文字列構文を使用してコレクションの順序を定義しないでください：

# Bad
items.order('created_at DESC')

代わりに、ハッシュ構文を使用してください：

# Good
items.order(created_at: :desc)

最初の例では、ソート情報(created_at, 上の例では)がページネーションカーソルに正しく埋め込まれません。

オフセット

ソートの複雑さがキーセットのページネーションで処理しきれない場合があります。

例えば、ProjectIssuesResolverで、priority_asc でソートする場合、順序が複雑すぎるため、キーセットのページ分割は使えません。詳しくはissuable.rbをお読みください。

このような場合、ActiveRecord::Relation の代わりにGitlab::Graphql::Pagination::OffsetActiveRecordRelationConnection を返すことで、通常のオフセット・ページ分割に戻すことができます：

    def resolve(parent, finder, **args)
      issues = apply_lookahead(Gitlab::Graphql::Loaders::IssuableLoader.new(parent, finder).batching_find_all)

      if non_stable_cursor_sort?(args[:sort])
        # Certain complex sorts are not supported by the stable cursor pagination yet.
        # In these cases, we use offset pagination, so we return the correct connection.
        offset_pagination(issues)
      else
        issues
      end
    end

外部ページ分割

他のシステムに保存されているデータをGitLab APIを通して返す必要がある場合があります。このような場合、サードパーティのAPIをページ分割する必要があるかもしれません。

この例はエラートラッキングの実装で、GitLab APIを通してSentryエラーをプロキシしています。これは、独自のページ分割ルールを強制するSentry APIを呼び出すことで行います。つまり、GitLab内でコレクションにアクセスして独自のページ分割を行うことはできません。

一貫性を保つために、Gitlab::Graphql::ExternallyPaginatedArray.new(previous_cursor, next_cursor, *items) を使って、外部APIから返された値に基づいて手動でページネーションカーソルを設定します。

以下のファイルで実装例を見ることができます：

テスト

ページネーションとソートをサポートするすべての GraphQL フィールドは、graphql/sorted_paginated_query_shared_examples.rb にあるソートされたページネーションクエリの共有例を使用してテストする必要があります。 これは、ソートキーが互換性があり、カーソルが正しく動作することを確認するのに役立ちます。

これは、キーセットのページ分割を使用する場合に特にインポートされます。

リクエスト仕様に次のようなセクションを追加してください：

describe 'sorting and pagination' do
  ...
end

そして、issues_spec.rb を例にしてテストを作成します。

graphql/sorted_paginated_query_shared_examples.rb には、共有例の使用法についてのドキュメントも含まれています。

共有サンプルでは、特定のlet 変数とメソッドを設定する必要があります：

describe 'sorting and pagination' do
  let_it_be(:sort_project) { create(:project, :public) }
  let(:data_path)    { [:project, :issues] }

  def pagination_query(params)
    graphql_query_for( :project, { full_path: sort_project.full_path },
      query_nodes(:issues, :id, include_pagination_info: true, args: params))
    )
  end

  def pagination_results_data(nodes)
    nodes.map { |issue| issue['iid'].to_i }
  end

  context 'when sorting by weight' do
    let_it_be(:issues) { make_some_issues_with_weights }

    context 'when ascending' do
      let(:ordered_issues) { issues.sort_by(&:weight) }

      it_behaves_like 'sorted paginated query' do
        let(:sort_param) { :WEIGHT_ASC }
        let(:first_param) { 2 }
        let(:all_records) { ordered_issues.map(&:iid) }
      end
    end
  end