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

Commit8d26091

Browse files
committed
Change the way the offset of downlink is stored in GISTInsertStack.
GISTInsertStack.childoffnum used to mean "offset of the downlink in thisnode, pointing to the child node in the stack". It's now replaced withdownlinkoffnum, which means "offset of the downlink in the parent of thisnode". gistFindPath() already used childoffnum with this new meaning, andhad an extra step at the end to pull all the childoffnum values down onenode in the stack, to adjust the stack for the meaning that childoffnum hadelsewhere. That's no longer required.The reason to do this now is this new representation is more convenient forthe GiST fast build patch that Alexander Korotkov is working on.While we're at it, replace the linked list used in gistFindPath with astandard List, and make gistFindPath() static.Alexander Korotkov, with some changes by me.
1 parentbc175eb commit8d26091

File tree

2 files changed

+41
-60
lines changed

2 files changed

+41
-60
lines changed

‎src/backend/access/gist/gist.c‎

Lines changed: 39 additions & 53 deletions
Original file line numberDiff line numberDiff line change
@@ -626,6 +626,7 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
626626
firststack.blkno=GIST_ROOT_BLKNO;
627627
firststack.lsn.xrecoff=0;
628628
firststack.parent=NULL;
629+
firststack.downlinkoffnum=InvalidOffsetNumber;
629630
state.stack=stack=&firststack;
630631

631632
/*
@@ -702,9 +703,10 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
702703
BlockNumberchildblkno;
703704
IndexTuplenewtup;
704705
GISTInsertStack*item;
706+
OffsetNumberdownlinkoffnum;
705707

706-
stack->childoffnum=gistchoose(state.r,stack->page,itup,giststate);
707-
iid=PageGetItemId(stack->page,stack->childoffnum);
708+
downlinkoffnum=gistchoose(state.r,stack->page,itup,giststate);
709+
iid=PageGetItemId(stack->page,downlinkoffnum);
708710
idxtuple= (IndexTuple)PageGetItem(stack->page,iid);
709711
childblkno=ItemPointerGetBlockNumber(&(idxtuple->t_tid));
710712

@@ -754,7 +756,7 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
754756
* tuple.
755757
*/
756758
if (gistinserttuples(&state,stack,giststate,&newtup,1,
757-
stack->childoffnum,InvalidBuffer))
759+
downlinkoffnum,InvalidBuffer))
758760
{
759761
/*
760762
* If this was a root split, the root page continues to be
@@ -778,6 +780,7 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
778780
item= (GISTInsertStack*)palloc0(sizeof(GISTInsertStack));
779781
item->blkno=childblkno;
780782
item->parent=stack;
783+
item->downlinkoffnum=downlinkoffnum;
781784
state.stack=stack=item;
782785
}
783786
else
@@ -854,29 +857,37 @@ gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate)
854857
/*
855858
* Traverse the tree to find path from root page to specified "child" block.
856859
*
857-
* returns from the beginning of closest parent;
860+
* returns a new insertion stack, starting from the parent of "child", up
861+
* to the root. *downlinkoffnum is set to the offset of the downlink in the
862+
* direct parent of child.
858863
*
859864
* To prevent deadlocks, this should lock only one page at a time.
860865
*/
861-
GISTInsertStack*
862-
gistFindPath(Relationr,BlockNumberchild)
866+
staticGISTInsertStack*
867+
gistFindPath(Relationr,BlockNumberchild,OffsetNumber*downlinkoffnum)
863868
{
864869
Pagepage;
865870
Bufferbuffer;
866871
OffsetNumberi,
867872
maxoff;
868873
ItemIdiid;
869874
IndexTupleidxtuple;
875+
List*fifo;
870876
GISTInsertStack*top,
871-
*tail,
872877
*ptr;
873878
BlockNumberblkno;
874879

875-
top=tail=(GISTInsertStack*)palloc0(sizeof(GISTInsertStack));
880+
top= (GISTInsertStack*)palloc0(sizeof(GISTInsertStack));
876881
top->blkno=GIST_ROOT_BLKNO;
882+
top->downlinkoffnum=InvalidOffsetNumber;
877883

878-
while (top&&top->blkno!=child)
884+
fifo=list_make1(top);
885+
while (fifo!=NIL)
879886
{
887+
/* Get next page to visit */
888+
top=linitial(fifo);
889+
fifo=list_delete_first(fifo);
890+
880891
buffer=ReadBuffer(r,top->blkno);
881892
LockBuffer(buffer,GIST_SHARE);
882893
gistcheckpage(r,buffer);
@@ -917,12 +928,10 @@ gistFindPath(Relation r, BlockNumber child)
917928
*/
918929
ptr= (GISTInsertStack*)palloc0(sizeof(GISTInsertStack));
919930
ptr->blkno=GistPageGetOpaque(page)->rightlink;
920-
ptr->childoffnum=InvalidOffsetNumber;
931+
ptr->downlinkoffnum=InvalidOffsetNumber;
921932
ptr->parent=top->parent;
922-
ptr->next=top->next;
923-
top->next=ptr;
924-
if (tail==top)
925-
tail=ptr;
933+
934+
fifo=lcons(ptr,fifo);
926935
}
927936

928937
maxoff=PageGetMaxOffsetNumber(page);
@@ -934,48 +943,24 @@ gistFindPath(Relation r, BlockNumber child)
934943
blkno=ItemPointerGetBlockNumber(&(idxtuple->t_tid));
935944
if (blkno==child)
936945
{
937-
OffsetNumberpoff=InvalidOffsetNumber;
938-
939-
/* make childs links */
940-
ptr=top;
941-
while (ptr->parent)
942-
{
943-
/* move childoffnum.. */
944-
if (ptr==top)
945-
{
946-
/* first iteration */
947-
poff=ptr->parent->childoffnum;
948-
ptr->parent->childoffnum=ptr->childoffnum;
949-
}
950-
else
951-
{
952-
OffsetNumbertmp=ptr->parent->childoffnum;
953-
954-
ptr->parent->childoffnum=poff;
955-
poff=tmp;
956-
}
957-
ptr=ptr->parent;
958-
}
959-
top->childoffnum=i;
946+
/* Found it! */
960947
UnlockReleaseBuffer(buffer);
948+
*downlinkoffnum=i;
961949
returntop;
962950
}
963951
else
964952
{
965-
/*Install next inner pageto theend ofstack */
953+
/*Append this childto thelist ofpages to visit later */
966954
ptr= (GISTInsertStack*)palloc0(sizeof(GISTInsertStack));
967955
ptr->blkno=blkno;
968-
ptr->childoffnum=i;/* set offsetnumber of child to child
969-
* !!! */
956+
ptr->downlinkoffnum=i;
970957
ptr->parent=top;
971-
ptr->next=NULL;
972-
tail->next=ptr;
973-
tail=ptr;
958+
959+
fifo=lappend(fifo,ptr);
974960
}
975961
}
976962

977963
UnlockReleaseBuffer(buffer);
978-
top=top->next;
979964
}
980965

981966
elog(ERROR,"failed to re-find parent of a page in index \"%s\", block %u",
@@ -997,7 +982,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
997982
parent->page= (Page)BufferGetPage(parent->buffer);
998983

999984
/* here we don't need to distinguish between split and page update */
1000-
if (parent->childoffnum==InvalidOffsetNumber|| !XLByteEQ(parent->lsn,PageGetLSN(parent->page)))
985+
if (child->downlinkoffnum==InvalidOffsetNumber|| !XLByteEQ(parent->lsn,PageGetLSN(parent->page)))
1001986
{
1002987
/* parent is changed, look child in right links until found */
1003988
OffsetNumberi,
@@ -1016,20 +1001,21 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
10161001
if (ItemPointerGetBlockNumber(&(idxtuple->t_tid))==child->blkno)
10171002
{
10181003
/* yes!!, found */
1019-
parent->childoffnum=i;
1004+
child->downlinkoffnum=i;
10201005
return;
10211006
}
10221007
}
10231008

10241009
parent->blkno=GistPageGetOpaque(parent->page)->rightlink;
10251010
UnlockReleaseBuffer(parent->buffer);
10261011
if (parent->blkno==InvalidBlockNumber)
1027-
1012+
{
10281013
/*
1029-
*end of chain and still didn'tfound parent, It's very-very
1030-
* rare situation when root splited
1014+
*End of chain and still didn'tfind parent. It's a very-very
1015+
* rare situation when root splited.
10311016
*/
10321017
break;
1018+
}
10331019
parent->buffer=ReadBuffer(r,parent->blkno);
10341020
LockBuffer(parent->buffer,GIST_EXCLUSIVE);
10351021
gistcheckpage(r,parent->buffer);
@@ -1050,7 +1036,7 @@ gistFindCorrectParent(Relation r, GISTInsertStack *child)
10501036
}
10511037

10521038
/* ok, find new path */
1053-
ptr=parent=gistFindPath(r,child->blkno);
1039+
ptr=parent=gistFindPath(r,child->blkno,&child->downlinkoffnum);
10541040

10551041
/* read all buffers as expected by caller */
10561042
/* note we don't lock them or gistcheckpage them here! */
@@ -1119,7 +1105,7 @@ gistformdownlink(Relation rel, Buffer buf, GISTSTATE *giststate,
11191105

11201106
LockBuffer(stack->parent->buffer,GIST_EXCLUSIVE);
11211107
gistFindCorrectParent(rel,stack);
1122-
iid=PageGetItemId(stack->parent->page,stack->parent->childoffnum);
1108+
iid=PageGetItemId(stack->parent->page,stack->downlinkoffnum);
11231109
downlink= (IndexTuple)PageGetItem(stack->parent->page,iid);
11241110
downlink=CopyIndexTuple(downlink);
11251111
LockBuffer(stack->parent->buffer,GIST_UNLOCK);
@@ -1147,7 +1133,7 @@ gistfixsplit(GISTInsertState *state, GISTSTATE *giststate)
11471133
RelationGetRelationName(state->r),stack->blkno);
11481134

11491135
Assert(GistFollowRight(stack->page));
1150-
Assert(OffsetNumberIsValid(stack->parent->childoffnum));
1136+
Assert(OffsetNumberIsValid(stack->downlinkoffnum));
11511137

11521138
buf=stack->buffer;
11531139

@@ -1284,7 +1270,7 @@ gistfinishsplit(GISTInsertState *state, GISTInsertStack *stack,
12841270
tuples[1]=right->downlink;
12851271
gistinserttuples(state,stack->parent,giststate,
12861272
tuples,2,
1287-
stack->parent->childoffnum,
1273+
stack->downlinkoffnum,
12881274
left->buf);
12891275
LockBuffer(stack->parent->buffer,GIST_UNLOCK);
12901276
UnlockReleaseBuffer(right->buf);

‎src/include/access/gist_private.h‎

Lines changed: 2 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -218,14 +218,11 @@ typedef struct GISTInsertStack
218218
*/
219219
GistNSNlsn;
220220

221-
/*child'soffset */
222-
OffsetNumberchildoffnum;
221+
/* offset of the downlink in the parent page, that points to this page */
222+
OffsetNumberdownlinkoffnum;
223223

224224
/* pointer to parent */
225225
structGISTInsertStack*parent;
226-
227-
/* for gistFindPath */
228-
structGISTInsertStack*next;
229226
}GISTInsertStack;
230227

231228
typedefstructGistSplitVector
@@ -293,8 +290,6 @@ extern void freeGISTstate(GISTSTATE *giststate);
293290
externSplitedPageLayout*gistSplit(Relationr,Pagepage,IndexTuple*itup,
294291
intlen,GISTSTATE*giststate);
295292

296-
externGISTInsertStack*gistFindPath(Relationr,BlockNumberchild);
297-
298293
/* gistxlog.c */
299294
externvoidgist_redo(XLogRecPtrlsn,XLogRecord*record);
300295
externvoidgist_desc(StringInfobuf,uint8xl_info,char*rec);

0 commit comments

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