diff --git a/db/post_migrate/20230127153229_add_fk_index_to_ci_job_variables_on_partition_id_and_job_id.rb b/db/post_migrate/20230127153229_add_fk_index_to_ci_job_variables_on_partition_id_and_job_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..b06da3fc93379f374de1d9419f9e578b5217e844
--- /dev/null
+++ b/db/post_migrate/20230127153229_add_fk_index_to_ci_job_variables_on_partition_id_and_job_id.rb
@@ -0,0 +1,17 @@
+# frozen_string_literal: true
+
+class AddFkIndexToCiJobVariablesOnPartitionIdAndJobId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  INDEX_NAME = :index_ci_job_variables_on_partition_id_job_id
+  TABLE_NAME = :ci_job_variables
+  COLUMNS = [:partition_id, :job_id]
+
+  def up
+    add_concurrent_index(TABLE_NAME, COLUMNS, name: INDEX_NAME)
+  end
+
+  def down
+    remove_concurrent_index_by_name(TABLE_NAME, INDEX_NAME)
+  end
+end
diff --git a/db/post_migrate/20230127153230_add_fk_to_ci_job_variables_on_partition_id_and_job_id.rb b/db/post_migrate/20230127153230_add_fk_to_ci_job_variables_on_partition_id_and_job_id.rb
new file mode 100644
index 0000000000000000000000000000000000000000..7a6950fa96cf55d1e16bb7978ccc4a09a00e4069
--- /dev/null
+++ b/db/post_migrate/20230127153230_add_fk_to_ci_job_variables_on_partition_id_and_job_id.rb
@@ -0,0 +1,37 @@
+# frozen_string_literal: true
+
+class AddFkToCiJobVariablesOnPartitionIdAndJobId < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  SOURCE_TABLE_NAME = :ci_job_variables
+  TARGET_TABLE_NAME = :ci_builds
+  COLUMN = :job_id
+  TARGET_COLUMN = :id
+  FK_NAME = :fk_rails_fbf3b34792_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/20230127153229 b/db/schema_migrations/20230127153229
new file mode 100644
index 0000000000000000000000000000000000000000..a61e9ebcf974ace6ad668eed3abf9ebdd8cae4c3
--- /dev/null
+++ b/db/schema_migrations/20230127153229
@@ -0,0 +1 @@
+4a1764bf10e6d07f0504a0bdac252c0820d20203ed1fe4a7d39d7bcf1ab524a0
\ No newline at end of file
diff --git a/db/schema_migrations/20230127153230 b/db/schema_migrations/20230127153230
new file mode 100644
index 0000000000000000000000000000000000000000..99afc6f1eecb5afdd796255269937c8c416867d8
--- /dev/null
+++ b/db/schema_migrations/20230127153230
@@ -0,0 +1 @@
+89ca31682d8d789ff29958cee8451decab966c934012fb6f973565ea18803205
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index 7cac710290a857ee5dcca650a099e3120100afff..6e25d774c248158d10838640d3ef1f35011ee9f2 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -29128,6 +29128,8 @@ CREATE INDEX index_ci_job_variables_on_job_id ON ci_job_variables USING btree (j
 
 CREATE UNIQUE INDEX index_ci_job_variables_on_key_and_job_id ON ci_job_variables USING btree (key, job_id);
 
+CREATE INDEX index_ci_job_variables_on_partition_id_job_id ON ci_job_variables USING btree (partition_id, job_id);
+
 CREATE INDEX index_ci_minutes_additional_packs_on_namespace_id_purchase_xid ON ci_minutes_additional_packs USING btree (namespace_id, purchase_xid);
 
 CREATE UNIQUE INDEX index_ci_namespace_mirrors_on_namespace_id ON ci_namespace_mirrors USING btree (namespace_id);
@@ -36140,6 +36142,9 @@ ALTER TABLE ONLY serverless_domain_cluster
 ALTER TABLE ONLY ci_job_variables
     ADD CONSTRAINT fk_rails_fbf3b34792 FOREIGN KEY (job_id) REFERENCES ci_builds(id) ON DELETE CASCADE;
 
+ALTER TABLE ONLY ci_job_variables
+    ADD CONSTRAINT fk_rails_fbf3b34792_p FOREIGN KEY (partition_id, job_id) REFERENCES ci_builds(partition_id, id) ON UPDATE CASCADE ON DELETE CASCADE NOT VALID;
+
 ALTER TABLE ONLY packages_nuget_metadata
     ADD CONSTRAINT fk_rails_fc0c19f5b4 FOREIGN KEY (package_id) REFERENCES packages_packages(id) ON DELETE CASCADE;