diff --git a/db/post_migrate/20230125093723_rebalance_partition_id_ci_pipeline.rb b/db/post_migrate/20230125093723_rebalance_partition_id_ci_pipeline.rb
new file mode 100644
index 0000000000000000000000000000000000000000..aaea55ce3311bf3ede8608209e9a56c3cbcacf8b
--- /dev/null
+++ b/db/post_migrate/20230125093723_rebalance_partition_id_ci_pipeline.rb
@@ -0,0 +1,30 @@
+# frozen_string_literal: true
+
+class RebalancePartitionIdCiPipeline < Gitlab::Database::Migration[2.1]
+  MIGRATION = 'RebalancePartitionId'
+  DELAY_INTERVAL = 2.minutes
+  TABLE = :ci_pipelines
+  BATCH_SIZE = 2_000
+  SUB_BATCH_SIZE = 200
+
+  restrict_gitlab_migration gitlab_schema: :gitlab_ci
+
+  def up
+    return unless Gitlab.com?
+
+    queue_batched_background_migration(
+      MIGRATION,
+      TABLE,
+      :id,
+      job_interval: DELAY_INTERVAL,
+      batch_size: BATCH_SIZE,
+      sub_batch_size: SUB_BATCH_SIZE
+    )
+  end
+
+  def down
+    return unless Gitlab.com?
+
+    delete_batched_background_migration(MIGRATION, TABLE, :id, [])
+  end
+end
diff --git a/db/schema_migrations/20230125093723 b/db/schema_migrations/20230125093723
new file mode 100644
index 0000000000000000000000000000000000000000..9c5782dcdacdcd02fada0cd4fb76cbd0860843eb
--- /dev/null
+++ b/db/schema_migrations/20230125093723
@@ -0,0 +1 @@
+364f785b564d92d2956c5ffea71091561231888ffa6f4cd9125fc8ebf9150f77
\ No newline at end of file
diff --git a/lib/gitlab/background_migration/rebalance_partition_id.rb b/lib/gitlab/background_migration/rebalance_partition_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..7000ae5a8566aae9d18c3a6f0d568960590c7623
--- /dev/null
+++ b/lib/gitlab/background_migration/rebalance_partition_id.rb
@@ -0,0 +1,21 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module BackgroundMigration
+    # This rebalances partition_id to fix invalid records in production
+    class RebalancePartitionId < BatchedMigrationJob
+      INVALID_PARTITION_ID = 101
+      VALID_PARTITION_ID = 100
+
+      scope_to ->(relation) { relation.where(partition_id: INVALID_PARTITION_ID) }
+      operation_name :update_all
+      feature_category :continuous_integration
+
+      def perform
+        each_sub_batch do |sub_batch|
+          sub_batch.update_all(partition_id: VALID_PARTITION_ID)
+        end
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/background_migration/rebalance_partition_id_spec.rb b/spec/lib/gitlab/background_migration/rebalance_partition_id_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..195e57e4e59e93c484826bf6c128ce7c4884e357
--- /dev/null
+++ b/spec/lib/gitlab/background_migration/rebalance_partition_id_spec.rb
@@ -0,0 +1,46 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+
+RSpec.describe Gitlab::BackgroundMigration::RebalancePartitionId,
+  :migration,
+  schema: 20230125093723,
+  feature_category: :continuous_integration do
+  let(:ci_builds_table) { table(:ci_builds, database: :ci) }
+  let(:ci_pipelines_table) { table(:ci_pipelines, database: :ci) }
+
+  let!(:valid_ci_pipeline) { ci_pipelines_table.create!(id: 1, partition_id: 100) }
+  let!(:invalid_ci_pipeline) { ci_pipelines_table.create!(id: 2, partition_id: 101) }
+
+  describe '#perform' do
+    using RSpec::Parameterized::TableSyntax
+
+    where(:table_name, :invalid_record, :valid_record) do
+      :ci_pipelines | invalid_ci_pipeline | valid_ci_pipeline
+    end
+
+    subject(:perform) do
+      described_class.new(
+        start_id: 1,
+        end_id: 2,
+        batch_table: table_name,
+        batch_column: :id,
+        sub_batch_size: 1,
+        pause_ms: 0,
+        connection: Ci::ApplicationRecord.connection
+      ).perform
+    end
+
+    shared_examples 'fix invalid records' do
+      it 'rebalances partition_id to 100 when partition_id is 101' do
+        expect { perform }
+          .to change { invalid_record.reload.partition_id }.from(101).to(100)
+          .and not_change { valid_record.reload.partition_id }
+      end
+    end
+
+    with_them do
+      it_behaves_like 'fix invalid records'
+    end
+  end
+end
diff --git a/spec/migrations/20230125093723_rebalance_partition_id_ci_pipeline_spec.rb b/spec/migrations/20230125093723_rebalance_partition_id_ci_pipeline_spec.rb
new file mode 100644
index 0000000000000000000000000000000000000000..3ccd92e15a4822b8f93962cac75a35bdee6c5829
--- /dev/null
+++ b/spec/migrations/20230125093723_rebalance_partition_id_ci_pipeline_spec.rb
@@ -0,0 +1,58 @@
+# frozen_string_literal: true
+
+require 'spec_helper'
+require_migration!
+
+RSpec.describe RebalancePartitionIdCiPipeline, migration: :gitlab_ci, feature_category: :continuous_integration do
+  let(:migration) { described_class::MIGRATION }
+
+  context 'when on sass' do
+    before do
+      allow(Gitlab).to receive(:com?).and_return(true)
+    end
+
+    describe '#up' do
+      it 'schedules background jobs for each batch of ci_builds' do
+        migrate!
+
+        expect(migration).to have_scheduled_batched_migration(
+          gitlab_schema: :gitlab_ci,
+          table_name: :ci_pipelines,
+          column_name: :id,
+          interval: described_class::DELAY_INTERVAL,
+          batch_size: described_class::BATCH_SIZE,
+          sub_batch_size: described_class::SUB_BATCH_SIZE
+        )
+      end
+    end
+
+    describe '#down' do
+      it 'deletes all batched migration records' do
+        migrate!
+        schema_migrate_down!
+
+        expect(migration).not_to have_scheduled_batched_migration
+      end
+    end
+  end
+
+  context 'when on self-managed instance' do
+    let(:migration) { described_class.new }
+
+    describe '#up' do
+      it 'does not schedule background job' do
+        expect(migration).not_to receive(:queue_batched_background_migration)
+
+        migration.up
+      end
+    end
+
+    describe '#down' do
+      it 'does not delete background job' do
+        expect(migration).not_to receive(:delete_batched_background_migration)
+
+        migration.down
+      end
+    end
+  end
+end