granicus.if.org Git - postgresql/blob - src/backend/access/nbtree/nbtsearch.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * nbtsearch.c
   4  *        Search code for postgres btrees.
   5  *
   6  *
   7  * Portions Copyright (c) 1996-2003, PostgreSQL Global Development Group
   8  * Portions Copyright (c) 1994, Regents of the University of California
   9  *
  10  * IDENTIFICATION
  11  *        $PostgreSQL: pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.84 2003/12/21 01:23:06 tgl Exp $
  12  *
  13  *-------------------------------------------------------------------------
  14  */
  15
  16 #include "postgres.h"
  17
  18 #include "access/genam.h"
  19 #include "access/nbtree.h"
  20 #include "utils/lsyscache.h"
  21
  22
  23 static Buffer _bt_walk_left(Relation rel, Buffer buf);
  24 static bool _bt_endpoint(IndexScanDesc scan, ScanDirection dir);
  25
  26
  27 /*
  28  *      _bt_search() -- Search the tree for a particular scankey,
  29  *              or more precisely for the first leaf page it could be on.
  30  *
  31  * When nextkey is false (the usual case), we are looking for the first
  32  * item >= scankey.  When nextkey is true, we are looking for the first
  33  * item strictly greater than scankey.
  34  *
  35  * Return value is a stack of parent-page pointers.  *bufP is set to the
  36  * address of the leaf-page buffer, which is read-locked and pinned.
  37  * No locks are held on the parent pages, however!
  38  *
  39  * NOTE that the returned buffer is read-locked regardless of the access
  40  * parameter.  However, access = BT_WRITE will allow an empty root page
  41  * to be created and returned.  When access = BT_READ, an empty index
  42  * will result in *bufP being set to InvalidBuffer.
  43  */
  44 BTStack
  45 _bt_search(Relation rel, int keysz, ScanKey scankey, bool nextkey,
  46                    Buffer *bufP, int access)
  47 {
  48         BTStack         stack_in = NULL;
  49
  50         /* Get the root page to start with */
  51         *bufP = _bt_getroot(rel, access);
  52
  53         /* If index is empty and access = BT_READ, no root page is created. */
  54         if (!BufferIsValid(*bufP))
  55                 return (BTStack) NULL;
  56
  57         /* Loop iterates once per level descended in the tree */
  58         for (;;)
  59         {
  60                 Page            page;
  61                 BTPageOpaque opaque;
  62                 OffsetNumber offnum;
  63                 ItemId          itemid;
  64                 BTItem          btitem;
  65                 IndexTuple      itup;
  66                 BlockNumber blkno;
  67                 BlockNumber par_blkno;
  68                 BTStack         new_stack;
  69
  70                 /*
  71                  * Race -- the page we just grabbed may have split since we read
  72                  * its pointer in the parent (or metapage).  If it has, we may
  73                  * need to move right to its new sibling.  Do that.
  74                  */
  75                 *bufP = _bt_moveright(rel, *bufP, keysz, scankey, nextkey, BT_READ);
  76
  77                 /* if this is a leaf page, we're done */
  78                 page = BufferGetPage(*bufP);
  79                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
  80                 if (P_ISLEAF(opaque))
  81                         break;
  82
  83                 /*
  84                  * Find the appropriate item on the internal page, and get the
  85                  * child page that it points to.
  86                  */
  87                 offnum = _bt_binsrch(rel, *bufP, keysz, scankey, nextkey);
  88                 itemid = PageGetItemId(page, offnum);
  89                 btitem = (BTItem) PageGetItem(page, itemid);
  90                 itup = &(btitem->bti_itup);
  91                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
  92                 par_blkno = BufferGetBlockNumber(*bufP);
  93
  94                 /*
  95                  * We need to save the location of the index entry we chose in the
  96                  * parent page on a stack. In case we split the tree, we'll use
  97                  * the stack to work back up to the parent page.  We also save the
  98                  * actual downlink (TID) to uniquely identify the index entry, in
  99                  * case it moves right while we're working lower in the tree.  See
 100                  * the paper by Lehman and Yao for how this is detected and
 101                  * handled. (We use the child link to disambiguate duplicate keys
 102                  * in the index -- Lehman and Yao disallow duplicate keys.)
 103                  */
 104                 new_stack = (BTStack) palloc(sizeof(BTStackData));
 105                 new_stack->bts_blkno = par_blkno;
 106                 new_stack->bts_offset = offnum;
 107                 memcpy(&new_stack->bts_btitem, btitem, sizeof(BTItemData));
 108                 new_stack->bts_parent = stack_in;
 109
 110                 /* drop the read lock on the parent page, acquire one on the child */
 111                 _bt_relbuf(rel, *bufP);
 112                 *bufP = _bt_getbuf(rel, blkno, BT_READ);
 113
 114                 /* okay, all set to move down a level */
 115                 stack_in = new_stack;
 116         }
 117
 118         return stack_in;
 119 }
 120
 121 /*
 122  *      _bt_moveright() -- move right in the btree if necessary.
 123  *
 124  * When we follow a pointer to reach a page, it is possible that
 125  * the page has changed in the meanwhile.  If this happens, we're
 126  * guaranteed that the page has "split right" -- that is, that any
 127  * data that appeared on the page originally is either on the page
 128  * or strictly to the right of it.
 129  *
 130  * When nextkey is false (the usual case), we are looking for the first
 131  * item >= scankey.  When nextkey is true, we are looking for the first
 132  * item strictly greater than scankey.
 133  *
 134  * This routine decides whether or not we need to move right in the
 135  * tree by examining the high key entry on the page.  If that entry
 136  * is strictly less than the scankey, or <= the scankey in the nextkey=true
 137  * case, then we followed the wrong link and we need to move right.
 138  *
 139  * On entry, we have the buffer pinned and a lock of the type specified by
 140  * 'access'.  If we move right, we release the buffer and lock and acquire
 141  * the same on the right sibling.  Return value is the buffer we stop at.
 142  */
 143 Buffer
 144 _bt_moveright(Relation rel,
 145                           Buffer buf,
 146                           int keysz,
 147                           ScanKey scankey,
 148                           bool nextkey,
 149                           int access)
 150 {
 151         Page            page;
 152         BTPageOpaque opaque;
 153         int32           cmpval;
 154
 155         page = BufferGetPage(buf);
 156         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 157
 158         /*
 159          * When nextkey = false (normal case): if the scan key that brought us to
 160          * this page is > the high key stored on the page, then the page has split
 161          * and we need to move right.  (If the scan key is equal to the high key,
 162          * we might or might not need to move right; have to scan the page first
 163          * anyway.)
 164          *
 165          * When nextkey = true: move right if the scan key is >= page's high key.
 166          *
 167          * The page could even have split more than once, so scan as far as needed.
 168          *
 169          * We also have to move right if we followed a link that brought us to a
 170          * dead page.
 171          */
 172         cmpval = nextkey ? 0 : 1;
 173
 174         while (!P_RIGHTMOST(opaque) &&
 175                    (P_IGNORE(opaque) ||
 176                         _bt_compare(rel, keysz, scankey, page, P_HIKEY) >= cmpval))
 177         {
 178                 /* step right one page */
 179                 BlockNumber rblkno = opaque->btpo_next;
 180
 181                 _bt_relbuf(rel, buf);
 182                 buf = _bt_getbuf(rel, rblkno, access);
 183                 page = BufferGetPage(buf);
 184                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 185         }
 186
 187         if (P_IGNORE(opaque))
 188                 elog(ERROR, "fell off the end of \"%s\"",
 189                          RelationGetRelationName(rel));
 190
 191         return buf;
 192 }
 193
 194 /*
 195  *      _bt_binsrch() -- Do a binary search for a key on a particular page.
 196  *
 197  * When nextkey is false (the usual case), we are looking for the first
 198  * item >= scankey.  When nextkey is true, we are looking for the first
 199  * item strictly greater than scankey.
 200  *
 201  * The scankey we get has the compare function stored in the procedure
 202  * entry of each data struct.  We invoke this regproc to do the
 203  * comparison for every key in the scankey.
 204  *
 205  * On a leaf page, _bt_binsrch() returns the OffsetNumber of the first
 206  * key >= given scankey, or > scankey if nextkey is true.  (NOTE: in
 207  * particular, this means it is possible to return a value 1 greater than the
 208  * number of keys on the page, if the scankey is > all keys on the page.)
 209  *
 210  * On an internal (non-leaf) page, _bt_binsrch() returns the OffsetNumber
 211  * of the last key < given scankey, or last key <= given scankey if nextkey
 212  * is true.  (Since _bt_compare treats the first data key of such a page as
 213  * minus infinity, there will be at least one key < scankey, so the result
 214  * always points at one of the keys on the page.)  This key indicates the
 215  * right place to descend to be sure we find all leaf keys >= given scankey
 216  * (or leaf keys > given scankey when nextkey is true).
 217  *
 218  * This procedure is not responsible for walking right, it just examines
 219  * the given page.      _bt_binsrch() has no lock or refcount side effects
 220  * on the buffer.
 221  */
 222 OffsetNumber
 223 _bt_binsrch(Relation rel,
 224                         Buffer buf,
 225                         int keysz,
 226                         ScanKey scankey,
 227                         bool nextkey)
 228 {
 229         TupleDesc       itupdesc;
 230         Page            page;
 231         BTPageOpaque opaque;
 232         OffsetNumber low,
 233                                 high;
 234         int32           result,
 235                                 cmpval;
 236
 237         itupdesc = RelationGetDescr(rel);
 238         page = BufferGetPage(buf);
 239         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 240
 241         low = P_FIRSTDATAKEY(opaque);
 242         high = PageGetMaxOffsetNumber(page);
 243
 244         /*
 245          * If there are no keys on the page, return the first available slot.
 246          * Note this covers two cases: the page is really empty (no keys), or
 247          * it contains only a high key.  The latter case is possible after
 248          * vacuuming.  This can never happen on an internal page, however,
 249          * since they are never empty (an internal page must have children).
 250          */
 251         if (high < low)
 252                 return low;
 253
 254         /*
 255          * Binary search to find the first key on the page >= scan key, or
 256          * first key > scankey when nextkey is true.
 257          *
 258          * For nextkey=false (cmpval=1), the loop invariant is: all slots
 259          * before 'low' are < scan key, all slots at or after 'high'
 260          * are >= scan key.
 261          *
 262          * For nextkey=true (cmpval=0), the loop invariant is: all slots
 263          * before 'low' are <= scan key, all slots at or after 'high'
 264          * are > scan key.
 265          *
 266          * We can fall out when high == low.
 267          */
 268         high++;                                         /* establish the loop invariant for high */
 269
 270         cmpval = nextkey ? 0 : 1;       /* select comparison value */
 271
 272         while (high > low)
 273         {
 274                 OffsetNumber mid = low + ((high - low) / 2);
 275
 276                 /* We have low <= mid < high, so mid points at a real slot */
 277
 278                 result = _bt_compare(rel, keysz, scankey, page, mid);
 279
 280                 if (result >= cmpval)
 281                         low = mid + 1;
 282                 else
 283                         high = mid;
 284         }
 285
 286         /*
 287          * At this point we have high == low, but be careful: they could point
 288          * past the last slot on the page.
 289          *
 290          * On a leaf page, we always return the first key >= scan key (resp.
 291          * > scan key), which could be the last slot + 1.
 292          */
 293         if (P_ISLEAF(opaque))
 294                 return low;
 295
 296         /*
 297          * On a non-leaf page, return the last key < scan key (resp. <= scan key).
 298          * There must be one if _bt_compare() is playing by the rules.
 299          */
 300         Assert(low > P_FIRSTDATAKEY(opaque));
 301
 302         return OffsetNumberPrev(low);
 303 }
 304
 305 /*----------
 306  *      _bt_compare() -- Compare scankey to a particular tuple on the page.
 307  *
 308  *      keysz: number of key conditions to be checked (might be less than the
 309  *      total length of the scan key!)
 310  *      page/offnum: location of btree item to be compared to.
 311  *
 312  *              This routine returns:
 313  *                      <0 if scankey < tuple at offnum;
 314  *                       0 if scankey == tuple at offnum;
 315  *                      >0 if scankey > tuple at offnum.
 316  *              NULLs in the keys are treated as sortable values.  Therefore
 317  *              "equality" does not necessarily mean that the item should be
 318  *              returned to the caller as a matching key!
 319  *
 320  * CRUCIAL NOTE: on a non-leaf page, the first data key is assumed to be
 321  * "minus infinity": this routine will always claim it is less than the
 322  * scankey.  The actual key value stored (if any, which there probably isn't)
 323  * does not matter.  This convention allows us to implement the Lehman and
 324  * Yao convention that the first down-link pointer is before the first key.
 325  * See backend/access/nbtree/README for details.
 326  *----------
 327  */
 328 int32
 329 _bt_compare(Relation rel,
 330                         int keysz,
 331                         ScanKey scankey,
 332                         Page page,
 333                         OffsetNumber offnum)
 334 {
 335         TupleDesc       itupdesc = RelationGetDescr(rel);
 336         BTPageOpaque opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 337         BTItem          btitem;
 338         IndexTuple      itup;
 339         int                     i;
 340
 341         /*
 342          * Force result ">" if target item is first data item on an internal
 343          * page --- see NOTE above.
 344          */
 345         if (!P_ISLEAF(opaque) && offnum == P_FIRSTDATAKEY(opaque))
 346                 return 1;
 347
 348         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 349         itup = &(btitem->bti_itup);
 350
 351         /*
 352          * The scan key is set up with the attribute number associated with
 353          * each term in the key.  It is important that, if the index is
 354          * multi-key, the scan contain the first k key attributes, and that
 355          * they be in order.  If you think about how multi-key ordering works,
 356          * you'll understand why this is.
 357          *
 358          * We don't test for violation of this condition here, however.  The
 359          * initial setup for the index scan had better have gotten it right
 360          * (see _bt_first).
 361          */
 362
 363         for (i = 1; i <= keysz; i++)
 364         {
 365                 Datum           datum;
 366                 bool            isNull;
 367                 int32           result;
 368
 369                 datum = index_getattr(itup, scankey->sk_attno, itupdesc, &isNull);
 370
 371                 /* see comments about NULLs handling in btbuild */
 372                 if (scankey->sk_flags & SK_ISNULL)              /* key is NULL */
 373                 {
 374                         if (isNull)
 375                                 result = 0;             /* NULL "=" NULL */
 376                         else
 377                                 result = 1;             /* NULL ">" NOT_NULL */
 378                 }
 379                 else if (isNull)                /* key is NOT_NULL and item is NULL */
 380                 {
 381                         result = -1;            /* NOT_NULL "<" NULL */
 382                 }
 383                 else
 384                 {
 385                         /*
 386                          * The sk_func needs to be passed the index value as left arg
 387                          * and the sk_argument as right arg (they might be of different
 388                          * types).  Since it is convenient for callers to think of
 389                          * _bt_compare as comparing the scankey to the index item,
 390                          * we have to flip the sign of the comparison result.
 391                          *
 392                          * Note: curious-looking coding is to avoid overflow if
 393                          * comparison function returns INT_MIN.  There is no risk of
 394                          * overflow for positive results.
 395                          */
 396                         result = DatumGetInt32(FunctionCall2(&scankey->sk_func,
 397                                                                                                  datum,
 398                                                                                                  scankey->sk_argument));
 399                         result = (result < 0) ? 1 : -result;
 400                 }
 401
 402                 /* if the keys are unequal, return the difference */
 403                 if (result != 0)
 404                         return result;
 405
 406                 scankey++;
 407         }
 408
 409         /* if we get here, the keys are equal */
 410         return 0;
 411 }
 412
 413 /*
 414  *      _bt_next() -- Get the next item in a scan.
 415  *
 416  *              On entry, we have a valid currentItemData in the scan, and a
 417  *              read lock and pin count on the page that contains that item.
 418  *              We return the next item in the scan, or false if no more.
 419  *              On successful exit, the page containing the new item is locked
 420  *              and pinned; on failure exit, no lock or pin is held.
 421  */
 422 bool
 423 _bt_next(IndexScanDesc scan, ScanDirection dir)
 424 {
 425         Relation        rel;
 426         Buffer          buf;
 427         Page            page;
 428         OffsetNumber offnum;
 429         ItemPointer current;
 430         BTItem          btitem;
 431         IndexTuple      itup;
 432         BTScanOpaque so;
 433         bool            continuescan;
 434
 435         rel = scan->indexRelation;
 436         so = (BTScanOpaque) scan->opaque;
 437         current = &(scan->currentItemData);
 438
 439         /* we still have the buffer pinned and locked */
 440         buf = so->btso_curbuf;
 441         Assert(BufferIsValid(buf));
 442
 443         do
 444         {
 445                 /* step one tuple in the appropriate direction */
 446                 if (!_bt_step(scan, &buf, dir))
 447                         return false;
 448
 449                 /* current is the next candidate tuple to return */
 450                 offnum = ItemPointerGetOffsetNumber(current);
 451                 page = BufferGetPage(buf);
 452                 btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 453                 itup = &btitem->bti_itup;
 454
 455                 if (_bt_checkkeys(scan, itup, dir, &continuescan))
 456                 {
 457                         /* tuple passes all scan key conditions, so return it */
 458                         scan->xs_ctup.t_self = itup->t_tid;
 459                         return true;
 460                 }
 461
 462                 /* This tuple doesn't pass, but there might be more that do */
 463         } while (continuescan);
 464
 465         /* No more items, so close down the current-item info */
 466         ItemPointerSetInvalid(current);
 467         so->btso_curbuf = InvalidBuffer;
 468         _bt_relbuf(rel, buf);
 469
 470         return false;
 471 }
 472
 473 /*
 474  *      _bt_first() -- Find the first item in a scan.
 475  *
 476  *              We need to be clever about the type of scan, the operation it's
 477  *              performing, and the tree ordering.      We find the
 478  *              first item in the tree that satisfies the qualification
 479  *              associated with the scan descriptor.  On exit, the page containing
 480  *              the current index tuple is read locked and pinned, and the scan's
 481  *              opaque data entry is updated to include the buffer.
 482  */
 483 bool
 484 _bt_first(IndexScanDesc scan, ScanDirection dir)
 485 {
 486         Relation        rel = scan->indexRelation;
 487         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 488         Buffer          buf;
 489         Page            page;
 490         BTStack         stack;
 491         OffsetNumber offnum;
 492         BTItem          btitem;
 493         IndexTuple      itup;
 494         ItemPointer current;
 495         BlockNumber blkno;
 496         StrategyNumber strat;
 497         bool            res;
 498         int32           result;
 499         bool            nextkey;
 500         bool            continuescan;
 501         ScanKey         scankeys = NULL;
 502         ScanKey    *startKeys = NULL;
 503         int                     keysCount = 0;
 504         int                     i;
 505         StrategyNumber strat_total;
 506
 507         /*
 508          * Examine the scan keys and eliminate any redundant keys; also
 509          * discover how many keys must be matched to continue the scan.
 510          */
 511         _bt_preprocess_keys(scan);
 512
 513         /*
 514          * Quit now if _bt_preprocess_keys() discovered that the scan keys can
 515          * never be satisfied (eg, x == 1 AND x > 2).
 516          */
 517         if (!so->qual_ok)
 518                 return false;
 519
 520         /*----------
 521          * Examine the scan keys to discover where we need to start the scan.
 522          *
 523          * We want to identify the keys that can be used as starting boundaries;
 524          * these are =, >, or >= keys for a forward scan or =, <, <= keys for
 525          * a backwards scan.  We can use keys for multiple attributes so long as
 526          * the prior attributes had only =, >= (resp. =, <=) keys.  Once we accept
 527          * a > or < boundary or find an attribute with no boundary (which can be
 528          * thought of as the same as "> -infinity"), we can't use keys for any
 529          * attributes to its right, because it would break our simplistic notion
 530          * of what initial positioning strategy to use.
 531          *
 532          * When the scan keys include non-default operators, _bt_preprocess_keys
 533          * may not be able to eliminate redundant keys; in such cases we will
 534          * arbitrarily pick a usable one for each attribute.  This is correct
 535          * but possibly not optimal behavior.  (For example, with keys like
 536          * "x >= 4 AND x >= 5" we would elect to scan starting at x=4 when
 537          * x=5 would be more efficient.)  Since the situation only arises in
 538          * hokily-worded queries, live with it.
 539          *
 540          * When both equality and inequality keys appear for a single attribute
 541          * (again, only possible when non-default operators appear), we *must*
 542          * select one of the equality keys for the starting point, because
 543          * _bt_checkkeys() will stop the scan as soon as an equality qual fails.
 544          * For example, if we have keys like "x >= 4 AND x = 10" and we elect to
 545          * start at x=4, we will fail and stop before reaching x=10.  If multiple
 546          * equality quals survive preprocessing, however, it doesn't matter which
 547          * one we use --- by definition, they are either redundant or
 548          * contradictory.
 549          *----------
 550          */
 551         strat_total = BTEqualStrategyNumber;
 552         if (so->numberOfKeys > 0)
 553         {
 554                 AttrNumber      curattr;
 555                 ScanKey         chosen;
 556                 ScanKey         cur;
 557
 558                 startKeys = (ScanKey *) palloc(so->numberOfKeys * sizeof(ScanKey));
 559                 /*
 560                  * chosen is the so-far-chosen key for the current attribute, if any.
 561                  * We don't cast the decision in stone until we reach keys for the
 562                  * next attribute.
 563                  */
 564                 curattr = 1;
 565                 chosen = NULL;
 566                 /*
 567                  * Loop iterates from 0 to numberOfKeys inclusive; we use the last
 568                  * pass to handle after-last-key processing.  Actual exit from the
 569                  * loop is at one of the "break" statements below.
 570                  */
 571                 for (cur = so->keyData, i = 0;; cur++, i++)
 572                 {
 573                         if (i >= so->numberOfKeys || cur->sk_attno != curattr)
 574                         {
 575                                 /*
 576                                  * Done looking at keys for curattr.  If we didn't find a
 577                                  * usable boundary key, quit; else save the boundary key
 578                                  * pointer in startKeys.
 579                                  */
 580                                 if (chosen == NULL)
 581                                         break;
 582                                 startKeys[keysCount++] = chosen;
 583                                 /*
 584                                  * Adjust strat_total, and quit if we have stored a > or < key.
 585                                  */
 586                                 strat = chosen->sk_strategy;
 587                                 if (strat != BTEqualStrategyNumber)
 588                                 {
 589                                         strat_total = strat;
 590                                         if (strat == BTGreaterStrategyNumber ||
 591                                                 strat == BTLessStrategyNumber)
 592                                                 break;
 593                                 }
 594                                 /*
 595                                  * Done if that was the last attribute.
 596                                  */
 597                                 if (i >= so->numberOfKeys)
 598                                         break;
 599                                 /*
 600                                  * Reset for next attr, which should be in sequence.
 601                                  */
 602                                 Assert(cur->sk_attno == curattr + 1);
 603                                 curattr = cur->sk_attno;
 604                                 chosen = NULL;
 605                         }
 606
 607                         /* Can we use this key as a starting boundary for this attr? */
 608                         switch (cur->sk_strategy)
 609                         {
 610                                 case BTLessStrategyNumber:
 611                                 case BTLessEqualStrategyNumber:
 612                                         if (chosen == NULL && ScanDirectionIsBackward(dir))
 613                                                 chosen = cur;
 614                                         break;
 615                                 case BTEqualStrategyNumber:
 616                                         /* override any non-equality choice */
 617                                         chosen = cur;
 618                                         break;
 619                                 case BTGreaterEqualStrategyNumber:
 620                                 case BTGreaterStrategyNumber:
 621                                         if (chosen == NULL && ScanDirectionIsForward(dir))
 622                                                 chosen = cur;
 623                                         break;
 624                         }
 625                 }
 626         }
 627
 628         /*
 629          * If we found no usable boundary keys, we have to start from one end
 630          * of the tree.  Walk down that edge to the first or last key, and
 631          * scan from there.
 632          */
 633         if (keysCount == 0)
 634         {
 635                 if (startKeys)
 636                         pfree(startKeys);
 637                 return _bt_endpoint(scan, dir);
 638         }
 639
 640         /*
 641          * We want to start the scan somewhere within the index.  Set up a
 642          * 3-way-comparison scankey we can use to search for the boundary
 643          * point we identified above.
 644          */
 645         scankeys = (ScanKey) palloc(keysCount * sizeof(ScanKeyData));
 646         for (i = 0; i < keysCount; i++)
 647         {
 648                 ScanKey         cur = startKeys[i];
 649
 650                 /*
 651                  * _bt_preprocess_keys disallows it, but it's place to add some code
 652                  * later
 653                  */
 654                 if (cur->sk_flags & SK_ISNULL)
 655                 {
 656                         pfree(startKeys);
 657                         pfree(scankeys);
 658                         elog(ERROR, "btree doesn't support is(not)null, yet");
 659                         return false;
 660                 }
 661                 /*
 662                  * If scankey operator is of default subtype, we can use the
 663                  * cached comparison procedure; otherwise gotta look it up in
 664                  * the catalogs.
 665                  */
 666                 if (cur->sk_subtype == InvalidOid)
 667                 {
 668                         FmgrInfo   *procinfo;
 669
 670                         procinfo = index_getprocinfo(rel, i + 1, BTORDER_PROC);
 671                         ScanKeyEntryInitializeWithInfo(scankeys + i,
 672                                                                                    cur->sk_flags,
 673                                                                                    i + 1,
 674                                                                                    InvalidStrategy,
 675                                                                                    InvalidOid,
 676                                                                                    procinfo,
 677                                                                                    cur->sk_argument);
 678                 }
 679                 else
 680                 {
 681                         RegProcedure cmp_proc;
 682
 683                         cmp_proc = get_opclass_proc(rel->rd_index->indclass[i],
 684                                                                                 cur->sk_subtype,
 685                                                                                 BTORDER_PROC);
 686                         ScanKeyEntryInitialize(scankeys + i,
 687                                                                    cur->sk_flags,
 688                                                                    i + 1,
 689                                                                    InvalidStrategy,
 690                                                                    cur->sk_subtype,
 691                                                                    cmp_proc,
 692                                                                    cur->sk_argument);
 693                 }
 694         }
 695
 696         pfree(startKeys);
 697
 698         current = &(scan->currentItemData);
 699
 700         /*
 701          * We want to locate either the first item >= boundary point, or
 702          * first item > boundary point, depending on the initial-positioning
 703          * strategy we just chose.
 704          */
 705         switch (strat_total)
 706         {
 707                 case BTLessStrategyNumber:
 708                         nextkey = false;
 709                         break;
 710
 711                 case BTLessEqualStrategyNumber:
 712                         nextkey = true;
 713                         break;
 714
 715                 case BTEqualStrategyNumber:
 716                         /*
 717                          * If a backward scan was specified, need to start with last
 718                          * equal item not first one.
 719                          */
 720                         if (ScanDirectionIsBackward(dir))
 721                                 nextkey = true;
 722                         else
 723                                 nextkey = false;
 724                         break;
 725
 726                 case BTGreaterEqualStrategyNumber:
 727                         nextkey = false;
 728                         break;
 729
 730                 case BTGreaterStrategyNumber:
 731                         nextkey = true;
 732                         break;
 733
 734                 default:
 735                         /* can't get here, but keep compiler quiet */
 736                         elog(ERROR, "unrecognized strat_total: %d", (int) strat_total);
 737                         return false;
 738         }
 739
 740         /*
 741          * Use the manufactured scan key to descend the tree and position
 742          * ourselves on the target leaf page.
 743          */
 744         stack = _bt_search(rel, keysCount, scankeys, nextkey, &buf, BT_READ);
 745
 746         /* don't need to keep the stack around... */
 747         _bt_freestack(stack);
 748
 749         if (!BufferIsValid(buf))
 750         {
 751                 /* Only get here if index is completely empty */
 752                 ItemPointerSetInvalid(current);
 753                 so->btso_curbuf = InvalidBuffer;
 754                 pfree(scankeys);
 755                 return false;
 756         }
 757
 758         /* remember which buffer we have pinned */
 759         so->btso_curbuf = buf;
 760         blkno = BufferGetBlockNumber(buf);
 761         page = BufferGetPage(buf);
 762
 763         /* position to the precise item on the page */
 764         offnum = _bt_binsrch(rel, buf, keysCount, scankeys, nextkey);
 765
 766         ItemPointerSet(current, blkno, offnum);
 767
 768         /*
 769          * It's now time to examine the initial-positioning strategy to find the
 770          * exact place to start the scan.
 771          *
 772          * If nextkey = false, we are positioned at the first item >= scan key,
 773          * or possibly at the end of a page on which all the existing items are
 774          * less than the scan key and we know that everything on later pages
 775          * is greater than or equal to scan key.
 776          *
 777          * If nextkey = true, we are positioned at the first item > scan key,
 778          * or possibly at the end of a page on which all the existing items are
 779          * less than or equal to the scan key and we know that everything on
 780          * later pages is greater than scan key.
 781          *
 782          * The actually desired starting point is either this item or an adjacent
 783          * one, or in the end-of-page case it's the last item on this page or
 784          * the first item on the next.  We apply _bt_step if needed to get to
 785          * the right place.
 786          *
 787          * Note: if _bt_step fails (meaning we fell off the end of the index in
 788          * one direction or the other), then there are no matches so we just
 789          * return false.
 790          *
 791          * it's yet other place to add some code later for is(not)null ...
 792          */
 793         switch (strat_total)
 794         {
 795                 case BTLessStrategyNumber:
 796
 797                         /*
 798                          * We are on first item >= scankey.
 799                          *
 800                          * Back up one to arrive at last item < scankey.  (Note: this
 801                          * positioning strategy is only used for a backward scan, so
 802                          * that is always the correct starting position.)
 803                          */
 804                         if (!_bt_step(scan, &buf, BackwardScanDirection))
 805                         {
 806                                 pfree(scankeys);
 807                                 return false;
 808                         }
 809                         break;
 810
 811                 case BTLessEqualStrategyNumber:
 812
 813                         /*
 814                          * We are on first item > scankey.
 815                          *
 816                          * Back up one to arrive at last item <= scankey.  (Note: this
 817                          * positioning strategy is only used for a backward scan, so
 818                          * that is always the correct starting position.)
 819                          */
 820                         if (!_bt_step(scan, &buf, BackwardScanDirection))
 821                         {
 822                                 pfree(scankeys);
 823                                 return false;
 824                         }
 825                         break;
 826
 827                 case BTEqualStrategyNumber:
 828                         /*
 829                          * If a backward scan was specified, need to start with last
 830                          * equal item not first one.
 831                          */
 832                         if (ScanDirectionIsBackward(dir))
 833                         {
 834                                 /*
 835                                  * We are on first item > scankey.
 836                                  *
 837                                  * Back up one to arrive at last item <= scankey, then
 838                                  * check to see if it is equal to scankey.
 839                                  */
 840                                 if (!_bt_step(scan, &buf, BackwardScanDirection))
 841                                 {
 842                                         pfree(scankeys);
 843                                         return false;
 844                                 }
 845                         }
 846                         else
 847                         {
 848                                 /*
 849                                  * We are on first item >= scankey.
 850                                  *
 851                                  * Make sure we are on a real item; might have to
 852                                  * step forward if currently at end of page.  Then check
 853                                  * to see if it is equal to scankey.
 854                                  */
 855                                 if (offnum > PageGetMaxOffsetNumber(page))
 856                                 {
 857                                         if (!_bt_step(scan, &buf, ForwardScanDirection))
 858                                         {
 859                                                 pfree(scankeys);
 860                                                 return false;
 861                                         }
 862                                 }
 863                         }
 864
 865                         /* If we are not now on an equal item, then there ain't any. */
 866                         offnum = ItemPointerGetOffsetNumber(current);
 867                         page = BufferGetPage(buf);
 868                         result = _bt_compare(rel, keysCount, scankeys, page, offnum);
 869                         if (result != 0)
 870                                 goto nomatches; /* no equal items! */
 871                         break;
 872
 873                 case BTGreaterEqualStrategyNumber:
 874
 875                         /*
 876                          * We want the first item >= scankey, which is where we are...
 877                          * unless we're not anywhere at all...
 878                          */
 879                         if (offnum > PageGetMaxOffsetNumber(page))
 880                         {
 881                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 882                                 {
 883                                         pfree(scankeys);
 884                                         return false;
 885                                 }
 886                         }
 887                         break;
 888
 889                 case BTGreaterStrategyNumber:
 890
 891                         /*
 892                          * We want the first item > scankey, which is where we are...
 893                          * unless we're not anywhere at all...
 894                          */
 895                         if (offnum > PageGetMaxOffsetNumber(page))
 896                         {
 897                                 if (!_bt_step(scan, &buf, ForwardScanDirection))
 898                                 {
 899                                         pfree(scankeys);
 900                                         return false;
 901                                 }
 902                         }
 903                         break;
 904         }
 905
 906         /* okay, current item pointer for the scan is right */
 907         offnum = ItemPointerGetOffsetNumber(current);
 908         page = BufferGetPage(buf);
 909         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
 910         itup = &btitem->bti_itup;
 911
 912         /* is the first item actually acceptable? */
 913         if (_bt_checkkeys(scan, itup, dir, &continuescan))
 914         {
 915                 /* yes, return it */
 916                 scan->xs_ctup.t_self = itup->t_tid;
 917                 res = true;
 918         }
 919         else if (continuescan)
 920         {
 921                 /* no, but there might be another one that is */
 922                 res = _bt_next(scan, dir);
 923         }
 924         else
 925         {
 926                 /* no tuples in the index match this scan key */
 927 nomatches:
 928                 ItemPointerSetInvalid(current);
 929                 so->btso_curbuf = InvalidBuffer;
 930                 _bt_relbuf(rel, buf);
 931                 res = false;
 932         }
 933
 934         pfree(scankeys);
 935
 936         return res;
 937 }
 938
 939 /*
 940  *      _bt_step() -- Step one item in the requested direction in a scan on
 941  *                                the tree.
 942  *
 943  *              *bufP is the current buffer (read-locked and pinned).  If we change
 944  *              pages, it's updated appropriately.
 945  *
 946  *              If successful, update scan's currentItemData and return true.
 947  *              If no adjacent record exists in the requested direction,
 948  *              release buffer pin/locks and return false.
 949  */
 950 bool
 951 _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir)
 952 {
 953         Relation        rel = scan->indexRelation;
 954         ItemPointer current = &(scan->currentItemData);
 955         BTScanOpaque so = (BTScanOpaque) scan->opaque;
 956         Page            page;
 957         BTPageOpaque opaque;
 958         OffsetNumber offnum,
 959                                 maxoff;
 960         BlockNumber blkno;
 961
 962         /*
 963          * Don't use ItemPointerGetOffsetNumber or you risk to get assertion
 964          * due to ability of ip_posid to be equal 0.
 965          */
 966         offnum = current->ip_posid;
 967
 968         page = BufferGetPage(*bufP);
 969         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 970         maxoff = PageGetMaxOffsetNumber(page);
 971
 972         if (ScanDirectionIsForward(dir))
 973         {
 974                 if (!PageIsEmpty(page) && offnum < maxoff)
 975                         offnum = OffsetNumberNext(offnum);
 976                 else
 977                 {
 978                         /* Walk right to the next page with data */
 979                         for (;;)
 980                         {
 981                                 /* if we're at end of scan, release the buffer and return */
 982                                 if (P_RIGHTMOST(opaque))
 983                                 {
 984                                         _bt_relbuf(rel, *bufP);
 985                                         ItemPointerSetInvalid(current);
 986                                         *bufP = so->btso_curbuf = InvalidBuffer;
 987                                         return false;
 988                                 }
 989                                 /* step right one page */
 990                                 blkno = opaque->btpo_next;
 991                                 _bt_relbuf(rel, *bufP);
 992                                 *bufP = _bt_getbuf(rel, blkno, BT_READ);
 993                                 page = BufferGetPage(*bufP);
 994                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
 995                                 if (!P_IGNORE(opaque))
 996                                 {
 997                                         maxoff = PageGetMaxOffsetNumber(page);
 998                                         /* done if it's not empty */
 999                                         offnum = P_FIRSTDATAKEY(opaque);
1000                                         if (!PageIsEmpty(page) && offnum <= maxoff)
1001                                                 break;
1002                                 }
1003                         }
1004                 }
1005         }
1006         else
1007         {
1008                 /* backwards scan */
1009                 if (offnum > P_FIRSTDATAKEY(opaque))
1010                         offnum = OffsetNumberPrev(offnum);
1011                 else
1012                 {
1013                         /*
1014                          * Walk left to the next page with data.  This is much more
1015                          * complex than the walk-right case because of the possibility
1016                          * that the page to our left splits while we are in flight to
1017                          * it, plus the possibility that the page we were on gets
1018                          * deleted after we leave it.  See nbtree/README for details.
1019                          */
1020                         for (;;)
1021                         {
1022                                 *bufP = _bt_walk_left(rel, *bufP);
1023
1024                                 /* if we're at end of scan, return failure */
1025                                 if (*bufP == InvalidBuffer)
1026                                 {
1027                                         ItemPointerSetInvalid(current);
1028                                         so->btso_curbuf = InvalidBuffer;
1029                                         return false;
1030                                 }
1031                                 page = BufferGetPage(*bufP);
1032                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1033
1034                                 /*
1035                                  * Okay, we managed to move left to a non-deleted page.
1036                                  * Done if it's not half-dead and not empty.  Else loop
1037                                  * back and do it all again.
1038                                  */
1039                                 if (!P_IGNORE(opaque))
1040                                 {
1041                                         maxoff = PageGetMaxOffsetNumber(page);
1042                                         offnum = maxoff;
1043                                         if (!PageIsEmpty(page) &&
1044                                                 maxoff >= P_FIRSTDATAKEY(opaque))
1045                                                 break;
1046                                 }
1047                         }
1048                 }
1049         }
1050
1051         /* Update scan state */
1052         so->btso_curbuf = *bufP;
1053         blkno = BufferGetBlockNumber(*bufP);
1054         ItemPointerSet(current, blkno, offnum);
1055
1056         return true;
1057 }
1058
1059 /*
1060  * _bt_walk_left() -- step left one page, if possible
1061  *
1062  * The given buffer must be pinned and read-locked.  This will be dropped
1063  * before stepping left.  On return, we have pin and read lock on the
1064  * returned page, instead.
1065  *
1066  * Returns InvalidBuffer if there is no page to the left (no lock is held
1067  * in that case).
1068  *
1069  * When working on a non-leaf level, it is possible for the returned page
1070  * to be half-dead; the caller should check that condition and step left
1071  * again if it's important.
1072  */
1073 static Buffer
1074 _bt_walk_left(Relation rel, Buffer buf)
1075 {
1076         Page            page;
1077         BTPageOpaque opaque;
1078
1079         page = BufferGetPage(buf);
1080         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1081
1082         for (;;)
1083         {
1084                 BlockNumber obknum;
1085                 BlockNumber lblkno;
1086                 BlockNumber blkno;
1087                 int                     tries;
1088
1089                 /* if we're at end of tree, release buf and return failure */
1090                 if (P_LEFTMOST(opaque))
1091                 {
1092                         _bt_relbuf(rel, buf);
1093                         break;
1094                 }
1095                 /* remember original page we are stepping left from */
1096                 obknum = BufferGetBlockNumber(buf);
1097                 /* step left */
1098                 blkno = lblkno = opaque->btpo_prev;
1099                 _bt_relbuf(rel, buf);
1100                 buf = _bt_getbuf(rel, blkno, BT_READ);
1101                 page = BufferGetPage(buf);
1102                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1103
1104                 /*
1105                  * If this isn't the page we want, walk right till we find what we
1106                  * want --- but go no more than four hops (an arbitrary limit). If
1107                  * we don't find the correct page by then, the most likely bet is
1108                  * that the original page got deleted and isn't in the sibling
1109                  * chain at all anymore, not that its left sibling got split more
1110                  * than four times.
1111                  *
1112                  * Note that it is correct to test P_ISDELETED not P_IGNORE here,
1113                  * because half-dead pages are still in the sibling chain.      Caller
1114                  * must reject half-dead pages if wanted.
1115                  */
1116                 tries = 0;
1117                 for (;;)
1118                 {
1119                         if (!P_ISDELETED(opaque) && opaque->btpo_next == obknum)
1120                         {
1121                                 /* Found desired page, return it */
1122                                 return buf;
1123                         }
1124                         if (P_RIGHTMOST(opaque) || ++tries > 4)
1125                                 break;
1126                         blkno = opaque->btpo_next;
1127                         _bt_relbuf(rel, buf);
1128                         buf = _bt_getbuf(rel, blkno, BT_READ);
1129                         page = BufferGetPage(buf);
1130                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1131                 }
1132
1133                 /* Return to the original page to see what's up */
1134                 _bt_relbuf(rel, buf);
1135                 buf = _bt_getbuf(rel, obknum, BT_READ);
1136                 page = BufferGetPage(buf);
1137                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1138                 if (P_ISDELETED(opaque))
1139                 {
1140                         /*
1141                          * It was deleted.      Move right to first nondeleted page (there
1142                          * must be one); that is the page that has acquired the
1143                          * deleted one's keyspace, so stepping left from it will take
1144                          * us where we want to be.
1145                          */
1146                         for (;;)
1147                         {
1148                                 if (P_RIGHTMOST(opaque))
1149                                         elog(ERROR, "fell off the end of \"%s\"",
1150                                                  RelationGetRelationName(rel));
1151                                 blkno = opaque->btpo_next;
1152                                 _bt_relbuf(rel, buf);
1153                                 buf = _bt_getbuf(rel, blkno, BT_READ);
1154                                 page = BufferGetPage(buf);
1155                                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1156                                 if (!P_ISDELETED(opaque))
1157                                         break;
1158                         }
1159
1160                         /*
1161                          * Now return to top of loop, resetting obknum to point to
1162                          * this nondeleted page, and try again.
1163                          */
1164                 }
1165                 else
1166                 {
1167                         /*
1168                          * It wasn't deleted; the explanation had better be that the
1169                          * page to the left got split or deleted. Without this check,
1170                          * we'd go into an infinite loop if there's anything wrong.
1171                          */
1172                         if (opaque->btpo_prev == lblkno)
1173                                 elog(ERROR, "could not find left sibling in \"%s\"",
1174                                          RelationGetRelationName(rel));
1175                         /* Okay to try again with new lblkno value */
1176                 }
1177         }
1178
1179         return InvalidBuffer;
1180 }
1181
1182 /*
1183  * _bt_get_endpoint() -- Find the first or last page on a given tree level
1184  *
1185  * If the index is empty, we will return InvalidBuffer; any other failure
1186  * condition causes ereport().  We will not return a dead page.
1187  *
1188  * The returned buffer is pinned and read-locked.
1189  */
1190 Buffer
1191 _bt_get_endpoint(Relation rel, uint32 level, bool rightmost)
1192 {
1193         Buffer          buf;
1194         Page            page;
1195         BTPageOpaque opaque;
1196         OffsetNumber offnum;
1197         BlockNumber blkno;
1198         BTItem          btitem;
1199         IndexTuple      itup;
1200
1201         /*
1202          * If we are looking for a leaf page, okay to descend from fast root;
1203          * otherwise better descend from true root.  (There is no point in
1204          * being smarter about intermediate levels.)
1205          */
1206         if (level == 0)
1207                 buf = _bt_getroot(rel, BT_READ);
1208         else
1209                 buf = _bt_gettrueroot(rel);
1210
1211         if (!BufferIsValid(buf))
1212         {
1213                 /* empty index... */
1214                 return InvalidBuffer;
1215         }
1216
1217         page = BufferGetPage(buf);
1218         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1219
1220         for (;;)
1221         {
1222                 /*
1223                  * If we landed on a deleted page, step right to find a live page
1224                  * (there must be one).  Also, if we want the rightmost page, step
1225                  * right if needed to get to it (this could happen if the page
1226                  * split since we obtained a pointer to it).
1227                  */
1228                 while (P_IGNORE(opaque) ||
1229                            (rightmost && !P_RIGHTMOST(opaque)))
1230                 {
1231                         blkno = opaque->btpo_next;
1232                         if (blkno == P_NONE)
1233                                 elog(ERROR, "fell off the end of \"%s\"",
1234                                          RelationGetRelationName(rel));
1235                         _bt_relbuf(rel, buf);
1236                         buf = _bt_getbuf(rel, blkno, BT_READ);
1237                         page = BufferGetPage(buf);
1238                         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1239                 }
1240
1241                 /* Done? */
1242                 if (opaque->btpo.level == level)
1243                         break;
1244                 if (opaque->btpo.level < level)
1245                         elog(ERROR, "btree level %u not found", level);
1246
1247                 /* Descend to leftmost or rightmost child page */
1248                 if (rightmost)
1249                         offnum = PageGetMaxOffsetNumber(page);
1250                 else
1251                         offnum = P_FIRSTDATAKEY(opaque);
1252
1253                 btitem = (BTItem) PageGetItem(page, PageGetItemId(page, offnum));
1254                 itup = &(btitem->bti_itup);
1255                 blkno = ItemPointerGetBlockNumber(&(itup->t_tid));
1256
1257                 _bt_relbuf(rel, buf);
1258                 buf = _bt_getbuf(rel, blkno, BT_READ);
1259                 page = BufferGetPage(buf);
1260                 opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1261         }
1262
1263         return buf;
1264 }
1265
1266 /*
1267  *      _bt_endpoint() -- Find the first or last key in the index, and scan
1268  * from there to the first key satisfying all the quals.
1269  *
1270  * This is used by _bt_first() to set up a scan when we've determined
1271  * that the scan must start at the beginning or end of the index (for
1272  * a forward or backward scan respectively).
1273  */
1274 static bool
1275 _bt_endpoint(IndexScanDesc scan, ScanDirection dir)
1276 {
1277         Relation        rel;
1278         Buffer          buf;
1279         Page            page;
1280         BTPageOpaque opaque;
1281         ItemPointer current;
1282         OffsetNumber maxoff;
1283         OffsetNumber start;
1284         BlockNumber blkno;
1285         BTItem          btitem;
1286         IndexTuple      itup;
1287         BTScanOpaque so;
1288         bool            res;
1289         bool            continuescan;
1290
1291         rel = scan->indexRelation;
1292         current = &(scan->currentItemData);
1293         so = (BTScanOpaque) scan->opaque;
1294
1295         /*
1296          * Scan down to the leftmost or rightmost leaf page.  This is a
1297          * simplified version of _bt_search().  We don't maintain a stack
1298          * since we know we won't need it.
1299          */
1300         buf = _bt_get_endpoint(rel, 0, ScanDirectionIsBackward(dir));
1301
1302         if (!BufferIsValid(buf))
1303         {
1304                 /* empty index... */
1305                 ItemPointerSetInvalid(current);
1306                 so->btso_curbuf = InvalidBuffer;
1307                 return false;
1308         }
1309
1310         blkno = BufferGetBlockNumber(buf);
1311         page = BufferGetPage(buf);
1312         opaque = (BTPageOpaque) PageGetSpecialPointer(page);
1313         Assert(P_ISLEAF(opaque));
1314
1315         maxoff = PageGetMaxOffsetNumber(page);
1316
1317         if (ScanDirectionIsForward(dir))
1318         {
1319                 /* There could be dead pages to the left, so not this: */
1320                 /* Assert(P_LEFTMOST(opaque)); */
1321
1322                 start = P_FIRSTDATAKEY(opaque);
1323         }
1324         else if (ScanDirectionIsBackward(dir))
1325         {
1326                 Assert(P_RIGHTMOST(opaque));
1327
1328                 start = PageGetMaxOffsetNumber(page);
1329                 if (start < P_FIRSTDATAKEY(opaque))             /* watch out for empty
1330                                                                                                  * page */
1331                         start = P_FIRSTDATAKEY(opaque);
1332         }
1333         else
1334         {
1335                 elog(ERROR, "invalid scan direction: %d", (int) dir);
1336                 start = 0;                              /* keep compiler quiet */
1337         }
1338
1339         ItemPointerSet(current, blkno, start);
1340         /* remember which buffer we have pinned */
1341         so->btso_curbuf = buf;
1342
1343         /*
1344          * Left/rightmost page could be empty due to deletions, if so step
1345          * till we find a nonempty page.
1346          */
1347         if (start > maxoff)
1348         {
1349                 if (!_bt_step(scan, &buf, dir))
1350                         return false;
1351                 start = ItemPointerGetOffsetNumber(current);
1352                 page = BufferGetPage(buf);
1353         }
1354
1355         btitem = (BTItem) PageGetItem(page, PageGetItemId(page, start));
1356         itup = &(btitem->bti_itup);
1357
1358         /*
1359          * Okay, we are on the first or last tuple.  Does it pass all the quals?
1360          */
1361         if (_bt_checkkeys(scan, itup, dir, &continuescan))
1362         {
1363                 /* yes, return it */
1364                 scan->xs_ctup.t_self = itup->t_tid;
1365                 res = true;
1366         }
1367         else if (continuescan)
1368         {
1369                 /* no, but there might be another one that does */
1370                 res = _bt_next(scan, dir);
1371         }
1372         else
1373         {
1374                 /* no tuples in the index match this scan key */
1375                 ItemPointerSetInvalid(current);
1376                 so->btso_curbuf = InvalidBuffer;
1377                 _bt_relbuf(rel, buf);
1378                 res = false;
1379         }
1380
1381         return res;
1382 }