pgvector.git / summary / log / commit / refs
commit d05d6ee83da96bc377bcf06d250e7d976b5254f0
Author: Andrew Kane <andrew@ankane.org>
Date: Sun Sep 03 08:35:21 2023 +0000
Get m from metapage
src/hnsw.h | 5 +++--
src/hnswinsert.c | 17 ++++++++---------
src/hnswscan.c | 10 +++++++---
src/hnswutils.c | 40 +++++++++++++++++++++++++++-------------
src/hnswvacuum.c | 6 +++---
5 files changed, 48 insertions(+), 30 deletions(-)
diff --git a/src/hnsw.h b/src/hnsw.h
index 3e8bdc2c..74a8d6c8 100644
--- a/src/hnsw.h
+++ b/src/hnsw.h
@@ -266,8 +266,9 @@ Buffer HnswNewBuffer(Relation index, ForkNumber forkNum);
void HnswInitPage(Buffer buf, Page page);
void HnswInitRegisterPage(Relation index, Buffer *buf, Page *page, GenericXLogState **state);
void HnswInit(void);
-List *HnswSearchLayer(Datum q, List *ep, int ef, int lc, Relation index, FmgrInfo *procinfo, Oid collation, bool inserting, HnswElement skipElement);
+List *HnswSearchLayer(Datum q, List *ep, int ef, int lc, Relation index, FmgrInfo *procinfo, Oid collation, int m, bool inserting, HnswElement skipElement);
HnswElement HnswGetEntryPoint(Relation index);
+void HnswGetMetaPageInfo(Relation index, int *m, HnswElement * entryPoint);
HnswElement HnswInitElement(ItemPointer tid, int m, double ml, int maxLevel);
void HnswFreeElement(HnswElement element);
HnswElement HnswInitElementFromBlock(BlockNumber blkno, OffsetNumber offno);
@@ -284,7 +285,7 @@ void HnswLoadElementFromTuple(HnswElement element, HnswElementTuple etup, bool
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);
-void HnswLoadNeighbors(HnswElement element, Relation index);
+void HnswLoadNeighbors(HnswElement element, Relation index, int m);
/* Index access methods */
IndexBuildResult *hnswbuild(Relation heap, Relation index, IndexInfo *indexInfo);
diff --git a/src/hnswinsert.c b/src/hnswinsert.c
index 685b0bf6..8ac96500 100644
--- a/src/hnswinsert.c
+++ b/src/hnswinsert.c
@@ -329,7 +329,7 @@ HnswUpdateNeighborPages(Relation index, FmgrInfo *procinfo, Oid collation, HnswE
/* Get latest neighbors since they may have changed */
/* Do not lock yet since selecting neighbors can take time */
- HnswLoadNeighbors(hc->element, index);
+ HnswLoadNeighbors(hc->element, index, m);
/*
* Could improve performance for vacuuming by checking neighbors
@@ -492,9 +492,8 @@ HnswInsertTuple(Relation index, Datum *values, bool *isnull, ItemPointer heap_ti
FmgrInfo *normprocinfo;
HnswElement entryPoint;
HnswElement element;
- int m = HnswGetM(index);
+ int m;
int efConstruction = HnswGetEfConstruction(index);
- double ml = HnswGetMl(m);
FmgrInfo *procinfo = index_getprocinfo(index, 1, HNSW_DISTANCE_PROC);
Oid collation = index->rd_indcollation[0];
HnswElement dup;
@@ -511,10 +510,6 @@ HnswInsertTuple(Relation index, Datum *values, bool *isnull, ItemPointer heap_ti
return false;
}
- /* Create an element */
- element = HnswInitElement(heap_tid, m, ml, HnswGetMaxLevel(m));
- element->vec = DatumGetVector(value);
-
/*
* Get a shared lock. This allows vacuum to ensure no in-flight inserts
* before repairing graph. Use a page lock so it does not interfere with
@@ -522,8 +517,12 @@ HnswInsertTuple(Relation index, Datum *values, bool *isnull, ItemPointer heap_ti
*/
LockPage(index, HNSW_UPDATE_LOCK, lockmode);
- /* Get entry point */
- entryPoint = HnswGetEntryPoint(index);
+ /* Get m and entry point */
+ HnswGetMetaPageInfo(index, &m, &entryPoint);
+
+ /* Create an element */
+ element = HnswInitElement(heap_tid, m, HnswGetMl(m), HnswGetMaxLevel(m));
+ element->vec = DatumGetVector(value);
/* Prevent concurrent inserts when likely updating entry point */
if (entryPoint == NULL || element->level > entryPoint->level)
diff --git a/src/hnswscan.c b/src/hnswscan.c
index 6190328e..48c53583 100644
--- a/src/hnswscan.c
+++ b/src/hnswscan.c
@@ -19,7 +19,11 @@ GetScanItems(IndexScanDesc scan, Datum q)
Oid collation = so->collation;
List *ep;
List *w;
- HnswElement entryPoint = HnswGetEntryPoint(index);
+ int m;
+ HnswElement entryPoint;
+
+ /* Get m and entry point */
+ HnswGetMetaPageInfo(index, &m, &entryPoint);
if (entryPoint == NULL)
return NIL;
@@ -28,11 +32,11 @@ GetScanItems(IndexScanDesc scan, Datum q)
for (int lc = entryPoint->level; lc >= 1; lc--)
{
- w = HnswSearchLayer(q, ep, 1, lc, index, procinfo, collation, false, NULL);
+ w = HnswSearchLayer(q, ep, 1, lc, index, procinfo, collation, m, false, NULL);
ep = w;
}
- return HnswSearchLayer(q, ep, hnsw_ef_search, 0, index, procinfo, collation, false, NULL);
+ return HnswSearchLayer(q, ep, hnsw_ef_search, 0, index, procinfo, collation, m, false, NULL);
}
/*
diff --git a/src/hnswutils.c b/src/hnswutils.c
index 8e6f2a9c..e7aeb034 100644
--- a/src/hnswutils.c
+++ b/src/hnswutils.c
@@ -210,25 +210,40 @@ HnswInitElementFromBlock(BlockNumber blkno, OffsetNumber offno)
}
/*
- * Get the entry point
+ * Get the metapage info
*/
-HnswElement
-HnswGetEntryPoint(Relation index)
+void
+HnswGetMetaPageInfo(Relation index, int *m, HnswElement * entryPoint)
{
Buffer buf;
Page page;
HnswMetaPage metap;
- HnswElement entryPoint = NULL;
buf = ReadBuffer(index, HNSW_METAPAGE_BLKNO);
LockBuffer(buf, BUFFER_LOCK_SHARE);
page = BufferGetPage(buf);
metap = HnswPageGetMeta(page);
+ if (m != NULL)
+ *m = metap->m;
+
if (BlockNumberIsValid(metap->entryBlkno))
- entryPoint = HnswInitElementFromBlock(metap->entryBlkno, metap->entryOffno);
+ *entryPoint = HnswInitElementFromBlock(metap->entryBlkno, metap->entryOffno);
+ else
+ *entryPoint = NULL;
UnlockReleaseBuffer(buf);
+}
+
+/*
+ * Get the entry point
+ */
+HnswElement
+HnswGetEntryPoint(Relation index)
+{
+ HnswElement entryPoint;
+
+ HnswGetMetaPageInfo(index, NULL, &entryPoint);
return entryPoint;
}
@@ -337,10 +352,9 @@ HnswSetNeighborTuple(HnswNeighborTuple ntup, HnswElement e, int m)
* Load neighbors from page
*/
static void
-LoadNeighborsFromPage(HnswElement element, Relation index, Page page)
+LoadNeighborsFromPage(HnswElement element, Relation index, Page page, int m)
{
HnswNeighborTuple ntup = (HnswNeighborTuple) PageGetItem(page, PageGetItemId(page, element->neighborOffno));
- int m = HnswGetM(index);
int neighborCount = (element->level + 2) * m;
Assert(HnswIsNeighborTuple(ntup));
@@ -381,7 +395,7 @@ LoadNeighborsFromPage(HnswElement element, Relation index, Page page)
* Load neighbors
*/
void
-HnswLoadNeighbors(HnswElement element, Relation index)
+HnswLoadNeighbors(HnswElement element, Relation index, int m)
{
Buffer buf;
Page page;
@@ -390,7 +404,7 @@ HnswLoadNeighbors(HnswElement element, Relation index)
LockBuffer(buf, BUFFER_LOCK_SHARE);
page = BufferGetPage(buf);
- LoadNeighborsFromPage(element, index, page);
+ LoadNeighborsFromPage(element, index, page, m);
UnlockReleaseBuffer(buf);
}
@@ -543,7 +557,7 @@ AddToVisited(HTAB *v, HnswCandidate * hc, Relation index, bool *found)
* Algorithm 2 from paper
*/
List *
-HnswSearchLayer(Datum q, List *ep, int ef, int lc, Relation index, FmgrInfo *procinfo, Oid collation, bool inserting, HnswElement skipElement)
+HnswSearchLayer(Datum q, List *ep, int ef, int lc, Relation index, FmgrInfo *procinfo, Oid collation, int m, bool inserting, HnswElement skipElement)
{
ListCell *lc2;
@@ -598,7 +612,7 @@ HnswSearchLayer(Datum q, List *ep, int ef, int lc, Relation index, FmgrInfo *pro
break;
if (c->element->neighbors == NULL)
- HnswLoadNeighbors(c->element, index);
+ HnswLoadNeighbors(c->element, index, m);
/* Get the neighborhood at layer lc */
neighborhood = &c->element->neighbors[lc];
@@ -956,7 +970,7 @@ HnswInsertElement(HnswElement element, HnswElement entryPoint, Relation index, F
/* 1st phase: greedy search to insert level */
for (int lc = entryLevel; lc >= level + 1; lc--)
{
- w = HnswSearchLayer(q, ep, 1, lc, index, procinfo, collation, true, skipElement);
+ w = HnswSearchLayer(q, ep, 1, lc, index, procinfo, collation, m, true, skipElement);
ep = w;
}
@@ -974,7 +988,7 @@ HnswInsertElement(HnswElement element, HnswElement entryPoint, Relation index, F
List *neighbors;
List *lw;
- w = HnswSearchLayer(q, ep, efConstruction, lc, index, procinfo, collation, true, skipElement);
+ w = HnswSearchLayer(q, ep, efConstruction, lc, index, procinfo, collation, m, true, skipElement);
/* Elements being deleted or skipped can help with search */
/* but should be removed before selecting neighbors */
diff --git a/src/hnswvacuum.c b/src/hnswvacuum.c
index 597fd8ee..f4a5f651 100644
--- a/src/hnswvacuum.c
+++ b/src/hnswvacuum.c
@@ -274,8 +274,8 @@ RepairGraphEntryPoint(HnswVacuumState * vacuumstate)
/* Prevent concurrent inserts when possibly updating entry point */
LockPage(index, HNSW_UPDATE_LOCK, ExclusiveLock);
- /* Get latest entry point */
- entryPoint = HnswGetEntryPoint(index);
+ /* Get m and latest entry point */
+ HnswGetMetaPageInfo(index, &vacuumstate->m, &entryPoint);
if (entryPoint != NULL)
{
@@ -582,7 +582,7 @@ InitVacuumState(HnswVacuumState * vacuumstate, IndexVacuumInfo *info, IndexBulkD
vacuumstate->stats = stats;
vacuumstate->callback = callback;
vacuumstate->callback_state = callback_state;
- vacuumstate->m = HnswGetM(index);
+ vacuumstate->m = 0; /* Get m from metapage later */
vacuumstate->efConstruction = HnswGetEfConstruction(index);
vacuumstate->bas = GetAccessStrategy(BAS_BULKREAD);
vacuumstate->procinfo = index_getprocinfo(index, 1, HNSW_DISTANCE_PROC);
[parent: 4022bb66a0c4]