diff --git a/db/post_migrate/20230119090944_add_index_to_ci_pending_build.rb b/db/post_migrate/20230119090944_add_index_to_ci_pending_build.rb
new file mode 100644
index 0000000000000000000000000000000000000000..de58b6a0ef89fafc09ecda140d766ba171d7d0db
--- /dev/null
+++ b/db/post_migrate/20230119090944_add_index_to_ci_pending_build.rb
@@ -0,0 +1,17 @@
+# frozen_string_literal: true
+
+class AddIndexToCiPendingBuild < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  INDEX_NAME = :index_ci_pending_builds_on_partition_id_build_id
+  TABLE_NAME = :ci_pending_builds
+  COLUMNS = [:partition_id, :build_id]
+
+  def up
+    add_concurrent_index(TABLE_NAME, COLUMNS, unique: true, name: INDEX_NAME)
+  end
+
+  def down
+    remove_concurrent_index_by_name(TABLE_NAME, INDEX_NAME)
+  end
+end
diff --git a/db/post_migrate/20230119091027_add_foreign_key_to_ci_pending_build.rb b/db/post_migrate/20230119091027_add_foreign_key_to_ci_pending_build.rb
new file mode 100644
index 0000000000000000000000000000000000000000..9f7f807e7383cba26dacf662de716d4c0f907d69
--- /dev/null
+++ b/db/post_migrate/20230119091027_add_foreign_key_to_ci_pending_build.rb
@@ -0,0 +1,31 @@
+# frozen_string_literal: true
+
+class AddForeignKeyToCiPendingBuild < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  SOURCE_TABLE_NAME = :ci_pending_builds
+  TARGET_TABLE_NAME = :ci_builds
+  COLUMN = :build_id
+  TARGET_COLUMN = :id
+  FK_NAME = :fk_rails_725a2644a3_p
+  PARTITION_COLUMN = :partition_id
+
+  def up
+    add_concurrent_foreign_key(
+      SOURCE_TABLE_NAME,
+      TARGET_TABLE_NAME,
+      column: [PARTITION_COLUMN, COLUMN],
+      target_column: [PARTITION_COLUMN, TARGET_COLUMN],
+      validate: true,
+      reverse_lock_order: true,
+      name: FK_NAME,
+      on_update: :cascade
+    )
+  end
+
+  def down
+    with_lock_retries do
+      remove_foreign_key_if_exists(SOURCE_TABLE_NAME, name: FK_NAME)
+    end
+  end
+end
diff --git a/db/schema_migrations/20230119090944 b/db/schema_migrations/20230119090944
new file mode 100644
index 0000000000000000000000000000000000000000..b9efaee5bc04fb1dddf8c7c932227d51b1c47a1a
--- /dev/null
+++ b/db/schema_migrations/20230119090944
@@ -0,0 +1 @@
+6d66200b1707cb469891aa661ed944b133833abe5a0cdd37e4cae1b78b36426f
\ No newline at end of file
diff --git a/db/schema_migrations/20230119091027 b/db/schema_migrations/20230119091027
new file mode 100644
index 0000000000000000000000000000000000000000..f4a5d3d556aabc1b4d7ab674fc090722c601b09c
--- /dev/null
+++ b/db/schema_migrations/20230119091027
@@ -0,0 +1 @@
+0e269f5d643757423c3597f646b298224ab3c2eb60ab92cb030edb6ec8fb3241
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 5f33b103d72f968c7f36b45768165eb4b496b6b8..0e3dbe781ce7b6319f589e2e9245ebd829ed343d 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -28983,6 +28983,8 @@ CREATE UNIQUE INDEX index_ci_pending_builds_on_build_id ON ci_pending_builds USI
 
 CREATE INDEX index_ci_pending_builds_on_namespace_id ON ci_pending_builds USING btree (namespace_id);
 
+CREATE UNIQUE INDEX index_ci_pending_builds_on_partition_id_build_id ON ci_pending_builds USING btree (partition_id, build_id);
+
 CREATE INDEX index_ci_pending_builds_on_project_id ON ci_pending_builds USING btree (project_id);
 
 CREATE INDEX index_ci_pending_builds_on_tag_ids ON ci_pending_builds USING btree (tag_ids) WHERE (cardinality(tag_ids) > 0);
@@ -35013,6 +35015,9 @@ ALTER TABLE ONLY project_custom_attributes
 ALTER TABLE ONLY ci_pending_builds
     ADD CONSTRAINT fk_rails_725a2644a3 FOREIGN KEY (build_id) REFERENCES ci_builds(id) ON DELETE CASCADE;
 
+ALTER TABLE ONLY ci_pending_builds
+    ADD CONSTRAINT fk_rails_725a2644a3_p FOREIGN KEY (partition_id, build_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE;
+
 ALTER TABLE security_findings
     ADD CONSTRAINT fk_rails_729b763a54 FOREIGN KEY (scanner_id) REFERENCES vulnerability_scanners(id) ON DELETE CASCADE;