src/backend/access/gin/gindatapage.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gindatapage.c
   4  *        page utilities routines for the postgres inverted index access method.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2009, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *                      $PostgreSQL$
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/gin.h"
  18 #include "storage/bufmgr.h"
  19 #include "utils/rel.h"
  20
  21 int
  22 compareItemPointers(ItemPointer a, ItemPointer b)
  23 {
  24         if (GinItemPointerGetBlockNumber(a) == GinItemPointerGetBlockNumber(b))
  25         {
  26                 if (GinItemPointerGetOffsetNumber(a) == GinItemPointerGetOffsetNumber(b))
  27                         return 0;
  28                 return (GinItemPointerGetOffsetNumber(a) > GinItemPointerGetOffsetNumber(b)) ? 1 : -1;
  29         }
  30
  31         return (GinItemPointerGetBlockNumber(a) > GinItemPointerGetBlockNumber(b)) ? 1 : -1;
  32 }
  33
  34 /*
  35  * Merge two ordered arrays of itempointers, eliminating any duplicates.
  36  * Returns the number of items in the result.
  37  * Caller is responsible that there is enough space at *dst.
  38  */
  39 uint32
  40 MergeItemPointers(ItemPointerData *dst,
  41                                   ItemPointerData *a, uint32 na,
  42                                   ItemPointerData *b, uint32 nb)
  43 {
  44         ItemPointerData *dptr = dst;
  45         ItemPointerData *aptr = a,
  46                            *bptr = b;
  47
  48         while (aptr - a < na && bptr - b < nb)
  49         {
  50                 int                     cmp = compareItemPointers(aptr, bptr);
  51
  52                 if (cmp > 0)
  53                         *dptr++ = *bptr++;
  54                 else if (cmp == 0)
  55                 {
  56                         /* we want only one copy of the identical items */
  57                         *dptr++ = *bptr++;
  58                         aptr++;
  59                 }
  60                 else
  61                         *dptr++ = *aptr++;
  62         }
  63
  64         while (aptr - a < na)
  65                 *dptr++ = *aptr++;
  66
  67         while (bptr - b < nb)
  68                 *dptr++ = *bptr++;
  69
  70         return dptr - dst;
  71 }
  72
  73 /*
  74  * Checks, should we move to right link...
  75  * Compares inserting itemp pointer with right bound of current page
  76  */
  77 static bool
  78 dataIsMoveRight(GinBtree btree, Page page)
  79 {
  80         ItemPointer iptr = GinDataPageGetRightBound(page);
  81
  82         if (GinPageRightMost(page))
  83                 return FALSE;
  84
  85         return (compareItemPointers(btree->items + btree->curitem, iptr) > 0) ? TRUE : FALSE;
  86 }
  87
  88 /*
  89  * Find correct PostingItem in non-leaf page. It supposed that page
  90  * correctly chosen and searching value SHOULD be on page
  91  */
  92 static BlockNumber
  93 dataLocateItem(GinBtree btree, GinBtreeStack *stack)
  94 {
  95         OffsetNumber low,
  96                                 high,
  97                                 maxoff;
  98         PostingItem *pitem = NULL;
  99         int                     result;
 100         Page            page = BufferGetPage(stack->buffer);
 101
 102         Assert(!GinPageIsLeaf(page));
 103         Assert(GinPageIsData(page));
 104
 105         if (btree->fullScan)
 106         {
 107                 stack->off = FirstOffsetNumber;
 108                 stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
 109                 return btree->getLeftMostPage(btree, page);
 110         }
 111
 112         low = FirstOffsetNumber;
 113         maxoff = high = GinPageGetOpaque(page)->maxoff;
 114         Assert(high >= low);
 115
 116         high++;
 117
 118         while (high > low)
 119         {
 120                 OffsetNumber mid = low + ((high - low) / 2);
 121
 122                 pitem = (PostingItem *) GinDataPageGetItem(page, mid);
 123
 124                 if (mid == maxoff)
 125
 126                         /*
 127                          * Right infinity, page already correctly chosen with a help of
 128                          * dataIsMoveRight
 129                          */
 130                         result = -1;
 131                 else
 132                 {
 133                         pitem = (PostingItem *) GinDataPageGetItem(page, mid);
 134                         result = compareItemPointers(btree->items + btree->curitem, &(pitem->key));
 135                 }
 136
 137                 if (result == 0)
 138                 {
 139                         stack->off = mid;
 140                         return PostingItemGetBlockNumber(pitem);
 141                 }
 142                 else if (result > 0)
 143                         low = mid + 1;
 144                 else
 145                         high = mid;
 146         }
 147
 148         Assert(high >= FirstOffsetNumber && high <= maxoff);
 149
 150         stack->off = high;
 151         pitem = (PostingItem *) GinDataPageGetItem(page, high);
 152         return PostingItemGetBlockNumber(pitem);
 153 }
 154
 155 /*
 156  * Searches correct position for value on leaf page.
 157  * Page should be correctly chosen.
 158  * Returns true if value found on page.
 159  */
 160 static bool
 161 dataLocateLeafItem(GinBtree btree, GinBtreeStack *stack)
 162 {
 163         Page            page = BufferGetPage(stack->buffer);
 164         OffsetNumber low,
 165                                 high;
 166         int                     result;
 167
 168         Assert(GinPageIsLeaf(page));
 169         Assert(GinPageIsData(page));
 170
 171         if (btree->fullScan)
 172         {
 173                 stack->off = FirstOffsetNumber;
 174                 return TRUE;
 175         }
 176
 177         low = FirstOffsetNumber;
 178         high = GinPageGetOpaque(page)->maxoff;
 179
 180         if (high < low)
 181         {
 182                 stack->off = FirstOffsetNumber;
 183                 return false;
 184         }
 185
 186         high++;
 187
 188         while (high > low)
 189         {
 190                 OffsetNumber mid = low + ((high - low) / 2);
 191
 192                 result = compareItemPointers(btree->items + btree->curitem, (ItemPointer) GinDataPageGetItem(page, mid));
 193
 194                 if (result == 0)
 195                 {
 196                         stack->off = mid;
 197                         return true;
 198                 }
 199                 else if (result > 0)
 200                         low = mid + 1;
 201                 else
 202                         high = mid;
 203         }
 204
 205         stack->off = high;
 206         return false;
 207 }
 208
 209 /*
 210  * Finds links to blkno on non-leaf page, returns
 211  * offset of PostingItem
 212  */
 213 static OffsetNumber
 214 dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
 215 {
 216         OffsetNumber i,
 217                                 maxoff = GinPageGetOpaque(page)->maxoff;
 218         PostingItem *pitem;
 219
 220         Assert(!GinPageIsLeaf(page));
 221         Assert(GinPageIsData(page));
 222
 223         /* if page isn't changed, we returns storedOff */
 224         if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
 225         {
 226                 pitem = (PostingItem *) GinDataPageGetItem(page, storedOff);
 227                 if (PostingItemGetBlockNumber(pitem) == blkno)
 228                         return storedOff;
 229
 230                 /*
 231                  * we hope, that needed pointer goes to right. It's true if there
 232                  * wasn't a deletion
 233                  */
 234                 for (i = storedOff + 1; i <= maxoff; i++)
 235                 {
 236                         pitem = (PostingItem *) GinDataPageGetItem(page, i);
 237                         if (PostingItemGetBlockNumber(pitem) == blkno)
 238                                 return i;
 239                 }
 240
 241                 maxoff = storedOff - 1;
 242         }
 243
 244         /* last chance */
 245         for (i = FirstOffsetNumber; i <= maxoff; i++)
 246         {
 247                 pitem = (PostingItem *) GinDataPageGetItem(page, i);
 248                 if (PostingItemGetBlockNumber(pitem) == blkno)
 249                         return i;
 250         }
 251
 252         return InvalidOffsetNumber;
 253 }
 254
 255 /*
 256  * returns blkno of leftmost child
 257  */
 258 static BlockNumber
 259 dataGetLeftMostPage(GinBtree btree, Page page)
 260 {
 261         PostingItem *pitem;
 262
 263         Assert(!GinPageIsLeaf(page));
 264         Assert(GinPageIsData(page));
 265         Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
 266
 267         pitem = (PostingItem *) GinDataPageGetItem(page, FirstOffsetNumber);
 268         return PostingItemGetBlockNumber(pitem);
 269 }
 270
 271 /*
 272  * add ItemPointer or PostingItem to page. data should point to
 273  * correct value! depending on leaf or non-leaf page
 274  */
 275 void
 276 GinDataPageAddItem(Page page, void *data, OffsetNumber offset)
 277 {
 278         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 279         char       *ptr;
 280
 281         if (offset == InvalidOffsetNumber)
 282         {
 283                 ptr = GinDataPageGetItem(page, maxoff + 1);
 284         }
 285         else
 286         {
 287                 ptr = GinDataPageGetItem(page, offset);
 288                 if (maxoff + 1 - offset != 0)
 289                         memmove(ptr + GinSizeOfItem(page), ptr, (maxoff - offset + 1) * GinSizeOfItem(page));
 290         }
 291         memcpy(ptr, data, GinSizeOfItem(page));
 292
 293         GinPageGetOpaque(page)->maxoff++;
 294 }
 295
 296 /*
 297  * Deletes posting item from non-leaf page
 298  */
 299 void
 300 PageDeletePostingItem(Page page, OffsetNumber offset)
 301 {
 302         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 303
 304         Assert(!GinPageIsLeaf(page));
 305         Assert(offset >= FirstOffsetNumber && offset <= maxoff);
 306
 307         if (offset != maxoff)
 308                 memmove(GinDataPageGetItem(page, offset), GinDataPageGetItem(page, offset + 1),
 309                                 sizeof(PostingItem) * (maxoff - offset));
 310
 311         GinPageGetOpaque(page)->maxoff--;
 312 }
 313
 314 /*
 315  * checks space to install new value,
 316  * item pointer never deletes!
 317  */
 318 static bool
 319 dataIsEnoughSpace(GinBtree btree, Buffer buf, OffsetNumber off)
 320 {
 321         Page            page = BufferGetPage(buf);
 322
 323         Assert(GinPageIsData(page));
 324         Assert(!btree->isDelete);
 325
 326         if (GinPageIsLeaf(page))
 327         {
 328                 if (GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff)
 329                 {
 330                         if ((btree->nitem - btree->curitem) * sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page))
 331                                 return true;
 332                 }
 333                 else if (sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page))
 334                         return true;
 335         }
 336         else if (sizeof(PostingItem) <= GinDataPageGetFreeSpace(page))
 337                 return true;
 338
 339         return false;
 340 }
 341
 342 /*
 343  * In case of previous split update old child blkno to
 344  * new right page
 345  * item pointer never deletes!
 346  */
 347 static BlockNumber
 348 dataPrepareData(GinBtree btree, Page page, OffsetNumber off)
 349 {
 350         BlockNumber ret = InvalidBlockNumber;
 351
 352         Assert(GinPageIsData(page));
 353
 354         if (!GinPageIsLeaf(page) && btree->rightblkno != InvalidBlockNumber)
 355         {
 356                 PostingItem *pitem = (PostingItem *) GinDataPageGetItem(page, off);
 357
 358                 PostingItemSetBlockNumber(pitem, btree->rightblkno);
 359                 ret = btree->rightblkno;
 360         }
 361
 362         btree->rightblkno = InvalidBlockNumber;
 363
 364         return ret;
 365 }
 366
 367 /*
 368  * Places keys to page and fills WAL record. In case leaf page and
 369  * build mode puts all ItemPointers to page.
 370  */
 371 static void
 372 dataPlaceToPage(GinBtree btree, Buffer buf, OffsetNumber off, XLogRecData **prdata)
 373 {
 374         Page            page = BufferGetPage(buf);
 375         static XLogRecData rdata[3];
 376         int                     sizeofitem = GinSizeOfItem(page);
 377         static ginxlogInsert data;
 378         int                     cnt = 0;
 379
 380         *prdata = rdata;
 381         Assert(GinPageIsData(page));
 382
 383         data.updateBlkno = dataPrepareData(btree, page, off);
 384
 385         data.node = btree->index->rd_node;
 386         data.blkno = BufferGetBlockNumber(buf);
 387         data.offset = off;
 388         data.nitem = 1;
 389         data.isDelete = FALSE;
 390         data.isData = TRUE;
 391         data.isLeaf = GinPageIsLeaf(page) ? TRUE : FALSE;
 392
 393         /*
 394          * Prevent full page write if child's split occurs. That is needed to
 395          * remove incomplete splits while replaying WAL
 396          *
 397          * data.updateBlkno contains new block number (of newly created right
 398          * page) for recently splited page.
 399          */
 400         if (data.updateBlkno == InvalidBlockNumber)
 401         {
 402                 rdata[0].buffer = buf;
 403                 rdata[0].buffer_std = FALSE;
 404                 rdata[0].data = NULL;
 405                 rdata[0].len = 0;
 406                 rdata[0].next = &rdata[1];
 407                 cnt++;
 408         }
 409
 410         rdata[cnt].buffer = InvalidBuffer;
 411         rdata[cnt].data = (char *) &data;
 412         rdata[cnt].len = sizeof(ginxlogInsert);
 413         rdata[cnt].next = &rdata[cnt + 1];
 414         cnt++;
 415
 416         rdata[cnt].buffer = InvalidBuffer;
 417         rdata[cnt].data = (GinPageIsLeaf(page)) ? ((char *) (btree->items + btree->curitem)) : ((char *) &(btree->pitem));
 418         rdata[cnt].len = sizeofitem;
 419         rdata[cnt].next = NULL;
 420
 421         if (GinPageIsLeaf(page))
 422         {
 423                 if (GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff)
 424                 {
 425                         /* usually, create index... */
 426                         uint32          savedPos = btree->curitem;
 427
 428                         while (btree->curitem < btree->nitem)
 429                         {
 430                                 GinDataPageAddItem(page, btree->items + btree->curitem, off);
 431                                 off++;
 432                                 btree->curitem++;
 433                         }
 434                         data.nitem = btree->curitem - savedPos;
 435                         rdata[cnt].len = sizeofitem * data.nitem;
 436                 }
 437                 else
 438                 {
 439                         GinDataPageAddItem(page, btree->items + btree->curitem, off);
 440                         btree->curitem++;
 441                 }
 442         }
 443         else
 444                 GinDataPageAddItem(page, &(btree->pitem), off);
 445 }
 446
 447 /*
 448  * split page and fills WAL record. original buffer(lbuf) leaves untouched,
 449  * returns shadow page of lbuf filled new data. In leaf page and build mode puts all
 450  * ItemPointers to pages. Also, in build mode splits data by way to full fulled
 451  * left page
 452  */
 453 static Page
 454 dataSplitPage(GinBtree btree, Buffer lbuf, Buffer rbuf, OffsetNumber off, XLogRecData **prdata)
 455 {
 456         static ginxlogSplit data;
 457         static XLogRecData rdata[4];
 458         static char vector[2 * BLCKSZ];
 459         char       *ptr;
 460         OffsetNumber separator;
 461         ItemPointer bound;
 462         Page            lpage = PageGetTempPageCopy(BufferGetPage(lbuf));
 463         ItemPointerData oldbound = *GinDataPageGetRightBound(lpage);
 464         int                     sizeofitem = GinSizeOfItem(lpage);
 465         OffsetNumber maxoff = GinPageGetOpaque(lpage)->maxoff;
 466         Page            rpage = BufferGetPage(rbuf);
 467         Size            pageSize = PageGetPageSize(lpage);
 468         Size            freeSpace;
 469         uint32          nCopied = 1;
 470
 471         GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
 472         freeSpace = GinDataPageGetFreeSpace(rpage);
 473
 474         *prdata = rdata;
 475         data.leftChildBlkno = (GinPageIsLeaf(lpage)) ?
 476                 InvalidOffsetNumber : PostingItemGetBlockNumber(&(btree->pitem));
 477         data.updateBlkno = dataPrepareData(btree, lpage, off);
 478
 479         memcpy(vector, GinDataPageGetItem(lpage, FirstOffsetNumber),
 480                    maxoff * sizeofitem);
 481
 482         if (GinPageIsLeaf(lpage) && GinPageRightMost(lpage) && off > GinPageGetOpaque(lpage)->maxoff)
 483         {
 484                 nCopied = 0;
 485                 while (btree->curitem < btree->nitem && maxoff * sizeof(ItemPointerData) < 2 * (freeSpace - sizeof(ItemPointerData)))
 486                 {
 487                         memcpy(vector + maxoff * sizeof(ItemPointerData), btree->items + btree->curitem,
 488                                    sizeof(ItemPointerData));
 489                         maxoff++;
 490                         nCopied++;
 491                         btree->curitem++;
 492                 }
 493         }
 494         else
 495         {
 496                 ptr = vector + (off - 1) * sizeofitem;
 497                 if (maxoff + 1 - off != 0)
 498                         memmove(ptr + sizeofitem, ptr, (maxoff - off + 1) * sizeofitem);
 499                 if (GinPageIsLeaf(lpage))
 500                 {
 501                         memcpy(ptr, btree->items + btree->curitem, sizeofitem);
 502                         btree->curitem++;
 503                 }
 504                 else
 505                         memcpy(ptr, &(btree->pitem), sizeofitem);
 506
 507                 maxoff++;
 508         }
 509
 510         /*
 511          * we suppose that during index creation table scaned from begin to end,
 512          * so ItemPointers are monotonically increased..
 513          */
 514         if (btree->isBuild && GinPageRightMost(lpage))
 515                 separator = freeSpace / sizeofitem;
 516         else
 517                 separator = maxoff / 2;
 518
 519         GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
 520         GinInitPage(lpage, GinPageGetOpaque(rpage)->flags, pageSize);
 521
 522         memcpy(GinDataPageGetItem(lpage, FirstOffsetNumber), vector, separator * sizeofitem);
 523         GinPageGetOpaque(lpage)->maxoff = separator;
 524         memcpy(GinDataPageGetItem(rpage, FirstOffsetNumber),
 525                  vector + separator * sizeofitem, (maxoff - separator) * sizeofitem);
 526         GinPageGetOpaque(rpage)->maxoff = maxoff - separator;
 527
 528         PostingItemSetBlockNumber(&(btree->pitem), BufferGetBlockNumber(lbuf));
 529         if (GinPageIsLeaf(lpage))
 530                 btree->pitem.key = *(ItemPointerData *) GinDataPageGetItem(lpage,
 531                                                                                         GinPageGetOpaque(lpage)->maxoff);
 532         else
 533                 btree->pitem.key = ((PostingItem *) GinDataPageGetItem(lpage,
 534                                                                           GinPageGetOpaque(lpage)->maxoff))->key;
 535         btree->rightblkno = BufferGetBlockNumber(rbuf);
 536
 537         /* set up right bound for left page */
 538         bound = GinDataPageGetRightBound(lpage);
 539         *bound = btree->pitem.key;
 540
 541         /* set up right bound for right page */
 542         bound = GinDataPageGetRightBound(rpage);
 543         *bound = oldbound;
 544
 545         data.node = btree->index->rd_node;
 546         data.rootBlkno = InvalidBlockNumber;
 547         data.lblkno = BufferGetBlockNumber(lbuf);
 548         data.rblkno = BufferGetBlockNumber(rbuf);
 549         data.separator = separator;
 550         data.nitem = maxoff;
 551         data.isData = TRUE;
 552         data.isLeaf = GinPageIsLeaf(lpage) ? TRUE : FALSE;
 553         data.isRootSplit = FALSE;
 554         data.rightbound = oldbound;
 555
 556         rdata[0].buffer = InvalidBuffer;
 557         rdata[0].data = (char *) &data;
 558         rdata[0].len = sizeof(ginxlogSplit);
 559         rdata[0].next = &rdata[1];
 560
 561         rdata[1].buffer = InvalidBuffer;
 562         rdata[1].data = vector;
 563         rdata[1].len = MAXALIGN(maxoff * sizeofitem);
 564         rdata[1].next = NULL;
 565
 566         return lpage;
 567 }
 568
 569 /*
 570  * Fills new root by right bound values from child.
 571  * Also called from ginxlog, should not use btree
 572  */
 573 void
 574 dataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf)
 575 {
 576         Page            page = BufferGetPage(root),
 577                                 lpage = BufferGetPage(lbuf),
 578                                 rpage = BufferGetPage(rbuf);
 579         PostingItem li,
 580                                 ri;
 581
 582         li.key = *GinDataPageGetRightBound(lpage);
 583         PostingItemSetBlockNumber(&li, BufferGetBlockNumber(lbuf));
 584         GinDataPageAddItem(page, &li, InvalidOffsetNumber);
 585
 586         ri.key = *GinDataPageGetRightBound(rpage);
 587         PostingItemSetBlockNumber(&ri, BufferGetBlockNumber(rbuf));
 588         GinDataPageAddItem(page, &ri, InvalidOffsetNumber);
 589 }
 590
 591 void
 592 prepareDataScan(GinBtree btree, Relation index)
 593 {
 594         memset(btree, 0, sizeof(GinBtreeData));
 595         btree->index = index;
 596         btree->isMoveRight = dataIsMoveRight;
 597         btree->findChildPage = dataLocateItem;
 598         btree->findItem = dataLocateLeafItem;
 599         btree->findChildPtr = dataFindChildPtr;
 600         btree->getLeftMostPage = dataGetLeftMostPage;
 601         btree->isEnoughSpace = dataIsEnoughSpace;
 602         btree->placeToPage = dataPlaceToPage;
 603         btree->splitPage = dataSplitPage;
 604         btree->fillRoot = dataFillRoot;
 605
 606         btree->searchMode = FALSE;
 607         btree->isDelete = FALSE;
 608         btree->fullScan = FALSE;
 609         btree->isBuild = FALSE;
 610 }
 611
 612 GinPostingTreeScan *
 613 prepareScanPostingTree(Relation index, BlockNumber rootBlkno, bool searchMode)
 614 {
 615         GinPostingTreeScan *gdi = (GinPostingTreeScan *) palloc0(sizeof(GinPostingTreeScan));
 616
 617         prepareDataScan(&gdi->btree, index);
 618
 619         gdi->btree.searchMode = searchMode;
 620         gdi->btree.fullScan = searchMode;
 621
 622         gdi->stack = ginPrepareFindLeafPage(&gdi->btree, rootBlkno);
 623
 624         return gdi;
 625 }
 626
 627 /*
 628  * Inserts array of item pointers, may execute several tree scan (very rare)
 629  */
 630 void
 631 insertItemPointer(GinPostingTreeScan *gdi, ItemPointerData *items, uint32 nitem)
 632 {
 633         BlockNumber rootBlkno = gdi->stack->blkno;
 634
 635         gdi->btree.items = items;
 636         gdi->btree.nitem = nitem;
 637         gdi->btree.curitem = 0;
 638
 639         while (gdi->btree.curitem < gdi->btree.nitem)
 640         {
 641                 if (!gdi->stack)
 642                         gdi->stack = ginPrepareFindLeafPage(&gdi->btree, rootBlkno);
 643
 644                 gdi->stack = ginFindLeafPage(&gdi->btree, gdi->stack);
 645
 646                 if (gdi->btree.findItem(&(gdi->btree), gdi->stack))
 647                 {
 648                         /*
 649                          * gdi->btree.items[gdi->btree.curitem] already exists in index
 650                          */
 651                         gdi->btree.curitem++;
 652                         LockBuffer(gdi->stack->buffer, GIN_UNLOCK);
 653                         freeGinBtreeStack(gdi->stack);
 654                 }
 655                 else
 656                         ginInsertValue(&(gdi->btree), gdi->stack);
 657
 658                 gdi->stack = NULL;
 659         }
 660 }
 661
 662 Buffer
 663 scanBeginPostingTree(GinPostingTreeScan *gdi)
 664 {
 665         gdi->stack = ginFindLeafPage(&gdi->btree, gdi->stack);
 666         return gdi->stack->buffer;
 667 }