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

Commitb065499

Browse files
committed
implement direction scan for posting tree (tree only)
1 parentd0e1e86 commitb065499

File tree

7 files changed

+108
-51
lines changed

7 files changed

+108
-51
lines changed

‎rum.h

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -120,6 +120,7 @@ typedef struct RumMetaPageData
120120
#defineRumPageSetNonDeleted(page) ( RumPageGetOpaque(page)->flags &= ~RUM_DELETED)
121121

122122
#defineRumPageRightMost(page) ( RumPageGetOpaque(page)->rightlink == InvalidBlockNumber)
123+
#defineRumPageLeftMost(page) ( RumPageGetOpaque(page)->leftlink == InvalidBlockNumber)
123124

124125
/*
125126
* We use our own ItemPointerGet(BlockNumber|GetOffsetNumber)
@@ -463,9 +464,10 @@ typedef struct RumBtreeData
463464
boolsearchMode;
464465

465466
Relationindex;
466-
RumState*rumstate;/* not valid in a data scan */
467+
RumState*rumstate;
467468
boolfullScan;
468469
boolisBuild;
470+
ScanDirectionscanDirection;
469471

470472
BlockNumberrightblkno;
471473

@@ -489,7 +491,8 @@ typedef struct RumBtreeData
489491
externRumBtreeStack*rumPrepareFindLeafPage(RumBtreebtree,BlockNumberblkno);
490492
externRumBtreeStack*rumFindLeafPage(RumBtreebtree,RumBtreeStack*stack);
491493
externRumBtreeStack*rumReFindLeafPage(RumBtreebtree,RumBtreeStack*stack);
492-
externBufferrumStepRight(Bufferbuffer,Relationindex,intlockmode);
494+
externBufferrumStep(Bufferbuffer,Relationindex,intlockmode,
495+
ScanDirectionscanDirection);
493496
externvoidfreeRumBtreeStack(RumBtreeStack*stack);
494497
externvoidrumInsertValue(Relationindex,RumBtreebtree,RumBtreeStack*stack,
495498
GinStatsData*buildStats);
@@ -532,7 +535,9 @@ typedef struct
532535
}RumPostingTreeScan;
533536

534537
externRumPostingTreeScan*rumPrepareScanPostingTree(Relationindex,
535-
BlockNumberrootBlkno,boolsearchMode,OffsetNumberattnum,RumState*rumstate);
538+
BlockNumberrootBlkno,boolsearchMode,
539+
ScanDirectionscanDirection,
540+
OffsetNumberattnum,RumState*rumstate);
536541
externvoidrumInsertItemPointers(RumState*rumstate,
537542
OffsetNumberattnum,
538543
RumPostingTreeScan*gdi,

‎rumbtree.c

Lines changed: 22 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -157,7 +157,8 @@ rumFindLeafPage(RumBtree btree, RumBtreeStack * stack)
157157
/* rightmost page */
158158
break;
159159

160-
stack->buffer=rumStepRight(stack->buffer,btree->index,access);
160+
stack->buffer=rumStep(stack->buffer,btree->index,access,
161+
ForwardScanDirection);
161162
stack->blkno=rightlink;
162163
page=BufferGetPage(stack->buffer);
163164
}
@@ -200,20 +201,31 @@ rumFindLeafPage(RumBtree btree, RumBtreeStack * stack)
200201
}
201202

202203
/*
203-
* Steprightfrom current page.
204+
* Step from current page.
204205
*
205206
* The next page is locked first, before releasing the current page. This is
206207
* crucial to protect from concurrent page deletion (see comment in
207208
* rumDeletePage).
208209
*/
209210
Buffer
210-
rumStepRight(Bufferbuffer,Relationindex,intlockmode)
211+
rumStep(Bufferbuffer,Relationindex,intlockmode,
212+
ScanDirectionscanDirection)
211213
{
212214
Buffernextbuffer;
213215
Pagepage=BufferGetPage(buffer);
214216
boolisLeaf=RumPageIsLeaf(page);
215217
boolisData=RumPageIsData(page);
216-
BlockNumberblkno=RumPageGetOpaque(page)->rightlink;
218+
BlockNumberblkno;
219+
220+
blkno= (ScanDirectionIsForward(scanDirection)) ?
221+
RumPageGetOpaque(page)->rightlink :
222+
RumPageGetOpaque(page)->leftlink;
223+
224+
if (blkno==InvalidBlockNumber)
225+
{
226+
UnlockReleaseBuffer(buffer);
227+
returnInvalidBuffer;
228+
}
217229

218230
nextbuffer=ReadBuffer(index,blkno);
219231
LockBuffer(nextbuffer,lockmode);
@@ -229,7 +241,8 @@ rumStepRight(Buffer buffer, Relation index, int lockmode)
229241
* page.
230242
*/
231243
if (RumPageIsDeleted(page))
232-
elog(ERROR,"right sibling of RUM page was deleted");
244+
elog(ERROR,"%s sibling of RUM page was deleted",
245+
ScanDirectionIsForward(scanDirection) ?"right" :"left");
233246

234247
returnnextbuffer;
235248
}
@@ -326,7 +339,8 @@ rumFindParents(RumBtree btree, RumBtreeStack * stack,
326339
UnlockReleaseBuffer(buffer);
327340
break;
328341
}
329-
buffer=rumStepRight(buffer,btree->index,RUM_EXCLUSIVE);
342+
buffer=rumStep(buffer,btree->index,RUM_EXCLUSIVE,
343+
ForwardScanDirection);
330344
page=BufferGetPage(buffer);
331345
}
332346

@@ -520,7 +534,8 @@ rumInsertValue(Relation index, RumBtree btree, RumBtreeStack * stack,
520534
break;
521535
}
522536

523-
parent->buffer=rumStepRight(parent->buffer,btree->index,RUM_EXCLUSIVE);
537+
parent->buffer=rumStep(parent->buffer,btree->index,
538+
RUM_EXCLUSIVE,ForwardScanDirection);
524539
parent->blkno=rightlink;
525540
page=BufferGetPage(parent->buffer);
526541
}

‎rumdatapage.c

Lines changed: 25 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,9 @@
1515

1616
#include"rum.h"
1717

18+
staticBlockNumberdataGetLeftMostPage(RumBtreebtree,Pagepage);
19+
staticBlockNumberdataGetRightMostPage(RumBtreebtree,Pagepage);
20+
1821
/* Does datatype allow packing into the 1-byte-header varlena format? */
1922
#defineTYPE_IS_PACKABLE(typlen,typstorage) \
2023
((typlen) == -1 && (typstorage) != 'p')
@@ -441,7 +444,10 @@ dataLocateItem(RumBtree btree, RumBtreeStack * stack)
441444
{
442445
stack->off=FirstOffsetNumber;
443446
stack->predictNumber *=RumPageGetOpaque(page)->maxoff;
444-
returnbtree->getLeftMostPage(btree,page);
447+
if (ScanDirectionIsForward(btree->scanDirection))
448+
returndataGetLeftMostPage(btree,page);
449+
else
450+
returndataGetRightMostPage(btree,page);
445451
}
446452

447453
low=FirstOffsetNumber;
@@ -690,6 +696,20 @@ dataGetLeftMostPage(RumBtree btree, Page page)
690696
returnPostingItemGetBlockNumber(pitem);
691697
}
692698

699+
staticBlockNumber
700+
dataGetRightMostPage(RumBtreebtree,Pagepage)
701+
{
702+
PostingItem*pitem;
703+
704+
Assert(!RumPageIsLeaf(page));
705+
Assert(RumPageIsData(page));
706+
Assert(RumPageGetOpaque(page)->maxoff >=FirstOffsetNumber);
707+
708+
pitem= (PostingItem*)
709+
RumDataPageGetItem(page,RumPageGetOpaque(page)->maxoff);
710+
returnPostingItemGetBlockNumber(pitem);
711+
}
712+
693713
/*
694714
* add ItemPointer or PostingItem to page. data should point to
695715
* correct value! depending on leaf or non-leaf page
@@ -1445,20 +1465,23 @@ rumPrepareDataScan(RumBtree btree, Relation index, OffsetNumber attnum, RumState
14451465
btree->isDelete= FALSE;
14461466
btree->fullScan= FALSE;
14471467
btree->isBuild= FALSE;
1468+
btree->scanDirection=ForwardScanDirection;
14481469

14491470
btree->entryAttnum=attnum;
14501471
}
14511472

14521473
RumPostingTreeScan*
14531474
rumPrepareScanPostingTree(Relationindex,BlockNumberrootBlkno,
1454-
boolsearchMode,OffsetNumberattnum,RumState*rumstate)
1475+
boolsearchMode,ScanDirectionscanDirection,
1476+
OffsetNumberattnum,RumState*rumstate)
14551477
{
14561478
RumPostingTreeScan*gdi= (RumPostingTreeScan*)palloc0(sizeof(RumPostingTreeScan));
14571479

14581480
rumPrepareDataScan(&gdi->btree,index,attnum,rumstate);
14591481

14601482
gdi->btree.searchMode=searchMode;
14611483
gdi->btree.fullScan=searchMode;
1484+
gdi->btree.scanDirection=scanDirection;
14621485

14631486
gdi->stack=rumPrepareFindLeafPage(&gdi->btree,rootBlkno);
14641487

‎rumget.c

Lines changed: 39 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -120,8 +120,8 @@ callConsistentFn(RumState * rumstate, RumScanKey key)
120120
*/
121121
staticbool
122122
findItemInPostingPage(Pagepage,RumKey*item,OffsetNumber*off,
123-
OffsetNumberattno,
124-
OffsetNumberattnum,RumState*rumstate)
123+
OffsetNumberattno,OffsetNumberattnum,
124+
ScanDirectionscanDirection,RumState*rumstate)
125125
{
126126
OffsetNumbermaxoff=RumPageGetOpaque(page)->maxoff;
127127
intres;
@@ -144,8 +144,17 @@ findItemInPostingPage(Page page, RumKey*item, OffsetNumber *off,
144144
ptr=rumDataPageLeafRead(ptr,attnum,&iter_item,rumstate);
145145
res=compareRumKey(rumstate,attno,item,&iter_item);
146146

147-
if (res <=0)
147+
if (res==0)
148+
{
149+
return true;
150+
}
151+
elseif (res<0)
152+
{
153+
if (ScanDirectionIsBackward(scanDirection)&&
154+
*off>FirstOffsetNumber)
155+
(*off)--;
148156
return true;
157+
}
149158
}
150159

151160
return false;
@@ -167,7 +176,8 @@ moveRightIfItNeeded(RumBtreeData * btree, RumBtreeStack * stack)
167176
if (RumPageRightMost(page))
168177
return false;/* no more pages */
169178

170-
stack->buffer=rumStepRight(stack->buffer,btree->index,RUM_SHARE);
179+
stack->buffer=rumStep(stack->buffer,btree->index,RUM_SHARE,
180+
ForwardScanDirection);
171181
stack->blkno=BufferGetBlockNumber(stack->buffer);
172182
stack->off=FirstOffsetNumber;
173183
}
@@ -187,8 +197,10 @@ scanPostingTree(Relation index, RumScanEntry scanEntry,
187197
Bufferbuffer;
188198
Pagepage;
189199

200+
Assert(ScanDirectionIsForward(scanEntry->scanDirection));
190201
/* Descend to the leftmost leaf page */
191-
gdi=rumPrepareScanPostingTree(index,rootPostingTree, TRUE,attnum,rumstate);
202+
gdi=rumPrepareScanPostingTree(index,rootPostingTree, TRUE,
203+
ForwardScanDirection,attnum,rumstate);
192204

193205
buffer=rumScanBeginPostingTree(gdi,NULL);
194206
IncrBufferRefCount(buffer);/* prevent unpin in freeRumBtreeStack */
@@ -228,7 +240,7 @@ scanPostingTree(Relation index, RumScanEntry scanEntry,
228240
if (RumPageRightMost(page))
229241
break;/* no more pages */
230242

231-
buffer=rumStepRight(buffer,index,RUM_SHARE);
243+
buffer=rumStep(buffer,index,RUM_SHARE,ForwardScanDirection);
232244
}
233245

234246
UnlockReleaseBuffer(buffer);
@@ -564,14 +576,15 @@ startScanEntry(RumState * rumstate, RumScanEntry entry)
564576
*/
565577
LockBuffer(stackEntry->buffer,RUM_UNLOCK);
566578
needUnlock= FALSE;
567-
gdi=rumPrepareScanPostingTree(rumstate->index,rootPostingTree, TRUE,entry->attnum,rumstate);
579+
gdi=rumPrepareScanPostingTree(rumstate->index,rootPostingTree, TRUE,
580+
entry->scanDirection,entry->attnum,rumstate);
568581

569582
entry->buffer=rumScanBeginPostingTree(gdi,entry->useMarkAddInfo ?
570583
&entry->markAddInfo :NULL);
571584

572585
entry->gdi=gdi;
573586
entry->context=AllocSetContextCreate(CurrentMemoryContext,
574-
"GiST temporary context",
587+
"RUM entry temporary context",
575588
ALLOCSET_DEFAULT_MINSIZE,
576589
ALLOCSET_DEFAULT_INITSIZE,
577590
ALLOCSET_DEFAULT_MAXSIZE);
@@ -801,7 +814,11 @@ entryGetNextItem(RumState * rumstate, RumScanEntry entry)
801814
* It's needed to go by right link. During that we should refind
802815
* first ItemPointer greater that stored
803816
*/
804-
if (RumPageRightMost(page))
817+
if ((ScanDirectionIsForward(entry->scanDirection)&&RumPageRightMost(page))
818+
||
819+
(ScanDirectionIsBackward(entry->scanDirection)&&RumPageLeftMost(page)))
820+
821+
805822
{
806823
UnlockReleaseBuffer(entry->buffer);
807824
ItemPointerSetInvalid(&entry->curRumKey.iptr);
@@ -812,17 +829,17 @@ entryGetNextItem(RumState * rumstate, RumScanEntry entry)
812829
return;
813830
}
814831

815-
entry->buffer=rumStepRight(entry->buffer,
816-
rumstate->index,
817-
RUM_SHARE);
832+
entry->buffer=rumStep(entry->buffer,rumstate->index,
833+
RUM_SHARE,entry->scanDirection);
818834
entry->gdi->stack->buffer=entry->buffer;
819835
entry->gdi->stack->blkno=BufferGetBlockNumber(entry->buffer);
820836
page=BufferGetPage(entry->buffer);
821837

822838
entry->offset=InvalidOffsetNumber;
823839
if (!ItemPointerIsValid(&entry->curRumKey.iptr)||
824840
findItemInPostingPage(page,&entry->curRumKey,&entry->offset,
825-
entry->attnumOrig,entry->attnum,rumstate))
841+
entry->attnumOrig,entry->attnum,
842+
entry->scanDirection,rumstate))
826843
{
827844
OffsetNumbermaxoff,
828845
i;
@@ -960,12 +977,13 @@ entryGetNextItemList(RumState * rumstate, RumScanEntry entry)
960977
LockBuffer(entry->stack->buffer,RUM_UNLOCK);
961978
needUnlock= false;
962979
gdi=rumPrepareScanPostingTree(rumstate->index,
963-
rootPostingTree, TRUE,entry->attnumOrig,rumstate);
980+
rootPostingTree, TRUE,entry->scanDirection,
981+
entry->attnumOrig,rumstate);
964982

965983
entry->buffer=rumScanBeginPostingTree(gdi,NULL);
966984
entry->gdi=gdi;
967985
entry->context=AllocSetContextCreate(CurrentMemoryContext,
968-
"GiST temporary context",
986+
"RUM entry temporary context",
969987
ALLOCSET_DEFAULT_MINSIZE,
970988
ALLOCSET_DEFAULT_INITSIZE,
971989
ALLOCSET_DEFAULT_MAXSIZE);
@@ -1652,34 +1670,21 @@ entryFindItem(RumState * rumstate, RumScanEntry entry, RumKey * item)
16521670
return;
16531671
}
16541672

1655-
/* At last try to traverse byright links */
1673+
/* At last try to traverse bydirection */
16561674
for (;;)
16571675
{
1658-
/*
1659-
* It's needed to go by right link. During that we should refind first
1660-
* ItemPointer greater that stored
1661-
*/
1662-
BlockNumberblkno;
1663-
1664-
blkno=RumPageGetOpaque(page)->rightlink;
1676+
entry->buffer=rumStep(entry->buffer,rumstate->index,
1677+
RUM_SHARE,entry->scanDirection);
1678+
entry->gdi->stack->buffer=entry->buffer;
16651679

1666-
LockBuffer(entry->buffer,RUM_UNLOCK);
1667-
if (blkno==InvalidBlockNumber)
1680+
if (entry->buffer==InvalidBuffer)
16681681
{
1669-
ReleaseBuffer(entry->buffer);
16701682
ItemPointerSetInvalid(&entry->curRumKey.iptr);
1671-
entry->buffer=InvalidBuffer;
1672-
entry->gdi->stack->buffer=InvalidBuffer;
16731683
entry->isFinished= TRUE;
16741684
return;
16751685
}
16761686

1677-
entry->buffer=ReleaseAndReadBuffer(entry->buffer,
1678-
rumstate->index,
1679-
blkno);
1680-
entry->gdi->stack->buffer=entry->buffer;
1681-
entry->gdi->stack->blkno=blkno;
1682-
LockBuffer(entry->buffer,RUM_SHARE);
1687+
entry->gdi->stack->blkno=BufferGetBlockNumber(entry->buffer);
16831688
page=BufferGetPage(entry->buffer);
16841689

16851690
if (scanPage(rumstate,entry,item,

‎ruminsert.c

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -284,7 +284,8 @@ addItemPointersToLeafTuple(RumState * rumstate,
284284
buildStats->nDataPages++;
285285

286286
/* Now insert the TIDs-to-be-added into the posting tree */
287-
gdi=rumPrepareScanPostingTree(rumstate->index,postingRoot, FALSE,attnum,rumstate);
287+
gdi=rumPrepareScanPostingTree(rumstate->index,postingRoot, FALSE,
288+
ForwardScanDirection,attnum,rumstate);
288289
gdi->btree.isBuild= (buildStats!=NULL);
289290

290291
rumInsertItemPointers(rumstate,attnum,gdi,items,nitem,buildStats);
@@ -364,6 +365,7 @@ buildFreshLeafTuple(RumState * rumstate,
364365
RumPostingTreeScan*gdi;
365366

366367
gdi=rumPrepareScanPostingTree(rumstate->index,postingRoot, FALSE,
368+
ForwardScanDirection,
367369
attnum,rumstate);
368370
gdi->btree.isBuild= (buildStats!=NULL);
369371

@@ -428,7 +430,8 @@ rumEntryInsert(RumState * rumstate,
428430

429431
/* insert into posting tree */
430432
gdi=rumPrepareScanPostingTree(rumstate->index,rootPostingTree,
431-
FALSE,attnum,rumstate);
433+
FALSE,ForwardScanDirection,
434+
attnum,rumstate);
432435
gdi->btree.isBuild= (buildStats!=NULL);
433436
rumInsertItemPointers(rumstate,attnum,gdi,items,
434437
nitem,buildStats);

0 commit comments

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