granicus.if.org Git - postgresql/blob - src/backend/access/gist/gistget.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * gistget.c
   4  *        fetch tuples from a GiST scan.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        src/backend/access/gist/gistget.c
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15 #include "postgres.h"
  16
  17 #include "access/gist_private.h"
  18 #include "access/relscan.h"
  19 #include "catalog/pg_type.h"
  20 #include "miscadmin.h"
  21 #include "pgstat.h"
  22 #include "lib/pairingheap.h"
  23 #include "utils/builtins.h"
  24 #include "utils/memutils.h"
  25 #include "utils/rel.h"
  26
  27 /*
  28  * gistkillitems() -- set LP_DEAD state for items an indexscan caller has
  29  * told us were killed.
  30  *
  31  * We re-read page here, so it's important to check page LSN. If the page
  32  * has been modified since the last read (as determined by LSN), we cannot
  33  * flag any entries because it is possible that the old entry was vacuumed
  34  * away and the TID was re-used by a completely different heap tuple.
  35  */
  36 static void
  37 gistkillitems(IndexScanDesc scan)
  38 {
  39         GISTScanOpaque  so = (GISTScanOpaque) scan->opaque;
  40         Buffer                  buffer;
  41         Page                    page;
  42         OffsetNumber    offnum;
  43         ItemId                  iid;
  44         int                             i;
  45         bool                    killedsomething = false;
  46
  47         Assert(so->curBlkno != InvalidBlockNumber);
  48         Assert(!XLogRecPtrIsInvalid(so->curPageLSN));
  49         Assert(so->killedItems != NULL);
  50
  51         buffer = ReadBuffer(scan->indexRelation, so->curBlkno);
  52         if (!BufferIsValid(buffer))
  53                 return;
  54
  55         LockBuffer(buffer, GIST_SHARE);
  56         gistcheckpage(scan->indexRelation, buffer);
  57         page = BufferGetPage(buffer);
  58
  59         /*
  60          * If page LSN differs it means that the page was modified since the last read.
  61          * killedItems could be not valid so LP_DEAD hints applying is not safe.
  62          */
  63         if(PageGetLSN(page) != so->curPageLSN)
  64         {
  65                 UnlockReleaseBuffer(buffer);
  66                 so->numKilled = 0; /* reset counter */
  67                 return;
  68         }
  69
  70         Assert(GistPageIsLeaf(page));
  71
  72         /*
  73          * Mark all killedItems as dead. We need no additional recheck,
  74          * because, if page was modified, pageLSN must have changed.
  75          */
  76         for (i = 0; i < so->numKilled; i++)
  77         {
  78                 offnum = so->killedItems[i];
  79                 iid = PageGetItemId(page, offnum);
  80                 ItemIdMarkDead(iid);
  81                 killedsomething = true;
  82         }
  83
  84         if (killedsomething)
  85         {
  86                 GistMarkPageHasGarbage(page);
  87                 MarkBufferDirtyHint(buffer, true);
  88         }
  89
  90         UnlockReleaseBuffer(buffer);
  91
  92         /*
  93          * Always reset the scan state, so we don't look for same items on other
  94          * pages.
  95          */
  96         so->numKilled = 0;
  97 }
  98
  99 /*
 100  * gistindex_keytest() -- does this index tuple satisfy the scan key(s)?
 101  *
 102  * The index tuple might represent either a heap tuple or a lower index page,
 103  * depending on whether the containing page is a leaf page or not.
 104  *
 105  * On success return for a heap tuple, *recheck_p is set to indicate whether
 106  * the quals need to be rechecked.  We recheck if any of the consistent()
 107  * functions request it.  recheck is not interesting when examining a non-leaf
 108  * entry, since we must visit the lower index page if there's any doubt.
 109  * Similarly, *recheck_distances_p is set to indicate whether the distances
 110  * need to be rechecked, and it is also ignored for non-leaf entries.
 111  *
 112  * If we are doing an ordered scan, so->distances[] is filled with distance
 113  * data from the distance() functions before returning success.
 114  *
 115  * We must decompress the key in the IndexTuple before passing it to the
 116  * sk_funcs (which actually are the opclass Consistent or Distance methods).
 117  *
 118  * Note that this function is always invoked in a short-lived memory context,
 119  * so we don't need to worry about cleaning up allocated memory, either here
 120  * or in the implementation of any Consistent or Distance methods.
 121  */
 122 static bool
 123 gistindex_keytest(IndexScanDesc scan,
 124                                   IndexTuple tuple,
 125                                   Page page,
 126                                   OffsetNumber offset,
 127                                   bool *recheck_p,
 128                                   bool *recheck_distances_p)
 129 {
 130         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 131         GISTSTATE  *giststate = so->giststate;
 132         ScanKey         key = scan->keyData;
 133         int                     keySize = scan->numberOfKeys;
 134         double     *distance_p;
 135         Relation        r = scan->indexRelation;
 136
 137         *recheck_p = false;
 138         *recheck_distances_p = false;
 139
 140         /*
 141          * If it's a leftover invalid tuple from pre-9.1, treat it as a match with
 142          * minimum possible distances.  This means we'll always follow it to the
 143          * referenced page.
 144          */
 145         if (GistTupleIsInvalid(tuple))
 146         {
 147                 int                     i;
 148
 149                 if (GistPageIsLeaf(page))               /* shouldn't happen */
 150                         elog(ERROR, "invalid GiST tuple found on leaf page");
 151                 for (i = 0; i < scan->numberOfOrderBys; i++)
 152                         so->distances[i] = -get_float8_infinity();
 153                 return true;
 154         }
 155
 156         /* Check whether it matches according to the Consistent functions */
 157         while (keySize > 0)
 158         {
 159                 Datum           datum;
 160                 bool            isNull;
 161
 162                 datum = index_getattr(tuple,
 163                                                           key->sk_attno,
 164                                                           giststate->tupdesc,
 165                                                           &isNull);
 166
 167                 if (key->sk_flags & SK_ISNULL)
 168                 {
 169                         /*
 170                          * On non-leaf page we can't conclude that child hasn't NULL
 171                          * values because of assumption in GiST: union (VAL, NULL) is VAL.
 172                          * But if on non-leaf page key IS NULL, then all children are
 173                          * NULL.
 174                          */
 175                         if (key->sk_flags & SK_SEARCHNULL)
 176                         {
 177                                 if (GistPageIsLeaf(page) && !isNull)
 178                                         return false;
 179                         }
 180                         else
 181                         {
 182                                 Assert(key->sk_flags & SK_SEARCHNOTNULL);
 183                                 if (isNull)
 184                                         return false;
 185                         }
 186                 }
 187                 else if (isNull)
 188                 {
 189                         return false;
 190                 }
 191                 else
 192                 {
 193                         Datum           test;
 194                         bool            recheck;
 195                         GISTENTRY       de;
 196
 197                         gistdentryinit(giststate, key->sk_attno - 1, &de,
 198                                                    datum, r, page, offset,
 199                                                    FALSE, isNull);
 200
 201                         /*
 202                          * Call the Consistent function to evaluate the test.  The
 203                          * arguments are the index datum (as a GISTENTRY*), the comparison
 204                          * datum, the comparison operator's strategy number and subtype
 205                          * from pg_amop, and the recheck flag.
 206                          *
 207                          * (Presently there's no need to pass the subtype since it'll
 208                          * always be zero, but might as well pass it for possible future
 209                          * use.)
 210                          *
 211                          * We initialize the recheck flag to true (the safest assumption)
 212                          * in case the Consistent function forgets to set it.
 213                          */
 214                         recheck = true;
 215
 216                         test = FunctionCall5Coll(&key->sk_func,
 217                                                                          key->sk_collation,
 218                                                                          PointerGetDatum(&de),
 219                                                                          key->sk_argument,
 220                                                                          Int32GetDatum(key->sk_strategy),
 221                                                                          ObjectIdGetDatum(key->sk_subtype),
 222                                                                          PointerGetDatum(&recheck));
 223
 224                         if (!DatumGetBool(test))
 225                                 return false;
 226                         *recheck_p |= recheck;
 227                 }
 228
 229                 key++;
 230                 keySize--;
 231         }
 232
 233         /* OK, it passes --- now let's compute the distances */
 234         key = scan->orderByData;
 235         distance_p = so->distances;
 236         keySize = scan->numberOfOrderBys;
 237         while (keySize > 0)
 238         {
 239                 Datum           datum;
 240                 bool            isNull;
 241
 242                 datum = index_getattr(tuple,
 243                                                           key->sk_attno,
 244                                                           giststate->tupdesc,
 245                                                           &isNull);
 246
 247                 if ((key->sk_flags & SK_ISNULL) || isNull)
 248                 {
 249                         /* Assume distance computes as null and sorts to the end */
 250                         *distance_p = get_float8_infinity();
 251                 }
 252                 else
 253                 {
 254                         Datum           dist;
 255                         bool            recheck;
 256                         GISTENTRY       de;
 257
 258                         gistdentryinit(giststate, key->sk_attno - 1, &de,
 259                                                    datum, r, page, offset,
 260                                                    FALSE, isNull);
 261
 262                         /*
 263                          * Call the Distance function to evaluate the distance.  The
 264                          * arguments are the index datum (as a GISTENTRY*), the comparison
 265                          * datum, the ordering operator's strategy number and subtype from
 266                          * pg_amop, and the recheck flag.
 267                          *
 268                          * (Presently there's no need to pass the subtype since it'll
 269                          * always be zero, but might as well pass it for possible future
 270                          * use.)
 271                          *
 272                          * If the function sets the recheck flag, the returned distance is
 273                          * a lower bound on the true distance and needs to be rechecked.
 274                          * We initialize the flag to 'false'.  This flag was added in
 275                          * version 9.5; distance functions written before that won't know
 276                          * about the flag, but are expected to never be lossy.
 277                          */
 278                         recheck = false;
 279                         dist = FunctionCall5Coll(&key->sk_func,
 280                                                                          key->sk_collation,
 281                                                                          PointerGetDatum(&de),
 282                                                                          key->sk_argument,
 283                                                                          Int32GetDatum(key->sk_strategy),
 284                                                                          ObjectIdGetDatum(key->sk_subtype),
 285                                                                          PointerGetDatum(&recheck));
 286                         *recheck_distances_p |= recheck;
 287                         *distance_p = DatumGetFloat8(dist);
 288                 }
 289
 290                 key++;
 291                 distance_p++;
 292                 keySize--;
 293         }
 294
 295         return true;
 296 }
 297
 298 /*
 299  * Scan all items on the GiST index page identified by *pageItem, and insert
 300  * them into the queue (or directly to output areas)
 301  *
 302  * scan: index scan we are executing
 303  * pageItem: search queue item identifying an index page to scan
 304  * myDistances: distances array associated with pageItem, or NULL at the root
 305  * tbm: if not NULL, gistgetbitmap's output bitmap
 306  * ntids: if not NULL, gistgetbitmap's output tuple counter
 307  *
 308  * If tbm/ntids aren't NULL, we are doing an amgetbitmap scan, and heap
 309  * tuples should be reported directly into the bitmap.  If they are NULL,
 310  * we're doing a plain or ordered indexscan.  For a plain indexscan, heap
 311  * tuple TIDs are returned into so->pageData[].  For an ordered indexscan,
 312  * heap tuple TIDs are pushed into individual search queue items.  In an
 313  * index-only scan, reconstructed index tuples are returned along with the
 314  * TIDs.
 315  *
 316  * If we detect that the index page has split since we saw its downlink
 317  * in the parent, we push its new right sibling onto the queue so the
 318  * sibling will be processed next.
 319  */
 320 static void
 321 gistScanPage(IndexScanDesc scan, GISTSearchItem *pageItem, double *myDistances,
 322                          TIDBitmap *tbm, int64 *ntids)
 323 {
 324         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 325         GISTSTATE  *giststate = so->giststate;
 326         Relation        r = scan->indexRelation;
 327         Buffer          buffer;
 328         Page            page;
 329         GISTPageOpaque opaque;
 330         OffsetNumber maxoff;
 331         OffsetNumber i;
 332         MemoryContext oldcxt;
 333
 334         Assert(!GISTSearchItemIsHeap(*pageItem));
 335
 336         buffer = ReadBuffer(scan->indexRelation, pageItem->blkno);
 337         LockBuffer(buffer, GIST_SHARE);
 338         gistcheckpage(scan->indexRelation, buffer);
 339         page = BufferGetPage(buffer);
 340         opaque = GistPageGetOpaque(page);
 341
 342         /*
 343          * Check if we need to follow the rightlink. We need to follow it if the
 344          * page was concurrently split since we visited the parent (in which case
 345          * parentlsn < nsn), or if the system crashed after a page split but
 346          * before the downlink was inserted into the parent.
 347          */
 348         if (!XLogRecPtrIsInvalid(pageItem->data.parentlsn) &&
 349                 (GistFollowRight(page) ||
 350                  pageItem->data.parentlsn < GistPageGetNSN(page)) &&
 351                 opaque->rightlink != InvalidBlockNumber /* sanity check */ )
 352         {
 353                 /* There was a page split, follow right link to add pages */
 354                 GISTSearchItem *item;
 355
 356                 /* This can't happen when starting at the root */
 357                 Assert(myDistances != NULL);
 358
 359                 oldcxt = MemoryContextSwitchTo(so->queueCxt);
 360
 361                 /* Create new GISTSearchItem for the right sibling index page */
 362                 item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
 363                 item->blkno = opaque->rightlink;
 364                 item->data.parentlsn = pageItem->data.parentlsn;
 365
 366                 /* Insert it into the queue using same distances as for this page */
 367                 memcpy(item->distances, myDistances,
 368                            sizeof(double) * scan->numberOfOrderBys);
 369
 370                 pairingheap_add(so->queue, &item->phNode);
 371
 372                 MemoryContextSwitchTo(oldcxt);
 373         }
 374
 375         so->nPageData = so->curPageData = 0;
 376         if (so->pageDataCxt)
 377                 MemoryContextReset(so->pageDataCxt);
 378
 379         /*
 380          * We save the LSN of the page as we read it, so that we know whether it
 381          * safe to apply LP_DEAD hints to the page later. This allows us to drop
 382          * the pin for MVCC scans, which allows vacuum to avoid blocking.
 383          */
 384         so->curPageLSN = PageGetLSN(page);
 385
 386         /*
 387          * check all tuples on page
 388          */
 389         maxoff = PageGetMaxOffsetNumber(page);
 390         for (i = FirstOffsetNumber; i <= maxoff; i = OffsetNumberNext(i))
 391         {
 392                 ItemId      iid = PageGetItemId(page, i);
 393                 IndexTuple      it;
 394                 bool            match;
 395                 bool            recheck;
 396                 bool            recheck_distances;
 397
 398                 /*
 399                  * If the scan specifies not to return killed tuples, then we treat a
 400                  * killed tuple as not passing the qual.
 401                  */
 402                 if(scan->ignore_killed_tuples && ItemIdIsDead(iid))
 403                         continue;
 404
 405                 it = (IndexTuple) PageGetItem(page, iid);
 406                 /*
 407                  * Must call gistindex_keytest in tempCxt, and clean up any leftover
 408                  * junk afterward.
 409                  */
 410                 oldcxt = MemoryContextSwitchTo(so->giststate->tempCxt);
 411
 412                 match = gistindex_keytest(scan, it, page, i,
 413                                                                   &recheck, &recheck_distances);
 414
 415                 MemoryContextSwitchTo(oldcxt);
 416                 MemoryContextReset(so->giststate->tempCxt);
 417
 418                 /* Ignore tuple if it doesn't match */
 419                 if (!match)
 420                         continue;
 421
 422                 if (tbm && GistPageIsLeaf(page))
 423                 {
 424                         /*
 425                          * getbitmap scan, so just push heap tuple TIDs into the bitmap
 426                          * without worrying about ordering
 427                          */
 428                         tbm_add_tuples(tbm, &it->t_tid, 1, recheck);
 429                         (*ntids)++;
 430                 }
 431                 else if (scan->numberOfOrderBys == 0 && GistPageIsLeaf(page))
 432                 {
 433                         /*
 434                          * Non-ordered scan, so report tuples in so->pageData[]
 435                          */
 436                         so->pageData[so->nPageData].heapPtr = it->t_tid;
 437                         so->pageData[so->nPageData].recheck = recheck;
 438                         so->pageData[so->nPageData].offnum = i;
 439
 440                         /*
 441                          * In an index-only scan, also fetch the data from the tuple.
 442                          */
 443                         if (scan->xs_want_itup)
 444                         {
 445                                 oldcxt = MemoryContextSwitchTo(so->pageDataCxt);
 446                                 so->pageData[so->nPageData].ftup =
 447                                         gistFetchTuple(giststate, r, it);
 448                                 MemoryContextSwitchTo(oldcxt);
 449                         }
 450                         so->nPageData++;
 451                 }
 452                 else
 453                 {
 454                         /*
 455                          * Must push item into search queue.  We get here for any lower
 456                          * index page, and also for heap tuples if doing an ordered
 457                          * search.
 458                          */
 459                         GISTSearchItem *item;
 460
 461                         oldcxt = MemoryContextSwitchTo(so->queueCxt);
 462
 463                         /* Create new GISTSearchItem for this item */
 464                         item = palloc(SizeOfGISTSearchItem(scan->numberOfOrderBys));
 465
 466                         if (GistPageIsLeaf(page))
 467                         {
 468                                 /* Creating heap-tuple GISTSearchItem */
 469                                 item->blkno = InvalidBlockNumber;
 470                                 item->data.heap.heapPtr = it->t_tid;
 471                                 item->data.heap.recheck = recheck;
 472                                 item->data.heap.recheckDistances = recheck_distances;
 473
 474                                 /*
 475                                  * In an index-only scan, also fetch the data from the tuple.
 476                                  */
 477                                 if (scan->xs_want_itup)
 478                                         item->data.heap.ftup = gistFetchTuple(giststate, r, it);
 479                         }
 480                         else
 481                         {
 482                                 /* Creating index-page GISTSearchItem */
 483                                 item->blkno = ItemPointerGetBlockNumber(&it->t_tid);
 484
 485                                 /*
 486                                  * LSN of current page is lsn of parent page for child. We
 487                                  * only have a shared lock, so we need to get the LSN
 488                                  * atomically.
 489                                  */
 490                                 item->data.parentlsn = BufferGetLSNAtomic(buffer);
 491                         }
 492
 493                         /* Insert it into the queue using new distance data */
 494                         memcpy(item->distances, so->distances,
 495                                    sizeof(double) * scan->numberOfOrderBys);
 496
 497                         pairingheap_add(so->queue, &item->phNode);
 498
 499                         MemoryContextSwitchTo(oldcxt);
 500                 }
 501         }
 502
 503         UnlockReleaseBuffer(buffer);
 504 }
 505
 506 /*
 507  * Extract next item (in order) from search queue
 508  *
 509  * Returns a GISTSearchItem or NULL.  Caller must pfree item when done with it.
 510  */
 511 static GISTSearchItem *
 512 getNextGISTSearchItem(GISTScanOpaque so)
 513 {
 514         GISTSearchItem *item;
 515
 516         if (!pairingheap_is_empty(so->queue))
 517         {
 518                 item = (GISTSearchItem *) pairingheap_remove_first(so->queue);
 519         }
 520         else
 521         {
 522                 /* Done when both heaps are empty */
 523                 item = NULL;
 524         }
 525
 526         /* Return item; caller is responsible to pfree it */
 527         return item;
 528 }
 529
 530 /*
 531  * Fetch next heap tuple in an ordered search
 532  */
 533 static bool
 534 getNextNearest(IndexScanDesc scan)
 535 {
 536         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 537         bool            res = false;
 538         int                     i;
 539
 540         if (scan->xs_itup)
 541         {
 542                 /* free previously returned tuple */
 543                 pfree(scan->xs_itup);
 544                 scan->xs_itup = NULL;
 545         }
 546
 547         do
 548         {
 549                 GISTSearchItem *item = getNextGISTSearchItem(so);
 550
 551                 if (!item)
 552                         break;
 553
 554                 if (GISTSearchItemIsHeap(*item))
 555                 {
 556                         /* found a heap item at currently minimal distance */
 557                         scan->xs_ctup.t_self = item->data.heap.heapPtr;
 558                         scan->xs_recheck = item->data.heap.recheck;
 559                         scan->xs_recheckorderby = item->data.heap.recheckDistances;
 560                         for (i = 0; i < scan->numberOfOrderBys; i++)
 561                         {
 562                                 if (so->orderByTypes[i] == FLOAT8OID)
 563                                 {
 564 #ifndef USE_FLOAT8_BYVAL
 565                                         /* must free any old value to avoid memory leakage */
 566                                         if (!scan->xs_orderbynulls[i])
 567                                                 pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
 568 #endif
 569                                         scan->xs_orderbyvals[i] = Float8GetDatum(item->distances[i]);
 570                                         scan->xs_orderbynulls[i] = false;
 571                                 }
 572                                 else if (so->orderByTypes[i] == FLOAT4OID)
 573                                 {
 574                                         /* convert distance function's result to ORDER BY type */
 575 #ifndef USE_FLOAT4_BYVAL
 576                                         /* must free any old value to avoid memory leakage */
 577                                         if (!scan->xs_orderbynulls[i])
 578                                                 pfree(DatumGetPointer(scan->xs_orderbyvals[i]));
 579 #endif
 580                                         scan->xs_orderbyvals[i] = Float4GetDatum((float4) item->distances[i]);
 581                                         scan->xs_orderbynulls[i] = false;
 582                                 }
 583                                 else
 584                                 {
 585                                         /*
 586                                          * If the ordering operator's return value is anything
 587                                          * else, we don't know how to convert the float8 bound
 588                                          * calculated by the distance function to that.  The
 589                                          * executor won't actually need the order by values we
 590                                          * return here, if there are no lossy results, so only
 591                                          * insist on converting if the *recheck flag is set.
 592                                          */
 593                                         if (scan->xs_recheckorderby)
 594                                                 elog(ERROR, "GiST operator family's FOR ORDER BY operator must return float8 or float4 if the distance function is lossy");
 595                                         scan->xs_orderbynulls[i] = true;
 596                                 }
 597                         }
 598
 599                         /* in an index-only scan, also return the reconstructed tuple. */
 600                         if (scan->xs_want_itup)
 601                                 scan->xs_itup = item->data.heap.ftup;
 602                         res = true;
 603                 }
 604                 else
 605                 {
 606                         /* visit an index page, extract its items into queue */
 607                         CHECK_FOR_INTERRUPTS();
 608
 609                         gistScanPage(scan, item, item->distances, NULL, NULL);
 610                 }
 611
 612                 pfree(item);
 613         } while (!res);
 614
 615         return res;
 616 }
 617
 618 /*
 619  * gistgettuple() -- Get the next tuple in the scan
 620  */
 621 Datum
 622 gistgettuple(PG_FUNCTION_ARGS)
 623 {
 624         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 625         ScanDirection dir = (ScanDirection) PG_GETARG_INT32(1);
 626         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 627
 628         if (dir != ForwardScanDirection)
 629                 elog(ERROR, "GiST only supports forward scan direction");
 630
 631         if (!so->qual_ok)
 632                 PG_RETURN_BOOL(false);
 633
 634         if (so->firstCall)
 635         {
 636                 /* Begin the scan by processing the root page */
 637                 GISTSearchItem fakeItem;
 638
 639                 pgstat_count_index_scan(scan->indexRelation);
 640
 641                 so->firstCall = false;
 642                 so->curPageData = so->nPageData = 0;
 643                 if (so->pageDataCxt)
 644                         MemoryContextReset(so->pageDataCxt);
 645
 646                 fakeItem.blkno = GIST_ROOT_BLKNO;
 647                 memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
 648                 gistScanPage(scan, &fakeItem, NULL, NULL, NULL);
 649         }
 650
 651         if (scan->numberOfOrderBys > 0)
 652         {
 653                 /* Must fetch tuples in strict distance order */
 654                 PG_RETURN_BOOL(getNextNearest(scan));
 655         }
 656         else
 657         {
 658                 /* Fetch tuples index-page-at-a-time */
 659                 for (;;)
 660                 {
 661                         if (so->curPageData < so->nPageData)
 662                         {
 663                                 if (scan->kill_prior_tuple && so->curPageData > 0)
 664                                 {
 665
 666                                         if (so->killedItems == NULL)
 667                                         {
 668                                                 MemoryContext oldCxt =
 669                                                         MemoryContextSwitchTo(so->giststate->scanCxt);
 670
 671                                                 so->killedItems =
 672                                                         (OffsetNumber *) palloc(MaxIndexTuplesPerPage
 673                                                                 * sizeof(OffsetNumber));
 674
 675                                                 MemoryContextSwitchTo(oldCxt);
 676                                         }
 677                                         if (so->numKilled < MaxIndexTuplesPerPage)
 678                                                 so->killedItems[so->numKilled++] =
 679                                                         so->pageData[so->curPageData - 1].offnum;
 680                                 }
 681                                 /* continuing to return tuples from a leaf page */
 682                                 scan->xs_ctup.t_self = so->pageData[so->curPageData].heapPtr;
 683                                 scan->xs_recheck = so->pageData[so->curPageData].recheck;
 684
 685                                 /* in an index-only scan, also return the reconstructed tuple */
 686                                 if (scan->xs_want_itup)
 687                                         scan->xs_itup = so->pageData[so->curPageData].ftup;
 688
 689                                 so->curPageData++;
 690
 691                                 PG_RETURN_BOOL(true);
 692                         }
 693
 694                         /*
 695                          * Check the last returned tuple and add it to killitems if
 696                          * necessary
 697                          */
 698                         if (scan->kill_prior_tuple
 699                                 && so->curPageData > 0
 700                                 && so->curPageData == so->nPageData)
 701                         {
 702
 703                                 if (so->killedItems == NULL)
 704                                 {
 705                                         MemoryContext oldCxt =
 706                                                 MemoryContextSwitchTo(so->giststate->scanCxt);
 707
 708                                         so->killedItems =
 709                                                 (OffsetNumber *) palloc(MaxIndexTuplesPerPage
 710                                                         * sizeof(OffsetNumber));
 711
 712                                         MemoryContextSwitchTo(oldCxt);
 713                                 }
 714                                 if (so->numKilled < MaxIndexTuplesPerPage)
 715                                         so->killedItems[so->numKilled++] =
 716                                                 so->pageData[so->curPageData - 1].offnum;
 717                         }
 718                         /* find and process the next index page */
 719                         do
 720                         {
 721                                 GISTSearchItem *item;
 722
 723                                 if ((so->curBlkno != InvalidBlockNumber) && (so->numKilled > 0))
 724                                         gistkillitems(scan);
 725
 726                                 item = getNextGISTSearchItem(so);
 727
 728                                 if (!item)
 729                                         PG_RETURN_BOOL(false);
 730
 731                                 CHECK_FOR_INTERRUPTS();
 732
 733                                 /* save current item BlockNumber for next gistkillitems() call */
 734                                 so->curBlkno = item->blkno;
 735
 736                                 /*
 737                                  * While scanning a leaf page, ItemPointers of matching heap
 738                                  * tuples are stored in so->pageData.  If there are any on
 739                                  * this page, we fall out of the inner "do" and loop around to
 740                                  * return them.
 741                                  */
 742                                 gistScanPage(scan, item, item->distances, NULL, NULL);
 743
 744                                 pfree(item);
 745                         } while (so->nPageData == 0);
 746                 }
 747         }
 748 }
 749
 750 /*
 751  * gistgetbitmap() -- Get a bitmap of all heap tuple locations
 752  */
 753 Datum
 754 gistgetbitmap(PG_FUNCTION_ARGS)
 755 {
 756         IndexScanDesc scan = (IndexScanDesc) PG_GETARG_POINTER(0);
 757         TIDBitmap  *tbm = (TIDBitmap *) PG_GETARG_POINTER(1);
 758         GISTScanOpaque so = (GISTScanOpaque) scan->opaque;
 759         int64           ntids = 0;
 760         GISTSearchItem fakeItem;
 761
 762         if (!so->qual_ok)
 763                 PG_RETURN_INT64(0);
 764
 765         pgstat_count_index_scan(scan->indexRelation);
 766
 767         /* Begin the scan by processing the root page */
 768         so->curPageData = so->nPageData = 0;
 769         if (so->pageDataCxt)
 770                 MemoryContextReset(so->pageDataCxt);
 771
 772         fakeItem.blkno = GIST_ROOT_BLKNO;
 773         memset(&fakeItem.data.parentlsn, 0, sizeof(GistNSN));
 774         gistScanPage(scan, &fakeItem, NULL, tbm, &ntids);
 775
 776         /*
 777          * While scanning a leaf page, ItemPointers of matching heap tuples will
 778          * be stored directly into tbm, so we don't need to deal with them here.
 779          */
 780         for (;;)
 781         {
 782                 GISTSearchItem *item = getNextGISTSearchItem(so);
 783
 784                 if (!item)
 785                         break;
 786
 787                 CHECK_FOR_INTERRUPTS();
 788
 789                 gistScanPage(scan, item, item->distances, tbm, &ntids);
 790
 791                 pfree(item);
 792         }
 793
 794         PG_RETURN_INT64(ntids);
 795 }
 796
 797 /*
 798  * Can we do index-only scans on the given index column?
 799  *
 800  * Opclasses that implement a fetch function support index-only scans.
 801  */
 802 Datum
 803 gistcanreturn(PG_FUNCTION_ARGS)
 804 {
 805         Relation        index = (Relation) PG_GETARG_POINTER(0);
 806         int                     attno = PG_GETARG_INT32(1);
 807
 808         if (OidIsValid(index_getprocid(index, attno, GIST_FETCH_PROC)))
 809                 PG_RETURN_BOOL(true);
 810         else
 811                 PG_RETURN_BOOL(false);
 812 }