granicus.if.org Git - postgresql/blob - 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-2013, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *                      src/backend/access/gin/gindatapage.c
  12  *-------------------------------------------------------------------------
  13  */
  14
  15 #include "postgres.h"
  16
  17 #include "access/gin_private.h"
  18 #include "miscadmin.h"
  19 #include "utils/rel.h"
  20
  21 /*
  22  * Checks, should we move to right link...
  23  * Compares inserting itemp pointer with right bound of current page
  24  */
  25 static bool
  26 dataIsMoveRight(GinBtree btree, Page page)
  27 {
  28         ItemPointer iptr = GinDataPageGetRightBound(page);
  29
  30         if (GinPageRightMost(page))
  31                 return FALSE;
  32
  33         return (ginCompareItemPointers(btree->items + btree->curitem, iptr) > 0) ? TRUE : FALSE;
  34 }
  35
  36 /*
  37  * Find correct PostingItem in non-leaf page. It supposed that page
  38  * correctly chosen and searching value SHOULD be on page
  39  */
  40 static BlockNumber
  41 dataLocateItem(GinBtree btree, GinBtreeStack *stack)
  42 {
  43         OffsetNumber low,
  44                                 high,
  45                                 maxoff;
  46         PostingItem *pitem = NULL;
  47         int                     result;
  48         Page            page = BufferGetPage(stack->buffer);
  49
  50         Assert(!GinPageIsLeaf(page));
  51         Assert(GinPageIsData(page));
  52
  53         if (btree->fullScan)
  54         {
  55                 stack->off = FirstOffsetNumber;
  56                 stack->predictNumber *= GinPageGetOpaque(page)->maxoff;
  57                 return btree->getLeftMostChild(btree, page);
  58         }
  59
  60         low = FirstOffsetNumber;
  61         maxoff = high = GinPageGetOpaque(page)->maxoff;
  62         Assert(high >= low);
  63
  64         high++;
  65
  66         while (high > low)
  67         {
  68                 OffsetNumber mid = low + ((high - low) / 2);
  69
  70                 pitem = GinDataPageGetPostingItem(page, mid);
  71
  72                 if (mid == maxoff)
  73                 {
  74                         /*
  75                          * Right infinity, page already correctly chosen with a help of
  76                          * dataIsMoveRight
  77                          */
  78                         result = -1;
  79                 }
  80                 else
  81                 {
  82                         pitem = GinDataPageGetPostingItem(page, mid);
  83                         result = ginCompareItemPointers(btree->items + btree->curitem, &(pitem->key));
  84                 }
  85
  86                 if (result == 0)
  87                 {
  88                         stack->off = mid;
  89                         return PostingItemGetBlockNumber(pitem);
  90                 }
  91                 else if (result > 0)
  92                         low = mid + 1;
  93                 else
  94                         high = mid;
  95         }
  96
  97         Assert(high >= FirstOffsetNumber && high <= maxoff);
  98
  99         stack->off = high;
 100         pitem = GinDataPageGetPostingItem(page, high);
 101         return PostingItemGetBlockNumber(pitem);
 102 }
 103
 104 /*
 105  * Searches correct position for value on leaf page.
 106  * Page should be correctly chosen.
 107  * Returns true if value found on page.
 108  */
 109 static bool
 110 dataLocateLeafItem(GinBtree btree, GinBtreeStack *stack)
 111 {
 112         Page            page = BufferGetPage(stack->buffer);
 113         OffsetNumber low,
 114                                 high;
 115         int                     result;
 116
 117         Assert(GinPageIsLeaf(page));
 118         Assert(GinPageIsData(page));
 119
 120         if (btree->fullScan)
 121         {
 122                 stack->off = FirstOffsetNumber;
 123                 return TRUE;
 124         }
 125
 126         low = FirstOffsetNumber;
 127         high = GinPageGetOpaque(page)->maxoff;
 128
 129         if (high < low)
 130         {
 131                 stack->off = FirstOffsetNumber;
 132                 return false;
 133         }
 134
 135         high++;
 136
 137         while (high > low)
 138         {
 139                 OffsetNumber mid = low + ((high - low) / 2);
 140
 141                 result = ginCompareItemPointers(btree->items + btree->curitem,
 142                                                                                 GinDataPageGetItemPointer(page, mid));
 143
 144                 if (result == 0)
 145                 {
 146                         stack->off = mid;
 147                         return true;
 148                 }
 149                 else if (result > 0)
 150                         low = mid + 1;
 151                 else
 152                         high = mid;
 153         }
 154
 155         stack->off = high;
 156         return false;
 157 }
 158
 159 /*
 160  * Finds links to blkno on non-leaf page, returns
 161  * offset of PostingItem
 162  */
 163 static OffsetNumber
 164 dataFindChildPtr(GinBtree btree, Page page, BlockNumber blkno, OffsetNumber storedOff)
 165 {
 166         OffsetNumber i,
 167                                 maxoff = GinPageGetOpaque(page)->maxoff;
 168         PostingItem *pitem;
 169
 170         Assert(!GinPageIsLeaf(page));
 171         Assert(GinPageIsData(page));
 172
 173         /* if page isn't changed, we return storedOff */
 174         if (storedOff >= FirstOffsetNumber && storedOff <= maxoff)
 175         {
 176                 pitem = GinDataPageGetPostingItem(page, storedOff);
 177                 if (PostingItemGetBlockNumber(pitem) == blkno)
 178                         return storedOff;
 179
 180                 /*
 181                  * we hope, that needed pointer goes to right. It's true if there
 182                  * wasn't a deletion
 183                  */
 184                 for (i = storedOff + 1; i <= maxoff; i++)
 185                 {
 186                         pitem = GinDataPageGetPostingItem(page, i);
 187                         if (PostingItemGetBlockNumber(pitem) == blkno)
 188                                 return i;
 189                 }
 190
 191                 maxoff = storedOff - 1;
 192         }
 193
 194         /* last chance */
 195         for (i = FirstOffsetNumber; i <= maxoff; i++)
 196         {
 197                 pitem = GinDataPageGetPostingItem(page, i);
 198                 if (PostingItemGetBlockNumber(pitem) == blkno)
 199                         return i;
 200         }
 201
 202         return InvalidOffsetNumber;
 203 }
 204
 205 /*
 206  * returns blkno of leftmost child
 207  */
 208 static BlockNumber
 209 dataGetLeftMostPage(GinBtree btree, Page page)
 210 {
 211         PostingItem *pitem;
 212
 213         Assert(!GinPageIsLeaf(page));
 214         Assert(GinPageIsData(page));
 215         Assert(GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber);
 216
 217         pitem = GinDataPageGetPostingItem(page, FirstOffsetNumber);
 218         return PostingItemGetBlockNumber(pitem);
 219 }
 220
 221 /*
 222  * add ItemPointer to a leaf page.
 223  */
 224 void
 225 GinDataPageAddItemPointer(Page page, ItemPointer data, OffsetNumber offset)
 226 {
 227         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 228         char       *ptr;
 229
 230         Assert(GinPageIsLeaf(page));
 231
 232         if (offset == InvalidOffsetNumber)
 233         {
 234                 ptr = (char *) GinDataPageGetItemPointer(page, maxoff + 1);
 235         }
 236         else
 237         {
 238                 ptr = (char *) GinDataPageGetItemPointer(page, offset);
 239                 if (maxoff + 1 - offset != 0)
 240                         memmove(ptr + sizeof(ItemPointerData),
 241                                         ptr,
 242                                         (maxoff - offset + 1) * sizeof(ItemPointerData));
 243         }
 244         memcpy(ptr, data, sizeof(ItemPointerData));
 245
 246         GinPageGetOpaque(page)->maxoff++;
 247 }
 248
 249 /*
 250  * add PostingItem to a non-leaf page.
 251  */
 252 void
 253 GinDataPageAddPostingItem(Page page, PostingItem *data, OffsetNumber offset)
 254 {
 255         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 256         char       *ptr;
 257
 258         Assert(!GinPageIsLeaf(page));
 259
 260         if (offset == InvalidOffsetNumber)
 261         {
 262                 ptr = (char *) GinDataPageGetPostingItem(page, maxoff + 1);
 263         }
 264         else
 265         {
 266                 ptr = (char *) GinDataPageGetPostingItem(page, offset);
 267                 if (maxoff + 1 - offset != 0)
 268                         memmove(ptr + sizeof(PostingItem),
 269                                         ptr,
 270                                         (maxoff - offset + 1) * sizeof(PostingItem));
 271         }
 272         memcpy(ptr, data, sizeof(PostingItem));
 273
 274         GinPageGetOpaque(page)->maxoff++;
 275 }
 276
 277 /*
 278  * Deletes posting item from non-leaf page
 279  */
 280 void
 281 GinPageDeletePostingItem(Page page, OffsetNumber offset)
 282 {
 283         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
 284
 285         Assert(!GinPageIsLeaf(page));
 286         Assert(offset >= FirstOffsetNumber && offset <= maxoff);
 287
 288         if (offset != maxoff)
 289                 memmove(GinDataPageGetPostingItem(page, offset),
 290                                 GinDataPageGetPostingItem(page, offset + 1),
 291                                 sizeof(PostingItem) * (maxoff - offset));
 292
 293         GinPageGetOpaque(page)->maxoff--;
 294 }
 295
 296 /*
 297  * checks space to install new value,
 298  * item pointer never deletes!
 299  */
 300 static bool
 301 dataIsEnoughSpace(GinBtree btree, Buffer buf, OffsetNumber off)
 302 {
 303         Page            page = BufferGetPage(buf);
 304
 305         Assert(GinPageIsData(page));
 306         Assert(!btree->isDelete);
 307
 308         if (GinPageIsLeaf(page))
 309         {
 310                 if (GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff)
 311                 {
 312                         if ((btree->nitem - btree->curitem) * sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page))
 313                                 return true;
 314                 }
 315                 else if (sizeof(ItemPointerData) <= GinDataPageGetFreeSpace(page))
 316                         return true;
 317         }
 318         else if (sizeof(PostingItem) <= GinDataPageGetFreeSpace(page))
 319                 return true;
 320
 321         return false;
 322 }
 323
 324 /*
 325  * In case of previous split update old child blkno to
 326  * new right page
 327  * item pointer never deletes!
 328  */
 329 static BlockNumber
 330 dataPrepareData(GinBtree btree, Page page, OffsetNumber off)
 331 {
 332         BlockNumber ret = InvalidBlockNumber;
 333
 334         Assert(GinPageIsData(page));
 335
 336         if (!GinPageIsLeaf(page) && btree->rightblkno != InvalidBlockNumber)
 337         {
 338                 PostingItem *pitem = GinDataPageGetPostingItem(page, off);
 339
 340                 PostingItemSetBlockNumber(pitem, btree->rightblkno);
 341                 ret = btree->rightblkno;
 342         }
 343
 344         btree->rightblkno = InvalidBlockNumber;
 345
 346         return ret;
 347 }
 348
 349 /*
 350  * Places keys to page and fills WAL record. In case leaf page and
 351  * build mode puts all ItemPointers to page.
 352  *
 353  * If none of the keys fit, returns false without modifying the page.
 354  */
 355 static bool
 356 dataPlaceToPage(GinBtree btree, Buffer buf, OffsetNumber off,
 357                                 XLogRecData **prdata)
 358 {
 359         Page            page = BufferGetPage(buf);
 360         int                     sizeofitem = GinSizeOfDataPageItem(page);
 361         int                     cnt = 0;
 362
 363         /* these must be static so they can be returned to caller */
 364         static XLogRecData rdata[3];
 365         static ginxlogInsert data;
 366
 367         /* quick exit if it doesn't fit */
 368         if (!dataIsEnoughSpace(btree, buf, off))
 369                 return false;
 370
 371         *prdata = rdata;
 372         Assert(GinPageIsData(page));
 373
 374         data.updateBlkno = dataPrepareData(btree, page, off);
 375
 376         data.node = btree->index->rd_node;
 377         data.blkno = BufferGetBlockNumber(buf);
 378         data.offset = off;
 379         data.nitem = 1;
 380         data.isDelete = FALSE;
 381         data.isData = TRUE;
 382         data.isLeaf = GinPageIsLeaf(page) ? TRUE : FALSE;
 383
 384         /*
 385          * Prevent full page write if child's split occurs. That is needed to
 386          * remove incomplete splits while replaying WAL
 387          *
 388          * data.updateBlkno contains new block number (of newly created right
 389          * page) for recently splited page.
 390          */
 391         if (data.updateBlkno == InvalidBlockNumber)
 392         {
 393                 rdata[0].buffer = buf;
 394                 rdata[0].buffer_std = FALSE;
 395                 rdata[0].data = NULL;
 396                 rdata[0].len = 0;
 397                 rdata[0].next = &rdata[1];
 398                 cnt++;
 399         }
 400
 401         rdata[cnt].buffer = InvalidBuffer;
 402         rdata[cnt].data = (char *) &data;
 403         rdata[cnt].len = sizeof(ginxlogInsert);
 404         rdata[cnt].next = &rdata[cnt + 1];
 405         cnt++;
 406
 407         rdata[cnt].buffer = InvalidBuffer;
 408         rdata[cnt].data = (GinPageIsLeaf(page)) ? ((char *) (btree->items + btree->curitem)) : ((char *) &(btree->pitem));
 409         rdata[cnt].len = sizeofitem;
 410         rdata[cnt].next = NULL;
 411
 412         if (GinPageIsLeaf(page))
 413         {
 414                 if (GinPageRightMost(page) && off > GinPageGetOpaque(page)->maxoff)
 415                 {
 416                         /* usually, create index... */
 417                         uint32          savedPos = btree->curitem;
 418
 419                         while (btree->curitem < btree->nitem)
 420                         {
 421                                 GinDataPageAddItemPointer(page, btree->items + btree->curitem, off);
 422                                 off++;
 423                                 btree->curitem++;
 424                         }
 425                         data.nitem = btree->curitem - savedPos;
 426                         rdata[cnt].len = sizeofitem * data.nitem;
 427                 }
 428                 else
 429                 {
 430                         GinDataPageAddItemPointer(page, btree->items + btree->curitem, off);
 431                         btree->curitem++;
 432                 }
 433         }
 434         else
 435                 GinDataPageAddPostingItem(page, &(btree->pitem), off);
 436
 437         return true;
 438 }
 439
 440 /*
 441  * split page and fills WAL record. original buffer(lbuf) leaves untouched,
 442  * returns shadow page of lbuf filled new data. In leaf page and build mode puts all
 443  * ItemPointers to pages. Also, in build mode splits data by way to full fulled
 444  * left page
 445  */
 446 static Page
 447 dataSplitPage(GinBtree btree, Buffer lbuf, Buffer rbuf, OffsetNumber off, XLogRecData **prdata)
 448 {
 449         char       *ptr;
 450         OffsetNumber separator;
 451         ItemPointer bound;
 452         Page            lpage = PageGetTempPageCopy(BufferGetPage(lbuf));
 453         bool            isleaf = GinPageIsLeaf(lpage);
 454         ItemPointerData oldbound = *GinDataPageGetRightBound(lpage);
 455         int                     sizeofitem = GinSizeOfDataPageItem(lpage);
 456         OffsetNumber maxoff = GinPageGetOpaque(lpage)->maxoff;
 457         Page            rpage = BufferGetPage(rbuf);
 458         Size            pageSize = PageGetPageSize(lpage);
 459         Size            freeSpace;
 460         uint32          nCopied = 1;
 461
 462         /* these must be static so they can be returned to caller */
 463         static ginxlogSplit data;
 464         static XLogRecData rdata[4];
 465         static char vector[2 * BLCKSZ];
 466
 467         GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
 468         freeSpace = GinDataPageGetFreeSpace(rpage);
 469
 470         *prdata = rdata;
 471         data.leftChildBlkno = (GinPageIsLeaf(lpage)) ?
 472                 InvalidOffsetNumber : PostingItemGetBlockNumber(&(btree->pitem));
 473         data.updateBlkno = dataPrepareData(btree, lpage, off);
 474
 475         if (isleaf)
 476         {
 477                 memcpy(vector,
 478                            GinDataPageGetItemPointer(lpage, FirstOffsetNumber),
 479                            maxoff * sizeof(ItemPointerData));
 480         }
 481         else
 482         {
 483                 memcpy(vector,
 484                            GinDataPageGetPostingItem(lpage, FirstOffsetNumber),
 485                            maxoff * sizeof(PostingItem));
 486         }
 487
 488         if (isleaf && GinPageRightMost(lpage) && off > GinPageGetOpaque(lpage)->maxoff)
 489         {
 490                 nCopied = 0;
 491                 while (btree->curitem < btree->nitem &&
 492                            maxoff * sizeof(ItemPointerData) < 2 * (freeSpace - sizeof(ItemPointerData)))
 493                 {
 494                         memcpy(vector + maxoff * sizeof(ItemPointerData),
 495                                    btree->items + btree->curitem,
 496                                    sizeof(ItemPointerData));
 497                         maxoff++;
 498                         nCopied++;
 499                         btree->curitem++;
 500                 }
 501         }
 502         else
 503         {
 504                 ptr = vector + (off - 1) * sizeofitem;
 505                 if (maxoff + 1 - off != 0)
 506                         memmove(ptr + sizeofitem, ptr, (maxoff - off + 1) * sizeofitem);
 507                 if (isleaf)
 508                 {
 509                         memcpy(ptr, btree->items + btree->curitem, sizeofitem);
 510                         btree->curitem++;
 511                 }
 512                 else
 513                         memcpy(ptr, &(btree->pitem), sizeofitem);
 514
 515                 maxoff++;
 516         }
 517
 518         /*
 519          * we assume that during index creation the table scanned from beginning
 520          * to end, so ItemPointers are in monotonically increasing order.
 521          */
 522         if (btree->isBuild && GinPageRightMost(lpage))
 523                 separator = freeSpace / sizeofitem;
 524         else
 525                 separator = maxoff / 2;
 526
 527         GinInitPage(rpage, GinPageGetOpaque(lpage)->flags, pageSize);
 528         GinInitPage(lpage, GinPageGetOpaque(rpage)->flags, pageSize);
 529
 530         if (isleaf)
 531                 memcpy(GinDataPageGetItemPointer(lpage, FirstOffsetNumber),
 532                            vector, separator * sizeof(ItemPointerData));
 533         else
 534                 memcpy(GinDataPageGetPostingItem(lpage, FirstOffsetNumber),
 535                            vector, separator * sizeof(PostingItem));
 536
 537         GinPageGetOpaque(lpage)->maxoff = separator;
 538         if (isleaf)
 539                 memcpy(GinDataPageGetItemPointer(rpage, FirstOffsetNumber),
 540                            vector + separator * sizeof(ItemPointerData),
 541                            (maxoff - separator) * sizeof(ItemPointerData));
 542         else
 543                 memcpy(GinDataPageGetPostingItem(rpage, FirstOffsetNumber),
 544                            vector + separator * sizeof(PostingItem),
 545                            (maxoff - separator) * sizeof(PostingItem));
 546
 547         GinPageGetOpaque(rpage)->maxoff = maxoff - separator;
 548
 549         /* set up right bound for left page */
 550         bound = GinDataPageGetRightBound(lpage);
 551         if (GinPageIsLeaf(lpage))
 552                 *bound = *GinDataPageGetItemPointer(lpage,
 553                                                                                         GinPageGetOpaque(lpage)->maxoff);
 554         else
 555                 *bound = GinDataPageGetPostingItem(lpage,
 556                                                                           GinPageGetOpaque(lpage)->maxoff)->key;
 557
 558         /* set up right bound for right page */
 559         bound = GinDataPageGetRightBound(rpage);
 560         *bound = oldbound;
 561
 562         data.node = btree->index->rd_node;
 563         data.rootBlkno = InvalidBlockNumber;
 564         data.lblkno = BufferGetBlockNumber(lbuf);
 565         data.rblkno = BufferGetBlockNumber(rbuf);
 566         data.separator = separator;
 567         data.nitem = maxoff;
 568         data.isData = TRUE;
 569         data.isLeaf = GinPageIsLeaf(lpage) ? TRUE : FALSE;
 570         data.isRootSplit = FALSE;
 571         data.rightbound = oldbound;
 572
 573         rdata[0].buffer = InvalidBuffer;
 574         rdata[0].data = (char *) &data;
 575         rdata[0].len = sizeof(ginxlogSplit);
 576         rdata[0].next = &rdata[1];
 577
 578         rdata[1].buffer = InvalidBuffer;
 579         rdata[1].data = vector;
 580         rdata[1].len = MAXALIGN(maxoff * sizeofitem);
 581         rdata[1].next = NULL;
 582
 583         /* Prepare a downlink tuple for insertion to the parent */
 584         PostingItemSetBlockNumber(&(btree->pitem), BufferGetBlockNumber(lbuf));
 585         btree->pitem.key = *GinDataPageGetRightBound(lpage);
 586         btree->rightblkno = BufferGetBlockNumber(rbuf);
 587
 588         return lpage;
 589 }
 590
 591 /*
 592  * Fills new root by right bound values from child.
 593  * Also called from ginxlog, should not use btree
 594  */
 595 void
 596 ginDataFillRoot(GinBtree btree, Buffer root, Buffer lbuf, Buffer rbuf)
 597 {
 598         Page            page = BufferGetPage(root),
 599                                 lpage = BufferGetPage(lbuf),
 600                                 rpage = BufferGetPage(rbuf);
 601         PostingItem li,
 602                                 ri;
 603
 604         li.key = *GinDataPageGetRightBound(lpage);
 605         PostingItemSetBlockNumber(&li, BufferGetBlockNumber(lbuf));
 606         GinDataPageAddPostingItem(page, &li, InvalidOffsetNumber);
 607
 608         ri.key = *GinDataPageGetRightBound(rpage);
 609         PostingItemSetBlockNumber(&ri, BufferGetBlockNumber(rbuf));
 610         GinDataPageAddPostingItem(page, &ri, InvalidOffsetNumber);
 611 }
 612
 613 /*
 614  * Creates new posting tree containing the given TIDs. Returns the page
 615  * number of the root of the new posting tree.
 616  *
 617  * items[] must be in sorted order with no duplicates.
 618  */
 619 BlockNumber
 620 createPostingTree(Relation index, ItemPointerData *items, uint32 nitems,
 621                                   GinStatsData *buildStats)
 622 {
 623         BlockNumber blkno;
 624         Buffer          buffer;
 625         Page            page;
 626         int                     nrootitems;
 627
 628         /* Calculate how many TIDs will fit on first page. */
 629         nrootitems = Min(nitems, GinMaxLeafDataItems);
 630
 631         /*
 632          * Create the root page.
 633          */
 634         buffer = GinNewBuffer(index);
 635         page = BufferGetPage(buffer);
 636         blkno = BufferGetBlockNumber(buffer);
 637
 638         START_CRIT_SECTION();
 639
 640         GinInitBuffer(buffer, GIN_DATA | GIN_LEAF);
 641         memcpy(GinDataPageGetData(page), items, sizeof(ItemPointerData) * nrootitems);
 642         GinPageGetOpaque(page)->maxoff = nrootitems;
 643
 644         MarkBufferDirty(buffer);
 645
 646         if (RelationNeedsWAL(index))
 647         {
 648                 XLogRecPtr      recptr;
 649                 XLogRecData rdata[2];
 650                 ginxlogCreatePostingTree data;
 651
 652                 data.node = index->rd_node;
 653                 data.blkno = blkno;
 654                 data.nitem = nrootitems;
 655
 656                 rdata[0].buffer = InvalidBuffer;
 657                 rdata[0].data = (char *) &data;
 658                 rdata[0].len = sizeof(ginxlogCreatePostingTree);
 659                 rdata[0].next = &rdata[1];
 660
 661                 rdata[1].buffer = InvalidBuffer;
 662                 rdata[1].data = (char *) items;
 663                 rdata[1].len = sizeof(ItemPointerData) * nrootitems;
 664                 rdata[1].next = NULL;
 665
 666                 recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_PTREE, rdata);
 667                 PageSetLSN(page, recptr);
 668         }
 669
 670         UnlockReleaseBuffer(buffer);
 671
 672         END_CRIT_SECTION();
 673
 674         /* During index build, count the newly-added data page */
 675         if (buildStats)
 676                 buildStats->nDataPages++;
 677
 678         /*
 679          * Add any remaining TIDs to the newly-created posting tree.
 680          */
 681         if (nitems > nrootitems)
 682         {
 683                 ginInsertItemPointers(index, blkno,
 684                                                           items + nrootitems,
 685                                                           nitems - nrootitems,
 686                                                           buildStats);
 687         }
 688
 689         return blkno;
 690 }
 691
 692 void
 693 ginPrepareDataScan(GinBtree btree, Relation index)
 694 {
 695         memset(btree, 0, sizeof(GinBtreeData));
 696
 697         btree->index = index;
 698
 699         btree->findChildPage = dataLocateItem;
 700         btree->getLeftMostChild = dataGetLeftMostPage;
 701         btree->isMoveRight = dataIsMoveRight;
 702         btree->findItem = dataLocateLeafItem;
 703         btree->findChildPtr = dataFindChildPtr;
 704         btree->placeToPage = dataPlaceToPage;
 705         btree->splitPage = dataSplitPage;
 706         btree->fillRoot = ginDataFillRoot;
 707
 708         btree->isData = TRUE;
 709         btree->isDelete = FALSE;
 710         btree->fullScan = FALSE;
 711         btree->isBuild = FALSE;
 712 }
 713
 714 /*
 715  * Inserts array of item pointers, may execute several tree scan (very rare)
 716  */
 717 void
 718 ginInsertItemPointers(Relation index, BlockNumber rootBlkno,
 719                                           ItemPointerData *items, uint32 nitem,
 720                                           GinStatsData *buildStats)
 721 {
 722         GinBtreeData btree;
 723         GinBtreeStack *stack;
 724
 725         ginPrepareDataScan(&btree, index);
 726         btree.isBuild = (buildStats != NULL);
 727         btree.items = items;
 728         btree.nitem = nitem;
 729         btree.curitem = 0;
 730
 731         while (btree.curitem < btree.nitem)
 732         {
 733                 stack = ginFindLeafPage(&btree, rootBlkno, false);
 734
 735                 if (btree.findItem(&btree, stack))
 736                 {
 737                         /*
 738                          * btree.items[btree.curitem] already exists in index
 739                          */
 740                         btree.curitem++;
 741                         LockBuffer(stack->buffer, GIN_UNLOCK);
 742                         freeGinBtreeStack(stack);
 743                 }
 744                 else
 745                         ginInsertValue(&btree, stack, buildStats);
 746         }
 747 }
 748
 749 /*
 750  * Starts a new scan on a posting tree.
 751  */
 752 GinBtreeStack *
 753 ginScanBeginPostingTree(Relation index, BlockNumber rootBlkno)
 754 {
 755         GinBtreeData btree;
 756         GinBtreeStack *stack;
 757
 758         ginPrepareDataScan(&btree, index);
 759
 760         btree.fullScan = TRUE;
 761
 762         stack = ginFindLeafPage(&btree, rootBlkno, TRUE);
 763
 764         return stack;
 765 }