diff --git a/db/post_migrate/20230227151608_validate_fk_on_ci_build_trace_metadata_partition_id_and_build_id.rb b/db/post_migrate/20230227151608_validate_fk_on_ci_build_trace_metadata_partition_id_and_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..b95c416c128a626d64ee595b467b8115bb1d6bb4
--- /dev/null
+++ b/db/post_migrate/20230227151608_validate_fk_on_ci_build_trace_metadata_partition_id_and_build_id.rb
@@ -0,0 +1,15 @@
+# frozen_string_literal: true
+
+class ValidateFkOnCiBuildTraceMetadataPartitionIdAndBuildId < Gitlab::Database::Migration[2.1]
+  TABLE_NAME = :ci_build_trace_metadata
+  FK_NAME = :fk_rails_aebc78111f_p
+  COLUMNS = [:partition_id, :build_id]
+
+  def up
+    validate_foreign_key(TABLE_NAME, COLUMNS, name: FK_NAME)
+  end
+
+  def down
+    # no-op
+  end
+end
diff --git a/db/post_migrate/20230227151609_remove_fk_to_ci_builds_ci_build_trace_metadata_on_build_id.rb b/db/post_migrate/20230227151609_remove_fk_to_ci_builds_ci_build_trace_metadata_on_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..16e24d7ed4ca6b9d8ff96d7d5db52f385caa20c4
--- /dev/null
+++ b/db/post_migrate/20230227151609_remove_fk_to_ci_builds_ci_build_trace_metadata_on_build_id.rb
@@ -0,0 +1,35 @@
+# frozen_string_literal: true
+
+class RemoveFkToCiBuildsCiBuildTraceMetadataOnBuildId < 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
+
+  def up
+    with_lock_retries do
+      remove_foreign_key_if_exists(
+        SOURCE_TABLE_NAME,
+        TARGET_TABLE_NAME,
+        name: FK_NAME,
+        reverse_lock_order: true
+      )
+    end
+  end
+
+  def down
+    add_concurrent_foreign_key(
+      SOURCE_TABLE_NAME,
+      TARGET_TABLE_NAME,
+      column: COLUMN,
+      target_column: TARGET_COLUMN,
+      validate: true,
+      reverse_lock_order: true,
+      on_delete: :cascade,
+      name: FK_NAME
+    )
+  end
+end
diff --git a/db/schema_migrations/20230227151608 b/db/schema_migrations/20230227151608
new file mode 100644
index 0000000000000000000000000000000000000000..333d71b1789c8386b32a40b254b305ce94abc245
--- /dev/null
+++ b/db/schema_migrations/20230227151608
@@ -0,0 +1 @@
+b43ebf61392e2857bd38f783f1ae46c4adce76a94dd8e7aa64fc02f234991229
\ No newline at end of file
diff --git a/db/schema_migrations/20230227151609 b/db/schema_migrations/20230227151609
new file mode 100644
index 0000000000000000000000000000000000000000..ec320e3c256aa9b39a11bc4de1873e00f1add0d7
--- /dev/null
+++ b/db/schema_migrations/20230227151609
@@ -0,0 +1 @@
+c2ac227a2e1a51423b043db9e992a519c096af8a309d3c1074fbd8bd744b4e3b
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 19171a90734ef471a3bc9f7475940bea0a584899..8733fa61ad142b70d3840fbb02c6b3c7f934bb2a 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -36102,10 +36102,7 @@ ALTER TABLE ONLY metrics_dashboard_annotations
     ADD CONSTRAINT fk_rails_aeb11a7643 FOREIGN KEY (environment_id) REFERENCES environments(id) ON DELETE CASCADE;
 
 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;
+    ADD CONSTRAINT fk_rails_aebc78111f_p FOREIGN KEY (partition_id, build_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE;
 
 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;
diff --git a/spec/db/schema_spec.rb b/spec/db/schema_spec.rb
index 756cb23b7a4ef84d9fb5858e1d14f0fbd7f6b293..f10adfe51732e92fdc82749b2218e7ffbca830bd 100644
--- a/spec/db/schema_spec.rb
+++ b/spec/db/schema_spec.rb
@@ -36,7 +36,7 @@
     ci_build_pending_states: %w[partition_id build_id],
     ci_build_report_results: %w[partition_id build_id],
     ci_build_trace_chunks: %w[partition_id build_id],
-    ci_build_trace_metadata: %w[partition_id],
+    ci_build_trace_metadata: %w[partition_id build_id],
     ci_builds: %w[erased_by_id trigger_request_id partition_id],
     ci_builds_runner_session: %w[partition_id build_id],
     p_ci_builds_metadata: %w[partition_id],