1 files changed, 30 insertions, 28 deletions

diff --git a/syncapi/storage/postgres/backward_extremities_table.go b/syncapi/storage/postgres/backward_extremities_table.go
index 8286ca43..b3ee28e0 100644
--- a/syncapi/storage/postgres/backward_extremities_table.go
+++ b/syncapi/storage/postgres/backward_extremities_table.go
@@ -21,39 +21,53 @@ import (
 	"github.com/matrix-org/dendrite/common"
 )
 
+// The purpose of this table is to keep track of backwards extremities for a room.
+// Backwards extremities are the earliest (DAG-wise) known events which we have
+// the entire event JSON. These event IDs are used in federation requests to fetch
+// even earlier events.
+//
+// We persist the previous event IDs as well, one per row, so when we do fetch even
+// earlier events we can simply delete rows which referenced it. Consider the graph:
+//        A
+//        |   Event C has 1 prev_event ID: A.
+//    B   C
+//    |___|   Event D has 2 prev_event IDs: B and C.
+//      |
+//      D
+// The earliest known event we have is D, so this table has 2 rows.
+// A backfill request gives us C but not B. We delete rows where prev_event=C. This
+// still means that D is a backwards extremity as we do not have event B. However, event
+// C is *also* a backwards extremity at this point as we do not have event A. Later,
+// when we fetch event B, we delete rows where prev_event=B. This then removes D as
+// a backwards extremity because there are no more rows with event_id=B.
 const backwardExtremitiesSchema = `
 -- Stores output room events received from the roomserver.
 CREATE TABLE IF NOT EXISTS syncapi_backward_extremities (
 	-- The 'room_id' key for the event.
 	room_id TEXT NOT NULL,
-	-- The event ID for the event.
+	-- The event ID for the last known event. This is the backwards extremity.
 	event_id TEXT NOT NULL,
+	-- The prev_events for the last known event. This is used to update extremities.
+	prev_event_id TEXT NOT NULL,
 
-	PRIMARY KEY(room_id, event_id)
+	PRIMARY KEY(room_id, event_id, prev_event_id)
 );
 `
 
 const insertBackwardExtremitySQL = "" +
-	"INSERT INTO syncapi_backward_extremities (room_id, event_id)" +
-	" VALUES ($1, $2)" +
+	"INSERT INTO syncapi_backward_extremities (room_id, event_id, prev_event_id)" +
+	" VALUES ($1, $2, $3)" +
 	" ON CONFLICT DO NOTHING"
 
 const selectBackwardExtremitiesForRoomSQL = "" +
 	"SELECT event_id FROM syncapi_backward_extremities WHERE room_id = $1"
 
-const isBackwardExtremitySQL = "" +
-	"SELECT EXISTS (" +
-	" SELECT TRUE FROM syncapi_backward_extremities" +
-	" WHERE room_id = $1 AND event_id = $2" +
-	")"
-
 const deleteBackwardExtremitySQL = "" +
-	"DELETE FROM syncapi_backward_extremities WHERE room_id = $1 AND event_id = $2"
+	"DELETE FROM syncapi_backward_extremities WHERE room_id = $1 AND prev_event_id = $2"
 
 type backwardExtremitiesStatements struct {
 	insertBackwardExtremityStmt          *sql.Stmt
 	selectBackwardExtremitiesForRoomStmt *sql.Stmt
-	isBackwardExtremityStmt              *sql.Stmt
 	deleteBackwardExtremityStmt          *sql.Stmt
 }
 
@@ -68,9 +82,6 @@ func (s *backwardExtremitiesStatements) prepare(db *sql.DB) (err error) {
 	if s.selectBackwardExtremitiesForRoomStmt, err = db.Prepare(selectBackwardExtremitiesForRoomSQL); err != nil {
 		return
 	}
-	if s.isBackwardExtremityStmt, err = db.Prepare(isBackwardExtremitySQL); err != nil {
-		return
-	}
 	if s.deleteBackwardExtremityStmt, err = db.Prepare(deleteBackwardExtremitySQL); err != nil {
 		return
 	}
@@ -78,17 +89,15 @@ func (s *backwardExtremitiesStatements) prepare(db *sql.DB) (err error) {
 }
 
 func (s *backwardExtremitiesStatements) insertsBackwardExtremity(
-	ctx context.Context, roomID, eventID string,
+	ctx context.Context, txn *sql.Tx, roomID, eventID string, prevEventID string,
 ) (err error) {
-	_, err = s.insertBackwardExtremityStmt.ExecContext(ctx, roomID, eventID)
+	_, err = txn.Stmt(s.insertBackwardExtremityStmt).ExecContext(ctx, roomID, eventID, prevEventID)
 	return
 }
 
 func (s *backwardExtremitiesStatements) selectBackwardExtremitiesForRoom(
 	ctx context.Context, roomID string,
 ) (eventIDs []string, err error) {
-	eventIDs = make([]string, 0)
-
 	rows, err := s.selectBackwardExtremitiesForRoomStmt.QueryContext(ctx, roomID)
 	if err != nil {
 		return
@@ -107,16 +116,9 @@ func (s *backwardExtremitiesStatements) selectBackwardExtremitiesForRoom(
 	return eventIDs, rows.Err()
 }
 
-func (s *backwardExtremitiesStatements) isBackwardExtremity(
-	ctx context.Context, roomID, eventID string,
-) (isBE bool, err error) {
-	err = s.isBackwardExtremityStmt.QueryRowContext(ctx, roomID, eventID).Scan(&isBE)
-	return
-}
-
 func (s *backwardExtremitiesStatements) deleteBackwardExtremity(
-	ctx context.Context, roomID, eventID string,
+	ctx context.Context, txn *sql.Tx, roomID, knownEventID string,
 ) (err error) {
-	_, err = s.insertBackwardExtremityStmt.ExecContext(ctx, roomID, eventID)
+	_, err = txn.Stmt(s.deleteBackwardExtremityStmt).ExecContext(ctx, roomID, knownEventID)
 	return
 }