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
@@ -2,6 +2,7 @@
 
 import fs from 'fs';
 
+import { dbQuery, SQL } from '../database/database';
 import { updateRolesAndPermissionsForAllThreads } from '../updaters/thread-permission-updaters';
 
 const migrations: $ReadOnlyMap<number, () => Promise<void>> = new Map([
@@ -29,6 +30,12 @@
   ],
 
   [3, updateRolesAndPermissionsForAllThreads],
+  [
+    4,
+    async () => {
+      await dbQuery(SQL`ALTER TABLE uploads ADD INDEX container (container)`);
+    },
+  ],
 ]);
 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
@@ -304,7 +304,8 @@
         ADD INDEX user_key_time (user, \`key\`, time);
 
       ALTER TABLE uploads
-        ADD PRIMARY KEY (id);
+        ADD PRIMARY KEY (id),
+        ADD INDEX container (container);
 
       ALTER TABLE users
         ADD PRIMARY KEY (id),