Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit5c9429a

Browse files
committed
Reduced memory usage for HNSW index scans
1 parent4b44d6e commit5c9429a

File tree

1 file changed

+43
-12
lines changed

1 file changed

+43
-12
lines changed

‎src/hnswutils.c‎

Lines changed: 43 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -112,6 +112,12 @@ typedef union
112112
tidhash_hash*tids;
113113
}visited_hash;
114114

115+
typedefunion
116+
{
117+
HnswElementelement;
118+
ItemPointerDataindextid;
119+
}HnswUnvisited;
120+
115121
/*
116122
* Get the max number of connections in an upper layer for each element in the index
117123
*/
@@ -547,19 +553,19 @@ HnswLoadElementFromTuple(HnswElement element, HnswElementTuple etup, bool loadHe
547553
/*
548554
* Load an element and optionally get its distance from q
549555
*/
550-
void
551-
HnswLoadElement(HnswElementelement,float*distance,Datum*q,Relationindex,FmgrInfo*procinfo,Oidcollation,boolloadVec,float*maxDistance)
556+
staticvoid
557+
HnswLoadElementImpl(BlockNumberblkno,OffsetNumberoffno,float*distance,Datum*q,Relationindex,FmgrInfo*procinfo,Oidcollation,boolloadVec,float*maxDistance,HnswElement*element)
552558
{
553559
Bufferbuf;
554560
Pagepage;
555561
HnswElementTupleetup;
556562

557563
/* Read vector */
558-
buf=ReadBuffer(index,element->blkno);
564+
buf=ReadBuffer(index,blkno);
559565
LockBuffer(buf,BUFFER_LOCK_SHARE);
560566
page=BufferGetPage(buf);
561567

562-
etup= (HnswElementTuple)PageGetItem(page,PageGetItemId(page,element->offno));
568+
etup= (HnswElementTuple)PageGetItem(page,PageGetItemId(page,offno));
563569

564570
Assert(HnswIsElementTuple(etup));
565571

@@ -574,11 +580,25 @@ HnswLoadElement(HnswElement element, float *distance, Datum *q, Relation index,
574580

575581
/* Load element */
576582
if (distance==NULL||maxDistance==NULL||*distance<*maxDistance)
577-
HnswLoadElementFromTuple(element,etup, true,loadVec);
583+
{
584+
if (*element==NULL)
585+
*element=HnswInitElementFromBlock(blkno,offno);
586+
587+
HnswLoadElementFromTuple(*element,etup, true,loadVec);
588+
}
578589

579590
UnlockReleaseBuffer(buf);
580591
}
581592

593+
/*
594+
* Load an element and optionally get its distance from q
595+
*/
596+
void
597+
HnswLoadElement(HnswElementelement,float*distance,Datum*q,Relationindex,FmgrInfo*procinfo,Oidcollation,boolloadVec,float*maxDistance)
598+
{
599+
HnswLoadElementImpl(element->blkno,element->offno,distance,q,index,procinfo,collation,loadVec,maxDistance,&element);
600+
}
601+
582602
/*
583603
* Get the distance for an element
584604
*/
@@ -720,7 +740,7 @@ CountElement(char *base, HnswElement skipElement, HnswElement e)
720740
* Load unvisited neighbors from memory
721741
*/
722742
staticvoid
723-
HnswLoadUnvisitedFromMemory(char*base,HnswElementelement,HnswElement*unvisited,int*unvisitedLength,visited_hash*v,intlc,HnswNeighborArray*neighborhoodData,SizeneighborhoodSize)
743+
HnswLoadUnvisitedFromMemory(char*base,HnswElementelement,HnswUnvisited*unvisited,int*unvisitedLength,visited_hash*v,intlc,HnswNeighborArray*neighborhoodData,SizeneighborhoodSize)
724744
{
725745
/* Get the neighborhood at layer lc */
726746
HnswNeighborArray*neighborhood=HnswGetNeighbors(base,element,lc);
@@ -741,15 +761,15 @@ HnswLoadUnvisitedFromMemory(char *base, HnswElement element, HnswElement * unvis
741761
AddToVisited(base,v,hc->element,NULL,&found);
742762

743763
if (!found)
744-
unvisited[(*unvisitedLength)++]=HnswPtrAccess(base,hc->element);
764+
unvisited[(*unvisitedLength)++].element=HnswPtrAccess(base,hc->element);
745765
}
746766
}
747767

748768
/*
749769
* Load unvisited neighbors from disk
750770
*/
751771
staticvoid
752-
HnswLoadUnvisitedFromDisk(HnswElementelement,HnswElement*unvisited,int*unvisitedLength,visited_hash*v,Relationindex,intm,intlm,intlc)
772+
HnswLoadUnvisitedFromDisk(HnswElementelement,HnswUnvisited*unvisited,int*unvisitedLength,visited_hash*v,Relationindex,intm,intlm,intlc)
753773
{
754774
Bufferbuf;
755775
Pagepage;
@@ -782,7 +802,7 @@ HnswLoadUnvisitedFromDisk(HnswElement element, HnswElement * unvisited, int *unv
782802
tidhash_insert(v->tids,*indextid,&found);
783803

784804
if (!found)
785-
unvisited[(*unvisitedLength)++]=HnswInitElementFromBlock(ItemPointerGetBlockNumber(indextid),ItemPointerGetOffsetNumber(indextid));
805+
unvisited[(*unvisitedLength)++].indextid=*indextid;
786806
}
787807
}
788808

@@ -801,7 +821,7 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
801821
HnswNeighborArray*neighborhoodData=NULL;
802822
SizeneighborhoodSize=0;
803823
intlm=HnswGetLayerM(m,lc);
804-
HnswElement*unvisited=palloc(lm*sizeof(HnswElement));
824+
HnswUnvisited*unvisited=palloc(lm*sizeof(HnswUnvisited));
805825
intunvisitedLength;
806826

807827
InitVisited(base,&v,index,ef,m);
@@ -853,16 +873,27 @@ HnswSearchLayer(char *base, Datum q, List *ep, int ef, int lc, Relation index, F
853873

854874
for (inti=0;i<unvisitedLength;i++)
855875
{
856-
HnswElementeElement=unvisited[i];
876+
HnswElementeElement;
857877
floateDistance;
858878
boolalwaysAdd=wlen<ef;
859879

860880
f=HnswGetPairingHeapCandidate(w_node,pairingheap_first(W));
861881

862882
if (index==NULL)
883+
{
884+
eElement=unvisited[i].element;
863885
eDistance=GetElementDistance(base,eElement,q,procinfo,collation);
886+
}
864887
else
865-
HnswLoadElement(eElement,&eDistance,&q,index,procinfo,collation,inserting,alwaysAdd ?NULL :&f->distance);
888+
{
889+
ItemPointerindextid=&unvisited[i].indextid;
890+
BlockNumberblkno=ItemPointerGetBlockNumber(indextid);
891+
OffsetNumberoffno=ItemPointerGetOffsetNumber(indextid);
892+
893+
/* Avoid any allocations if not adding */
894+
eElement=NULL;
895+
HnswLoadElementImpl(blkno,offno,&eDistance,&q,index,procinfo,collation,inserting,alwaysAdd ?NULL :&f->distance,&eElement);
896+
}
866897

867898
if (eDistance<f->distance||alwaysAdd)
868899
{

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp