diff --git a/doc/api/admin/data_management.md b/doc/api/admin/data_management.md
index f33556179263e3d2b34a0e7b75cabd1cadb98bf5..165b135c94863abc816da4c82e5ea3fda6d621bb 100644
--- a/doc/api/admin/data_management.md
+++ b/doc/api/admin/data_management.md
@@ -62,11 +62,13 @@ The `:model_name` parameter must be one of:
 
 Supported attributes:
 
-| Attribute         | Type   | Required | Description                                                                                                                 |
-|-------------------|--------|----------|-----------------------------------------------------------------------------------------------------------------------------|
-| `model_name`      | string | Yes      | The name of the requested model. Must belong to the `:model_name` list above.                                               |
-| `checksum_state`  | string | No       | Search by checksum status. Allowed values: pending, started, succeeded, failed, disabled.                                   |
-| `identifiers`     | array  | No       | Filter results with an array of unique identifiers of the requested model, which can be integers or base64 encoded strings. |
+| Attribute        | Type   | Required | Description                                                                                                                 |
+|------------------|--------|----------|-----------------------------------------------------------------------------------------------------------------------------|
+| `model_name`     | string | Yes      | The name of the requested model. Must belong to the `:model_name` list above.                                               |
+| `checksum_state` | string | No       | Search by checksum status. Allowed values: pending, started, succeeded, failed, disabled.                                   |
+| `identifiers`    | array  | No       | Filter results with an array of unique identifiers of the requested model, which can be integers or base64 encoded strings. |
+
+This endpoint supports [keyset pagination](../rest/_index.md#keyset-based-pagination) on the model's primary key, with sorting in ascending or descending order.
 
 If successful, returns [`200`](../rest/troubleshooting.md#status-codes) and information about the model. It includes the following
 response attributes:
diff --git a/ee/app/models/concerns/orderable.rb b/ee/app/models/concerns/orderable.rb
index d0724d9d1ba97341978dda4fc9590e9ea2415f32..f441b0b40ebaa1d68bc3e4183bc8e973c1581fbb 100644
--- a/ee/app/models/concerns/orderable.rb
+++ b/ee/app/models/concerns/orderable.rb
@@ -5,5 +5,21 @@ module Orderable # rubocop:disable Gitlab/BoundedContexts -- general purpose con
 
   included do
     scope :order_by_primary_key, -> { order(*Array(primary_key).map { |key| arel_table[key] }) }
+    scope :keyset_order_by_primary_key, ->(sort_order = 'asc') {
+      keyset_order = Gitlab::Pagination::Keyset::Order.build(
+        Array(primary_key).map do |key|
+          Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
+            attribute_name: key,
+            order_expression: sort_order == 'asc' ? arel_table[key.to_sym].asc : arel_table[key.to_sym].desc)
+        end
+      )
+
+      order(keyset_order)
+    }
+
+    # By default, only support generic ordering on primary keys as they're always indexed
+    def self.supported_keyset_orderings
+      Array(primary_key).index_with { |_k| [:asc, :desc] }.symbolize_keys
+    end
   end
 end
diff --git a/ee/lib/api/admin/data_management.rb b/ee/lib/api/admin/data_management.rb
index dbc58076dec720bb7e6b5394469eb3f635b2b773..cd0372a5e9d8497c2673a09201c380e48a077a1b 100644
--- a/ee/lib/api/admin/data_management.rb
+++ b/ee/lib/api/admin/data_management.rb
@@ -153,6 +153,8 @@ def decoded_identifiers(identifier_array)
                 type: String,
                 desc: 'The checksum status of the records to filter by',
                 values: VERIFICATION_STATES
+              optional :cursor, type: String, desc: 'Cursor for obtaining the next set of records'
+              optional :sort, type: String, values: %w[asc desc], default: 'asc', desc: 'Order of sorting'
             end
             get do
               model_class = Gitlab::Geo::ModelMapper.find_from_name(params[:model_name])
@@ -168,9 +170,17 @@ def decoded_identifiers(identifier_array)
                 relation = relation.with_verification_state(:"verification_#{params[:checksum_state]}")
               end
 
-              relation = relation.order_by_primary_key
+              if params[:pagination] == 'keyset'
+                # the order_by parameter's default value is the primary key column of the model -
+                # using the first column for composite keys
+                model_pk = model_class.primary_key
+                params[:order_by] = model_pk.is_a?(Array) ? model_pk.first : model_pk
 
-              present paginate(relation, without_count: true), with: Entities::Admin::Model
+                present paginate_with_strategies(relation.keyset_order_by_primary_key(params[:sort])),
+                  with: Entities::Admin::Model
+              else
+                present paginate(relation.order_by_primary_key), with: Entities::Admin::Model
+              end
             end
 
             # Example request:
diff --git a/ee/spec/models/concerns/orderable_spec.rb b/ee/spec/models/concerns/orderable_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..f0b5f9370336863b7f5c743d2b28cd20d5bd6ad4
--- /dev/null
+++ b/ee/spec/models/concerns/orderable_spec.rb
@@ -0,0 +1,94 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Orderable, feature_category: :api do
+  let_it_be(:dummy_model_class) do
+    Class.new(ActiveRecord::Base) do
+      self.table_name = '_test_dummy_models'
+      include Orderable
+    end
+  end
+
+  context 'when primary_key is a single column' do
+    before do
+      allow(dummy_model_class).to receive(:primary_key).and_return('id')
+    end
+
+    describe '.supported_keyset_orderings' do
+      it 'returns a hash with the primary key and asc/desc orderings' do
+        expect(dummy_model_class.supported_keyset_orderings).to eq({ id: [:asc, :desc] })
+      end
+    end
+
+    describe '.order_by_primary_key' do
+      it 'orders by primary key in ascending order' do
+        result = dummy_model_class.order_by_primary_key
+
+        expect(result.to_sql).to include("ORDER BY \"_test_dummy_models\".\"id\"")
+      end
+    end
+
+    describe '.keyset_order_by_primary_key' do
+      shared_examples 'orders by primary key with given order' do |order|
+        it 'orders by primary key' do
+          result = if order
+                     dummy_model_class.keyset_order_by_primary_key(order)
+                   else
+                     dummy_model_class.keyset_order_by_primary_key
+                   end
+
+          expect(result.to_sql).to include("ORDER BY \"_test_dummy_models\".\"id\" #{order&.upcase || 'ASC'}")
+        end
+      end
+
+      it_behaves_like 'orders by primary key with given order'
+      it_behaves_like 'orders by primary key with given order', 'asc'
+      it_behaves_like 'orders by primary key with given order', 'desc'
+    end
+  end
+
+  context 'when primary_key is an array of columns (composite primary key)' do
+    before do
+      allow(dummy_model_class).to receive(:primary_key).and_return(%w[id partition_id])
+    end
+
+    describe '.supported_keyset_orderings' do
+      it 'returns a hash with each primary key and asc/desc orderings' do
+        expect(dummy_model_class.supported_keyset_orderings).to eq({ id: [:asc, :desc],
+                                                                     partition_id: [:asc, :desc] })
+      end
+    end
+
+    describe '.order_by_primary_key' do
+      it 'orders by primary key in ascending order' do
+        expected_order = "ORDER BY \"_test_dummy_models\".\"id\", \"_test_dummy_models\".\"partition_id\""
+        result = dummy_model_class.order_by_primary_key
+
+        expect(result.to_sql).to include(expected_order)
+      end
+    end
+
+    describe '.keyset_order_by_primary_key' do
+      shared_examples 'orders by primary key with given order' do |order|
+        it 'orders by primary key' do
+          expected_order = order&.upcase || 'ASC'
+          first_column_sql = "ORDER BY \"_test_dummy_models\".\"id\" #{expected_order},"
+          second_column_sql = " \"_test_dummy_models\".\"partition_id\" #{expected_order}"
+
+          result = if order
+                     dummy_model_class.keyset_order_by_primary_key(order)
+                   else
+                     dummy_model_class.keyset_order_by_primary_key
+                   end
+
+          expect(result.to_sql).to include(first_column_sql + second_column_sql)
+        end
+      end
+
+      it_behaves_like 'orders by primary key with given order'
+      it_behaves_like 'orders by primary key with given order', 'asc'
+      it_behaves_like 'orders by primary key with given order', 'desc'
+    end
+  end
+end
diff --git a/ee/spec/requests/api/admin/data_management_spec.rb b/ee/spec/requests/api/admin/data_management_spec.rb
index 1db63ab22209d6d4095e2471fe4379b637441b92..ee741f01d7070ad0081bc32a0d7f5e2c6da6630e 100644
--- a/ee/spec/requests/api/admin/data_management_spec.rb
+++ b/ee/spec/requests/api/admin/data_management_spec.rb
@@ -13,13 +13,15 @@
     context 'with feature flag enabled' do
       context 'when authenticated as admin' do
         context 'with valid model name' do
+          let_it_be(:api_path) { "/admin/data_management/snippet_repository" }
+
           it 'returns matching object data' do
             expected_model = create(:snippet_repository)
 
-            get api("/admin/data_management/snippet_repository", admin, admin_mode: true)
+            get api(api_path, admin, admin_mode: true)
 
             expect(response).to have_gitlab_http_status(:ok)
-            expect(json_response.first).to include('record_identifier' => expected_model.id,
+            expect(json_response.first).to include('record_identifier' => record_identifier(expected_model),
               'model_class' => expected_model.class.name)
           end
 
@@ -27,7 +29,7 @@
             it 'paginates results correctly' do
               create_list(:snippet_repository, 9)
 
-              get api("/admin/data_management/snippet_repository?per_page=5", admin, admin_mode: true)
+              get api("#{api_path}?per_page=5", admin, admin_mode: true)
 
               expect(response).to have_gitlab_http_status(:ok)
               expect(json_response.size).to eq(5)
@@ -35,7 +37,7 @@
               expect(response.headers['X-Page']).to eq('1')
               expect(response.headers['X-Per-Page']).to eq('5')
 
-              get api("/admin/data_management/snippet_repository?per_page=5&page=2", admin, admin_mode: true)
+              get api("#{api_path}?per_page=5&page=2", admin, admin_mode: true)
 
               expect(response).to have_gitlab_http_status(:ok)
               expect(json_response.size).to eq(4) # Remaining 4 records
@@ -57,27 +59,79 @@
               expect(second_page_ids).to eq(second_page_ids.sort)
               expect(first_page_ids.last).to be < second_page_ids.first
             end
+          end
 
-            context 'with composite IDs' do
-              let_it_be(:list) { create_list(:virtual_registries_packages_maven_cache_entry, 9) }
-              # We're using this Entry model because it will be the first model with composite PKs supported by Geo.
-              # The model isn't Geo-ready yet, so we need to mock its interface in this test to simulate its future
-              # implementation.
-              let_it_be(:orderable_klass) do
-                Class.new(list.first.class) do
-                  include Orderable
-                end
-              end
+          context 'with keyset pagination and ordering' do
+            let_it_be(:list) { create_list(:snippet_repository, 3) }
 
-              before do
-                # The VirtualRegistries::Packages::Maven::Cache::Entry model is not in the allowed list yet.
-                # This is why we need to force the ModelMapper to return the stubbed class instead of the model
-                # passed as parameters.
-                allow(Gitlab::Geo::ModelMapper).to receive(:find_from_name).with('project').and_return(orderable_klass)
+            it 'returns first page with cursor to next page' do
+              get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 2 }
+
+              expect(response).to have_gitlab_http_status(:ok)
+              expect(json_response.size).to eq(2)
+              expect(json_response.pluck('record_identifier')).to contain_exactly(list.first.id, list.second.id)
+              expect(response.headers["Link"]).to include("cursor")
+              next_cursor = response.headers["Link"].match("(?<cursor_data>cursor=.*?)&")["cursor_data"]
+
+              get api(api_path, admin, admin_mode: true),
+                params: { pagination: 'keyset', per_page: 2 }.merge(Rack::Utils.parse_query(next_cursor))
+
+              expect(json_response.size).to eq(1)
+              expect(json_response.pluck('record_identifier')).to contain_exactly(list.last.id)
+              expect(response.headers).not_to include("Link")
+            end
+
+            it 'orders descending results correctly' do
+              get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 3, sort: 'desc' }
+
+              expect(response).to have_gitlab_http_status(:ok)
+              expect(json_response.size).to eq(3)
+              expect(json_response.pluck('record_identifier')).to eq(list.map(&:id).reverse)
+            end
+
+            it 'orders ascending results correctly' do
+              get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 3, sort: 'asc' }
+
+              expect(response).to have_gitlab_http_status(:ok)
+              expect(json_response.size).to eq(3)
+              expect(json_response.pluck('record_identifier')).to eq(list.map(&:id))
+            end
+          end
+
+          context 'with composite ids' do
+            let_it_be(:list) { create_list(:virtual_registries_packages_maven_cache_entry, 9) }
+            let_it_be(:ids_list) { list.map { |model| record_identifier(model) } }
+            # We're using this Entry model because it will be the first model with composite PKs supported by Geo.
+            # The model isn't Geo-ready yet, so we need to mock its interface in this test to simulate its future
+            # implementation.
+            let_it_be(:orderable_klass) do
+              Class.new(list.first.class) do
+                include Orderable
               end
+            end
+
+            before do
+              # The VirtualRegistries::Packages::Maven::Cache::Entry model is not in the allowed list yet.
+              # This is why we need to force the ModelMapper to return the stubbed class instead of the model
+              # passed as parameters.
+              allow(Gitlab::Geo::ModelMapper).to receive(:find_from_name)
+                                                   .with('snippet_repository')
+                                                   .and_return(orderable_klass)
+            end
 
+            it 'filters passed ids' do
+              get api("#{api_path}?identifiers[]=#{ids_list.first}&identifiers[]=#{ids_list.last}",
+                admin,
+                admin_mode: true)
+
+              expect(response).to have_gitlab_http_status(:ok)
+              expect(json_response.pluck('record_identifier')).to match_array([ids_list.first, ids_list.last])
+              expect(json_response.size).to eq(2)
+            end
+
+            context 'with offset pagination' do
               it 'paginates results' do
-                get api("/admin/data_management/project?per_page=5", admin, admin_mode: true)
+                get api("#{api_path}?per_page=5", admin, admin_mode: true)
 
                 expect(response).to have_gitlab_http_status(:ok)
                 expect(json_response.size).to eq(5)
@@ -85,7 +139,7 @@
                 expect(response.headers['X-Page']).to eq('1')
                 expect(response.headers['X-Per-Page']).to eq('5')
 
-                get api("/admin/data_management/project?per_page=5&page=2", admin, admin_mode: true)
+                get api("#{api_path}?per_page=5&page=2", admin, admin_mode: true)
 
                 expect(response).to have_gitlab_http_status(:ok)
                 expect(json_response.size).to eq(4) # Remaining 4 records
@@ -93,57 +147,55 @@
                 expect(response.headers['X-Next-Page']).to be_empty
               end
             end
-          end
 
-          context 'with filtering based on ids' do
-            context 'with integer ids' do
-              let_it_be(:list) { create_list(:project, 3) }
-
-              it 'filters passed ids' do
-                get api("/admin/data_management/project?identifiers[]=#{list.first.id}&identifiers[]=#{list.last.id}",
-                  admin,
-                  admin_mode: true)
+            context 'with keyset pagination and ordering' do
+              it 'returns first page with cursor to next page' do
+                get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 5 }
 
                 expect(response).to have_gitlab_http_status(:ok)
-                expect(json_response.pluck('record_identifier')).to eq([list.first.id, list.last.id])
-                expect(json_response.size).to eq(2)
-              end
-            end
+                expect(json_response.size).to eq(5)
 
-            context 'with composite ids' do
-              let_it_be(:list) { create_list(:virtual_registries_packages_maven_cache_entry, 3) }
-              # We're using this Entry model because it will be the first model with composite PKs supported by Geo.
-              # The model isn't Geo-ready yet, so we need to mock its interface in this test to simulate its future
-              # implementation.
-              let_it_be(:orderable_klass) do
-                Class.new(list.first.class) do
-                  include Orderable
-                end
+                expect(json_response.pluck('record_identifier')).to match_array(ids_list.first(5))
+                expect(response.headers["Link"]).to include("cursor")
+                next_cursor = response.headers["Link"].match("(?<cursor_data>cursor=.*?)&")["cursor_data"]
+
+                get api(api_path, admin, admin_mode: true),
+                  params: { pagination: 'keyset', per_page: 5 }.merge(Rack::Utils.parse_query(next_cursor))
+
+                expect(json_response.size).to eq(4)
+                expect(json_response.pluck('record_identifier')).to match_array(ids_list.last(4))
+                expect(response.headers).not_to include("Link")
               end
 
-              let_it_be(:ids_list) do
-                list.map do |model|
-                  Base64.urlsafe_encode64(orderable_klass
-                                            .primary_key
-                                            .map { |field| model.read_attribute_before_type_cast(field) }
-                                            .join(' '))
-                end
+              it 'orders descending results correctly' do
+                get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 9, sort: 'desc' }
+
+                expect(response).to have_gitlab_http_status(:ok)
+                expect(json_response.size).to eq(9)
+                expect(json_response.pluck('record_identifier')).to eq(ids_list.reverse)
               end
 
-              before do
-                # The VirtualRegistries::Packages::Maven::Cache::Entry model is not in the allowed list yet.
-                # This is why we need to force the ModelMapper to return the stubbed class instead of the model
-                # passed as parameters.
-                allow(Gitlab::Geo::ModelMapper).to receive(:find_from_name).with('project').and_return(orderable_klass)
+              it 'orders ascending results correctly' do
+                get api(api_path, admin, admin_mode: true), params: { pagination: 'keyset', per_page: 9, sort: 'asc' }
+
+                expect(response).to have_gitlab_http_status(:ok)
+                expect(json_response.size).to eq(9)
+                expect(json_response.pluck('record_identifier')).to eq(ids_list)
               end
+            end
+          end
+
+          context 'with filtering based on ids' do
+            context 'with integer ids' do
+              let_it_be(:list) { create_list(:project, 3) }
 
               it 'filters passed ids' do
-                get api("/admin/data_management/project?identifiers[]=#{ids_list.first}&identifiers[]=#{ids_list.last}",
+                get api("/admin/data_management/project?identifiers[]=#{list.first.id}&identifiers[]=#{list.last.id}",
                   admin,
                   admin_mode: true)
 
                 expect(response).to have_gitlab_http_status(:ok)
-                expect(json_response.pluck('record_identifier')).to eq([ids_list.first, ids_list.last])
+                expect(json_response.pluck('record_identifier')).to match_array([list.first.id, list.last.id])
                 expect(json_response.size).to eq(2)
               end
             end
@@ -785,9 +837,10 @@ def build_record_for_given_state(state)
 
         describe 'PUT /admin/data_management/:model_name/checksum' do
           let(:list) { create_list(factory_name(model_classes), 3, :verification_failed) }
+          let(:ids_list) { list.map { |model| record_identifier(model) } }
 
           it 'handles parameters appropriately' do
-            query_params = "identifiers[]=#{list.first.id}&identifiers[]=#{list.last.id}&checksum_state=failed"
+            query_params = "identifiers[]=#{ids_list.first}&identifiers[]=#{ids_list.last}&checksum_state=failed"
 
             expected_ids = [list.first.verification_state_object.id, list.last.verification_state_object.id]
             expected_params = { checksum_state: "verification_failed", identifiers: expected_ids }
@@ -823,14 +876,24 @@ def build_record_for_given_state(state)
       end
 
       describe 'GET /admin/data_management/:model_name/:record_identifier' do
+        let(:identifier) { record_identifier(expected_record) }
+
         it 'handles all known replicable model names' do
-          get api("#{api_path}/#{expected_record.id}", admin, admin_mode: true)
+          get api("#{api_path}/#{identifier}", admin, admin_mode: true)
 
           expect(response).to have_gitlab_http_status(:ok)
-          expect(json_response).to include('record_identifier' => expected_record.id,
+          expect(json_response).to include('record_identifier' => identifier,
             'model_class' => expected_record.class.name)
         end
       end
     end
   end
+
+  def record_identifier(model_record)
+    return model_record.id unless model_record.class.primary_key.is_a?(Array)
+
+    Base64.urlsafe_encode64(model_record.class.primary_key
+                                        .map { |field| model_record.read_attribute_before_type_cast(field) }
+                                        .join(' '))
+  end
 end
diff --git a/lib/api/helpers/pagination_strategies.rb b/lib/api/helpers/pagination_strategies.rb
index 4353ba0e99adfe74fd78c8bf60fa9ec3860458eb..fad34101aa6270cb3f7f5a00479859301698fd1d 100644
--- a/lib/api/helpers/pagination_strategies.rb
+++ b/lib/api/helpers/pagination_strategies.rb
@@ -4,8 +4,8 @@ module API
   module Helpers
     module PaginationStrategies
       # paginator_params are only currently supported with offset pagination
-      def paginate_with_strategies(relation, request_scope = nil, paginator_params: {})
-        paginator = paginator(relation, request_scope)
+      def paginate_with_strategies(relation, request_scope = nil, paginator_params: {}, use_cursor: true)
+        paginator = paginator(relation, request_scope, use_cursor)
 
         result = if block_given?
                    yield(paginator.paginate(relation, **paginator_params))
@@ -18,16 +18,16 @@ def paginate_with_strategies(relation, request_scope = nil, paginator_params: {}
         end
       end
 
-      def paginator(relation, request_scope = nil)
-        return keyset_paginator(relation) if keyset_pagination_enabled?
+      def paginator(relation, request_scope = nil, use_cursor = true)
+        return keyset_paginator(relation, use_cursor) if keyset_pagination_enabled?
 
         offset_paginator(relation, request_scope)
       end
 
       private
 
-      def keyset_paginator(relation)
-        if cursor_based_keyset_pagination_supported?(relation)
+      def keyset_paginator(relation, use_cursor)
+        if cursor_based_keyset_pagination_supported?(relation) && use_cursor
           request_context_class = Gitlab::Pagination::Keyset::CursorBasedRequestContext
           paginator_class = Gitlab::Pagination::Keyset::CursorPager
           availability_checker = Gitlab::Pagination::CursorBasedKeyset
diff --git a/lib/api/projects.rb b/lib/api/projects.rb
index 6270eda286cc81fb12187ecadc3c33f0fad75932..d209c42013d732fcfe4f21cfab2f505248fb0175 100644
--- a/lib/api/projects.rb
+++ b/lib/api/projects.rb
@@ -214,7 +214,7 @@ def present_projects(projects, options = {})
         projects = reorder_projects(projects) unless order_by_similarity?(allow_unauthorized: false)
         projects = apply_filters(projects)
 
-        records, options = paginate_with_strategies(projects, options[:request_scope]) do |projects|
+        records, options = paginate_with_strategies(projects, options[:request_scope], use_project_cursor: false) do |projects|
           projects, options = with_custom_attributes(projects, options)
 
           options = options.reverse_merge(
diff --git a/spec/lib/api/helpers/pagination_strategies_spec.rb b/spec/lib/api/helpers/pagination_strategies_spec.rb
index 7ba185e13feee8ce1e74f1d98210456dc07fe71f..1e5189e8b69219286633babe0d3c3576b5db79ec 100644
--- a/spec/lib/api/helpers/pagination_strategies_spec.rb
+++ b/spec/lib/api/helpers/pagination_strategies_spec.rb
@@ -2,7 +2,7 @@
 
 require 'spec_helper'
 
-RSpec.describe API::Helpers::PaginationStrategies do
+RSpec.describe API::Helpers::PaginationStrategies, feature_category: :api do
   subject { Class.new.include(described_class).new }
 
   let(:expected_result) { double("result") }
@@ -17,7 +17,7 @@
     let(:paginator) { double("paginator", paginate: expected_result, finalize: nil) }
 
     before do
-      allow(subject).to receive(:paginator).with(relation, nil).and_return(paginator)
+      allow(subject).to receive(:paginator).with(relation, nil, true).and_return(paginator)
     end
 
     it 'yields paginated relation' do
@@ -174,6 +174,67 @@
           subject.paginator(relation)
         end
       end
+
+      context 'when cursor based keyset pagination is available' do
+        before do
+          allow(subject).to receive(:cursor_based_keyset_pagination_supported?).and_return(true)
+        end
+
+        context 'when use_cursor is true - default' do
+          before do
+            allow(Gitlab::Pagination::CursorBasedKeyset).to receive(:available?).and_return(true)
+            allow(Gitlab::Pagination::Keyset::CursorBasedRequestContext).to receive(:new)
+                                                                              .with(subject)
+                                                                              .and_return(request_context)
+            allow(Gitlab::Pagination::Keyset::CursorPager).to receive(:new).with(request_context).and_return(pager)
+          end
+
+          it 'delegates to CursorPager' do
+            expect(subject.paginator(relation)).to eq(pager)
+          end
+        end
+
+        context 'when use_cursor is false' do
+          before do
+            allow(Gitlab::Pagination::Keyset).to receive(:available?).and_return(true)
+            allow(Gitlab::Pagination::Keyset::Pager).to receive(:new).with(request_context).and_return(pager)
+          end
+
+          it 'delegates to Pager' do
+            expect(subject.paginator(relation, nil, false)).to eq(pager)
+          end
+        end
+      end
+
+      context 'when cursor based keyset pagination is not supported' do
+        before do
+          allow(subject).to receive(:cursor_based_keyset_pagination_supported?).and_return(false)
+          allow(Gitlab::Pagination::Keyset).to receive(:available?).and_return(true)
+          allow(Gitlab::Pagination::Keyset::Pager).to receive(:new).with(request_context).and_return(pager)
+        end
+
+        it 'delegate to keyset Pager' do
+          expect(subject.paginator(relation)).to eq(pager)
+        end
+      end
+
+      context 'when cursor based keyset pagination is not available' do
+        before do
+          allow(subject).to receive(:cursor_based_keyset_pagination_supported?).and_return(true)
+          allow(Gitlab::Pagination::CursorBasedKeyset).to receive(:available?)
+                                                            .with(request_context, relation)
+                                                            .and_return(false)
+          allow(Gitlab::Pagination::Keyset::CursorBasedRequestContext).to receive(:new)
+                                                                            .with(subject)
+                                                                            .and_return(request_context)
+        end
+
+        it 'renders a 501 error' do
+          expect(subject).to receive(:error!).with(/not yet available/, 405)
+
+          subject.paginator(relation)
+        end
+      end
     end
   end
 end