3 files changed, 21 insertions, 5 deletions
diff --git a/synapse/storage/data_stores/main/events.py b/synapse/storage/data_stores/main/events.py
index 0480161056..577e79bcf9 100644
--- a/synapse/storage/data_stores/main/events.py
+++ b/synapse/storage/data_stores/main/events.py
@@ -1493,7 +1493,9 @@ class EventsStore(
             # Store the labels for this event.
             labels = event.content.get(EventContentFields.Labels)
             if labels:
-                self.insert_labels_for_event_txn(txn, event.event_id, labels)
+                self.insert_labels_for_event_txn(
+                    txn, event.event_id, labels, event.room_id, event.depth
+                )
 
         # Insert into the room_memberships table.
         self._store_room_members_txn(
@@ -2482,7 +2484,9 @@ class EventsStore(
             get_all_updated_current_state_deltas_txn,
         )
 
-    def insert_labels_for_event_txn(self, txn, event_id, labels):
+    def insert_labels_for_event_txn(
+        self, txn, event_id, labels, room_id, topological_ordering
+    ):
         """Store the mapping between an event's ID and its labels, with one row per
         (event_id, label) tuple.
 
@@ -2490,11 +2494,21 @@ class EventsStore(
             txn (LoggingTransaction): The transaction to execute.
             event_id (str): The event's ID.
             labels (list[str]): A list of text labels.
+            room_id (str): The ID of the room the event was sent to.
+            topological_ordering (int): The position of the event in the room's topology.
         """
         return self._simple_insert_many_txn(
             txn=txn,
             table="event_labels",
-            values=[{"event_id": event_id, "label": label} for label in labels],
+            values=[
+                {
+                    "event_id": event_id,
+                    "label": label,
+                    "room_id": room_id,
+                    "topological_ordering": topological_ordering,
+                }
+                for label in labels
+            ],
         )
 
 
diff --git a/synapse/storage/data_stores/main/schema/delta/56/event_labels.sql b/synapse/storage/data_stores/main/schema/delta/56/event_labels.sql
index 9550b0adaa..765124d131 100644
--- a/synapse/storage/data_stores/main/schema/delta/56/event_labels.sql
+++ b/synapse/storage/data_stores/main/schema/delta/56/event_labels.sql
@@ -16,7 +16,9 @@
 CREATE TABLE IF NOT EXISTS event_labels (
     event_id TEXT,
     label TEXT,
+    room_id TEXT NOT NULL,
+    topological_ordering bigint NOT NULL,
     PRIMARY KEY(event_id, label)
 );
 
-CREATE INDEX event_labels_label_idx ON event_labels(label);
+CREATE INDEX event_labels_room_id_label_idx ON event_labels(room_id, label, topological_ordering);
diff --git a/synapse/storage/data_stores/main/stream.py b/synapse/storage/data_stores/main/stream.py
index cfa34ba1e7..616ef91d4e 100644
--- a/synapse/storage/data_stores/main/stream.py
+++ b/synapse/storage/data_stores/main/stream.py
@@ -874,7 +874,7 @@ class StreamWorkerStore(EventsWorkerStore, SQLBaseStore):
         sql = (
             "SELECT DISTINCT event_id, topological_ordering, stream_ordering"
             " FROM events"
-            " LEFT JOIN event_labels USING (event_id)"
+            " LEFT JOIN event_labels USING (event_id, room_id, topological_ordering)"
             " WHERE outlier = ? AND room_id = ? AND %(bounds)s"
             " ORDER BY topological_ordering %(order)s,"
             " stream_ordering %(order)s LIMIT ?"