diff --git a/db/post_migrate/20230220134145_validate_fk_on_ci_build_needs_partition_id_and_build_id.rb b/db/post_migrate/20230220134145_validate_fk_on_ci_build_needs_partition_id_and_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..eec60a51834740010103e1bf00f9f98f6a2e5174
--- /dev/null
+++ b/db/post_migrate/20230220134145_validate_fk_on_ci_build_needs_partition_id_and_build_id.rb
@@ -0,0 +1,15 @@
+# frozen_string_literal: true
+
+class ValidateFkOnCiBuildNeedsPartitionIdAndBuildId < Gitlab::Database::Migration[2.1]
+  TABLE_NAME = :ci_build_needs
+  FK_NAME = :fk_rails_3cf221d4ed_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/20230220134146_remove_fk_to_ci_builds_ci_build_needs_on_build_id.rb b/db/post_migrate/20230220134146_remove_fk_to_ci_builds_ci_build_needs_on_build_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..04e7ec11ee678a0b8cde208e684f899f7962141b
--- /dev/null
+++ b/db/post_migrate/20230220134146_remove_fk_to_ci_builds_ci_build_needs_on_build_id.rb
@@ -0,0 +1,35 @@
+# frozen_string_literal: true
+
+class RemoveFkToCiBuildsCiBuildNeedsOnBuildId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  SOURCE_TABLE_NAME = :ci_build_needs
+  TARGET_TABLE_NAME = :ci_builds
+  COLUMN = :build_id
+  TARGET_COLUMN = :id
+  FK_NAME = :fk_rails_3cf221d4ed
+
+  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/20230220134145 b/db/schema_migrations/20230220134145
new file mode 100644
index 0000000000000000000000000000000000000000..91238639d7893b57bf3264f8d914af72d8532b76
--- /dev/null
+++ b/db/schema_migrations/20230220134145
@@ -0,0 +1 @@
+d20d4bd35b5e4132515c731e7df802c0fd6f3e88d4bee2d3b9fe42af4307977c
\ No newline at end of file
diff --git a/db/schema_migrations/20230220134146 b/db/schema_migrations/20230220134146
new file mode 100644
index 0000000000000000000000000000000000000000..3d0745d3f2215f87a0e4f28b7e8ad103d37b6b6b
--- /dev/null
+++ b/db/schema_migrations/20230220134146
@@ -0,0 +1 @@
+7fe8e5e2e9019ccb29f29df161f7b7c45aa2576188b326e60f758dd2d5f56a47
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 61b0e28c8ad79baa5137681c1954b625ac9ac06c..15eba362e8303ff15b73f045f86edd0c50c3d053 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -35221,10 +35221,7 @@ ALTER TABLE ONLY chat_teams
     ADD CONSTRAINT fk_rails_3b543909cb FOREIGN KEY (namespace_id) REFERENCES namespaces(id) ON DELETE CASCADE;
 
 ALTER TABLE ONLY ci_build_needs
-    ADD CONSTRAINT fk_rails_3cf221d4ed FOREIGN KEY (build_id) REFERENCES ci_builds(id) ON DELETE CASCADE;
-
-ALTER TABLE ONLY ci_build_needs
-    ADD CONSTRAINT fk_rails_3cf221d4ed_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_3cf221d4ed_p FOREIGN KEY (partition_id, build_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE;
 
 ALTER TABLE ONLY cluster_groups
     ADD CONSTRAINT fk_rails_3d28377556 FOREIGN KEY (group_id) REFERENCES namespaces(id) ON DELETE CASCADE;
diff --git a/spec/db/schema_spec.rb b/spec/db/schema_spec.rb
index 17647a0a6c99fc801f912b9ec006f05855294a2a..8b9bcfdeaba10bc49563dcc4da3b5b260aba9b1c 100644
--- a/spec/db/schema_spec.rb
+++ b/spec/db/schema_spec.rb
@@ -35,7 +35,7 @@
     boards: %w[milestone_id iteration_id],
     chat_names: %w[chat_id team_id user_id integration_id],
     chat_teams: %w[team_id],
-    ci_build_needs: %w[partition_id],
+    ci_build_needs: %w[partition_id build_id],
     ci_build_pending_states: %w[partition_id build_id],
     ci_build_report_results: %w[partition_id],
     ci_build_trace_chunks: %w[partition_id build_id],