Skip to content

Commit 79e4293

Browse files
feodorfeodor
committed
Fixes backward index scan for fast and regular scan.
Both of them could fail if search item is exactly beetween pages, ie one page contains only items greater than current one and previous - less.
1 parent 3ad528d commit 79e4293

File tree

1 file changed

+60
-106
lines changed

1 file changed

+60
-106
lines changed

‎rumget.c

Lines changed: 60 additions & 106 deletions
Original file line numberDiff line numberDiff line change
@@ -135,51 +135,6 @@ callConsistentFn(RumState * rumstate, RumScanKey key)
135135
return res;
136136
}
137137

138-
/*
139-
* Tries to refind previously taken ItemPointer on a posting page.
140-
*/
141-
static bool
142-
findItemInPostingPage(Page page, RumKey *item, int16 *off,
143-
OffsetNumber attno, OffsetNumber attnum,
144-
ScanDirection scanDirection, RumState * rumstate)
145-
{
146-
OffsetNumber maxoff = RumPageGetOpaque(page)->maxoff;
147-
int res;
148-
Pointer ptr;
149-
RumKey iter_item;
150-
151-
ItemPointerSetMin(&iter_item.iptr);
152-
153-
if (RumPageGetOpaque(page)->flags & RUM_DELETED)
154-
/* page was deleted by concurrent vacuum */
155-
return false;
156-
157-
ptr = RumDataPageGetData(page);
158-
159-
/*
160-
* scan page to find equal or first greater value
161-
*/
162-
for (*off = FirstOffsetNumber; *off <= maxoff; (*off)++)
163-
{
164-
ptr = rumDataPageLeafRead(ptr, attnum, &iter_item, rumstate);
165-
res = compareRumKey(rumstate, attno, item, &iter_item);
166-
167-
if (res == 0)
168-
{
169-
return true;
170-
}
171-
else if (res < 0)
172-
{
173-
if (ScanDirectionIsBackward(scanDirection) &&
174-
*off > FirstOffsetNumber)
175-
(*off)--;
176-
return true;
177-
}
178-
}
179-
180-
return false;
181-
}
182-
183138
/*
184139
* Goes to the next page if current offset is outside of bounds
185140
*/
@@ -650,6 +605,8 @@ startScanEntry(RumState * rumstate, RumScanEntry entry)
650605

651606
LockBuffer(entry->buffer, RUM_UNLOCK);
652607
entry->isFinished = setListPositionScanEntry(rumstate, entry);
608+
if (!entry->isFinished)
609+
entry->curRumKey = entry->list[entry->offset];
653610
}
654611
else if (RumGetNPosting(itup) > 0)
655612
{
@@ -659,6 +616,8 @@ startScanEntry(RumState * rumstate, RumScanEntry entry)
659616

660617
rumReadTuple(rumstate, entry->attnum, itup, entry->list);
661618
entry->isFinished = setListPositionScanEntry(rumstate, entry);
619+
if (!entry->isFinished)
620+
entry->curRumKey = entry->list[entry->offset];
662621
}
663622

664623
if (entry->queryCategory == RUM_CAT_EMPTY_QUERY &&
@@ -837,26 +796,12 @@ entryGetNextItem(RumState * rumstate, RumScanEntry entry)
837796

838797
for (;;)
839798
{
840-
if (ScanDirectionIsForward(entry->scanDirection))
841-
{
842-
if (entry->offset < entry->nlist)
843-
{
844-
entry->curRumKey = entry->list[entry->offset];
845-
entry->offset++;
846-
return;
847-
}
848-
}
849-
else if (ScanDirectionIsBackward(entry->scanDirection))
799+
if (entry->offset >= 0 && entry->offset < entry->nlist)
850800
{
851-
if (entry->offset >= 0)
852-
{
853-
entry->curRumKey = entry->list[entry->offset];
854-
entry->offset--;
855-
return;
856-
}
801+
entry->curRumKey = entry->list[entry->offset];
802+
entry->offset += entry->scanDirection;
803+
return;
857804
}
858-
else
859-
elog(ERROR,"NoMovementScanDirection");
860805

861806
LockBuffer(entry->buffer, RUM_SHARE);
862807
page = BufferGetPage(entry->buffer);
@@ -871,6 +816,13 @@ entryGetNextItem(RumState * rumstate, RumScanEntry entry)
871816

872817
for (;;)
873818
{
819+
OffsetNumber maxoff,
820+
i;
821+
Pointer ptr;
822+
RumKey item;
823+
bool searchBorder =
824+
(ScanDirectionIsForward(entry->scanDirection) &&
825+
ItemPointerIsValid(&entry->curRumKey.iptr));
874826
/*
875827
* It's needed to go by right link. During that we should refind
876828
* first ItemPointer greater that stored
@@ -896,55 +848,48 @@ entryGetNextItem(RumState * rumstate, RumScanEntry entry)
896848
entry->gdi->stack->blkno = BufferGetBlockNumber(entry->buffer);
897849
page = BufferGetPage(entry->buffer);
898850

899-
entry->offset = InvalidOffsetNumber;
900-
if (!ItemPointerIsValid(&entry->curRumKey.iptr) ||
901-
findItemInPostingPage(page, &entry->curRumKey, &entry->offset,
902-
entry->attnumOrig, entry->attnum,
903-
entry->scanDirection, rumstate))
904-
{
905-
OffsetNumber maxoff,
906-
i;
907-
Pointer ptr;
908-
RumKey item;
909-
910-
ItemPointerSetMin(&item.iptr);
911-
912-
/*
913-
* Found position equal to or greater than stored
914-
*/
915-
maxoff = RumPageGetOpaque(page)->maxoff;
916-
entry->nlist = maxoff;
851+
entry->offset = -1;
852+
maxoff = RumPageGetOpaque(page)->maxoff;
853+
entry->nlist = maxoff;
854+
ItemPointerSetMin(&item.iptr);
855+
ptr = RumDataPageGetData(page);
917856

918-
ptr = RumDataPageGetData(page);
857+
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
858+
{
859+
ptr = rumDataPageLeafRead(ptr, entry->attnum, &item, rumstate);
860+
entry->list[i - FirstOffsetNumber] = item;
919861

920-
for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
862+
if (searchBorder)
921863
{
922-
ptr = rumDataPageLeafRead(ptr, entry->attnum, &item,
923-
rumstate);
924-
entry->list[i - FirstOffsetNumber] = item;
864+
/* don't search position for backward scan,
865+
because of split algorithm */
866+
int cmp = compareRumKey(rumstate,
867+
entry->attnumOrig,
868+
&entry->curRumKey,
869+
&item);
870+
871+
if (cmp > 0)
872+
{
873+
entry->offset = i - FirstOffsetNumber;
874+
searchBorder = false;
875+
}
925876
}
877+
}
926878

927-
LockBuffer(entry->buffer, RUM_UNLOCK);
879+
LockBuffer(entry->buffer, RUM_UNLOCK);
928880

929-
if (!ItemPointerIsValid(&entry->curRumKey.iptr) ||
930-
compareRumKey(rumstate, entry->attnumOrig,
931-
&entry->curRumKey,
932-
&entry->list[entry->offset - 1]) == 0)
933-
{
934-
/*
935-
* First pages are deleted or empty, or we found exact
936-
* position, so break inner loop and continue outer one.
937-
*/
881+
if (entry->offset < 0)
882+
{
883+
if (ScanDirectionIsForward(entry->scanDirection) &&
884+
ItemPointerIsValid(&entry->curRumKey.iptr))
885+
/* go on next page */
938886
break;
939-
}
940-
941-
/*
942-
* Find greater than entry->curItem position, store it.
943-
*/
944-
entry->curRumKey = entry->list[entry->offset - 1];
945-
946-
return;
887+
entry->offset = (ScanDirectionIsForward(entry->scanDirection)) ?
888+
0 : entry->nlist - 1;
947889
}
890+
891+
entry->curRumKey = entry->list[entry->offset];
892+
return;
948893
}
949894
}
950895
}
@@ -1635,7 +1580,7 @@ scanPage(RumState * rumstate, RumScanEntry entry, RumKey *item, Page page,
16351580

16361581
ItemPointerSetMin(&iter_item.iptr);
16371582

1638-
if (!RumPageRightMost(page))
1583+
if (ScanDirectionIsForward(entry->scanDirection) && !RumPageRightMost(page))
16391584
{
16401585
cmp = compareRumKey(rumstate, entry->attnumOrig,
16411586
RumDataPageGetRightBound(page), item);
@@ -1683,7 +1628,7 @@ scanPage(RumState * rumstate, RumScanEntry entry, RumKey *item, Page page,
16831628
}
16841629
}
16851630

1686-
if (ScanDirectionIsBackward(entry->scanDirection))
1631+
if (ScanDirectionIsBackward(entry->scanDirection) && first >= maxoff)
16871632
{
16881633
first = FirstOffsetNumber;
16891634
ItemPointerSetMin(&iter_item.iptr);
@@ -1712,8 +1657,16 @@ scanPage(RumState * rumstate, RumScanEntry entry, RumKey *item, Page page,
17121657
}
17131658

17141659
if (bound == -1)
1660+
{
1661+
if (ScanDirectionIsBackward(entry->scanDirection))
1662+
{
1663+
entry->offset = maxoff - first;
1664+
goto end;
1665+
}
17151666
return false;
17161667

1668+
}
1669+
17171670
if (found_eq)
17181671
{
17191672
entry->offset = bound;
@@ -1728,6 +1681,7 @@ scanPage(RumState * rumstate, RumScanEntry entry, RumKey *item, Page page,
17281681
if (entry->offset < 0 || entry->offset >= entry->nlist)
17291682
return false;
17301683

1684+
end:
17311685
entry->curRumKey = entry->list[entry->offset];
17321686
return true;
17331687
}

0 commit comments

Comments
 (0)