diff --git a/keyserver/src/database/migration-config.js b/keyserver/src/database/migration-config.js
--- a/keyserver/src/database/migration-config.js
+++ b/keyserver/src/database/migration-config.js
@@ -85,6 +85,17 @@
       );
     },
   ],
+  [
+    10,
+    async () => {
+      await dbQuery(
+        SQL`
+          ALTER TABLE messages
+            ADD INDEX target_message (target_message);
+        `,
+      );
+    },
+  ],
 ]);
 const newDatabaseVersion: number = Math.max(...migrations.keys());
 
diff --git a/keyserver/src/database/setup-db.js b/keyserver/src/database/setup-db.js
--- a/keyserver/src/database/setup-db.js
+++ b/keyserver/src/database/setup-db.js
@@ -264,7 +264,8 @@
       ALTER TABLE messages
         ADD PRIMARY KEY (id),
         ADD UNIQUE KEY user_creation (user,creation),
-        ADD KEY thread (thread);
+        ADD KEY thread (thread),
+        ADD INDEX target_message (target_message);
 
       ALTER TABLE notifications
         ADD PRIMARY KEY (id),