diff --git a/db/migrate/20230124122143_add_deploy_key_id_to_create_access_levels.rb b/db/migrate/20230124122143_add_deploy_key_id_to_create_access_levels.rb
new file mode 100644
index 0000000000000000000000000000000000000000..d26cf2a1e5f04bfdc8aed53dcaaba22ad860c1d9
--- /dev/null
+++ b/db/migrate/20230124122143_add_deploy_key_id_to_create_access_levels.rb
@@ -0,0 +1,11 @@
+# frozen_string_literal: true
+
+class AddDeployKeyIdToCreateAccessLevels < Gitlab::Database::Migration[2.1]
+  def up
+    add_column :protected_tag_create_access_levels, :deploy_key_id, :integer
+  end
+
+  def down
+    remove_column :protected_tag_create_access_levels, :deploy_key_id
+  end
+end
diff --git a/db/migrate/20230124193917_add_index_for_protected_tag_create_access_levels.rb b/db/migrate/20230124193917_add_index_for_protected_tag_create_access_levels.rb
new file mode 100644
index 0000000000000000000000000000000000000000..7068f4f0447c996169827c174d8b5fb0c3109077
--- /dev/null
+++ b/db/migrate/20230124193917_add_index_for_protected_tag_create_access_levels.rb
@@ -0,0 +1,18 @@
+# frozen_string_literal: true
+
+class AddIndexForProtectedTagCreateAccessLevels < Gitlab::Database::Migration[2.1]
+  disable_ddl_transaction!
+
+  DEPLOY_KEY_INDEX_NAME = 'index_protected_tag_create_access_levels_on_deploy_key_id'
+
+  def up
+    add_concurrent_foreign_key :protected_tag_create_access_levels, :keys, column: :deploy_key_id, on_delete: :cascade
+    add_concurrent_index :protected_tag_create_access_levels, :deploy_key_id,
+                         name: DEPLOY_KEY_INDEX_NAME
+  end
+
+  def down
+    remove_foreign_key_if_exists :protected_tag_create_access_levels, column: :deploy_key_id
+    remove_concurrent_index_by_name :protected_tag_create_access_levels, name: DEPLOY_KEY_INDEX_NAME
+  end
+end
diff --git a/db/schema_migrations/20230124122143 b/db/schema_migrations/20230124122143
new file mode 100644
index 0000000000000000000000000000000000000000..a38e5b7c40ba260c1dad64dc51b07c92cb6bbcd8
--- /dev/null
+++ b/db/schema_migrations/20230124122143
@@ -0,0 +1 @@
+be87eb6052d3f853f05f59a6deb8669857047ca95d28b209b1c19c66fa96ff15
\ No newline at end of file
diff --git a/db/schema_migrations/20230124193917 b/db/schema_migrations/20230124193917
new file mode 100644
index 0000000000000000000000000000000000000000..b8e45dd4692d05509817e781bcf6d7ce8d6b0671
--- /dev/null
+++ b/db/schema_migrations/20230124193917
@@ -0,0 +1 @@
+277c1abd9cc4f9fb6aca4991b7643d8b9964ef466f4d209848c90b34c8eec9c0
\ No newline at end of file
diff --git a/db/structure.sql b/db/structure.sql
index cbc4b291335f5aec25e7c29e485e8a4ec3bffeff..f1d0310ac3aa8dd0f4443a762d65a33e35d37cbf 100644
--- a/db/structure.sql
+++ b/db/structure.sql
@@ -21003,7 +21003,8 @@ CREATE TABLE protected_tag_create_access_levels (
     user_id integer,
     group_id integer,
     created_at timestamp without time zone NOT NULL,
-    updated_at timestamp without time zone NOT NULL
+    updated_at timestamp without time zone NOT NULL,
+    deploy_key_id integer
 );
 
 CREATE SEQUENCE protected_tag_create_access_levels_id_seq
@@ -31027,6 +31028,8 @@ CREATE UNIQUE INDEX index_protected_environments_on_project_id_and_name ON prote
 
 CREATE INDEX index_protected_tag_create_access ON protected_tag_create_access_levels USING btree (protected_tag_id);
 
+CREATE INDEX index_protected_tag_create_access_levels_on_deploy_key_id ON protected_tag_create_access_levels USING btree (deploy_key_id);
+
 CREATE INDEX index_protected_tag_create_access_levels_on_group_id ON protected_tag_create_access_levels USING btree (group_id);
 
 CREATE INDEX index_protected_tag_create_access_levels_on_user_id ON protected_tag_create_access_levels USING btree (user_id);
@@ -33548,6 +33551,9 @@ ALTER TABLE ONLY sprints
 ALTER TABLE ONLY push_event_payloads
     ADD CONSTRAINT fk_36c74129da FOREIGN KEY (event_id) REFERENCES events(id) ON DELETE CASCADE;
 
+ALTER TABLE ONLY protected_tag_create_access_levels
+    ADD CONSTRAINT fk_386a642e13 FOREIGN KEY (deploy_key_id) REFERENCES keys(id) ON DELETE CASCADE;
+
 ALTER TABLE ONLY incident_management_timeline_events
     ADD CONSTRAINT fk_38a74279df FOREIGN KEY (updated_by_user_id) REFERENCES users(id) ON DELETE SET NULL;