Skip to content

Commit b065499

Browse files
feodorfeodor
committed
implement direction scan for posting tree (tree only)
1 parent d0e1e86 commit b065499

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
#define RumPageSetNonDeleted(page) ( RumPageGetOpaque(page)->flags &= ~RUM_DELETED)
121121

122122
#define RumPageRightMost(page) ( RumPageGetOpaque(page)->rightlink == InvalidBlockNumber)
123+
#define RumPageLeftMost(page) ( RumPageGetOpaque(page)->leftlink == InvalidBlockNumber)
123124

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

465466
Relation index;
466-
RumState *rumstate; /* not valid in a data scan */
467+
RumState *rumstate;
467468
bool fullScan;
468469
bool isBuild;
470+
ScanDirection scanDirection;
469471

470472
BlockNumber rightblkno;
471473

@@ -489,7 +491,8 @@ typedef struct RumBtreeData
489491
extern RumBtreeStack *rumPrepareFindLeafPage(RumBtree btree, BlockNumber blkno);
490492
extern RumBtreeStack *rumFindLeafPage(RumBtree btree, RumBtreeStack * stack);
491493
extern RumBtreeStack *rumReFindLeafPage(RumBtree btree, RumBtreeStack * stack);
492-
extern Buffer rumStepRight(Buffer buffer, Relation index, int lockmode);
494+
extern Buffer rumStep(Buffer buffer, Relation index, int lockmode,
495+
ScanDirection scanDirection);
493496
extern void freeRumBtreeStack(RumBtreeStack * stack);
494497
extern void rumInsertValue(Relation index, RumBtree btree, RumBtreeStack * stack,
495498
GinStatsData *buildStats);
@@ -532,7 +535,9 @@ typedef struct
532535
} RumPostingTreeScan;
533536

534537
extern RumPostingTreeScan *rumPrepareScanPostingTree(Relation index,
535-
BlockNumber rootBlkno, bool searchMode, OffsetNumber attnum, RumState * rumstate);
538+
BlockNumber rootBlkno, bool searchMode,
539+
ScanDirection scanDirection,
540+
OffsetNumber attnum, RumState * rumstate);
536541
extern void rumInsertItemPointers(RumState * rumstate,
537542
OffsetNumber attnum,
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-
* Step right from 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(Buffer buffer, Relation index, int lockmode)
211+
rumStep(Buffer buffer, Relation index, int lockmode,
212+
ScanDirection scanDirection)
211213
{
212214
Buffer nextbuffer;
213215
Page page = BufferGetPage(buffer);
214216
bool isLeaf = RumPageIsLeaf(page);
215217
bool isData = RumPageIsData(page);
216-
BlockNumber blkno = RumPageGetOpaque(page)->rightlink;
218+
BlockNumber blkno;
219+
220+
blkno = (ScanDirectionIsForward(scanDirection)) ?
221+
RumPageGetOpaque(page)->rightlink :
222+
RumPageGetOpaque(page)->leftlink;
223+
224+
if (blkno == InvalidBlockNumber)
225+
{
226+
UnlockReleaseBuffer(buffer);
227+
return InvalidBuffer;
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
return nextbuffer;
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+
static BlockNumber dataGetLeftMostPage(RumBtree btree, Page page);
19+
static BlockNumber dataGetRightMostPage(RumBtree btree, Page page);
20+
1821
/* Does datatype allow packing into the 1-byte-header varlena format? */
1922
#define TYPE_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-
return btree->getLeftMostPage(btree, page);
447+
if (ScanDirectionIsForward(btree->scanDirection))
448+
return dataGetLeftMostPage(btree, page);
449+
else
450+
return dataGetRightMostPage(btree, page);
445451
}
446452

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

699+
static BlockNumber
700+
dataGetRightMostPage(RumBtree btree, Page page)
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+
return PostingItemGetBlockNumber(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(Relation index, BlockNumber rootBlkno,
1454-
bool searchMode, OffsetNumber attnum, RumState * rumstate)
1475+
bool searchMode, ScanDirection scanDirection,
1476+
OffsetNumber attnum, 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
static bool
122122
findItemInPostingPage(Page page, RumKey *item, OffsetNumber *off,
123-
OffsetNumber attno,
124-
OffsetNumber attnum, RumState * rumstate)
123+
OffsetNumber attno, OffsetNumber attnum,
124+
ScanDirection scanDirection, RumState * rumstate)
125125
{
126126
OffsetNumber maxoff = RumPageGetOpaque(page)->maxoff;
127127
int res;
@@ -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+
else if (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
Buffer buffer;
188198
Page page;
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
OffsetNumber maxoff,
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 by right links */
1673+
/* At last try to traverse by direction */
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-
BlockNumber blkno;
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)