diff --git a/db/post_migrate/20230218152729_validate_fk_on_ci_job_artifacts_partition_id_and_job_id.rb b/db/post_migrate/20230218152729_validate_fk_on_ci_job_artifacts_partition_id_and_job_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..9a9cb0d9487816edc74ae6b1c18852b344d0b179
--- /dev/null
+++ b/db/post_migrate/20230218152729_validate_fk_on_ci_job_artifacts_partition_id_and_job_id.rb
@@ -0,0 +1,15 @@
+# frozen_string_literal: true
+
+class ValidateFkOnCiJobArtifactsPartitionIdAndJobId < Gitlab::Database::Migration[2.1]
+  TABLE_NAME = :ci_job_artifacts
+  FK_NAME = :fk_rails_c5137cb2c1_p
+  COLUMNS = [:partition_id, :job_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/20230218152730_remove_fk_to_ci_builds_ci_job_artifacts_on_job_id.rb b/db/post_migrate/20230218152730_remove_fk_to_ci_builds_ci_job_artifacts_on_job_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..02747d57eabba2da8d251ebeb4ef4d8243aa3971
--- /dev/null
+++ b/db/post_migrate/20230218152730_remove_fk_to_ci_builds_ci_job_artifacts_on_job_id.rb
@@ -0,0 +1,35 @@
+# frozen_string_literal: true
+
+class RemoveFkToCiBuildsCiJobArtifactsOnJobId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  SOURCE_TABLE_NAME = :ci_job_artifacts
+  TARGET_TABLE_NAME = :ci_builds
+  COLUMN = :job_id
+  TARGET_COLUMN = :id
+  FK_NAME = :fk_rails_c5137cb2c1
+
+  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/20230218152729 b/db/schema_migrations/20230218152729
new file mode 100644
index 0000000000000000000000000000000000000000..f78be05543589edc4cf489d20837102b7a6836c2
--- /dev/null
+++ b/db/schema_migrations/20230218152729
@@ -0,0 +1 @@
+ac404c1dd1b2a38b8d02563b4b9306076f35120448d78b130c0421364c11822c
\ No newline at end of file
diff --git a/db/schema_migrations/20230218152730 b/db/schema_migrations/20230218152730
new file mode 100644
index 0000000000000000000000000000000000000000..55fb606940364fab32c99bb57b967642579f0bd0
--- /dev/null
+++ b/db/schema_migrations/20230218152730
@@ -0,0 +1 @@
+f85595c6176426369f8558ba3dadf6ee2a5efa17f2d304dc8397862fc7d52545
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 61b0e28c8ad79baa5137681c1954b625ac9ac06c..98f41b2c259afe57748f75ff93ad60da899a794e 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -36145,10 +36145,7 @@ ALTER TABLE ONLY boards_epic_board_recent_visits
     ADD CONSTRAINT fk_rails_c4dcba4a3e FOREIGN KEY (group_id) REFERENCES namespaces(id) ON DELETE CASCADE;
 
 ALTER TABLE ONLY ci_job_artifacts
-    ADD CONSTRAINT fk_rails_c5137cb2c1 FOREIGN KEY (job_id) REFERENCES ci_builds(id) ON DELETE CASCADE;
-
-ALTER TABLE ONLY ci_job_artifacts
-    ADD CONSTRAINT fk_rails_c5137cb2c1_p FOREIGN KEY (partition_id, job_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE NOT VALID;
+    ADD CONSTRAINT fk_rails_c5137cb2c1_p FOREIGN KEY (partition_id, job_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE;
 
 ALTER TABLE ONLY packages_events
     ADD CONSTRAINT fk_rails_c6c20d0094 FOREIGN KEY (package_id) REFERENCES packages_packages(id) ON DELETE SET NULL;
diff --git a/spec/db/schema_spec.rb b/spec/db/schema_spec.rb
index 17647a0a6c99fc801f912b9ec006f05855294a2a..3f8bdee990ff24264985f347221a2205dc13ac4c 100644
--- a/spec/db/schema_spec.rb
+++ b/spec/db/schema_spec.rb
@@ -43,7 +43,7 @@
     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],
-    ci_job_artifacts: %w[partition_id],
+    ci_job_artifacts: %w[partition_id job_id],
     ci_job_variables: %w[partition_id],
     ci_namespace_monthly_usages: %w[namespace_id],
     ci_pending_builds: %w[partition_id],