src/backend/access/gin/ginget.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * ginget.c
   4  *        fetch tuples from a GIN scan.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2008, 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 "access/relscan.h"
  19 #include "catalog/index.h"
  20 #include "miscadmin.h"
  21 #include "storage/bufmgr.h"
  22 #include "utils/datum.h"
  23 #include "utils/memutils.h"
  24
  25
  26 /*
  27  * Tries to refind previously taken ItemPointer on page.
  28  */
  29 static bool
  30 findItemInPage(Page page, ItemPointer item, OffsetNumber *off)
  31 {
  32         OffsetNumber maxoff = GinPageGetOpaque(page)->maxoff;
  33         int                     res;
  34
  35         if (GinPageGetOpaque(page)->flags & GIN_DELETED)
  36                 /* page was deleted by concurrent  vacuum */
  37                 return false;
  38
  39         /*
  40          * scan page to find equal or first greater value
  41          */
  42
  43         for (*off = FirstOffsetNumber; *off <= maxoff; (*off)++)
  44         {
  45                 res = compareItemPointers(item, (ItemPointer) GinDataPageGetItem(page, *off));
  46
  47                 if (res <= 0)
  48                         return true;
  49         }
  50
  51         return false;
  52 }
  53
  54 /*
  55  * Goes to the next page if current offset is outside of bounds
  56  */
  57 static bool
  58 moveRightIfItNeeded( GinBtreeData *btree, GinBtreeStack *stack )
  59 {
  60         Page page = BufferGetPage(stack->buffer);
  61
  62         if ( stack->off > PageGetMaxOffsetNumber(page) )
  63         {
  64                 /*
  65                  * We scanned the whole page, so we should take right page
  66                  */
  67                 stack->blkno = GinPageGetOpaque(page)->rightlink;
  68
  69                 if ( GinPageRightMost(page) )
  70                         return false;  /* no more pages */
  71
  72                 LockBuffer(stack->buffer, GIN_UNLOCK);
  73                 stack->buffer = ReleaseAndReadBuffer(stack->buffer, btree->index, stack->blkno);
  74                 LockBuffer(stack->buffer, GIN_SHARE);
  75                 stack->off = FirstOffsetNumber;
  76         }
  77
  78         return true;
  79 }
  80
  81 /*
  82  * Does fullscan of posting tree and saves ItemPointers
  83  * in scanEntry->partialMatch TIDBitmap
  84  */
  85 static void
  86 scanForItems( Relation index, GinScanEntry scanEntry, BlockNumber rootPostingTree )
  87 {
  88         GinPostingTreeScan *gdi;
  89         Buffer                          buffer;
  90         Page                            page;
  91         BlockNumber                     blkno;
  92
  93         gdi = prepareScanPostingTree(index, rootPostingTree, TRUE);
  94
  95         buffer = scanBeginPostingTree(gdi);
  96         IncrBufferRefCount(buffer); /* prevent unpin in freeGinBtreeStack */
  97
  98         freeGinBtreeStack(gdi->stack);
  99         pfree(gdi);
 100
 101         /*
 102          * Goes through all leaves
 103          */
 104         for(;;)
 105         {
 106                 page = BufferGetPage(buffer);
 107
 108                 if ((GinPageGetOpaque(page)->flags & GIN_DELETED) == 0 && GinPageGetOpaque(page)->maxoff >= FirstOffsetNumber )
 109                 {
 110                         tbm_add_tuples( scanEntry->partialMatch,
 111                                                         (ItemPointer)GinDataPageGetItem(page, FirstOffsetNumber),
 112                                                         GinPageGetOpaque(page)->maxoff, false);
 113                         scanEntry->predictNumberResult += GinPageGetOpaque(page)->maxoff;
 114                 }
 115
 116                 blkno = GinPageGetOpaque(page)->rightlink;
 117                 if ( GinPageRightMost(page) )
 118                 {
 119                         UnlockReleaseBuffer(buffer);
 120                         return;  /* no more pages */
 121                 }
 122
 123                 LockBuffer(buffer, GIN_UNLOCK);
 124                 buffer = ReleaseAndReadBuffer(buffer, index, blkno);
 125                 LockBuffer(buffer, GIN_SHARE);
 126         }
 127 }
 128
 129 /*
 130  * Collects all ItemPointer into the TIDBitmap struct
 131  * for entries partially matched to search entry.
 132  *
 133  * Returns true if done, false if it's needed to restart scan from scratch
 134  */
 135 static bool
 136 computePartialMatchList( GinBtreeData *btree, GinBtreeStack *stack, GinScanEntry scanEntry )
 137 {
 138         Page            page;
 139         IndexTuple  itup;
 140         Datum           idatum;
 141         int32           cmp;
 142
 143         scanEntry->partialMatch = tbm_create( work_mem * 1024L );
 144
 145         for(;;)
 146         {
 147                 /*
 148                  * stack->off points to the interested entry, buffer is already locked
 149                  */
 150                 if ( moveRightIfItNeeded(btree, stack) == false )
 151                         return true;
 152
 153                 page = BufferGetPage(stack->buffer);
 154                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
 155
 156                 /*
 157                  * If tuple stores another attribute then stop scan
 158                  */
 159                 if ( gintuple_get_attrnum( btree->ginstate, itup ) != scanEntry->attnum )
 160                         return true;
 161
 162                 idatum = gin_index_getattr( btree->ginstate, itup );
 163
 164
 165                 /*----------
 166                  * Check of partial match.
 167                  * case cmp == 0 => match
 168                  * case cmp > 0 => not match and finish scan
 169                  * case cmp < 0 => not match and continue scan
 170                  *----------
 171                  */
 172         cmp = DatumGetInt32(FunctionCall3(&btree->ginstate->comparePartialFn[scanEntry->attnum-1],
 173                                                                                   scanEntry->entry,
 174                                                                                   idatum,
 175                                                                                   UInt16GetDatum(scanEntry->strategy)));
 176
 177                 if ( cmp > 0 )
 178                         return true;
 179                 else if ( cmp < 0 )
 180                 {
 181                         stack->off++;
 182                         continue;
 183                 }
 184
 185                 if ( GinIsPostingTree(itup) )
 186                 {
 187                         BlockNumber rootPostingTree = GinGetPostingTree(itup);
 188                         Datum           newDatum,
 189                                                 savedDatum = datumCopy (
 190                                                                                 idatum,
 191                                                                                 btree->ginstate->origTupdesc->attrs[scanEntry->attnum-1]->attbyval,
 192                                                                                 btree->ginstate->origTupdesc->attrs[scanEntry->attnum-1]->attlen
 193                                                                         );
 194                         /*
 195                          * We should unlock current page (but not unpin) during
 196                          * tree scan to prevent deadlock with vacuum processes.
 197                          *
 198                          * We save current entry value (savedDatum) to be able to refind
 199                          * our tuple after re-locking
 200                          */
 201                         LockBuffer(stack->buffer, GIN_UNLOCK);
 202                         scanForItems( btree->index, scanEntry, rootPostingTree );
 203
 204                         /*
 205                          * We lock again the entry page and while it was unlocked
 206                          * insert might occured, so we need to refind our position
 207                          */
 208                         LockBuffer(stack->buffer, GIN_SHARE);
 209                         page = BufferGetPage(stack->buffer);
 210                         if ( !GinPageIsLeaf(page) )
 211                         {
 212                                 /*
 213                                  * Root page becomes non-leaf while we unlock it. We
 214                                  * will start again, this situation doesn't cause
 215                                  * often - root can became a non-leaf only one per
 216                                  * life of index.
 217                                  */
 218
 219                                 return false;
 220                         }
 221
 222                         for(;;)
 223                         {
 224                                 if ( moveRightIfItNeeded(btree, stack) == false )
 225                                         elog(ERROR, "lost saved point in index"); /* must not happen !!! */
 226
 227                                 page = BufferGetPage(stack->buffer);
 228                                 itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stack->off));
 229                                 newDatum = gin_index_getattr( btree->ginstate, itup );
 230
 231                                 if ( gintuple_get_attrnum( btree->ginstate, itup ) != scanEntry->attnum )
 232                                         elog(ERROR, "lost saved point in index"); /* must not happen !!! */
 233
 234                                 if ( compareEntries(btree->ginstate, scanEntry->attnum, newDatum, savedDatum) == 0 )
 235                                 {
 236                                         /* Found!  */
 237                                         if ( btree->ginstate->origTupdesc->attrs[scanEntry->attnum-1]->attbyval == false )
 238                                                 pfree( DatumGetPointer(savedDatum) );
 239                                         break;
 240                                 }
 241
 242                                 stack->off++;
 243                         }
 244                 }
 245                 else
 246                 {
 247                         tbm_add_tuples( scanEntry->partialMatch, GinGetPosting(itup),  GinGetNPosting(itup), false);
 248                         scanEntry->predictNumberResult +=  GinGetNPosting(itup);
 249                 }
 250
 251                 /*
 252                  * Ok, we save ItemPointers, go to the next entry
 253                  */
 254                 stack->off++;
 255         }
 256
 257         return true;
 258 }
 259
 260 /*
 261  * Start* functions setup begining state of searches: finds correct buffer and pins it.
 262  */
 263 static void
 264 startScanEntry(Relation index, GinState *ginstate, GinScanEntry entry)
 265 {
 266         GinBtreeData    btreeEntry;
 267         GinBtreeStack  *stackEntry;
 268         Page                    page;
 269         bool                    needUnlock = TRUE;
 270
 271         if (entry->master != NULL)
 272         {
 273                 entry->isFinished = entry->master->isFinished;
 274                 return;
 275         }
 276
 277         /*
 278          * we should find entry, and begin scan of posting tree
 279          * or just store posting list in memory
 280          */
 281
 282         prepareEntryScan(&btreeEntry, index, entry->attnum, entry->entry, ginstate);
 283         btreeEntry.searchMode = TRUE;
 284         stackEntry = ginFindLeafPage(&btreeEntry, NULL);
 285         page = BufferGetPage(stackEntry->buffer);
 286
 287         entry->isFinished = TRUE;
 288         entry->buffer = InvalidBuffer;
 289         entry->offset = InvalidOffsetNumber;
 290         entry->list = NULL;
 291         entry->nlist = 0;
 292         entry->partialMatch = NULL;
 293         entry->partialMatchResult = NULL;
 294         entry->reduceResult = FALSE;
 295         entry->predictNumberResult = 0;
 296
 297         if ( entry->isPartialMatch )
 298         {
 299                 /*
 300                  * btreeEntry.findItem points to the first equal or greater value
 301                  * than needed. So we will scan further and collect all
 302                  * ItemPointers
 303                  */
 304                 btreeEntry.findItem(&btreeEntry, stackEntry);
 305                 if ( computePartialMatchList( &btreeEntry, stackEntry, entry ) == false )
 306                 {
 307                         /*
 308                          * GIN tree was seriously restructured, so we will
 309                          * cleanup all found data and rescan. See comments near
 310                          * 'return false' in computePartialMatchList()
 311                          */
 312                         if ( entry->partialMatch )
 313                         {
 314                                 tbm_free( entry->partialMatch );
 315                                 entry->partialMatch = NULL;
 316                         }
 317                         LockBuffer(stackEntry->buffer, GIN_UNLOCK);
 318                         freeGinBtreeStack(stackEntry);
 319
 320                         startScanEntry(index, ginstate, entry);
 321                         return;
 322                 }
 323
 324                 if ( entry->partialMatch && !tbm_is_empty(entry->partialMatch) )
 325                 {
 326                         tbm_begin_iterate(entry->partialMatch);
 327                         entry->isFinished = FALSE;
 328                 }
 329         }
 330         else if (btreeEntry.findItem(&btreeEntry, stackEntry))
 331         {
 332                 IndexTuple      itup = (IndexTuple) PageGetItem(page, PageGetItemId(page, stackEntry->off));
 333
 334                 if (GinIsPostingTree(itup))
 335                 {
 336                         BlockNumber rootPostingTree = GinGetPostingTree(itup);
 337                         GinPostingTreeScan *gdi;
 338                         Page            page;
 339
 340                         /*
 341                          * We should unlock entry page before make deal with
 342                          * posting tree to prevent deadlocks with vacuum processes.
 343                          * Because entry is never deleted from page and posting tree is
 344                          * never reduced to the posting list, we can unlock page after
 345                          * getting BlockNumber of root of posting tree.
 346                          */
 347                         LockBuffer(stackEntry->buffer, GIN_UNLOCK);
 348                         needUnlock = FALSE;
 349                         gdi = prepareScanPostingTree(index, rootPostingTree, TRUE);
 350
 351                         entry->buffer = scanBeginPostingTree(gdi);
 352                         /*
 353                          * We keep buffer pinned because we need to prevent deletition
 354                          * page during scan. See GIN's vacuum implementation. RefCount
 355                          * is increased to keep buffer pinned after freeGinBtreeStack() call.
 356                          */
 357                         IncrBufferRefCount(entry->buffer);
 358
 359                         page = BufferGetPage(entry->buffer);
 360                         entry->predictNumberResult = gdi->stack->predictNumber * GinPageGetOpaque(page)->maxoff;
 361
 362                         /*
 363                          * Keep page content in memory to prevent durable page locking
 364                          */
 365                         entry->list = (ItemPointerData *) palloc( BLCKSZ );
 366                         entry->nlist = GinPageGetOpaque(page)->maxoff;
 367                         memcpy( entry->list, GinDataPageGetItem(page, FirstOffsetNumber),
 368                                                 GinPageGetOpaque(page)->maxoff * sizeof(ItemPointerData) );
 369
 370                         LockBuffer(entry->buffer, GIN_UNLOCK);
 371                         freeGinBtreeStack(gdi->stack);
 372                         pfree(gdi);
 373                         entry->isFinished = FALSE;
 374                 }
 375                 else if (GinGetNPosting(itup) > 0)
 376                 {
 377                         entry->nlist = GinGetNPosting(itup);
 378                         entry->list = (ItemPointerData *) palloc(sizeof(ItemPointerData) * entry->nlist);
 379                         memcpy(entry->list, GinGetPosting(itup), sizeof(ItemPointerData) * entry->nlist);
 380                         entry->isFinished = FALSE;
 381                 }
 382         }
 383
 384         if (needUnlock)
 385                         LockBuffer(stackEntry->buffer, GIN_UNLOCK);
 386         freeGinBtreeStack(stackEntry);
 387 }
 388
 389 static void
 390 startScanKey(Relation index, GinState *ginstate, GinScanKey key)
 391 {
 392         uint32          i;
 393
 394         if (!key->firstCall)
 395                 return;
 396
 397         for (i = 0; i < key->nentries; i++)
 398                 startScanEntry(index, ginstate, key->scanEntry + i);
 399
 400         memset(key->entryRes, TRUE, sizeof(bool) * key->nentries);
 401         key->isFinished = FALSE;
 402         key->firstCall = FALSE;
 403
 404         if (GinFuzzySearchLimit > 0)
 405         {
 406                 /*
 407                  * If all of keys more than threshold we will try to reduce
 408                  * result, we hope (and only hope, for intersection operation of
 409                  * array our supposition isn't true), that total result will not
 410                  * more than minimal predictNumberResult.
 411                  */
 412
 413                 for (i = 0; i < key->nentries; i++)
 414                         if (key->scanEntry[i].predictNumberResult <= key->nentries * GinFuzzySearchLimit)
 415                                 return;
 416
 417                 for (i = 0; i < key->nentries; i++)
 418                         if (key->scanEntry[i].predictNumberResult > key->nentries * GinFuzzySearchLimit)
 419                         {
 420                                 key->scanEntry[i].predictNumberResult /= key->nentries;
 421                                 key->scanEntry[i].reduceResult = TRUE;
 422                         }
 423         }
 424 }
 425
 426 static void
 427 startScan(IndexScanDesc scan)
 428 {
 429         uint32          i;
 430         GinScanOpaque so = (GinScanOpaque) scan->opaque;
 431
 432         for (i = 0; i < so->nkeys; i++)
 433                 startScanKey(scan->indexRelation, &so->ginstate, so->keys + i);
 434 }
 435
 436 /*
 437  * Gets next ItemPointer from PostingTree. Note, that we copy
 438  * page into GinScanEntry->list array and unlock page, but keep it pinned
 439  * to prevent interference with vacuum
 440  */
 441 static void
 442 entryGetNextItem(Relation index, GinScanEntry entry)
 443 {
 444         Page            page;
 445         BlockNumber blkno;
 446
 447         for(;;)
 448         {
 449                 entry->offset++;
 450
 451                 if (entry->offset <= entry->nlist)
 452                 {
 453                         entry->curItem = entry->list[entry->offset - 1];
 454                         return;
 455                 }
 456
 457                 LockBuffer(entry->buffer, GIN_SHARE);
 458                 page = BufferGetPage(entry->buffer);
 459                 for(;;)
 460                 {
 461                         /*
 462                          * It's needed to go by right link. During that we should refind
 463                          * first ItemPointer greater that stored
 464                          */
 465
 466                         blkno = GinPageGetOpaque(page)->rightlink;
 467
 468                         LockBuffer(entry->buffer, GIN_UNLOCK);
 469                         if (blkno == InvalidBlockNumber)
 470                         {
 471                                 ReleaseBuffer(entry->buffer);
 472                                 ItemPointerSet(&entry->curItem, InvalidBlockNumber, InvalidOffsetNumber);
 473                                 entry->buffer = InvalidBuffer;
 474                                 entry->isFinished = TRUE;
 475                                 return;
 476                         }
 477
 478                         entry->buffer = ReleaseAndReadBuffer(entry->buffer, index, blkno);
 479                         LockBuffer(entry->buffer, GIN_SHARE);
 480                         page = BufferGetPage(entry->buffer);
 481
 482                         entry->offset = InvalidOffsetNumber;
 483                         if (!ItemPointerIsValid(&entry->curItem) || findItemInPage(page, &entry->curItem, &entry->offset))
 484                         {
 485                                 /*
 486                                  * Found position equal to or greater than stored
 487                                  */
 488                                 entry->nlist = GinPageGetOpaque(page)->maxoff;
 489                                 memcpy( entry->list, GinDataPageGetItem(page, FirstOffsetNumber),
 490                                                         GinPageGetOpaque(page)->maxoff * sizeof(ItemPointerData) );
 491
 492                                 LockBuffer(entry->buffer, GIN_UNLOCK);
 493
 494                                 if ( !ItemPointerIsValid(&entry->curItem) ||
 495                                          compareItemPointers( &entry->curItem, entry->list + entry->offset - 1 ) == 0 )
 496                                 {
 497                                         /*
 498                                          * First pages are deleted or empty, or we found exact position,
 499                                          * so break inner loop and continue outer one.
 500                                          */
 501
 502                                          break;
 503                                 }
 504
 505                                 /*
 506                                  * Find greater than entry->curItem position, store it.
 507                                  */
 508                                 entry->curItem = entry->list[entry->offset - 1];
 509
 510                                 return;
 511                         }
 512                 }
 513         }
 514 }
 515
 516 #define gin_rand() (((double) random()) / ((double) MAX_RANDOM_VALUE))
 517 #define dropItem(e) ( gin_rand() > ((double)GinFuzzySearchLimit)/((double)((e)->predictNumberResult)) )
 518
 519 /*
 520  * Sets entry->curItem to new found heap item pointer for one
 521  * entry of one scan key
 522  */
 523 static bool
 524 entryGetItem(Relation index, GinScanEntry entry)
 525 {
 526         if (entry->master)
 527         {
 528                 entry->isFinished = entry->master->isFinished;
 529                 entry->curItem = entry->master->curItem;
 530         }
 531         else if ( entry->partialMatch )
 532         {
 533                 do
 534                 {
 535                         if ( entry->partialMatchResult == NULL || entry->offset >= entry->partialMatchResult->ntuples )
 536                         {
 537                                 entry->partialMatchResult = tbm_iterate( entry->partialMatch );
 538
 539                                 if ( entry->partialMatchResult == NULL )
 540                                 {
 541                                         ItemPointerSet(&entry->curItem, InvalidBlockNumber, InvalidOffsetNumber);
 542                                         entry->isFinished = TRUE;
 543                                         break;
 544                                 }
 545                                 else if ( entry->partialMatchResult->ntuples < 0 )
 546                                 {
 547                                         /* bitmap became lossy */
 548                                         ereport(ERROR,
 549                                                         (errcode(ERRCODE_OUT_OF_MEMORY),
 550                                                         errmsg("not enough memory to store result of partial match operator" ),
 551                                                         errhint("Increase the \"work_mem\" parameter.")));
 552                                 }
 553                                 entry->offset = 0;
 554                         }
 555
 556                         ItemPointerSet(&entry->curItem,
 557                                                         entry->partialMatchResult->blockno,
 558                                                         entry->partialMatchResult->offsets[ entry->offset ]);
 559                         entry->offset ++;
 560
 561                 } while (entry->isFinished == FALSE && entry->reduceResult == TRUE && dropItem(entry));
 562         }
 563         else if (!BufferIsValid(entry->buffer))
 564         {
 565                 entry->offset++;
 566                 if (entry->offset <= entry->nlist)
 567                         entry->curItem = entry->list[entry->offset - 1];
 568                 else
 569                 {
 570                         ItemPointerSet(&entry->curItem, InvalidBlockNumber, InvalidOffsetNumber);
 571                         entry->isFinished = TRUE;
 572                 }
 573         }
 574         else
 575         {
 576                 do
 577                 {
 578                         entryGetNextItem(index, entry);
 579                 } while (entry->isFinished == FALSE && entry->reduceResult == TRUE && dropItem(entry));
 580         }
 581
 582         return entry->isFinished;
 583 }
 584
 585 /*
 586  * restart from saved position. Actually it's needed only for
 587  * partial match. function is called only by ginrestpos()
 588  */
 589 void
 590 ginrestartentry(GinScanEntry entry)
 591 {
 592         ItemPointerData stopItem = entry->curItem;
 593         bool savedReduceResult;
 594
 595         if ( entry->master || entry->partialMatch == NULL )
 596                 return; /* entry is slave or not a partial match type*/
 597
 598         if ( entry->isFinished )
 599                 return; /* entry was finished before ginmarkpos() call */
 600
 601         if ( ItemPointerGetBlockNumber(&stopItem) == InvalidBlockNumber )
 602                 return; /* entry  wasn't began before ginmarkpos() call */
 603
 604         /*
 605          * Reset iterator
 606          */
 607         tbm_begin_iterate( entry->partialMatch );
 608         entry->partialMatchResult = NULL;
 609         entry->offset = 0;
 610
 611         /*
 612          * Temporary reset reduceResult flag to guarantee refinding
 613          * of curItem
 614          */
 615         savedReduceResult = entry->reduceResult;
 616         entry->reduceResult = FALSE;
 617
 618         do
 619         {
 620                 /*
 621                  * We can use null instead of index because
 622                  * partial match doesn't use it
 623                  */
 624                 if ( entryGetItem( NULL, entry ) == false )
 625                         elog(ERROR, "cannot refind scan position"); /* must not be here! */
 626         } while( compareItemPointers( &stopItem, &entry->curItem ) != 0 );
 627
 628         Assert( entry->isFinished == FALSE );
 629
 630         entry->reduceResult = savedReduceResult;
 631 }
 632
 633 /*
 634  * Sets key->curItem to new found heap item pointer for one scan key
 635  * Returns isFinished, ie TRUE means we did NOT get a new item pointer!
 636  * Also, *keyrecheck is set true if recheck is needed for this scan key.
 637  */
 638 static bool
 639 keyGetItem(Relation index, GinState *ginstate, MemoryContext tempCtx,
 640                    GinScanKey key, bool *keyrecheck)
 641 {
 642         uint32          i;
 643         GinScanEntry entry;
 644         bool            res;
 645         MemoryContext oldCtx;
 646
 647         if (key->isFinished)
 648                 return TRUE;
 649
 650         do
 651         {
 652                 /*
 653                  * move forward from previously value and set new curItem, which is
 654                  * minimal from entries->curItems
 655                  */
 656                 ItemPointerSetMax(&key->curItem);
 657                 for (i = 0; i < key->nentries; i++)
 658                 {
 659                         entry = key->scanEntry + i;
 660
 661                         if (key->entryRes[i])
 662                         {
 663                                 if (entry->isFinished == FALSE && entryGetItem(index, entry) == FALSE)
 664                                 {
 665                                         if (compareItemPointers(&entry->curItem, &key->curItem) < 0)
 666                                                 key->curItem = entry->curItem;
 667                                 }
 668                                 else
 669                                         key->entryRes[i] = FALSE;
 670                         }
 671                         else if (entry->isFinished == FALSE)
 672                         {
 673                                 if (compareItemPointers(&entry->curItem, &key->curItem) < 0)
 674                                         key->curItem = entry->curItem;
 675                         }
 676                 }
 677
 678                 if (ItemPointerIsMax(&key->curItem))
 679                 {
 680                         /* all entries are finished */
 681                         key->isFinished = TRUE;
 682                         return TRUE;
 683                 }
 684
 685                 /*
 686                  * if key->nentries == 1 then the consistentFn should always succeed,
 687                  * but we must call it anyway to find out the recheck status.
 688                  */
 689
 690                 /* setting up array for consistentFn */
 691                 for (i = 0; i < key->nentries; i++)
 692                 {
 693                         entry = key->scanEntry + i;
 694
 695                         if (entry->isFinished == FALSE &&
 696                                 compareItemPointers(&entry->curItem, &key->curItem) == 0)
 697                                 key->entryRes[i] = TRUE;
 698                         else
 699                                 key->entryRes[i] = FALSE;
 700                 }
 701
 702                 /*
 703                  * Initialize *keyrecheck in case the consistentFn doesn't know it
 704                  * should set it.  The safe assumption in that case is to force
 705                  * recheck.
 706                  */
 707                 *keyrecheck = true;
 708
 709                 oldCtx = MemoryContextSwitchTo(tempCtx);
 710                 res = DatumGetBool(FunctionCall4(&ginstate->consistentFn[key->attnum-1],
 711                                                                                  PointerGetDatum(key->entryRes),
 712                                                                                  UInt16GetDatum(key->strategy),
 713                                                                                  key->query,
 714                                                                                  PointerGetDatum(keyrecheck)));
 715                 MemoryContextSwitchTo(oldCtx);
 716                 MemoryContextReset(tempCtx);
 717         } while (!res);
 718
 719         return FALSE;
 720 }
 721
 722 /*
 723  * Get heap item pointer from scan
 724  * returns true if found
 725  */
 726 static bool
 727 scanGetItem(IndexScanDesc scan, ItemPointerData *item, bool *recheck)
 728 {
 729         GinScanOpaque so = (GinScanOpaque) scan->opaque;
 730         uint32          i;
 731         bool            keyrecheck;
 732
 733         /*
 734          * We return recheck = true if any of the keyGetItem calls return
 735          * keyrecheck = true.  Note that because the second loop might advance
 736          * some keys, this could theoretically be too conservative.  In practice
 737          * though, we expect that a consistentFn's recheck result will depend
 738          * only on the operator and the query, so for any one key it should
 739          * stay the same regardless of advancing to new items.  So it's not
 740          * worth working harder.
 741          */
 742         *recheck = false;
 743
 744         ItemPointerSetMin(item);
 745         for (i = 0; i < so->nkeys; i++)
 746         {
 747                 GinScanKey      key = so->keys + i;
 748
 749                 if (keyGetItem(scan->indexRelation, &so->ginstate, so->tempCtx,
 750                                            key, &keyrecheck))
 751                         return FALSE;           /* finished one of keys */
 752                 if (compareItemPointers(item, &key->curItem) < 0)
 753                         *item = key->curItem;
 754                 *recheck |= keyrecheck;
 755         }
 756
 757         for (i = 1; i <= so->nkeys; i++)
 758         {
 759                 GinScanKey      key = so->keys + i - 1;
 760
 761                 for (;;)
 762                 {
 763                         int                     cmp = compareItemPointers(item, &key->curItem);
 764
 765                         if (cmp == 0)
 766                                 break;
 767                         else if (cmp > 0)
 768                         {
 769                                 if (keyGetItem(scan->indexRelation, &so->ginstate, so->tempCtx,
 770                                                            key, &keyrecheck))
 771                                         return FALSE;           /* finished one of keys */
 772                                 *recheck |= keyrecheck;
 773                         }
 774                         else
 775                         {                                       /* returns to begin */
 776                                 *item = key->curItem;
 777                                 i = 0;
 778                                 break;
 779                         }
 780                 }
 781         }
 782
 783         return TRUE;
 784 }
 785
 786 #define GinIsNewKey(s)          ( ((GinScanOpaque) scan->opaque)->keys == NULL )
 787 #define GinIsVoidRes(s)         ( ((GinScanOpaque) scan->opaque)->isVoidRes == true )
 788
 789 Datum
 790 gingetbitmap(PG_FUNCTION_ARGS)
 791 {
 792         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 793         TIDBitmap *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
 794         int64           ntids;
 795
 796         if (GinIsNewKey(scan))
 797                 newScanKey(scan);
 798
 799         if (GinIsVoidRes(scan))
 800                 PG_RETURN_INT64(0);
 801
 802         startScan(scan);
 803
 804         ntids = 0;
 805         for (;;)
 806         {
 807                 ItemPointerData iptr;
 808                 bool            recheck;
 809
 810                 CHECK_FOR_INTERRUPTS();
 811
 812                 if (!scanGetItem(scan, &iptr, &recheck))
 813                         break;
 814
 815                 tbm_add_tuples(tbm, &iptr, 1, recheck);
 816                 ntids++;
 817         }
 818
 819         PG_RETURN_INT64(ntids);
 820 }
 821
 822 Datum
 823 gingettuple(PG_FUNCTION_ARGS)
 824 {
 825         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 826         ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1);
 827         bool            res;
 828
 829         if (dir != ForwardScanDirection)
 830                 elog(ERROR, "GIN doesn't support other scan directions than forward");
 831
 832         if (GinIsNewKey(scan))
 833                 newScanKey(scan);
 834
 835         if (GinIsVoidRes(scan))
 836                 PG_RETURN_BOOL(false);
 837
 838         startScan(scan);
 839         res = scanGetItem(scan, &scan->xs_ctup.t_self, &scan->xs_recheck);
 840
 841         PG_RETURN_BOOL(res);
 842 }