pgvector.git / summary / log / commit / refs

commit    b72a22b3c0304c8f35bc34ff682da2eb46043201
Author:   Andrew Kane <andrew@ankane.org>
Date:     Thu Aug 17 00:07:19 2023 +0000

    Fixed duplicate connections when repairing graph


 src/hnsw.h       |  2 +-
 src/hnswinsert.c | 26 +++++++++++++++++++++++---
 src/hnswvacuum.c |  2 +-
 3 files changed, 25 insertions(+), 5 deletions(-)

diff --git a/src/hnsw.h b/src/hnsw.h
index bc79c8a5..0a8e633c 100644
--- a/src/hnsw.h
+++ b/src/hnsw.h
@@ -271,7 +271,7 @@ void		HnswSetNeighborTuple(HnswNeighborTuple ntup, HnswElement e, int m);
 void		HnswAddHeapTid(HnswElement element, ItemPointer heaptid);
 void		HnswInitNeighbors(HnswElement element, int m);
 bool		HnswInsertTuple(Relation index, Datum *values, bool *isnull, ItemPointer heap_tid, Relation heapRel);
-void		UpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswElement e, int m);
+void		UpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswElement e, int m, bool checkExisting);
 void		HnswLoadElement(HnswElement element, float *distance, Datum *q, Relation index, FmgrInfo *procinfo, Oid collation, bool loadVec);
 void		HnswSetElementTuple(HnswElementTuple etup, HnswElement element);
 void		HnswUpdateConnection(HnswElement element, HnswCandidate * hc, int m, int lc, int *updateIdx, Relation index, FmgrInfo *procinfo, Oid collation);
diff --git a/src/hnswinsert.c b/src/hnswinsert.c
index 0e52f104..3ac793ea 100644
--- a/src/hnswinsert.c
+++ b/src/hnswinsert.c
@@ -283,11 +283,28 @@ WriteNewElementPages(Relation index, HnswElement e, int m, BlockNumber insertPag
 		*updatedInsertPage = newInsertPage;
 }
 
+/*
+ * Check if connection already exists
+ */
+static bool
+ConnectionExists(HnswElement e, HnswNeighborTuple ntup, int startIdx, int lm)
+{
+	for (int i = 0; i < lm; i++)
+	{
+		ItemPointer indextid = &ntup->indextids[startIdx + i];
+
+		if (ItemPointerGetBlockNumber(indextid) == e->blkno && ItemPointerGetOffsetNumber(indextid) == e->offno)
+			return true;
+	}
+
+	return false;
+}
+
 /*
  * Update neighbors
  */
 void
-UpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswElement e, int m)
+UpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswElement e, int m, bool checkExisting)
 {
 	for (int lc = e->level; lc >= 0; lc--)
 	{
@@ -339,7 +356,10 @@ UpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswEleme
 			/* Calculate index for update */
 			startIdx = (hc->element->level - lc) * m;
 
-			if (idx == -2)
+			/* Check for existing connection */
+			if (checkExisting && ConnectionExists(e, ntup, startIdx, lm))
+				idx = -1;
+			else if (idx == -2)
 			{
 				/* Find free offset if still exists */
 				/* TODO Retry updating connections if not */
@@ -496,7 +516,7 @@ WriteElement(Relation index, FmgrInfo *procinfo, Oid collation, HnswElement elem
 		HnswUpdateMetaPage(index, 0, NULL, newInsertPage, MAIN_FORKNUM);
 
 	/* Update neighbors */
-	UpdateNeighborPages(index, procinfo, collation, element, m);
+	UpdateNeighborPages(index, procinfo, collation, element, m, false);
 
 	/* Update metapage if needed */
 	if (element->level > entryPoint->level)
diff --git a/src/hnswvacuum.c b/src/hnswvacuum.c
index eb7c869a..6f137e21 100644
--- a/src/hnswvacuum.c
+++ b/src/hnswvacuum.c
@@ -255,7 +255,7 @@ RepairGraphElement(HnswVacuumState * vacuumstate, HnswElement element)
 	UnlockReleaseBuffer(buf);
 
 	/* Update neighbors */
-	UpdateNeighborPages(index, procinfo, collation, element, m);
+	UpdateNeighborPages(index, procinfo, collation, element, m, true);
 }
 
 /*


[parent: 8c5c0f791e86]