diff --git a/db/post_migrate/20230127151606_add_fk_index_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb b/db/post_migrate/20230127151606_add_fk_index_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..a13ba0c21fbcbe573417636d7503b3c539ee0f86
--- /dev/null
+++ b/db/post_migrate/20230127151606_add_fk_index_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb
@@ -0,0 +1,17 @@
+# frozen_string_literal: true
+
+class AddFkIndexToCiBuildTraceMetadataOnPartitionIdAndBuildId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  INDEX_NAME = :index_ci_build_trace_metadata_on_partition_id_build_id
+  TABLE_NAME = :ci_build_trace_metadata
+  COLUMNS = [:partition_id, :build_id]
+
+  def up
+    add_concurrent_index(TABLE_NAME, COLUMNS, name: INDEX_NAME, unique: true)
+  end
+
+  def down
+    remove_concurrent_index_by_name(TABLE_NAME, INDEX_NAME)
+  end
+end
diff --git a/db/post_migrate/20230127151607_add_fk_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb b/db/post_migrate/20230127151607_add_fk_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..389cfc6a4ec1f257e7890e0f3428fef6e62f46bb
--- /dev/null
+++ b/db/post_migrate/20230127151607_add_fk_to_ci_build_trace_metadata_on_partition_id_and_build_id.rb
@@ -0,0 +1,37 @@
+# frozen_string_literal: true
+
+class AddFkToCiBuildTraceMetadataOnPartitionIdAndBuildId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  SOURCE_TABLE_NAME = :ci_build_trace_metadata
+  TARGET_TABLE_NAME = :ci_builds
+  COLUMN = :build_id
+  TARGET_COLUMN = :id
+  FK_NAME = :fk_rails_aebc78111f_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: false,
+      reverse_lock_order: true,
+      on_update: :cascade,
+      on_delete: :cascade,
+      name: FK_NAME
+    )
+  end
+
+  def down
+    with_lock_retries do
+      remove_foreign_key_if_exists(
+        SOURCE_TABLE_NAME,
+        TARGET_TABLE_NAME,
+        name: FK_NAME,
+        reverse_lock_order: true
+      )
+    end
+  end
+end
diff --git a/db/schema_migrations/20230127151606 b/db/schema_migrations/20230127151606
new file mode 100644
index 0000000000000000000000000000000000000000..576d1fcf615d32939f3acca254beac1927b977c7
--- /dev/null
+++ b/db/schema_migrations/20230127151606
@@ -0,0 +1 @@
+a8a968bf361b6807757d61720adf502528749b6d0236415d709bb393e540eefc
\ No newline at end of file
diff --git a/db/schema_migrations/20230127151607 b/db/schema_migrations/20230127151607
new file mode 100644
index 0000000000000000000000000000000000000000..a39fc0dbfffd0a5a69c8e63c859fae3b1cc397e7
--- /dev/null
+++ b/db/schema_migrations/20230127151607
@@ -0,0 +1 @@
+814f3c5716966479aff28a3c2b1713632847c4c30381f2634e7136d5b5cf9f74
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 9f4100a0d20d40adee10575bf295b7c7f427f983..e5311d96e8f1cf1420d24e3acd4055d54ed5d068 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -29140,6 +29140,8 @@ CREATE UNIQUE INDEX index_ci_build_trace_chunks_on_build_id_and_chunk_index ON c
 
 CREATE INDEX index_ci_build_trace_chunks_on_partition_id_build_id ON ci_build_trace_chunks USING btree (partition_id, build_id);
 
+CREATE UNIQUE INDEX index_ci_build_trace_metadata_on_partition_id_build_id ON ci_build_trace_metadata USING btree (partition_id, build_id);
+
 CREATE INDEX index_ci_build_trace_metadata_on_trace_artifact_id ON ci_build_trace_metadata USING btree (trace_artifact_id);
 
 CREATE INDEX p_ci_builds_metadata_build_id_idx ON ONLY p_ci_builds_metadata USING btree (build_id) WHERE (has_exposed_artifacts IS TRUE);
@@ -35781,6 +35783,9 @@ ALTER TABLE ONLY metrics_dashboard_annotations
 ALTER TABLE ONLY ci_build_trace_metadata
     ADD CONSTRAINT fk_rails_aebc78111f FOREIGN KEY (build_id) REFERENCES ci_builds(id) ON DELETE CASCADE;
 
+ALTER TABLE ONLY ci_build_trace_metadata
+    ADD CONSTRAINT fk_rails_aebc78111f_p FOREIGN KEY (partition_id, build_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE NOT VALID;
+
 ALTER TABLE ONLY bulk_import_trackers
     ADD CONSTRAINT fk_rails_aed566d3f3 FOREIGN KEY (bulk_import_entity_id) REFERENCES bulk_import_entities(id) ON DELETE CASCADE;